인공지능 - 유한 상태 기계(Finite state machine)

FSM은 기초적이지만, 아주 유용하게 쓰일 수 있다. 점점 행동 트리(Behavior tree)나 계획 시스템(Planning system)을 많이 쓰는 추세지만, 다음과 같은 특정 문제 해결을 위한 모델링으로써는 충분하다.

• 내부 상태에 따라 객체 동작이 바뀔 때

• 이런 상태가 그다지 많지 않은 선택지로 분명하게 구분될 수 있을 때

• 객체가 입력이나 이벤트에 따라 반응할 때

게임 AI로도 이용되지만, 입력 처리, 메뉴 화면 전환, 문자 해석, 네트워크 프로토콜, 비동기 동작 등을 구현하는 데에도 많이 사용된다.

---

유한 상태 기계(Finite state machine)

• 가질 수 있는 '상태'가 한정된다.

• 한 번에 '한 가지' 상태만 될 수 있다.

• '입력'이나 '이벤트'가 기계에 전달된다.

• 각 상태에는 입력에 따라 다음 상태로 바뀌는 '전이'가 있다.

스테이트 패턴은 유한상태기계를 구현하는 방법 중 하나이다. 순수하게 형식만 놓고 보면, '상태, 입력, 전이'가 FSM의 전부다.

상태 객체에 필드가 따로 없다면 정적 객체로 만들어 쓰면 된다.

상태 기계는 엄격하게 제한된 구조를 강제함으로써 복잡하게 얽히는 코드를 정리할 수 있게 해 준다. 그러나 FSM에는 미리 정해놓은 여러 상태와 현재 상태 하나, 하드코딩된 전이만 존재한다. 그러므로 유한상태기계를 인공지능같이 더 복잡한 곳에 적용하다보면 한계에 부딪히게 된다.


병행 상태 기계

 여러 상태를 각각 참조해서 사용한다. 예를 들어 플레이어 캐릭터가 무엇을 하고 있는가, 플레이어 캐릭터가 무엇을 들고 있는가 등으로 나눠서 병행으로 들고 있는 것이다.
 두 상태 기계가 서로 연관이 없다면 잘 맞는 방법이다. 그러나 서로 상호작용하기 시작하면 지저분해진다.


계층형 상태 기계
상태 기계를 객체지향 코드라고 생각하고, 상속으로 여러 상태가 코드를 공유하게끔 한다.
'땅 위에 있는' 상태기계를 상속받아 '걷기' 동작같은 고유 동작을 추가하면 된다.

---

푸시다운 오토마타

FSM에는 히스토리 개념이 없다는 문제가 있다. 현재 상태는 알 수 있지만 직전 상태가 무엇인지를 따로 저장하지 않기 때문에 이전 상태로 쉽게 돌아갈 수 없다.

FSM은 한 개의 상태를 포인터로 관리했다면, 푸시다운 오토마타에서는 상태를 스택으로 관리한다.
FSM에서 상태를 덮어썼다면, 푸시다운 오토마타에서는 부가적인 두 가지 명령이 더 있다. 하나는 새로운 상태를 스택에 푸시(Push)하는 것이고, 또 하나는 최상위 상태를 빼는(Pop) 것이다. 최상위 상태를 빼면 그 아래에 있던 상태가 최상위 상태가 될 것이다.