유한 상태 기계(finite-state machine, FSM)
유한 상태 기계는 AI를 구현하는 가장 기본적인 방법 중 하나입니다.
그림과 같이 캐릭터가 수행할 행동에 대해 상태를 정의해주고, 컨디션에 따라 상태가 변경이 됩니다. 새로운 행동을 추가하기 위해서는 새로운 상태를 만들고, 기존 상태와 연결을 시켜주면 됩니다. 캐릭터의 행동을 각 상태로 모듈화하였기 때문에 캐릭터의 행동 추가/삭제에 대해 어느 정도 유연함을 가지고 있는 편입니다.
다만, 연관되어 있는 상태들이 많아지면 많아질수록 컨디션 설정도 복잡해지며 관리가 힘들어집니다. 예를 들어 IDLE/MOVE/ATTACK 상태에서 사용할 수 있는 SuperAttack 상태가 추가 된다고 했을 때, IDLE/MOVE/ATTACK 상태에 SuperAttack을 사용할 수 있는 컨디션을 모두 추가 수정 해야 합니다.
행동 트리(Behavior Trees)
행동 트리는 유한 상태 기계와 다르게 이름 처럼 트리 방식으로 행동을 정의합니다. 각 Node에 Selector와 Sequence 노드를 이용하여 컨디션을 체크하고, 액션을 정의해 트리를 구성하게 됩니다.
Selector는 자식 노드를 실행하여, 이 중 하나라도 True를 리턴하면 True를 리턴하고, Sequence는 모든 자식 노드가 True를 리턴할 때, True를 리턴하게 됩니다. 반대로 Sequence는 자식 중 하나라도 False면 False를 리턴합니다. 코드로 보면 이해하기 쉽습니다.
class Node
{
public:
virtual bool Invoke() = 0;
};
class CompositeNode : public Node
{
public:
void AddChild(Node *node)
{
mChildren.emplace_back(node);
}
const std::list<Node*>& GetChildren()
{
return mChildren;
}
private:
std::list<Node*> mChildren;
};
class Selector : public CompositeNode
{
public:
virtual bool Invoke() override
{
for (auto node : GetChildren())
{
if (node->Invoke())
return true;
}
return false;
}
};
class Sequence : public CompositeNode
{
public:
virtual bool Invoke() override
{
for (auto node : GetChildren())
{
if (!node->Invoke())
return false;
}
return true;
}
};
BT::Sequence *root = new BT::Sequence(); // 루트 노드(시퀀스 노드로 생성)
BT::Selector *selector = new BT::Selector(); // 셀렉터
BT::Sequence *seqOrcKill = new BT::Sequence(); // 오크가 있으면 오크를 공격하는 시퀀스
BT::Sequence *seqMove = new BT::Sequence(); // 플레이어 이동 시퀀스
BT::Node *playerIsDead = new PlayerIsDead(); // 플레이어가 죽었는지 체크
BT::Node *checkIsHereOrc = new CheckIsHereOrc(); // 현 위치에 오크가 있는지 체크
BT::Node *attackOrc = new AttackOrc(); // 오크 공격 액션
BT::Node *playerMove = new PlayerMove(); // 플레이어 이동 액션
root->AddChild(selector);
root->AddChild(playerIsDead);
selector->AddChild(seqOrcKill);
selector->AddChild(seqMove);
seqOrcKill->AddChild(checkIsHereOrc);
seqOrcKill->AddChild(attackOrc);
seqMove->AddChild(playerMove);
while (!root->Invoke())
{
std::cout << "--------------------------------------" << std::endl;
std::this_thread::sleep_for(std::chrono::seconds(1));
}
유한 상태 기계에서 스테이트가 추가될 때마다 연결되는 스테이트에 컨디션을 추가 해주는 것과는 다르게 행동 트리에서 컨디션 체크는 자신의 노드에 대해서만 이루어집니다. 그렇기 때문에 추가 확장이 굉장히 자유롭습니다. 노드를 필요한 곳에 중복 복사해서 붙여넣기 해도 무방하죠.
위에서 오크가 있을때 공격하는 시퀀스와 이동 시퀀스를 아래와 같이 묶어도 됩니다(그냥 짤라서 붙여넣기 하면 되죠)
유의할 점은 노드는 추가된 순서에 따라 차례대로 호출 되기때문에 노드 순서가 캐릭터의 행동에 영향을 끼치게 됩니다.
위의 오크 사냥 행동 트리가 작동 되는 동작 순서를 보면...
Root에 Selector를 먼저 추가하였기 때문에 실행되면 Selector의 노드를 먼저 탐하게 됩니다. Selector에는 오크를 찾아 공격하는 시퀀스와 플레이어를 이동하는 시퀀스 2개가 추가되어있습니다.
먼저 첫번째 시퀀스인 오크를 찾아 공격하는 시퀀스를 탐색하게됩니다. CheckIsHereOrc 노드를 통해 오크가 현 위치에 있는 경우 True가 리턴되기 때문에 다음 노드인 AttackOrc 노드가 실행됩니다. 만약 오크가 없다면 False가 리턴 되기 때문에 다음 노드를 실행하지 않고, 현재 시퀀스 노드도 False를 리턴 합니다.
첫 번째 시퀀스가 False가 되면, Selector는 다음 시퀀스 노드를 탐색하게 됩니다. 두 번째 시퀀스에는 PlayerMove 만 있습니다. 이는 플레이어 이동 후 True를 리턴하게됩니다. Selector는 두 번째 시퀀스에서 True를 리턴 받았기 때문에 True를 리턴해줍니다.
Root는 이제 다음 노드인 IsPlayerDead를 실행합니다. 플레이어가 죽었다면 True, 아직 안죽었으면 False를 리턴합니다.
이렇게 노드들을 탐색하면서 Root 노드가 True를 리턴하게 되면 (IsPlayerDead가 True면) 프로그램을 종료하게 됩니다.
참고
http://www.cplusplus.com/forum/general/141582/
http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php