어제자 기업협약 프로젝트의 킥오프였고, 사실상 업무 배정과 깃허브 프로젝트를 만들고 할 일을 정리하는 것만으로 하루가 끝나버렸다. 그리고 오늘부터 휴일이라 사실상 모두가 작업을 하고 있는 상태는 아니라서 뭔가 하기는 애매한 상황이기는 했다.
하지만 R&D라도 먼저 진행해보자는 생각에 R&D 진행부터 시작했다.
1. 금일 한 업무 정리
현재 깃허브로 공유된 프로젝트는 Json으로 인한 오류가 발생하고 있던 상황이라 별도의 테스트 프로젝트를 파서 진행 중에 있다.
- 캐릭터 편성 시스템 구현
- 캐릭터 자동 편성 시스템 구현
2. 문제의 발생과 해결 과정
2.1 피할 수 없는 UI 작업
UI는 테스트를 위해 이와 같이 제작했다.
캐릭터의 이름, 그 하단에 캐릭터의 전투력이 표시되며, 좌측 상단에는 코스트, 좌측 하단 직업 시너지, 우측 하단 역할 시너지가 표시된다.
캐릭터는 코스트를 넘겨서 편성되서는 안되며, 아래쪽 편성 캐릭터 버튼 클릭으로 편성을 하고, 위쪽 선택된 편성칸을 누르는 것으로 캐릭터를 편성해제할 수 있어야 한다.
우선은 수동 편성을 위한 방식으로 구조를 작성하기 시작했으며, 아래와 같이 구조를 설계하였다.
데이터와 UI의 분리가 중요하다고 생각하여 데이터를 관리하는 관리부를 만들고, 해당 부분에서 데이터를 저장하면서 편성 칸에서의 데이터 전달을 담당하도록 설계해보았다.
using System;
using System.Collections.Generic;
using System.Linq;
using TMPro;
using UnityEngine;
public class TeamOrganizeManager : MonoBehaviour
{
[SerializeField] private CollectedCharacterData _collectedCharacterData;
[SerializeField] private CharacterSO[] _characterSOs = new CharacterSO[5];
[SerializeField] private int _totalCost = 10;
[SerializeField] private int _currentCost;
[SerializeField] private TMP_Text _costInfoText;
[SerializeField] private int _currentOverallPower;
[SerializeField] private TMP_Text _totalOverallPowerText;
public Action OnCharacterDataChanged;
private CharacterSO _selectedCharacterSO;
private List<CharacterSO> _collectedCharData;
#region Event
private void OnEnable()
{
OnCharacterDataChanged += ShowCostInfo;
OnCharacterDataChanged += ShowTotalOverallPowerInfo;
ShowCostInfo();
ShowTotalOverallPowerInfo();
_collectedCharData = _collectedCharacterData.CollectedCharData;
}
private void OnDisable()
{
OnCharacterDataChanged -= ShowCostInfo;
OnCharacterDataChanged -= ShowTotalOverallPowerInfo;
}
#endregion
public CharacterSO GetCurrentCharacterData(int index)
{
return _characterSOs[index];
}
#region Manual Selection
public void AddCharacterData(CharacterSO data)
{
_selectedCharacterSO = data;
if(_characterSOs.Contains(data))
{
Debug.Log("이미 편성된 캐릭터입니다");
return;
}
if(_currentCost + data.Cost > _totalCost)
{
Debug.Log("코스트 상한치를 초과했습니다");
return;
}
for(int i = 0; i < _characterSOs.Length; i++)
{
if(_characterSOs[i] == null)
{
_characterSOs[i] = _selectedCharacterSO;
_currentCost += _selectedCharacterSO.Cost;
_currentOverallPower += _selectedCharacterSO.OverallPower;
break;
}
if(i == _characterSOs.Length - 1)
{
Debug.Log("편성 제한치를 초과했습니다.");
return;
}
}
OnCharacterDataChanged?.Invoke();
}
public void RemoveCharacterData(int index)
{
if (_characterSOs[index] != null)
{
_currentCost -= _characterSOs[index].Cost;
_currentOverallPower -= _characterSOs[index].OverallPower;
_characterSOs[index] = null;
OnCharacterDataChanged?.Invoke();
}
}
#endregion
#region AutoMatic Selection
/// <summary>
/// 동적 계획법 알고리즘을 이용한 캐릭터 자동편성
/// </summary>
public void AutoSelectCharacters()
{
int n = _collectedCharData.Count;
int[,,] dp = new int[n + 1, _totalCost + 1, _characterSOs.Length + 1];
bool[,,] take = new bool[n + 1, _totalCost + 1, _characterSOs.Length + 1];
// DP 진행 - Bottom-Up 방식
for (int i = 1; i <= n; i++)
{
int power = _collectedCharData[i - 1].OverallPower;
int cost = _collectedCharData[i - 1].Cost;
for (int c = 0; c <= _totalCost; c++)
{
for (int k = 0; k <= _characterSOs.Length; k++)
{
// 선택 안함
dp[i, c, k] = dp[i - 1, c, k];
// 선택 가능할 때
if (c >= cost && k >= 1)
{
int newPower = dp[i - 1, c - cost, k - 1] + power;
if (newPower > dp[i, c, k])
{
dp[i, c, k] = newPower;
take[i, c, k] = true;
}
}
}
}
}
// 최적 값 찾기
int bestPower = 0;
int bestC = 0;
int bestK = 0;
for (int c = 0; c <= _totalCost; c++)
{
for (int k = 0; k <= _characterSOs.Length; k++)
{
if (dp[n, c, k] > bestPower)
{
bestPower = dp[n, c, k];
bestC = c;
bestK = k;
}
}
}
// 역추적
List<CharacterSO> bestTeam = new List<CharacterSO>();
int ci = bestC;
int ki = bestK;
for (int i = n; i > 0; i--)
{
if (take[i, ci, ki])
{
bestTeam.Add(_collectedCharData[i - 1]);
ci -= _collectedCharData[i - 1].Cost;
ki -= 1;
}
}
// 전투력이 높은 순으로 정렬
bestTeam.OrderByDescending(n => n);
// 기존 편성 초기화
Array.Clear(_characterSOs, 0, _characterSOs.Length);
_currentCost = 0;
// 최적 편성 적용
for (int i = 0; i < bestTeam.Count; i++)
{
_characterSOs[i] = bestTeam[i];
_currentCost += bestTeam[i].Cost;
}
_currentOverallPower = bestPower;
OnCharacterDataChanged?.Invoke();
}
#endregion
#region UI Output
private void ShowCostInfo()
{
_costInfoText.text = $"{_currentCost} / {_totalCost}";
}
private void ShowTotalOverallPowerInfo()
{
_totalOverallPowerText.text = $"OverallPower : {_currentOverallPower}";
Debug.Log("실행");
}
#endregion
}using TMPro;
using UnityEngine;
using UnityEngine.UI;
public class CharacterData : MonoBehaviour
{
[SerializeField] private CharacterSO _charData;
public CharacterSO CharData => _charData;
[SerializeField] private TMP_Text _charText;
[SerializeField] private TMP_Text _costText;
[SerializeField] private TMP_Text _jobSynergyText;
[SerializeField] private TMP_Text _roleSynergyText;
[SerializeField] private TMP_Text _overallPowerText;
private bool _isCollected = true;
public bool IsCollected => _isCollected;
private TeamOrganizeManager _manager;
private void Awake()
{
_manager = GetComponentInParent<TeamOrganizeManager>();
GetComponent<Button>().onClick.AddListener(TryAddCharacter);
}
private void OnEnable()
{
_manager.OnCharacterDataChanged += UIUpdate;
if (_isCollected)
{
GetComponent<Button>().interactable = true;
}
else
{
GetComponent<Button>().interactable = false;
}
UIUpdate();
}
private void OnDisable()
{
_manager.OnCharacterDataChanged -= UIUpdate;
}
private void TryAddCharacter()
{
_manager.AddCharacterData(_charData);
}
private void UIUpdate()
{
_charText.text = $"{_charData.name}";
_costText.text = $"{_charData.Cost}";
_jobSynergyText.text = $"{_charData.CharacterSynergy.JobSynergy}";
_roleSynergyText.text = $"{_charData.CharacterSynergy.RoleSynergy}";
_overallPowerText.text = $"{_charData.OverallPower}";
}
public void InputData(CharacterSO data)
{
_charData = data;
}
}using TMPro;
using UnityEngine;
using UnityEngine.UI;
public class SelectedCharacterData : MonoBehaviour
{
[SerializeField] private TMP_Text _charText;
[SerializeField] private TMP_Text _costText;
[SerializeField] private TMP_Text _jobSynergyText;
[SerializeField] private TMP_Text _roleSynergyText;
[SerializeField] private TMP_Text _overallPowerText;
[SerializeField] private int _index;
private CharacterSO _charData;
private TeamOrganizeManager _manager;
private void Awake()
{
_manager = GetComponentInParent<TeamOrganizeManager>();
GetComponent<Button>().onClick.AddListener(TryDeleteCharacter);
}
private void OnEnable()
{
_manager.OnCharacterDataChanged += UIUpdate;
UIUpdate();
}
private void OnDisable()
{
_manager.OnCharacterDataChanged -= UIUpdate;
}
private void TryDeleteCharacter()
{
_manager.RemoveCharacterData(_index);
_charData = null;
}
private void UIUpdate()
{
_charData = _manager.GetCurrentCharacterData(_index);
if(_charData == null)
{
_charText.text = "";
_costText.text = "";
_jobSynergyText.text = "";
_roleSynergyText.text = "";
_overallPowerText.text = "";
}
else
{
_charText.text = $"{_charData.name}";
_costText.text = $"{_charData.Cost}";
_jobSynergyText.text = $"{_charData.CharacterSynergy.JobSynergy}";
_roleSynergyText.text = $"{_charData.CharacterSynergy.RoleSynergy}";
_overallPowerText.text = $"{_charData.OverallPower}";
}
}
}using System.Collections.Generic;
using UnityEngine;
public class CollectedCharacterData : MonoBehaviour
{
[SerializeField] private CharacterData[] _characters;
[SerializeField] private List<CharacterSO> _CollectedCharData = new List<CharacterSO>();
public List<CharacterSO> CollectedCharData => _CollectedCharData;
private void OnEnable()
{
for(int i = 0; i < _characters.Length; i++)
{
if(_characters[i].IsCollected)
{
_CollectedCharData.Add(_characters[i].CharData);
}
}
}
}캐릭터 획득 여부에 관한 판정은 나중에 파이어베이스 및 다른 상황을 고려하여 미리 만들어 놓았다.
2.2 자동 편성을 위한 방법, 동적 계획법 알고리즘
캐릭터 자동 편성, 이 문제를 어떻게 하면 해결할 수 있을까?
이 문제는 생각보다 쉽지 않은 문제이다. 어제자로 썼던 의사코드에도 따르면, 편성 가능 캐릭터 수 및 코스트를 고려한 채 전투력이 최대가 되도록 계산하는 과정이 필요하므로, 단순히 전투력이 높은 캐릭터 순서대로 편성을 시도해보는 방식으로는 이 문제를 해결할 수 없다.
그러므로, 코스트와 편성 캐릭터 수를 충족하는 모든 경우의 수에 대한 계산을 한 후, 거기서 제일 결과값이 높은 값이 출력되도록 해야 한다.
1. 0-1 배낭 문제
현재 상황과 가장 유사한 문제로는 0-1 배낭 문제라는 것이 있다.
담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. 나의 상황의 경우 여기에서 최대 담을 수 있는 물건 수가 추가된 경우라고 할 수 있겠다.
이 0-1 배낭 문제의 경우 그리디 알고리즘 만으로는 풀 수가 없으며, 동적 계획법 혹은 백트래킹을 통해서 문제를 해결해야 한다. 여기서 그리디 알고리즘이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"는 방식으로, 매 순간의 선택의 종합에 따른 결과가 무조건 최적의 결과라는 보장은 없다. 어떻게 보면 단순히 전투력이 높은 캐릭터 순서대로 편성을 시도해보는 방식이 그리디 알고리즘과 유사하다고 할 수 있다.
2. 동적 계획법
그렇다면 여기서 결국 동적 계산법을 활용해야 한다는 건데, 동적 계획법이란 무엇인가?
동적 계획법이란 모든 경우의 수를 구하는 방법에 있어서, 사전 계산된(pre-computed) 값들을 재활용하는 방법을 말한다. 즉 지금 상황의 경우 모든 가능성의 경우를 전부 계산하여 저장한 다음, 거기서 제일 최적의 값을 찾아야 하는 것인데, 동적 계획법은 이 계산 과정에서 중복되는 계산 과정을 없애는, 최적화를 위한 알고리즘이다.
해당 방법을 가장 쉽게 설명하면서도 가장 많이 쓰이는 예제가 피보나치 수열을 동적 계획법으로 계산하는 방법이다.
피보나치 수열의 경우 n번째의 값이 n-1 번째와 n-2번째의 합으로 이루어지는 수열을 말하는데, 이는 보통 재귀함수를 사용하여 계산하는 방식이 많이 사용된다.
void fibonacci(int n) {
if(n <= 2) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}하지만 이와 같은 방식의 경우 계산해야 하는 값이 커질수록 반복 계산이 들어가게 되고 계산 속도가 느려지는 문제가 있다.
고작 5번째 피보나치 수를 구하기 위해 15번이나 연산이 일어나므로, 재귀함수의 반복에 따라 연산횟수가 기하급수적으로 늘어난다는 것이다. 이런 문제를 위해 계산 반복을 방지하기 위한 알고리즘이 동적 계획법이다.
그러면 동적 계획법으로 피보나치 수열을 계산하려면 어떻게 계산하는가? 계산 과정에서의 값을 저장해주면 된다.
int fibonacci(int n)
{
int[] memo = new int[n + 1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++)
{
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo;
}이와 같이 n번째 피보나치 수열의 값을 구한다고 할 때, n+1 크기의 배열을 미리 만들어 두고, 해당 배열에 값이 계산될 때마다 값을 저장해준다. 이후 해당 값이 다시 사용될 경우 해당 값이 저장되어 있는 배열에서 바로 가져와서 쓰기 때문에 해당 값을 계산하는 과정이 생략된다. 이를 통해 기존의 방법보다 비약적으로 연산 횟수를 줄일 수 있다.
3. 동적 계획법의 설계 - Top-Down(Memoization) 방식 / Bottom-Up(Tabulation) 방식
동적 계획법의 설계방법은 두 가지로 나뉜다.
이와 같이 방식에 있어서도 두 가지로 나뉘며, 사용의 목적 및 특징 또한 상이하기 때문에 유의해서 사용해야 한다.
이를 바탕으로 피보나치 수열 또한 두 가지 방식으로 처리할 수 있다.
해당 정보를 제공해준 링크는 하단 참고자료로 정리해놨으며, 내용이 매우 유용하여 참고하면 좋을 것 같다.
4. 문제의 해결 및 코드 분석
이와 같이 이론적인 내용을 길게 정리했으니, 결론적으로 필요한 건 캐릭터의 자동 편성 시스템을 어떻게 만들까에 대한 질문을 해야 한다.
효율성을 위해 동적 계산법을 사용할 것이며, 현재 문제의 상황상 모든 부분에 대한 연산이 필요하므로 Bottom-Up 방식으로 구현할 필요가 있다. 또한, 경우의 수를 구하는 과정에서 어떤 캐릭터를 뽑았는지에 대한 체크 과정이 필요하므로 해당 체크를 위해 아래와 같이 코드를 작성하였다.
/// <summary>
/// 동적 계획법 알고리즘을 이용한 캐릭터 자동편성
/// </summary>
public void AutoSelectCharacters()
{
int n = _collectedCharData.Count;
int[,,] dp = new int[n + 1, _totalCost + 1, _characterSOs.Length + 1];
bool[,,] take = new bool[n + 1, _totalCost + 1, _characterSOs.Length + 1]; // 선택한 캐릭터 체크용
// DP 진행 - Bottom-Up 방식
for (int i = 1; i <= n; i++)
{
int power = _collectedCharData[i - 1].OverallPower;
int cost = _collectedCharData[i - 1].Cost;
for (int c = 0; c <= _totalCost; c++)
{
for (int k = 0; k <= _characterSOs.Length; k++)
{
// 선택 안함
dp[i, c, k] = dp[i - 1, c, k];
// 선택 가능할 때
if (c >= cost && k >= 1)
{
int newPower = dp[i - 1, c - cost, k - 1] + power;
if (newPower > dp[i, c, k])
{
dp[i, c, k] = newPower;
take[i, c, k] = true; // 선택한 캐릭터를 체크
}
}
}
}
}
// 최적 값 찾기
int bestPower = 0;
int bestC = 0;
int bestK = 0;
for (int c = 0; c <= _totalCost; c++)
{
for (int k = 0; k <= _characterSOs.Length; k++)
{
if (dp[n, c, k] > bestPower)
{
bestPower = dp[n, c, k];
bestC = c;
bestK = k;
}
}
}
// 역추적
List<CharacterSO> bestTeam = new List<CharacterSO>();
int ci = bestC;
int ki = bestK;
for (int i = n; i > 0; i--)
{
if (take[i, ci, ki])
{
// 해당 추가된 캐릭터를 리스트에 추가하고, 해당 캐릭터가 추가되기 전의 배열을 추적
bestTeam.Add(_collectedCharData[i - 1]);
ci -= _collectedCharData[i - 1].Cost; // 해당 추가된 캐릭터의 코스트값 제외
ki -= 1; // 해당 추가된 캐릭터를 빼면서 편성수 - 1
}
}
// 전투력이 높은 순으로 정렬
bestTeam.OrderByDescending(n => n);
// 기존 편성 초기화
Array.Clear(_characterSOs, 0, _characterSOs.Length);
_currentCost = 0;
// 최적 편성 적용
for (int i = 0; i < bestTeam.Count; i++)
{
_characterSOs[i] = bestTeam[i];
_currentCost += bestTeam[i].Cost;
}
_currentOverallPower = bestPower;
OnCharacterDataChanged?.Invoke();
}상당히 내용이 어려운데, 작동 방식을 간략하게 설명하자면 다음과 같다.
for문을 통해 캐릭터를 0개 뽑았을 경우, 1개 뽑았을 경우, 2개 뽑았을 경우 ~ n개 뽑았을 경우에 대한 모든 기록을 진행한다. 이때 코스트와 편성수에 대한 제한 조건이 충족되는 범위 내에서 기록할 수 있게 된다.
이를 바탕으로 최적의 값을 구한 다음, 그 최적의 값을 기준으로 어떤 캐릭터를 뽑았는지 역추적을 진행하여 해당 캐릭터 데이터를 리스트로 저장한다.
이를 필요한 방식으로 정렬한 다음 기존 편성 데이터를 초기화한 후, 최종적으로 결정된 편성을 적용하게 된다.
여기서 한 가지 특징이 있다고 한다면, 만약 최고 점수가 동점이 나왔을 경우, 해당 방식은 먼저 발견된 방식으로 적용되게 된다. 따라서 이에 따른 우선순위 설정을 추가로 진행하고 싶다면 추가로 설정해주면 된다.
2.3 UI에 일일히 데이터를 꼽을 수는 없는데, 데이터 연동 쉽게 하는 방법
지금 방식으로 원하는 기능은 잘 돌아가는데, 다소 귀찮은 문제가 있다.
이와 같이 지금은 데이터를 직접 인스펙터 상에서 일일히 삽입한 상태이다. 하지만 나중의 확장성을 고려하면, 캐릭터가 몇십 개가 될 지 모르는데 이걸 일일히 꽃고 있는 건 너무도 귀찮은 작업일 것이다. 그래서 이걸 자동으로 꽃아주는 기능을 만들 수 없을까 고민을 해 보았다.
using System.Collections.Generic;
using UnityEngine;
// 현재 정상작동하지 않아 테스트중
public class CharacterDataListInput : MonoBehaviour
{
[SerializeField] private GameObject[] _characterGroups;
[SerializeField] private List<CharacterSO> _characterSOs = new List<CharacterSO>();
private void Awake()
{
for(int i = 0; i < _characterGroups.Length; i++)
{
CharacterData[] data = _characterGroups[i].GetComponentsInChildren<CharacterData>();
for(int j = 0; j < data.Length; j++)
{
data[j].InputData(_characterSOs[(i * data.Length) + (j)]);
}
}
}
}분명 이렇게 해 봤을 때 처음에는 잘 작동을 했는데, 이상하게 저녁 먹고 돌아와서 다시 테스트를 해보니 제대로 작동하지 않았다. 원인이 뭔지 약간 알 것 같기도 한데, 살펴봐야 할 필요성이 있어 보인다.
3. 개선점 및 과제
3.1 편성 프리셋 기능 구현
팀장(같은 팀원)에게 다음으로 구현할 기능으로 편성 프리셋 기능을 만들어달라는 부탁을 받았다. 해당 부분을 구현해보자.
3.2 캐릭터 배치 기능 구현
인게임 전투 씬에서 캐릭터를 배치하는 기능과, 자동 배치 기능도 구현해야 할 것이다
3.3 데이터를 쉽게 적용할 방법? 오류 수정
3.4 리팩토링
<참고자료>
