[UNSEEN 테스트 대비] A* 길찾기, FSM, 비헤이비어트리, Quadtree 공간 분할

쿼드 트리(Quad Tree)

• 트리의 자식 노드가 4개인 트리를 의미한다.
• 공간을 재귀적인 호출로 4개의 자식 노드로 분할하는 방법
• 게임에서는 일반적으로 지형 정보를 저장하는 데 사용된다.
• 컬링을 위한 지형 검색에 쿼드 트리를 사용한다. (컬링 : 렌더링에 필요하지 않은 오브젝트들을 추려 내는 것)
  -> 쿼드 트리를 이용하면 필요 없는 데이터를 큰 덩어리 단위로 버릴 수 있게 되므로 거대한 지형을 빠르게 검색할 수 있기 때문이다.

 

 

 

FSM(Finite State Machine)

• 유한 상태 머신이라고도 한다.
• 유한 상태 머신은 자신이 취할 수 있는 유한한 갯수의 상태들을 가진다.
• 그리고 그 중에서 반드시 하나의 상태만 취한다. (상태 중복을 피할 수 있다.)
• 현재 상태는 특정 조건이 되면 다른 상태로 변할 수 있다.
• 유한 상태 머신은 가능한 상태들의 집합 + 각 상태들의 전이 조건으로 정의된다.
• 상태들이 많아지면 각 상태 내에서 다른 상태로 전이하는 조건을 전부 구현해주어야 하기 때문에 구조가 매우 복잡해진다.
• FSM 을 개선한 HFSM(Hierarchical Finite State Machine == 계층적 유한 상태) 가 존재한다.
  -> 각각의 상태로 전이 후 조건에 맞는 하위 상태를 선택하는 구조이다.

 

 

 

 

비헤이비어 트리(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을 반환한다. 
• selector의 모든 자식 노드가 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)를 판단하여 그 반환값을 부모 노드에 반환한다.
• 어떤 자식 노드도 가질 수 없다.
• 비헤이비어 트리가 적용되는 대상이 실제로 어떤 행동을 하도록 하는 작성되는 것이 해당 노드이기 때문에 가장 강력한 노드이다.

 

서비스 (Service)

• 컴포짓 노드에 분기가 실행되는 동안 정해진 빈도에 맞춰서 실행된다.
  지정된 시간마다 콜백을 등록하고 주기적으로 발생시켜야 하는 업데이트를 수행한다.
• 틱과 비슷하지만 주기 등을 직접 설정해 줄 수 있기 때문에 효율적이다.
• 자신이 추가된 컴포짓 노드의 서브트리에 실행이 머물러있는 동안만 활성화된다.

 

태스크 (Task)

• AI가 수행할 액션
• ExecuteTask 멤버함수를 실행해서 넷 중 하나의 값을 반환해야 한다.
  Aborted : 태스크 실행 중 중단되어 실패
  Failed : 태스크 수행했지만 실패
  Succeeded : 태스크 성공적으로 수행
  InProgress : 태스크 수행중. (실행 결과는 나중에 알려줌)
• 태스크 노드에도 데코레이터가 붙을 수 있다.

 

A* 알고리즘

다익스트라 알고리즘은 연결된 정점에 대한 비용을 전부 계산해서 최소 비용으로 경로를 선택하는 반면
A* 알고리즘은  시작 노드부터 현재 노드까지의 비용을 g(n), 현재 노드에서 목표 노드까지의 예상 비용을 h(n) 이라 할 때, f(n) = g(n) + h(n) 이 가장 최소가 되는 노드를 다음 탐색 노드로 선정한다.

일반적으로 가장 작은 f(n)을 찾기 위해 우선순위 큐가 사용된다.

 

이때 h(n) 을 휴리스틱 함수라 하며 휴리스틱 함수에는 맨해튼 거리 함수(격자) 와 유클리디안 거리 함수(직선거리) 가 있다. 

 

 

1) 시작 사각형에서 검색된 인접 사각형들을 열린 목록에 넣는다. 시작 사각형은 닫힌 목록에 넣는다.

2) 다음 과정 반복

 

• 열린 목록에서 가장 낮은 비용 F(n) 를 찾아 현재 사각형으로 선택
• 현재 사각형을 열린 목록에서 꺼내고 닫힌 목록에 넣는다.
• 현재 사각형에 인접한 8개의 사각형에 대해 탐색한다.
  • 만약 인접 사각형이 갈 수 없는 곳이거나 닫힌 목록에 있으면 무시
  • 아니라면 다음을 계속 실행
  • 인접 사각형이 열린 목록에 있지 않다면 열린 목록에 넣고 G(n) , H(n) , F(n) 비용을 계산해 기록하고, 이 사각형의 부모를 현재 사각형으로 만든다.
  • 인접 사각형이 이미 열린 목록에 있다면 해당 사각형의 G(n) 비용을 확인해 기존 G(n) 비용보다 현재 사각형을 경유했을 때의 G 비용이 더 작다면 해당 사각형의 부모를 현재 사각형으로 변경하고, G(n) , F(n) , H(n) 비용을 재계산해 기록한다.

3) 해당 경우에는 알고리즘을 종료한다.

• 목표 사각형을 목록에 추가했을 때 (경로 찾음) 
• 열린 목록이 비어있을 때 (경로가 존재하지 않음)

 

아래 블로그에서 매우 잘 정리해 놓았다. 매우 유익하게 읽을 수 있었다.

 

https://recall.tistory.com/40

A* 알고리즘(A star algorithm) grid map 개념 및 구현

 

 

 

 

출처

https://velog.io/@doorbals_512/UNSEEN-테스트-대비-게임-알고리즘

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