Машина состояний

Представляю вашему вниманию перевод статьи «Finite State Machines». Сегодня поговорим о конечных машинах состояний (finite state mashine). На русском языке более распространено название «конечные автоматы». Машина состояний это основа искусственного интеллекта (AI) большинства игр, особенно RPG, платформеров, RTS.

Что это такое и для чего нужно?

Машина состояний может использоваться, чтобы определить поведение игрового объекта, которое основывается на определенных условиях. По сути, она дает иллюзию разумности этого объекта. Кодирование машины состояний – это простой вопрос. Существуют многочисленные реализации машины состояний и понятно, что единственно правильного решения нет.


Для начала посмотрим на простой, но потенциально проблематичный подход.

public function update() : void
{
	if( health < 0 )
	{
		changeState( DIE_STATE );
	}
 
	switch( currentState )
	{
		case IDLE_STATE:
			patrol();
 
			if( isEnemySighted )
			{
				changeState( CHASE_STATE );
			}
 
			break;
 
		case CHASE_STATE:
			chaseEnemy();
 
			if( isEnemyInRange )
			{
				if( health < 30 && mana > 20 )
				{
					castHeal();
				}
				else
				{
					attackEnemy();
				}
			}
 
			break;
 
		case DIE_STATE:
			if( isDeathAnimationComplete )
			{
				removeEntity();
			}
			else
			{
				playDeathAnimation();
			}
 
			break;
	}
 
}

Как видите, здесь у нас есть конструкция switch … case и несколько условных операторов if, которые служат для переключения основных поведений объекта. Проблемы с таким подходом начнутся, когда будет необходимо ввести множество состояний, условий и переходов. Представьте себе, что у какого-нибудь монстра может быть более десяти и нужно их условия все держать в голове, чтобы не ошибиться в создании условий для нового поведения, т.к. будут трудности с переключением в ожидаемое поведение.

Проектирование состояний.

Лучшая реализация расширяемой машины состояний, которую я нашел – это использование так называемого шаблона состояний. При таком подходе мы добавляем правила для перехода в это состояние в самом состоянии.

Нам нужно, чтобы каждое состояние имело одни и те же методы, для его использования в конечном автомате. Это методы введения состояния в действие, выполнения и выхода из этого состояния.

Вот интерфейс состояния:

public interface IState extends IEventDispatcher
{
	function setEntity( a_entity:* ) : void;
	function getEntity() : *;
 
	function enter():void;
	function execute():void;
	function exit():void;
}

Как видите, структура интерфейса предельно проста. Состояние содержит ссылку на объект, над которым будут выполняться операции состояния. Ниже пример класса одного из состояний.

public class PatrolState extends EventDispatcher implements IState
{
public function setEntity( a_entity:* ) : void
{
	if( !(a_entity is Unit) )
	{
		throw new Error( " a_entity must be of type Unit!" );
	}
	m_entity = a_entity;
}
 
public function getEntity() : *
{
	return m_entity;
}
 
public function enter():void
{
	// set up patrol path and steering behaviors
}
 
public function execute():void
{
	// if enemy is close, set state to chase state
	// else continue patrolling
}
 
public function exit():void
{
	// clean up patrol paths
	// remove steering behaviors
}
 
private var m_mine:Mine;
private var m_base:Building;
private var m_entity:Harvester;
 
}

Теперь, когда у нас есть состояние, мы можем разнообразить нашу систему множеством состояний и создать конечный автомат многократного использования, который будет переключать/обновлять состояния. Вот интерфейс автомата:

public class StateMachine
{
public function StateMachine( a_owner:Entity, a_currentState:IState = null, a_globalState:IState = null )
 
public function update() : void
 
public function dispose() : void
 
public function changeState( newState:IState ):void
 
public function changeGlobalState( newState:IState ):void
 
public function revertToPreviousState() : void
}

В моей реализации в добавок к изменения локальных состояний объекта (changeState) я создал возможность переключения некоего глобального состояния (changeGlobalState). (Примечание переводчика – тут видимо идет речь о том, что можно представить следующим примером: если патрулирующий юнит заметил вражеского юнита, то он может включить глобальное состояние «тревога» и все дружественные юниты будут двигаться к месту обнаружения, чтобы атаковать этого вражеского юнита). Также я сохранил ссылку на предыдущее состояние для того, чтобы была возможность введения «временного» состояния, после которого объект переключается на «основное». Опять же если патрулирующий юнит обнаружил вражеского, он переходит в состояние атаки, а после того как враг будет мертв, он может опять вернуться к патрулированию.

Вот быстрый пример, чтобы показать конечный автомат в действии. Возможно, недостаточно хорошо (примечание переводчика - в оригинале shitty :)), но я очень спешил :)

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/08/20/FSM.swf, 550, 425[/SWF]