[UNSEEN] 테스트 대비 7. 게임 알고리즘

Doorbals·2023년 2월 17일
0

UNSEEN

목록 보기
7/10

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 노드의 로직만 수정해주면 된다.

비헤이비어 트리의 주요 노드

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* 알고리즘의 예제

https://itmining.tistory.com/66

profile
게임 클라이언트 개발자 지망생의 TIL

0개의 댓글