[Algorithm] Finite State Machine

유한 상태 기계 (Finite State Machine)

• 유한한 개수의 상태(state)를 가지는 오토마타.
• 한 번에는 오로지 하나의 상태만을 가지며, 현재 상태에서 어떠한 사건(event)이 발생하면 다른 상태로 전이된다.
• 게임 AI를 구현하기 위해 사용된다.

알고리즘

다양한 구현 방법이 있겠지만…! 이건 유튜브에서 본…!
관련 디자인 패턴 : state design pattern

#include<iostream>
#include<list>
using namespace std;

class FSMState // 상태
{
	virtual void onEnter();  // 칼을 꺼낸다 (시작 시)
	virtual void onUpdate();  // 공격한다 (계속)
	virtual void onExit();  // 칼을 넣는다 (종료 시)
	list<FSMTransition> transitions; // 상태들 자신의 내부에 전이 조건을 내장
};

class FSMTransition // 전이
{
	virtual bool isValid();	  // 전이 조건 만족 시 true 리턴
	virtual FSMState* getNextState();  // 전이 조건 만족 시 전이해야할 State를 리턴
	virtual void onTransition();  // 전이가 이루어 질때 필요한 행동 로직 실행. FSMState()의 onEnter()와 유사
};

class FiniteStateMachine
{
	void update(); // 
	list<FSMState> states;  // 모든 상태들
	FSMState* initialState;  // 초기 상태
	FSMState* activeState;	// 현재 상태
};

(1). isValid()에서 유효한 전이 T가 발견
(2). 현재 activeState의 onExit() 실행
(3). T의 getNextState()로 다음 State를 activeState 넣는다
(4). activeState의 onEnter() 실행
(5). activeState의 onUpdate() 실행

단점 :

• 상태가 많아지면 전이도 많아져서 새로운 상태의 추가 및 관리하기 어려워짐.

이러한 단점을 보완하는

• HFSM (Hierarchical Finite-State Machines)
  상태(state) 그룹 사이의 전이

• Behavior Tree
  행동을 정의하는 Behavior 노드로 이루어진 트리 자료구조