게임인공지능 4주차 - FSM

FSM (Finite State Machine)

프로그램 로직을 제어하고 구성하는 방법으로, AI 프로그램에 주로 사용된다.

 

- 기계가 최초 가동될 때 하나의 초기 상태(inital state)를 갖는다.

- 기계가 가질 수 있는 상태(state)의 개수는 유한(finite)하다.

- 기계는 한 순간에는 하나의 상태를 갖는다. 이것을 현 상태(current state)라고 한다.

- 하나의 입력에 의해 현재의 상태에서 다음의 상태로 바뀐다. 이것을 전이(transition)라고 한다.

- 새로운 상태 f(현재 상태, 입력 정보) f는 함수.

- 입력이 종료될 때 기계가 종료 상태(final state)가 된다면 입력이 제대로 인식되었다고 한다.

- 복수개의 종료 상태가 가능하다.

- 상태 전이도(state transition diagram)로 기계의 동작을 표현한다.

- Pac Man 등 초창기 게임부터 적용되었다.

 

State transition diagram

상태 전이도는 다음을 나타내는 다이어그램이다.

- 객체가 가질 수 있는 모든 상태 (states)

- 객체가 상태를 변경하는 이벤트 (전이/ transition)

- 전이가 발생하기 전에 충족되어야 하는 조건 (condition)

- 객체가 살아있는 동안 수행할 행동

 

FSM examples : switch

- Inital state : off

- Switch up : on

- Switch down : off

 

FSM examples : turnstile

new state = f(current state, input info)

- Locked - coin : Unlocked - Unlockes the turnstile so that the customer can push through.

- Locked - push : Locked

- Unlocked - coin : Unlocked

- Unlocked - push : Locked - When the customer has pushed through, locks the turnstile.

 

FSM examples

상태 : 경계(G), 탄약 찾기(FA), 회복약 찾기(FH), 공격(A)

- 적 발견, 적 처치, 생명력 저하, 탄약 부족

 

FSM 구현 방법

방법 #1. Ad hoc implementation : if~else 또는 switch 문장을 이용한 구현

방법 #2. Design Pattern : state 자체를 클래스로 추상화 하는 방법 (State design Pattern)

실습 진행 : 신호등 제작

#pragma once
#include <windows.h>
#include <iostream>
#include <string>
using namespace std;

class FSM
{
public:
	enum States
	{
		red,
		yellow,
		green
	};

	States m_state;

	FSM(States state = red) : m_state(red) {}

	void StartTrafficLight()
	{
		PrintState();

		switch (m_state) 
		{
		case red:
			Sleep(2000);
			m_state = green;
			break;

		case yellow:
			Sleep(1000);
			m_state = red;
			break;

		case green:
			Sleep(3000);
			m_state = yellow;
			break;
		}
	}

	void PrintState()
	{
		switch (m_state) 
		{
		case red:
			cout << "red\n";
			break;

		case yellow:
			cout << "yellow\n";
			break;

		case green:
			cout << "green\n";
			break;
		}
	}
};

 

#pragma once
#include <iostream>
#include <string>
#include <synchapi.h>
using namespace std;


//StateDesignPattern
class BaseGameEntity 
{
public:
	virtual void Update();
};

class GameEntity : public BaseGameEntity
{
private:
	State* m_state;
	int m_timer;

public:
	void Update();
	void ChangeState(State* pNewState);
	void SetTimer(int time) { m_timer = time; };
	int GetTimer() { return m_timer; };
};


class State
{
public:
private:
	static State* m_instance;

public:
	virtual State* GetInstance();
	virtual void Enter(BaseGameEntity* ge);
	virtual void Excute(BaseGameEntity* ge);
	virtual void Exit(BaseGameEntity* ge);
};


class RedState : public State
{
private:
	static State* m_instance;

public:
	static State* GetInstance();
	void Enter(GameEntity* ge);
	void Excute(GameEntity* ge);
	void Exit(GameEntity* ge);
};

class YellowState : public State
{
private:
	static State* m_instance;

public:
	static State* GetInstance();
	void Enter(GameEntity* ge);
	void Excute(GameEntity* ge);
	void Exit(GameEntity* ge);
};

class GreenState : public State
{
private:
	static State* m_instance;

public:
	static State* GetInstance();
	void Enter(GameEntity* ge);
	void Excute(GameEntity* ge);
	void Exit(GameEntity* ge);
};

 

#pragma once
#include "FSM2.h"
using namespace std;


void GameEntity::Update()
{
	m_state->Excute(this);
	Sleep(1000);
}

void GameEntity::ChangeState(State* pNewState)
{
	m_state->Exit(this);
	m_state = pNewState;
	m_state->Enter(this);
}

State* RedState::GetInstance()
{
	// 처음 실행일 경우
	if (!m_instance)
	{
		m_instance = new RedState();
	}

	return m_instance;
}
void RedState::Enter(GameEntity* ge)
{
	// 처음 실행일 경우
	if (!m_instance) 
	{
		m_instance = new RedState();
	}

	cout << "Red Enter\n";
}
void RedState::Excute(GameEntity* ge)
{
	cout << "Red Excute\n";

	// 시간 체크
	if (ge->GetTimer() > 3)
	{
		ge->SetTimer(0);
		ge->ChangeState(GreenState::GetInstance());
	}
	else
	{
		int time = ge->GetTimer();
		ge->SetTimer(time++);
	}
}
void RedState::Exit(GameEntity* ge)
{
	cout << "Red Exit\n";
}


State* YellowState::GetInstance()
{
	// 처음 실행일 경우
	if (!m_instance)
	{
		m_instance = new YellowState();
	}

	return m_instance;
}
void YellowState::Enter(GameEntity* ge)
{
	cout << "Yellow Enter\n";
}
void YellowState::Excute(GameEntity* ge)
{
	cout << "Yellow Excute\n";

	// 시간 체크
	if (ge->GetTimer() > 3)
	{
		ge->SetTimer(0);
		ge->ChangeState(RedState::GetInstance());
	}
	else
	{
		int time = ge->GetTimer();
		ge->SetTimer(time++);
	}
}
void YellowState::Exit(GameEntity* ge)
{
	cout << "Yellow Exit\n";
}


State* GreenState::GetInstance()
{
	// 처음 실행일 경우
	if (!m_instance)
	{
		m_instance = new GreenState();
	}

	return m_instance;
}
void GreenState::Enter(GameEntity* ge)
{
	cout << "Green Enter\n";
}

void GreenState::Excute(GameEntity* ge)
{
	cout << "Green Excute\n";

	// 시간 체크
	if (ge->GetTimer() > 3)
	{
		ge->SetTimer(0);
		ge->ChangeState(YellowState::GetInstance());
	}
	else
	{
		int time = ge->GetTimer();
		ge->SetTimer(time++);
	}
}
void GreenState::Exit(GameEntity* ge)
{
	cout << "Green Exit\n";
}

FSM의 장점

- 코딩이 빠르고 쉽다. (Fast and easy to code)

- 오류 수정이 용이하다. (Easy to correct errors)

- 계산 부담이 적다. (Light calculation)

- 직관적이다. (Intuitive)

- 유연하다. (Flexible)

FSM의 단점

이벤트가 추가될 때 상태의 수가 빠르게 증가할 수 있다.

비례적 표현을 처리하기가 어렵다.