[AI] FSM (Finite State Machine : 유한 상태 기계)

AI ( Artificial Intelligence ) 란, 인공지능으로 인간의 학습능력, 추론능력, 지각능력, 이해능력 등을 컴퓨터 프로그램으로 실현한 것이다.

FSM 은 인공지능 기법중 하나로 유한한 개수의 상태를 가지는 추상기계이다.

한번에 보통 하나의 상태만을 가지며 현재 상태(Current State)란 임의로 주어진 시간의 상태를 말한다. 

FSM은 어떤 이벤트에 의해 한 상태에서 다른 상태로 변화할 수 있으며 이를 전이라고 한다.

현재 상태로부터 가능한 전이 상태와 이러한 전이를 유발하는 조건의 집합으로 정의된다.

프로그래밍에서 FSM은 실행 시점에서 현재 상태에 기반해 객체의 코드 일부를 선택적으로 수행하므로써 객체의 행동을 제어하는 용도로 쓰인다. 이론적으로는 어떠한 객체의 제어에도 쓰일 수 있으나 AI 프로그래밍에 더 유용하다. 

왜냐하면 복잡한 행동을 더 작고 간단하게 할 수 있고, AI 행동과 외부 사건등을 동기화 하는데 유용하다.

또한, 신경망이나 유전 알고리즘 등 다른 AI 기법들에 비해 디버깅이나 조율이 쉽다. FSM 에서는 주어진 상태와 입력 이벤트들에 대한 상태 전이가 미리 정의되어 있다.

FSM의 특징을 정리해보면 다음과 같다.

- 유한한 개수의 상태를 가진다.

- 외부로부터 입력을 받아들인다.

- 시간의 흐름에 따라 자신의 상태를 변화시킬 수 있다.

- 외부에서 입력받았을 때 특정한 규칙에 따라 자신의 상태를 변화시킬 수 있다.

FSM의 예를 들어보자.

A. 비 선공 몬스터

일정 범위내에 플레이어가 없다면 몬스터는 그저 대기 혹은 배회 한다. 

이때 일정 범위 내에 플레이어가 들어온다면 몬스터는 인식 상태로 바뀌고, 

플레이어가 먼저 공격하면 공격한다. 

만약 플레이어가 일정 범위내에서 다시 사라진다면 몬스터는 인식을 풀고 대기, 배회로 상태가 바뀐다.

B. 오락실 게임

동전을 넣기 전까지 게임화면은 준비상태이다. 동전을 넣으면 게임 진행 상태가 된다. 

그러다 게임에서 죽으면, 동전을 입력할 것인지를 묻는 대기 상태가 나타난다. 

여기서 동전을 넣으면 게임 진행 상태로 돌아가고, 넣지 않으면 다시 게임 대기 상태로 돌아간다.

FSM 은 다른 AI 기법들에 비해 구현이 쉽고, 오류 수정이 용이하다.

또한 계산 부담이 없고, 직관적이다.

하지만 구조가 단순하기 때문에 예측이 쉽다는 단점이 있다.

코드를 보자. ( GPG를 참조하면서 하다가 나중에 제멋대로 가버렸다 ... )

cState는 추상클래스이고, 

cFSM은 cState를 현재 상태와 새로운 상태로 포함하고 있다. 

cGameCenter는 cFSM을 상속받고 있다. 

<cState.h> #pragma once class cState { public: cState(void) {}; virtual ~cState(void) {}; // 시작 virtual void BeginState(void) = 0; // 상태 virtual void DoingState(void) = 0; // 종료 virtual void EndState(void) = 0; }; <cState.cpp> #include "cState.h" <cFSM.h> #pragma once #include <iostream> using namespace std; class cState; class cFSM { protected: cState* m_pCurrentState; cState* m_pNewState; public: cFSM(void); virtual ~cFSM(void); // 업데이트 virtual void Update(void); // 현재 상태 bool IsState(cState& State); // 상태 전이 bool StateTransition(cState& NewState); }; <cFSM.cpp> #include "cState.h" #include "cFSM.h" cFSM::cFSM(void) :m_pCurrentState(NULL),m_pNewState(NULL) { } cFSM::~cFSM(void) { } // 업데이트 void cFSM::Update(void) { if(m_pNewState != NULL) { // 현재 상태 끝내기 m_pCurrentState->EndState(); // 새로운 상태를 현재 상태로 m_pCurrentState = m_pNewState; m_pNewState = NULL; // 현재 상태 시작 m_pCurrentState->BeginState(); } // 현재 상태 진행중 m_pCurrentState->DoingState(); } // 현재 상태 bool cFSM::IsState(cState& State) { if(m_pCurrentState == &State) { return true; } return false; } // 상태 전이 bool cFSM::StateTransition(cState& NewState) { // 상태 연결 m_pNewState = &NewState; return true; } <cGameCenter.h> #pragma once #include <iostream> #include <Windows.h> using namespace std; #include "cFSM.h" // 게임 상태 enum GAME_STATE { // 준비 GS_READY = 0, // 게임 중 GS_DOING, // 게임 대기 GS_STAND, // 게임 종료 GS_GAMEOVER, GS_END, }; class cGameCenter : public cFSM { protected: // 게임 상태 cState* m_pState[GS_END]; // 현재 상태 int m_nCurState; public: cGameCenter(void) {}; ~cGameCenter(void) {}; // 초기화 void Init(void); // 업데이트 void Update(void); // 상태 진행 void DoingState(void); }; <cGameCenter.cpp> #include "cState.h" #include "cGameCenter.h" // 초기화 void cGameCenter::Init(void) { for(int i=0;i<GS_END;i++) { m_pState[i] = NULL; } // 현재 상태를 준비 상태로 초기화한다. m_pCurrentState = m_pState[GS_READY]; m_nCurState = GS_READY; } // 업데이트 void cGameCenter::Update(void) { while(true) { // 준비 상태일 때 동전이 들어온다면, if((GetKeyState(VK_UP) & 0x8000) && m_nCurState != GS_DOING) { m_nCurState = GS_DOING; } if(GetKeyState(VK_DOWN) & 0x8000) { cout << "게임이 종료됩니다." << endl; Sleep(1000); break; } // 상태 진행 DoingState(); } } // 상태 진행 void cGameCenter::DoingState(void) { switch(m_nCurState) { case GS_READY: { cout << "준비중 : 동전을 넣으세요 !! " << endl; } break; case GS_DOING: { static int i = 0; cout << "게임 중 입니다." << endl; i++; if(i > 10000) { m_nCurState = GS_STAND; i = 0; } } break; case GS_STAND: { static int nNum = 0; cout << "게임 대기 : 동전을 넣으세요 " << nNum << endl; nNum++; // 대기 시간 까지 동전을 넣지 않으면 // 다시 준비 상태로 간다. if(nNum > 10000) { m_nCurState = GS_READY; } } break; } }

---

[참고] GPG 3.3 함수 포인터 기반의 내장형 유한상태기계