트리의 자식 노드가 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);
}
유한 상태 머신이라고도 한다.
유한 상태 머신은 자신이 취할 수 있는 유한한 갯수의 상태들을 가진다.
그리고 그 중에서 반드시 하나의 상태만 취한다. (상태 중복을 피할 수 있다.)
현재 상태는 특정 조건이 되면 다른 상태로 변할 수 있다.
유한 상태 머신은 가능한 상태들의 집합 + 각 상태들의 전이 조건으로 정의된다.
상태들이 많아지면 각 상태 내에서 다른 상태로 전이하는 조건을 전부 구현해주어야 하기 때문에 구조가 매우 복잡해진다.
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() { ... }
행동을 트리 구조로 기술한 것.
상위 노드에서 매 틱마다 우선순위를 평가하고 상태를 결정한다.
각 상태 내에서 다른 상태로 가기 위한 로직을 구현하는 것이 아니라, 최상위의 Root 노드에서 상태를 지정해주는 것이다. 때문에 각 상태 노드들은 자신들이 맡은 독립적인 행동 노드들만 제어하면 된다.
[Composite 노드의 종류]
[Decorator 노드의 종류]
while
if
repeat(Loop)
inverter
succeeder
repeat until fail
https://engineering.linecorp.com/ko/blog/behavior-tree
1) 시작 사각형에서 검색된 인접 사각형들을 열린 목록에 넣는다. 시작 사각형은 닫힌 목록에 넣는다.
2) 다음 과정 반복
3) 해당 경우에는 알고리즘을 종료한다.