[알고리즘] FSM, HFSM, BT의 특징

🎲 Finite State Machine (유한상태머신)

캐릭터나 몬스터의 행동을 정의하고 구현하기 위해 나온 방법입니다. 각각의 행동상태를 state로 정의하고 특정 조건에 따라 다른state로 넘어가는 방식입니다. 단순히 조건문을 도배하는것보다 훨씬 효율적인 방법이긴 하지만 state가 많아질수록 걷잡을 수 없이 복잡해지기 때문에 복잡한 형태의 AI는 구현하거나 행동들을 추가, 삭제, 수정하기 힘듭니다. 언리얼의 애니메이션 블루프린트와 유니티의 애니메이터 컨트롤러가 이러한 형태입니다.

 

 

🎲 Hirerarchy Finite State Machine (계층적 유한상태기계)

FSM의 문제점을 조금 개선한 형태의 방식입니다. 특정 상태들이 동시에 이루어지는 것을 FSM에서는 구현하기 힘들었기 때문에 HFSM에서는 서로 동시에 이루어질 수 없는 노드들을 계층으로 묶은 뒤 각각의 계층은 해당 계층 내에서만 상태가 결정되도록 해주는 방식입니다.

 

 

🎲 Behaviour Tree (비헤이비어 트리)

BT또한 FSM의 문제점을 보완한 방식으로 트리형태의 행동 알고리즘입니다. 모든 하위 노드의 행동 여부는 상위 노드에서 결정이 됩니다. 시각적으로 표현하기가 좀 더 용이할 뿐만 아니라 노드를 추가, 삭제, 수정을 할 때도 FSM는 해당 노드와 연결된 모든 노드들의 코드를 수정해주어야하는 반면에 BT는 간편하게 해당 노드만 고쳐주면 되어서 유지보수에 용이합니다.

 

🍳 Composite

노드의 분기점 역할로, 어떤 자식노드가 실행될지 결정합니다.

 

    🎨 sequence : 모든 자식들이 success를 반환할경우에만 success를 반환하고 하나라도 failure일 경우 failure를 즉시 반환합니다. AND연산과 비슷합니다.

    🎨 Selector : 하나라도 success를 반환할경우 즉시 success를 반환합니다. OR 연산과 비슷합니다.

    🎨 Parellel : 모든 자식들을 실행합니다.

 

🍳 Decorator

일종의 조건문 혹은 반복문으로 자식노드의 결과값을 변형하거나 반복하여 실행해주는 기능을 합니다.

 

    🎨 condition : 조건에 맞으면 자식을 실행하고 틀리면 failure를 반환합니다. 

    🎨 Inverter : 자식의 반환값이 success면 failure를, failure면 success를 반환합니다. Not 연산과 비슷합니다.

    🎨 Loop : 특정 조건에 맞게 자식을 반복 실행합니다. 반복문과 비슷합니다.

 

 

🍳 BlackBoard

BlackBoard는 일종의 공용 데이터입니다. 각각의 노드에서 사용되는 데이터 중에 중복되는 데이터들의 중복 계산을 피하기 위해서 만들어 졌습니다. 자주 사용되는 데이터를 미리 계산하고 BlackBoard에 넣어 둠으로써 다른 노드들이 추가적으로 계산하지않고 이를 꺼내 쓰도록 하는 방식입니다.