1. 쿼드 트리(Quad Tree)
-
트리의 자식 노드가 4개인 트리를 의미한다.
-
게임에서는 일반적으로 지형 정보를 저장하는 데에 사용된다.
-
컬링을 위한 지형 검색에 쿼드 트리를 사용한다.
-> 쿼드 트리를 이용하면 필요 없는 데이터를 큰 덩어리 단위로 버릴 수 있게 되므로 거대한 지형을 빠르게 검색할 수 있기 때문이다.
예제
: 백준 1992번 : 쿼드트리 (https://www.acmicpc.net/problem/1992)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int map[65][65];
void compress(int n, int y, int x)
{
if (n == 1)
{
cout << map[y][x];
return;
}
bool exist0 = false;
bool exist1 = false;
for (int i = y; i < y + n; i++)
{
for (int j = x; j < x + n; j++)
{
if (map[i][j] == 0)
exist0 = true;
else
exist1 = true;
if (exist0 && exist1)
break;
}
if (exist0 && exist1)
break;
}
if (exist0 && exist1)
{
cout << '(';
compress(n / 2, y, x); // 2사분면
compress(n / 2, y, x + n / 2); // 1사분면
compress(n / 2, y + n / 2, x); // 3사분면
compress(n / 2, y + n / 2, x + n / 2); // 4사분면
cout << ')';
}
else if (exist0)
cout << 0;
else
cout << 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < n; j++)
{
map[i][j] = str[j] - '0';
}
}
compress(n, 0, 0);
}2. FSM(Finite State Machine)
-
유한 상태 머신이라고도 한다.
-
유한 상태 머신은 자신이 취할 수 있는 유한한 갯수의 상태들을 가진다.
-
그리고 그 중에서 반드시 하나의 상태만 취한다. (상태 중복을 피할 수 있다.)
-
현재 상태는 특정 조건이 되면 다른 상태로 변할 수 있다.
-
유한 상태 머신은 가능한 상태들의 집합 + 각 상태들의 전이 조건으로 정의된다.
-
상태들이 많아지면 각 상태 내에서 다른 상태로 전이하는 조건을 전부 구현해주어야 하기 때문에 구조가 매우 복잡해진다.
-
FSM을 개선한 HFSM(Hierarchical Finite State Machine == 계층적 유한 상태 머신)가 존재한다.
- 각각의 상태로 전이 후 조건에 맞는 하위 상태를 선택하는 구조이다.
예제
public class PlayerBehavior
{
enum State
{
Idle,
Jump,
Run,
Attack
}
}
void Start()
{
State playerState = State.Idle;
}
void Update()
{
switch(playerState)
{
case State.Idle:
Idle();
break;
case State.Jump:
Jump();
break;
case State.Run:
Run();
break;
case State.Attack:
Attack();
break;
}
}
void Idle()
{
if(Input.KeyDown(Space))
state = State.Jump;
if(Input.KeyDown(MouseLeft))
state = State.Attack;
...
}
void Jump() { ... }
void Run() { ... }
void Attack() { ... }
3. 비헤이비어 트리(Behavior Tree)
-
행동을 트리 구조로 기술한 것.
- 한 덩어리의 태스크가 서브트리를 이룬다.
- 평가 시 각 노드는 깊이 우선 탐색 한다.
- 탐색 결과 자식 노드에서 부모 노드로 상태가 반환된다.
- success : 실행 성공
- failure : 실행 실패
- running : 실행 중. 이후 running을 반환한 노드가 다시 호출됨.
-
상위 노드에서 매 틱마다 우선순위를 평가하고 상태를 결정한다.
-
각 상태 내에서 다른 상태로 가기 위한 로직을 구현하는 것이 아니라, 최상위의 Root 노드에서 상태를 지정해주는 것이다. 때문에 각 상태 노드들은 자신들이 맡은 독립적인 행동 노드들만 제어하면 된다.
- ex. 이동 -> 공격 상태로 상태 전이가 이루어진다고 할 때
- FSM : 이동 상태에서 로직을 통해 판단 후 공격 상태로 전이
- BT : Root 노드에서 우선순위를 재판단 후 즉각 공격 상태로 전이
- 어떤 상태가 추가되거나 삭제될 때
- FSM : 추가되거나 삭제되는 상태와 연결된 모든 상태의 로직을 변경해야 한다.
- BT : 해당 노드를 추가하거나 삭제하고 Root 노드의 로직만 수정해주면 된다.
- ex. 이동 -> 공격 상태로 상태 전이가 이루어진다고 할 때
비헤이비어 트리의 주요 노드
1) Composite
- 해당 노드 아래에 있는 서브트리를 통해 표현되는 행동(서브 태스크)을 제어한다.
- 자식 노드 중 하나 이상을 특정 Composite 노드에 따라 차례대로, 또는 무작위로 처리한다.
- 하나 이상의 자식 노드를 가질 수 있다.
[Composite 노드의 종류]
- Selector
- 자식 노드 가운데 하나를 실행하기 위한 노드
- 평가를 시작하면 selector의 자식 노드를 왼쪽에서 오른쪽의 순서(우선도가 높은 쪽 -> 낮은 쪽)로 깊이 우선 탐색 방식으로 평가하게 된다.
- selector의 자식 노드 중 하나가 success나 running을 반환하면 selector는 부모 노드에 즉시 success나 running을 반환한다.
- selecotr의 모든 자식 노드가 failure를 반환했을 때는 selector가 부모 노드에 failure를 반환한다.
- Sequence
- 자식 노드를 순서대로 실행하기 위한 노드
- 평가를 시작하면 selector의 자식 노드를 왼쪽에서 오른쪽의 순서(우선도가 높은 쪽 -> 낮은 쪽)로 깊이 우선 탐색 방식으로 평가하게 된다.
- sequence의 자식 노드 중 하나가 failure나 running을 반환하면 sequence는 부모 노드에 즉시 failure나 running을 반환한다.
- sequence의 모든 자식 노드가 success를 반환했을 때는 sequence도 부모 노드에 success를 반환한다.
2) Decorator
- 조건을 만족하면 자식을 실행하고, 조건을 만족하지 못하면 false를 반환 -> 조건문과 같은 역할
- 자식 노드의 상태로부터 받은 결과를 변형시키거나, 자식 노드를 종료시키거나, Decorator 유형에 따라 자식 노드의 처리를 반복한다.
- 하나의 자식 노드만 가질 수 있다.
[Decorator 노드의 종류]
-
while
- 조건 충족을 평가하는 함수가 true를 반환하는 한 자식 노드의 평가를 반복
- 조건 충족 평가 함수가 failure를 반환하면 while도 부모 노드에 failure를 반환
-
if
- 조건 충족 평가 함수가 true를 반환한 경우, 현재 유효한 자식 노드를 호출해 그 결과 반환
- 그 밖의 경우에는 자식 노드 호출 없이 부모 노드에 failure 반환
-
repeat(Loop)
- 자식 노드가 결과를 반환할 때마다 자식 노드를 재처리
- 미리 설정해 둔 횟수만큼 자식 노드가 처리되었다면 부모 노드에 success 반환
- 이외에는 전부 running 반환
-
inverter
- 자식 노드의 결과를 뒤집거나 부정한다.
- 성공은 실패, 실패는 성공이 된다.
-
succeeder
- 자식 노드가 실제로 무엇을 반환하든 상관없이 항상 성공 반환
- 고장이 예상되거나 트리의 분기를 처리하려는 경우 유용
- 고장이 필요한 경우 succeeder에 inverter 처리하면 정반대의 결과가 나오기 때문에 따로 succeeder의 반대 유형이 필요하지 않음.
-
repeat until fail
- 자식 노드가 실패를 반환할 때까지 자식 노드를 반복 실행
- 실패를 반환하면 부모 노드에게 성공 반환
- 그 이외에는 running 반환
3) Execution (== Leaf, Action)
- 비헤이비어 트리 외부에 구현된 구체적인 함수를 호출한다.
- 호출된 함수의 반환값에 따라 실행 결과의 상태(succeess, failure, running)를 판단하여 그 반환값을 부모 노드에 반환한다.
- 어떤 자식 노드도 가질 수 없다.
- 비헤이비어 트리가 적용되는 대상이 실제로 어떤 행동을 하도록 하는 작성되는 것이 해당 노드이기 때문에 가장 강력한 노드이다.
비헤이비어트리의 예제
https://engineering.linecorp.com/ko/blog/behavior-tree
4. A* 알고리즘
1) 시작 사각형에서 검색된 인접 사각형들을 열린 목록에 넣는다. 시작 사각형은 닫힌 목록에 넣는다.
2) 다음 과정 반복
- 열린 목록에서 가장 낮은 비용 F를 찾아 현재 사각형으로 선택
- 현재 사각형을 열린 목록에서 꺼내고 닫힌 목록에 넣는다.
- 현재 사각형에 인접한 8개의 사각형에 대해 탐색한다.
- 만약 인접 사각형이 갈 수 없는 곳이거나 닫힌 목록에 있으면 무시
- 아니라면 다음을 계속 실행
- 인접 사각형이 열린 목록에 있지 않다면 열린 목록에 넣고 G, H, F 비용을 계산해 기록하고, 이 사각형의 부모를 현재 사각형으로 만든다.
- 인접 사각형이 이미 열린 목록에 있다면 해당 사각형의 G 비용을 확인해 기존 G 비용보다 현재 사각형을 경유했을 때의 G 비용이 더 작다면 해당 사각형의 부모를 현재 사각형으로 변경하고, G, F, H 비용을 재계산해 기록한다.
3) 해당 경우에는 알고리즘을 종료한다.
- 목표 사각형을 목록에 추가했을 때 (경로 찾음)
- 열린 목록이 비어있을 때 (경로가 존재하지 않음)
A* 알고리즘의 예제
게임 클라이언트 개발자 지망생의 TIL