의사 결정 - State machines

2021.10.21 - [Game AI] - 의사 결정 - Decision Tree

의사 결정 - Decision Tree

 

State Machine

---

개요

State Machine은 캐릭터가 정해진 행동들 중 하나를 골라 행동할 때 쓰기 좋다. (예를 들면, 정찰, 공격, 대기 중 하나를 선택해서 행동하는 경비원 AI) GoF의 상태패턴을 사용한다고 보면 된다.

 

State Machine은 Script와 함께 쓰이는일이 많다. Script 안에 상태들을 정의해둔 뒤 게임 실행시 이를 불러와 State Machine을 구성한다. 이런 방식은 지금도 게임AI에서 많이 쓰이는 방법이다.

---

구현

• 캐릭터는 한 State Machine에서 단 하나의 State만 가진다. (단, 여러 개의 State Machine을 가질 경우는 그 수만큼)
• State끼리는 Transition을 통해 연결되어 있으며, State가 Transition의 목록을 가진다.
• 각 State는 들어갈 때, 나갈 때 수행할 액션을 지정할 수 있다.
• Transition이 trigger될 때도 수행할 액션을 지정할 수 있다.

//행동의 리스트를 반환한다.
public List<StateAction> Update()
{
	//트리거 될 전이(Transition)가 있는지 체크
    Transition triggered = null;
    
    //Transition의 목록은 상태에서 얻어온다.
    foreach (var transition in _currentState.GetTransitions())
    {
        if (transition.IsTriggered())
        {
            triggered = transition;
            break;
        }
    }
    
    var actions = new List<StateAction>();     
    if (triggered)
    {
        State targetState = triggered.GetTargetState();
        
        //전이가 트리거되면 다음의 행동들을 추가할 수 있다.
        actions.AddRange(_currentState.GetExitActions());
        actions.AddRange(triggered.GetActions());
        actions.AddRange(targetState.GetEntryActions());
    }
    else
    {
    	//트리거된 전이가 없다면 현재 상태에서 행동들을 얻어온다.
        actions.AddRange(_currentState.GetActions());
    }

    return actions;
}

---

Transition의 구현

앞서 State Machine은 Script와 쓰이는 일이 잦다고 했다. 그런 만큼 일반화(Generalize)가 잘 되어있어야 한다.

 

예를 들어, [적이 근처에 있음] <그리고> [내 체력이 낮음] 일때 트리거되는 Transition이 있다. 스크립트에는 기획자가 다음과 같이 써놓을 것이다.

<Trigger Condition>
[Enemy Nearby] AND [Low HP]
</Trigger Condition>

 

따라서 Transition의 Trigger여부를 체크하는데 사용되는 Condition을 일반화 해줘야 한다.

 

abstract class Condition
{
    public abstract bool Test();
}

class SomeCondition : Condition
{
    public override bool Test()
    {
        //조건에 맞게 값 반환
    }
}

class AndCondition : Condition
{
    private Condition _a;
    private Condition _b;
    public AndCondition(Condition a, Condition b)
    {
        _a = a;
        _b = b;
    }

    public override bool Test()
    {
        return _a.Test() && _b.Test();
    }
}

class Transition
{
    private Condition _condition;

    public bool IsTriggered()
    {
        return _condition.Test();
    }
}

 

혹은 이런 Condition 방식 대신 Decision Tree를 사용해서 여러 조건들을 조합할 수 있다. (이전 글 참고)

 

---

Hierachical FSM

때로는 하나의 State Machine으로 부족할 때가 있다. 이 때 여러 개의 State Machine을 사용할 수 있는데, 병렬적으로 State Machine들을 구성해도 모자랄 때가 있다. 이런 경우 FSM을 계층적으로 구성한다.

 

예를 들어, 로봇 청소기를 생각해보자.로봇 청소기는 [쓰레기 탐색], [쓰레기로 이동], [쓰레기 수거]의 세 가지 상태를 지닐 수 있다. 그런데 여기서 전원이 모자란 경우 최우선적으로 [충전]을 수행한다고 하자.

 

이 경우 전원을 체크하고 충전을 하는 상태가 청소를 하는 상태보다 우선순위가 높다. 이런 경우 상위 계층에 {[청소], [충전]} State Machine을 두고 [청소] 내부에 {[탐색],[이동],[수거]} State Machine을 둘 수 있다.

 

또한 Transition에는 Level 값을 두어 이 값이 0 이상이면 상위 레벨의 상태로 전이, 0이하이면 하위 레벨의 상태로 전이하는 방식으로 계층간 상태 이동을 할 수 있다.

---

참고 : Ian Millington, AI for GAMES 3rd edition, CRC press, [314~337p]