[C#][C++] 콤보 시스템으로 배우는 Trie 만들기
저번 시간에는 랜덤 박스를
포스팅했었습니다.
포스팅 중간에
이름을 검색하는 방법이
나와 있었죠.
이런 식으로, 문자를 이어서
문자열을 찾는
Trie 자료구조였습니다.
이거면 모든 내용을 돌면서
문자열을 하나하나
대조할 필요가 없이
문자열 길이만큼의 참조로
바로 원하는 내용에
갈 수 있게 도와주는
이정표 역할을 했었죠.
여기서 문자가 아닌
입력 키를 받으면
콤보 시스템을 만들 수 있습니다!
만들면서 Trie도 알아보도록 합시다~
<C# 코드>
다음과 같은 네임스페이스
참조가 필요합니다.
using System.Collections.Generic; //list<T>를 사용하기 위해서 참조list만 쓰기 때문에
다른 list를 사용하실 분은
교체해주시면 되겠습니다!
<C++ 코드>
다음과 같은
헤더 참조가 필요합니다.
#include<string> //문자열 관리를 위해 필요
#include<vector> //하위 노드의 관리를 위해 필요역시나 다른 자료구조를
사용하시는 분은
해당 자료구조로 교체하셔도
무방합니다.
<목표>
키 입력을 받고
해당하는 스킬이 있을 때
그 스킬의 이름을 반환하는
클래스를 만듭시다!
<제작>
※이 강좌는 C#을 기준으로
작성되었습니다.
※언리얼과 유니티 엔진이
시간을 float으로 쓰기 때문에
float으로 만들었습니다.
///입력할 수 있는 키를 미리 표시해둡니다.
public enum EnumKey
{
UP,
DOWN,
FRONT,
BACK,
PUNCH,
KICK
}우선 입력할 키를
미리 준비해둡시다.
필요에 따라서
넣어두시면 되겠습니다.
///콤보의 내용이 들어갈 노드입니다.
private class TrieNode
{
///이 노드가 가리키고 있는 키입니다.
EnumKey currentKey;
///이 노드에 할당된 기능이 있다면, 표시합니다.
public string currentName = "";
///이 노드의 상위 노드입니다.
TrieNode parent = null;
///이 노드의 하위 노드 리스트입니다.
List<TrieNode> childList = new List<TrieNode>();
///입력 키를 사용해서 새로운 노드를 추가합니다.
public TrieNode(EnumKey wantKey)
{
currentKey = wantKey;
}
}노드의 구성입니다.
본인 노드를 만든 부모 노드
본인이 만든 자식 노드 리스트
두 종류에 이어져 있고
본인이 의미하는 입력 키
본인이 담고 있는 스킬 이름
이렇게 네 종류로 구성해두었습니다!
///하위 노드 중에서 해당하는 키를 가진 노드를 찾습니다.
public TrieNode FindChild(EnumKey wantKey)
{
for (int i = 0; i < childList.Count; ++i)
{
if (childList[i].currentKey == wantKey)
{
return childList[i];
};
};
return null;
}제일 먼저 구성할 것은
자식 노드 확인입니다.
자식 노드를 전부 확인해서
원하는 키에 해당하는 노드가
있는지 확인하면
그 노드를 보여줍시다.
간단하죠?
///해당하는 키를 가진 하위 노드를 만듭니다.
public TrieNode NewChild(EnumKey wantKey)
{
TrieNode returnNode = FindChild(wantKey);
if(returnNode == null)
{
new TrieNode(wantKey);
returnNode.parent = this;
childList.Add(returnNode);
};
return returnNode;
}뭘 생성하기도 전에
찾기부터 만든 이유는
중복 생성을 막기 위해서였습니다!
키가 들어오면, 이미 있는지 확인하고
없으면 새로운 노드를 만들죠~
이 때, 부모 노드가 본인이라고
알려준 후에
새로 만든 노드를 자식 노드 리스트에
추가를 해두도록 합시다.
///해당하는 배열과 순서가 일치하는 마지막 노드를 찾습니다.
public TrieNode Find(EnumKey[] wantArray, int index)
{
//내 다음 위치를 찾기 위해 1을 더합니다.
++index;
//다음 위치가 아직 남은 경우
if (index < wantArray.Length)
{
//다음 위치에 해당하는 키를 가진 하위 노드를 찾습니다.
TrieNode nextChild = FindChild(wantArray[index]);
//있다면, 그 노드에게 나머지 탐색을 요청합니다.
if (nextChild != null)
{
return nextChild.Find(wantArray , index);
}
//없다면, null을 반환합니다.
else
{
return null;
};
}
//다음 위치가 없는 경우
else
{
//마지막 키가 본인과 같으면, 본인이라고 알리고 아니면 null을 반환합니다.
if (wantArray[wantArray.Length - 1] == currentKey)
{
return this;
}
else
{
return null;
};
};
}같은 순서로
배열 찾기를 만들어봅시다.
배열에 나열된 키를 그대로 쫓아서
배열 마지막까지 달립니다.
혹시라도 중간에 막히면
null을 반환하고
만약 끝까지 와도
마지막 키가 본인과 맞지 않으면
null을 반환합니다.
그림으로 보자면 이런 느낌입니다.
처음 이 함수가 입력될 0번째 노드는
루트에서 판별할 것이므로
0번은 건너 뛰고 판단합니다.
그래서 함수 시작할 때
위치에 1을 더하고 시작하는 것이고
더 나아갈 위치가 없으면
마지막으로 본인을 한 번 더
확인하고, 본인을 반환합시다.
///해당하는 배열의 순서에 맞춰 새로운 노드들을 만듭니다.
public void Insert(EnumKey[] wantArray, int index, string wantName)
{
//내 다음 위치를 찾기 위해 1을 더합니다.
++index;
//다음 위치가 존재하는 경우
if (index < wantArray.Length)
{
//다음 위치에 해당하는 키를 가진 하위 노드를 찾고, 없으면 새로 만듭니다.
TrieNode nextChild = NewChild(wantArray[index]);
//다음 위치의 하위 노드에게 계속 생성해달라고 요청합니다.
nextChild.Insert(wantArray, index, wantName);
}
//다음 위치가 없다면, 여기가 대상이므로 스킬이 없었을 때 새로운 스킬을 받습니다.
else if (currentName == "")
{
currentName = wantName;
};
}배열 생성도 찾기와 같은 순서로
노드를 찾아 나갑시다.
찾기와 다른 점은
찾아서 없을 때마다
새로 생성한다는 점입니다!
///해당 노드를 삭제합니다.
public void Delete()
{
//스킬을 비웁니다.
currentName = "";
//하위 노드를 가지고 있지 않았을 때에만 실행합니다.
if (childList.Count <= 0)
{
//상위 노드가 있는 경우
if (parent != null)
{
//상위 노드가 가진 하위 노드가 이것뿐이라면, 그 노드도 삭제합니다.
if (parent.childList.Count <= 1 && parent.currentName == "")
{
parent.Delete();
}
//다른 하위 노드가 있었다면, 이 노드만 빼달라고 요청합니다.
else
{
parent.childList.Remove(this);
};
//상위 노드와 연결을 끊습니다.
parent = null;
};
//하위 노드와 연결을 끊습니다.
childList.Clear();
};
}생성도 했으니 삭제도 해야죠!
삭제는 맨 마지막 노드에
요청을 하도록 하구요
삭제를 할 때에는
다음과 같은 상황을 고려해야 합니다.
-자식 노드가 있을 때-
이 때에는 본인이 중간이기 때문에
삭제되면 예기치 않은
연쇄삭제가 생기게 됩니다.
스킬 이름만 지우고 넘어갑시다.
-부모 노드가 없을 때-
본인에게 삭제 요청이 왔는데
부모 노드가 없다면
본인이 자료구조의
뿌리(root)이기 때문에
삭제되면 자료구조 사용에
문제가 생길 수 있습니다.
그래서 삭제를 처리하지 않습니다.
-부모 노드에 연결된 다른 노드가 있을 때-
다른 노드가 있다면
부모와 본인의 연결만 끊습니다.
-부모 노드에 본인만 있을 때-
본인만 연결된 부모 노드는
본인을 위해 만들어진 것이기 때문에
같은 라인으로 보고
연쇄 삭제를 요청합니다.
이러한 과정을 통해
삭제활동을 하도록 합니다.
///해당 노드에 이어진 모든 하위 노드들을 삭제합니다.
public void Destroy()
{
if(parent != null)
{
//하위 노드들에게 모두 삭제 요청을 돌립니다.
for (int i = 0; i < childList.Count; ++i)
{
childList[i].Destroy();
};
//상위, 하위 노드의 연결을 해제합니다.
parent = null;
childList.Clear();
};
}한 단계 더 높은 삭제도
만들어 둘게요!
이건 콤보시스템을 삭제할 때
완전히 삭제하기 위해 만들었습니다~
뿌리 노드에 넣어주시면 됩니다!
트라이 삽입, 삭제, 검색
세 개면 다 만든 것 같으니
콤보 시스템도 만들어 봅시다~
class ComboSystem
{
///트라이 노드의 시작점(root)입니다.
private TrieNode rootTrie = new TrieNode(0);
///마지막으로 입력한 키의 노드입니다.
private TrieNode lastChecked = null;
///이 클래스가 기다려주는 한계 시간입니다.
private float expiredTime = 0.0f;
///입력을 받은 후, 다음 연계까지 몇 초의 시간을 기다려줄지 설정합니다.
private float limitInputTime = 0.0f;
///연계 대기 시간을 정해서 인스턴스를 생성합니다.
public ComboSystem(float limitTime)
{
limitInputTime = limitTime;
}
~ComboSystem()
{
rootTrie.Destroy();
}
}콤보 시스템의 기본 구조입니다.
위에서 작성한 노드가
두 개 들어가 있습니다!
-rootTrie-
모든 노드의 시작 지점!
이 부분이 되겠네요!
여기는 어차피 다른 노드를 찾는
시작점이기 때문에
내용은 상관 없지만,
그래도 0번째 키를 넣어주었습니다.
쓰는 것이 아니기 때문에
그냥 아무렇게나 두셔도 됩니다!
-lastChecked-
마지막으로 확인한 노드!
이건 콤보시스템이기 때문에
마지막으로 입력한 값이
가장 중요하게 되겠는데요!
이걸 미리 저장해두어서
빠르게 접근하도록 합시다.
-expiredTime-
콤보를 사용하는 데에 있어서
한정 없이 입력을 기다릴 순 없죠~
입력한 시간이 여기에 기록된
시간보다 늦는다면
가차없이 처음부터
다시 입력하게 합시다~
-limitInputTime-
그럼 언제까지 기다리느냐?
를 기록하는 칸입니다.
여기에 적힌 시간만큼 기다립시다.
기본적으로 필요한 칸인 만큼
콤보시스템의 생성자도
이 칸의 입력을 필요로 하죠!
///한계 대기 시간을 다시 조정합니다.
public void SetTimeLimit(float wantTime)
{
limitInputTime = wantTime;
}
///다음 연계까지 기다려주는 시간을 직접 정합니다.
public void SetExpireTime(float wantTime)
{
expiredTime = wantTime;
}이 시간에 관련된 두 변수는
그냥 설정할 수 있게 해두겠습니다~
///최상위 노드 중에서 원하는 키를 가진 노드를 찾습니다.
private TrieNode FindNodeStart(EnumKey wantKey)
{
return rootTrie.FindChild(wantKey);
}일을 진행하기에 앞서
작업할 공간은 찾아야겠죠?
시작 노드 바로 밑에 달린
노드를 찾는 함수입니다!
///해당 배열의 순서와 같은 최하위 노드를 찾습니다.
private TrieNode FindNodeEnd(EnumKey[] wantArray)
{
//진입 노드를 찾습니다.
TrieNode targetNode = FindNodeStart(wantArray[0]);
//진입 노드가 존재한다면
if (targetNode != null)
{
//찾기 요청을 전달합니다.
targetNode = targetNode.Find(wantArray, 0);
//찾은 노드가 있다면 해당 노드를 반환합니다.
if (targetNode != null)
{
return targetNode;
};
};
//진입 노드가 없다면 그냥 null을 반환합니다.
return null;
}시작 위치를 찾았다면
끝나는 위치도 찾아야죠!
진입할 노드를 찾아보고
그 노드에 Find함수를 실행합니다.
그럼 알아서 맨 밑에 있는
내용을 가져다 주겠죠~
///해당 배열의 순서에 맞게 스킬을 넣습니다. 이미 그 자리에 스킬이 있다면, 실패합니다.
public void Insert(EnumKey[] wantArray, string wantName)
{
//첫 번째 진입 노드를 찾습니다. 없으면 새로 만듭니다.
TrieNode targetNode = rootTrie.NewChild(wantArray[0]);
//진입 노드에 생성 요청을 전달합니다.
targetNode.Insert(wantArray, 0, wantName);
}
///해당 배열과 순서가 같은 스킬이 있다면, 해당 스킬을 제거합니다.
public void Delete(EnumKey[] wantArray)
{
//해당하는 스킬을 찾습니다.
TrieNode targetNode = FindNodeEnd(wantArray);
//있으면 제거합니다.
if(targetNode != null)
{
targetNode.Delete();
};
}
///해당 배열과 순서가 같은 스킬이 있다면, 그 스킬의 이름을 바꿉니다.
public void ChangeName(EnumKey[] wantArray, string wantName)
{
//해당하는 스킬을 찾습니다.
TrieNode targetNode = FindNodeEnd(wantArray);
//있으면 이름을 바꿉니다.
if (targetNode != null)
{
targetNode.currentName = wantName;
};
}찾기를 만들었다면 이미 끝입니다!
Trie에서 모든 내용을 만들었기 때문에
찾은 대상에게 명령을 전달만 하면 됩니다~
Insert함수는 노드가 없을 때
새로 만든다는 선택지가
추가되었을 뿐이네요!
///유저가 키를 입력했을 때 실행하는 함수입니다.
public string Input(EnumKey inputKey, float inputTime)
{
//기다려주는 시간보다 입력한 시간이 더 빠르면
if(expiredTime >= inputTime)
{
//직전에 확인한 노드가 있었는지 봅니다.
if(lastChecked != null)
{
//있었다면, 하위 노드 중에 새로 입력된 키로 옮겨갑니다.
lastChecked = lastChecked.FindChild(inputKey);
};
}
//늦게 입력되었으면, 직전 노드를 비웁니다.
else
{
lastChecked = null;
};
//기다려주는 시간을 현재시간 + 한계시간으로 조정합니다.
expiredTime = inputTime + limitInputTime;
//확인할 노드가 없다면
if (lastChecked == null)
{
//최상단 노드들 중에서 해당하는 키를 확인하도록 합니다.
lastChecked = FindNodeStart(inputKey);
};
//모든 확인을 끝낸 뒤에 도출된 노드가 있다면
if(lastChecked != null)
{
//해당 노드의 이름을 받아옵니다.
return lastChecked.currentName;
}
//최상단 노드에도 해당하는 키가 없었다면, 빈 문자열을 반환합니다.
else
{
return "";
};
}대망의 콤보 구현 함수입니다!
이걸 위해 지금까지 달려왔죠~
근데 사실 생각보다 간단합니다.
Trie만 있으면 콤보는
이렇게 쉽게 완성되는 거네요!
천천히 살펴볼까요?
먼저 시간 안에 입력했는지
확인합니다.
시간을 넘었으면 null
직전 입력이 없으면 null
입력한 내용이 콤보에 없으면 null
이 세 가지의 경우를 뚫으면
다음 노드를 이어줍시다!
중간에 대기시간을 조정하구요.
위에서 null을 받았으면
콤보를 시작하는 키를 확인합니다.
전 콤보가 끊겨도
다시 시작할 수 있게 말이죠!
근데 다음 콤보에 있는 키도,
콤보 시작하는 키도 아니면
그냥 빈 문자열을 반환하구요.
둘 중 하나라도 해당한다면
그 노드를 lastChecked로 놓고
들어있는 문자열을 반환합니다.
물론 그래도 빈 문자열일 수 있지만
빈 문자열이면 아직 스킬이
나오지 않은 걸로 보면 되겠습니다!
<마치며>
이렇게 Trie를 사용한
콤보 시스템을 만들어 보았습니다!
Insert로 콤보를 넣고
Input으로 키 입력만 받으면
기본적인 콤보를 구현할 수 있겠네요!
물론 스킬 쓸 때 걸리는 시간도 있고
정지하는 시간도 있고 하지만
expiredTime을 조정해서
입력을 받으면 좋을 것 같습니다~
실시간으로 콤보를 넣고 뺄 수 있어서
튜토리얼에 콤보를
천천히 추가해 준다거나
조건을 만족하면
콤보를 얻는다거나
한 게임에 한 번만 쓸 수 있는
콤보를 만든다거나
유저가 직접
콤보를 만든다거나
다양한 곳에 응용할 수 있을 것 같네요!
만들기는 굉장히 쉬운 편이라
다양하게 응용해보시는 것도
좋을 것 같습니다!
글 읽어주셔서 정말 감사드리고
다음 포스팅에서 뵙겠습니다!