Gurugail Main/FSM
Main

FSM

인공지능을 열심히 공부하고?, 첫 회사에서 가상 공간에서의 강아지에 대한 행동 패턴을 인공지능으로 구현하는 프로젝트가 있었는데, 처음에는 교배 등을 고려하여 나름 멋지게 설계하여 유전자 알고리즘으로 시작하였으나 최종 결과물은 다름아닌 FSM 으로 마무리 한 기억이 있다. 강아지 행동을 표출할 때 인공지능 학습에 있어서의 오류로 나타나는 부자연스러움을 극복하지 못한 데 기인한다. 명료한 FSM은 사실 인공지능은 아니지만, 기획자가 의도된대로 구성할 수 있기에, 두루 두루 많이 사용되고 있다. 한 때 퀘이크(Quake) 라는 유명한 게임도 HFSM (Hierarchical FSM)을 기반으로 개발한 것이다.

I. FSM (Finite State Machine) 이란? ...

  • FSM의 개념

FSM이라는 용어 그대로, 유한한 개수의 상태들로 구성된 기계를 말한다. 여기서 상태(state)라는 말은 하나의 조건이라고 생각하면 된다. 자판기에서부터 게임안에서의 몬스터(monster)까지 그냥 시스템이라고 생각하자. 놀라운 사실은, 그러한 대부분의 시스템들이 유한한 상태들로 표현될 수 있다라는 것이다. FSM을 더 간단히 설명하면, 상태제어 알고리즘이라고 간단히 말할 수 있다. FSM의 알고리즘 자체는 간단하기는 하지만, 상태라는 말을 결코 간과해서는 안된다. 거의 모든 시스템들이 상태들로 표현될 수 있다. 그렇기 때문에 FSM은 시스템을 제어하는 알고리즘으로 간단하면서 가장 많이 사용된다.

FSM은 하나의 입력을 받고 그에 의거해서 현재 상태로부터 다른 어떤 상태로 전이(transition)한다. 예를 들어, 문을 하나의 상태 기계라고 하자. 문의 상태가 "열림"과 "닫힘" 상태가 있으며, "키 사용"이라는 입력이 들어가면 상태변화가 일어나는 것이다. 문이라는 시스템을 간단히 FSM으로 표현해보자.

  • 게임에서의 FSM 사용

FSM을 컴퓨터 게임의 AI에 적용하려면 어떻게 해야 할까? 그 유명한 퀘이크(Quake)도 NPC(Non Player Character)의 행동패턴을 제어하는데 FSM을 사용하였으며, Half life는 Hierarchical FSM(HFSM)을 사용하였다. FSM을 여러 층(Layer)으로 사용한 것이 HFSM이라고 생가하면 된다. 또는 NPC의 감정을 흉내내기 위한 도구가 될 수도 있다. 이해를 돕기 위해 RPG 게임의 몬스터(monster)의 감정을 FSM로 표현해 보자.

[1] FSM(monster)의 상태 결정 - 대단히 중요한 단계이며, 신중해야 한다. 몬스터(monster)의 감정은 광분, 분노, 흥분, 불쾌, 보통이라는 다섯 가지의 상태
[2] 다음은 입력 정의 - 상태 변화를 일으키게 하는 입력, 시스템에 줄 수 있는 입력을 결정하는 단계이다. 플레이어의 등장, 플레이어의 공격, 플레이어 떠남, 몬스터 다침, 몬스터 치료됨의 입력

이를 이용하여 상태 전이 과정을 도표로 그린것이 아래 그림이다. 즉, 몬스터(monster)라는 시스템을 FSM으로 표기한 것이다.

그림. 몬스터(monster)의 FSM

FSM의 기본적인 아이디어나 알고리즘은 간단하지만, 물론 FSM의 변종(^^;)이 많이 있다. 오히려 알고리즘이 너무 간단해, 이것도 알고리즘에 낄 수 있는가라는 생각이 들 때도 있다. 그렇다하더라도 FSM은 시스템 제어에 근본이 되는 알고리즘이다.

II. FSM 주요 특징 (다음의 아이디어들을 통합시킨다면 FSM이 더 쉽고 강인하게 적용할 수 있을 것임, Game Programming 468p 인용)

  • 상태 기계는 읽기 쉬어야 한다.
  • 상태 기계는 디버그하기 쉬어야 한다.
  • 상태 기계는 만들기 쉽고 프로토타입하기 쉬어야 한다.
  • 상태 기계에는 다른 게임 객체들과 통신할 수 있는 방법이 있어야 한다.
  • 상태 기계에는 반복되는 코드를 줄이기 위한 전역적 이벤트 응답이 있어야 한다.
  • 상태 기계에는 이벤트 타이머를 둘 수 있는 방법이 있어야 한다.
  • 상태 기계는 디버깅을 위해 투명한 모니터링과 모든 이벤트들과 상태 전이에 대한 로깅을 허용해야 한다.
  • 상태들은 처음 상태에 들어 갔을 때 트수한 코드의 실행을 허용해야 한다.
  • 상태들은 상태가 종료할 때 특수한 코드의 실행을 허용해야 한다.

III. 참조