비헤이비어 트리 vs FSM

FSM 이란?

• Finite State Machine, 유한 상태 기계
  
  
• 유한한 개수의 상태들로 구성된 하나의 간단한 기계
  
  
• 캐릭터의 행동을 각 상태로 모듈화
• 캐릭터의 행동 추가/삭제에 대해 어느 정도 유연함을 가지고 있는 편
  하지만 State를 나누거나, Transition을 리와이어링 하기가 매우 어렵다.(State가 늘어날 수록)
  
  
• 확장이 제한된다.
  
  
• HFSM(Hierarchical Finite State Machine)을 사용하여 문제점을 보완할 수 있지만 유지 보수 코스트는 여전히 높다
  
  
• 콘솔 게임에서는 온라인 게임보다 AI가 훨씬 더 중요한 요소 -> FSM이 부적합

유한 상태 기계라고도 한다.

보통 단순한 AI 구조에 사용된다.

FSM은 한 번에 한 가지의 상태만 가지고 있을수 있고 상태를 바꾸기위해서는 전이가 필요하다.

이 전이를 하기 위한 조건들을 코드로 만들어 줘야 한다.

언리얼 ABP

 

심플하고 직관적인 모습이 FSM의 장점이지만 상태가 증가할수록 FSM은 장점을 잃어버리게 된다.

점점 조건들이 많아지고 AI가 복잡해진다면 아래와 같은 구조가 될 것이다.

 

단점 : state 간에 너무 많은 이동이 있어야하고, 이는 너무 많은 one-way control transfer이 많아진다는 것이다. 만약 하나의 state가 빠지게 되면 모든 state의 연결성이 변경되어야 한다는 치명적인 단점이 있다. 또한 당연하게도 하나의 state가 추가 되면 다양한 state에서도 추가 된 state로 이동하는 one-way control transfer를 모두 만들어줘야 한다. (엄청만 복잡도의 증가) 

 

---

HFSM (Hierachical Finite State Machines) 이란?

 

 

계층적 유한 상태 기계이다.

앞선 FSM의 복잡한 구조를 개선한 버전이다.

간단히 이야기하자면 항목별로 분류하여 정리된 FSM라 할 수 있다.

 

FSM이 단순 AI에 최적화되어 있다면 HFSM은 보다 더 복잡한 행동 패턴을 직관적이고 깔끔하게 그릴 수 있다.

대기, 이동, 공격 각각의 상태로 전이 후 조건에 맞는 하위 상태를 선택하는 구조이다.

 

하지만 전체적인 틀은 FSM과 동일하다.

이 역시 그 수가 많이 늘어난다면 복잡한 구조를 띄게 되고 가독성과 유지 보수가 어려워진다.

---

BT 란?

언리얼 엔진의 BT

 

HFSM 구조는 각 상태마다 지닌 로직을 통해 다음 상태로 전이했다고 하면,

BT 구조는 상위 노드에서 매 틱마다 우선순위를 평가하고 상태를 결정한다.
그림으로 쉽게 이야기하자면 서로 엇갈리는 화살표가 필요없다.

 

BT에서는 상태를 정해주는 건 Root 노드라고 생각하면 된다.

그 때문에 각각의 상태 노드들은 자신들이 맡은 독립적인 행동 노드들만 컨트롤하면 된다.

또한 우선순위를 미리 결정할 수 있기에 먼저 처리해야 하는 일들이 있으면 우선순위를 조정해서 처리가 가능하다.

복잡한 화살표도 없고 트리 구조를 띄고 있기 때문에 높은 가독성과 유지 보수가 장점이다.
HFSM은 각 상태들이 스스로 다음 행동을 결정하지만 BT는 상위 상태가 할 일을 결정해 준다.

 

장점

• 우선순위를 조정해서 처리가 가능
  
  
• Divide & Conquer로 작업을 쪼개기 쉬움
  
  
• 모듈 재활용이 용이, 읽기 쉽고 유지보수가 간편하다.
  
  
• visual Tool 제작이 용이

 

주의할 점

• BT 노드의 탐색 순서가 행동에 영향을 미친다
• BT 노드는 서로간에 의존성이 없어야 한다
• BT 노드는 Blackboard나 게임 오브젝트에서 정보를 얻어와야 한다.

 

BlackBoard

• Blackboard란 : 의사결정을 위해 데이터를 쓰고 읽을 수 있는 간단한 장소
  • Blackboard는 단일 AI Pawn에 사용하거나, 분대(Squad)에서 공유하거나, 관련 데이터를 검색할 수 있는 중앙 장소가 있는 편리한 다른 용도로 사용할 수 있다.
  • Blackboard는 일반적으로 BT와 함께 사용되지만, 편의상 BT와 별도로 사용하거나 Blackboard가 필요없는 BT를 만들 수 있다.
• Blackboard를 사용해야 하는 이유.
  
  • 1) 효율적인 이벤트 기반 동작을 만들기 위해
    :Blackboard를 변경하면 값을 확인하기 위해 모든 프레임을 업데이트할 필요 없이 BT의 흐름을 변경하는 이벤트가 발생할 수 있다.
    
    
  • 2)캐시 연산
    :계산 되어야 하는 일부 데이터들은 반복해야 하거나 단순히 성능 면에서 비용이 많이 들 수 있다.
    따라서 BT 전체에서 사용할 수 있도록 계산된 값을 캐싱하여 반복해서 다시 계산할 필요가 없도록 하는 것이 좋다.
    
    
  • 데이터 집중화
    :Blackboard는 데이터를 중앙 집중화하고 데이터의 출처에 대한 추가 지식이 필요하지 않은 좋은 방법이다.
    Blackboard가 없으면 다양한 클래스에 저장된 정보를 쿼리하기 위해 여러 단계를 거쳐야 하는 경우가 많다.