18 мар. 2012 г.

Finite-state machine


Конечные автоматы (FSM, Finite-state machine) - системы основанные на правилах, которые можно применять к строго ограниченному набору состояний (ситуаций). Переход из одного состояния в другое определяется структурой конечного автомата. FSM относится к рефлексивным детерминированным методам, а значит можно полностью предсказать реакцию поведения. И как становится ясно из определения, состояния в конечных автоматах это системы основанные на правилах (RBS, которые мы рассмотрели в прошлой статье).
Давайте попробуем реализовать этот рефлексивный метод на практике. Для этого мы будем использовать все то, что проходили в прошлых уроках. Когда мы реализовывали Rule Based Systems, у нас "NPС'ы" убегали от курсора, в этой статье мы эту задачу усложним, реализуем салки. У нас будет:
  • определенное количество неигровых персонажей, которые будут убегать от догоняющего;
  • кто то будет являться догоняющим, но только один;
  • догоняющий может осалить убегающего и они поменяются ролями.
Немного "обмусолим" все в теории. Так как NPC может быть и догоняющим и убегающим, то они являются одним и тем же персонажем, просто с разным поведением. Можно было бы сделать, всего два состояния:
догоняющий <-> убегающий
но я посчитал удобнее сделать:
состояние инициализации догоняющего;
состояние инициализации убегающего;
состояние поиска ближайшего NPC и его преследование с попыткой осалить;
состояние проверки, есть ли "враг" рядом, если есть убегать;
состояние ожидания (чтобы у убегающих была фора, перед новым догоняющим).

Работу программы, которую мы создадим, можно посмотреть тут:

Приступим! Для начала дополним класс из прошлого урока под именем "CNpc". Мы объявим там новую переменную, которая будет обозначать догоняющий ли данный персонаж или нет.
class CNpc: public CPathUser
{
private:
...
bool m_bCatchState;
public:
void SetCatchState(bool bCatch)
{
m_bCatchState = bCatch;
}
bool IsCatcher()
{
return m_bCatchState;
}
...
};

Так же в классе "CNpc" изменим функцию RunFromEnemy, которая отвечает за то, как персонаж будет убегать от "врага". В прошлой версии NPC подходил к краю карты и останавливался, а нас сейчас это никак не устраивает, исправим это:
void CNpc::RunFromEnemy(vector2f EnemyPos)
{
vector2f Diff = normalize(GetPos() - EnemyPos);
if (GetPos() == EnemyPos)
Diff = vector2f(1.0f, 0.0f);

vector2f TravelPos = Diff*CHUNK_SIZE*2 + GetPos();
bool bGoodWay = SetWay(TravelPos);

// угол в радианах, около 11 градусов
float fAngle = 0.2f;

// если путь не установлен
while (!bGoodWay)
{
// поворачиваем вектор направления для движения
vector2f sDir = rotate_vector_2D(Diff, fAngle);
TravelPos = sDir*CHUNK_SIZE*2 + GetPos();

bGoodWay = SetWay(TravelPos);

// если путь опять не установлен
if (!bGoodWay)
{
// поворачиваем в другую сторону
sDir = rotate_vector_2D(Diff, -fAngle);
TravelPos = sDir*CHUNK_SIZE*2 + GetPos();
bGoodWay = SetWay(TravelPos);
}
// прибавляем ещё 11 градусов к углу
fAngle+=0.2f;
// если был сделан "круг", а путь так и не утсановлен
// выходим
if (fAngle > 6.283f)
return;
}
}

Теперь нам понадобится менеджер, который будет создавать, обновлять, очищать неигровых персонажей, а так же заниматься поиском ближайшего NPC, установкой догоняющего и другими общими их делами. Так как такой менеджер нам нужен один, то для реализации нам подойдет singleton (шаблон одиночка, который гарантирует, что у класса есть только один экземпляр, и предоставляет к нему глобальную точку доступа). Так как я пользуюсь библиотекой Boost, то шаблон одиночку я возьму из него.

class ManagerNPC : public boost::serialization::singleton<ManagerNPC>
{
public:
// функция добавления нового NPC
void AddNPC(CNpc* pNPC);
// возвращает кол-во NPSов
unsigned int GetCountNPC();
// возвращает NPC по номеру в массиве
CNpc* GetNPC(unsigned int ID);
// функция обновления всех NPSов
void Update(int iDeltaMilliSeconds);
// функция инициализации
void Init();
// функция освобождения
void Clear();
// поиск ближайшего NPC относительно заданного
CNpc* FindNearestNPC(CNpc* pNPC);
// возвращение догоняющего
CNpc* GetCatcher();
// может ли один NPC осалить другого
bool IsCatch(CNpc* pFrom, CNpc* pTo);
// установка нового догоняющего
void SetCatcher(CNpc* pNPC);
protected:
private:
// указатель на догоняющего
CNpc* m_pCatcher;
// массив NPCов
std::vector<CNpc*> m_aNpc;
};

Рассмотрим функции класса подробнее:
// функция добавления нового NPC
void ManagerNPC::AddNPC(CNpc* pNPC)
{
m_aNpc.push_back(pNPC);
}

// возвращает NPC по номеру в массиве
unsigned int ManagerNPC::GetCountNPC()
{
return m_aNpc.size();
}

// возвращает NPC по номеру в массиве
CNpc* ManagerNPC::GetNPC(unsigned int ID)
{
if (ID < GetCountNPC())
return m_aNpc[ID];
return NULL;
}

// функция обновления всех NPSов
void ManagerNPC::Update(int iDeltaMilliSeconds)
{
for (unsigned int i = 0; i < GetCountNPC(); i++)
{
GetNPC(i)->Update(iDeltaMilliSeconds);
}
}

// функция инициализации
void ManagerNPC::Init()
{
m_pCatcher = NULL;
}

// функция освобождения
void ManagerNPC::Clear()
{
for (unsigned int i = 0; i < m_aNpc.size(); i++)
{
if (m_aNpc[i])
{
delete m_aNpc[i];
m_aNpc[i] = NULL;
}
}
m_aNpc.clear();
}

// поиск ближайшего NPC относительно заданного
CNpc* ManagerNPC::FindNearestNPC(CNpc* pNPC)
{
// если у менеджера вообще нет NPCов
if (GetCountNPC() == 0)
return NULL;

// позиция NPC, относительно которой надо найти другого ближайшего
vector2f Pos = pNPC->GetPos();
// указатель на ближайшего NPC
CNpc* pNearestNPC = NULL;
// расстояние до него
float fMinLen = 0;

// найдем самого первого NPC, который не является заданным
for (unsigned int i = 0; i < GetCountNPC(); i++)
{
if (GetNPC(i) != pNPC)
{
// предположим, что она самый ближайший
pNearestNPC = GetNPC(i);
fMinLen = length(pNearestNPC->GetPos() - Pos);
break;
}
}

// пройдем по всем NPCам
for (unsigned int i = 0; i < GetCountNPC(); i++)
{
// если это не заданный
if (GetNPC(i) != pNPC)
{
// вычислим вектор между ними
vector2f Diff = GetNPC(i)->GetPos() - Pos;
// вычислим расстоянием между ними
float fLen = length(Diff);
// если оно меньше, прошлого
if (fLen < fMinLen)
{
// то на данный момент он ближайший
pNearestNPC = GetNPC(i);
fMinLen = fLen;
}
}
}
return pNearestNPC;
}

// возвращение догоняющего
CNpc* ManagerNPC::GetCatcher()
{
// так как у нас NPCы не удаляются на протяжении работы программы,
// то можемпросто хранить указатель на догоняющего,
// иначе бы искали в массиве NPCa с флагом догоняющего
return m_pCatcher;
}

// может ли один NPC осалить другого
bool ManagerNPC::IsCatch(CNpc* pFrom, CNpc* pTo)
{
// вычислим расстояние между ними и сверим его с расстоянием,
// при котором можно осалить
// #define CATCH_RADIUS CHUNK_SIZE*1.1f
if (length(pFrom->GetPos()-pTo->GetPos()) > CATCH_RADIUS)
return false;
return true;
}

// установка нового догоняющего
void ManagerNPC::SetCatcher(CNpc* pNPC)
{
// если догоняющий уже есть
if (m_pCatcher)
// меняем ему флаг
m_pCatcher->SetCatchState(false);
// устанавливаем флаг новому догоняющему
pNPC->SetCatchState(true);
// запоминаем нового догоняющего
m_pCatcher = pNPC;
}

Вызов функций моего класса одиночки выглядит не очень приятно:
ManagerNPC::get_mutable_instance().Init();
// поэтому я заменю её с помощью define
#define MANAGER_NPC ManagerNPC::get_mutable_instance()
// а теперь это выглядит так
MANAGER_NPC.Init();

Так, у нас есть класс NPC и класс менеджера неигровых персонажей. Так как вся логика ИИ у нас будет в скриптах (как и в прошлом уроке), то расшарим наши функции для LUA.

CNpc* FindNearestNPC(CNpc* pNPC)
{
return MANAGER_NPC.FindNearestNPC(pNPC);
}

CNpc* GetCatcher()
{
return MANAGER_NPC.GetCatcher();
}

bool IsCatch(CNpc* pFrom, CNpc* pTo)
{
return MANAGER_NPC.IsCatch(pFrom, pTo);
}

void SetCatcher(CNpc* pNPC)
{
return MANAGER_NPC.SetCatcher(pNPC);
}

void LuaShareNPC(lua_State* pLua)
{
using namespace luabind;
module(pLua)
[
class_<CNpc>("Npc")
.def("RunFromEnemy", &CNpc::RunFromEnemy )
.def("SetScriptName", &CNpc::SetScriptName )
.def("SetPauseTime", &CNpc::SetPauseTime )
.def("IsSeeEnemy", &CNpc::IsSeeEnemy )
.def("SetWay", &CNpc::SetWay )
.def("SetSpeed", &CNpc::SetSpeed )
.def("GetPos", &CNpc::GetPos ),

class_<vector2f>("vec2"),

def("FindNearestNPC", &FindNearestNPC),
def("GetCatcher", &GetCatcher),
def("IsCatch", &IsCatch),
def("SetCatcher", &SetCatcher)
];
}

Все! Теперь у нас есть все, чтобы приступить к реализации игровой логики для FSM.
-- состояние инициализации убегающего
function Escapee_Init(self)
-- устанавливаем паузу между апдейтами
self:SetPauseTime(300)
-- устанавливаем скорость
self:SetSpeed(0.1)
-- устанавливаем имя скрипта
self:SetScriptName("Escapee_Go")
end

-- состояние инициализации догоняющего
function Catcher_Init(self)
-- устанавливаем паузу между апдейтами
self:SetPauseTime(3000)
-- устанавливаем скорость
self:SetSpeed(0.12)
-- устанавливаем имя скрипта
self:SetScriptName("Catcher_Wait")
end

-- состояние проверки, есть ли "враг" рядом, если есть убегать
function Escapee_Go(self)
-- получаем догоняющего
catcher = GetCatcher()
-- если он есть
if catcher ~= nil then
-- если мы его видим
if self:IsSeeEnemy(catcher:GetPos()) then
-- убегаем от него
self:RunFromEnemy(catcher:GetPos());
end
end
end

-- состояние поиска ближайшего NPC и его преследование с попыткой осалить
function Catcher_Go(self)
-- ищем ближайшего
npc = FindNearestNPC(self)
-- если он есть
if npc ~= nil then
-- двигаемся к нему
self:SetWay(npc:GetPos())
-- если осалили
if IsCatch(self, npc) then
-- ставим себе новый скрипт
self:SetScriptName("Escapee_Init")
-- ставим ему новый скрипт
npc:SetScriptName("Catcher_Init")
-- указываем нового догоняющего
SetCatcher(npc)
end
end
end

-- состояние ожидания (чтобы у убегающих была фора, перед новым догоняющим)
function Catcher_Wait(self)
-- устанавливаем паузу между апдейтами
self:SetPauseTime(100)
-- устанавливаем имя скрипта
self:SetScriptName("Catcher_Go")
end

Нам осталось использовать все то, что мы написали выше и увидеть результат.

// НАЧАЛО ПРОГРАММЫ
// расшариваем функции для LUA
LuaShareNPC(myLua);
// инициализация менеджера NPC
MANAGER_NPC.Init();

// создаем убегающих
for (int x = 0; x < 20; x++)
{
CNpc* pNewNPC = new CNpc();
int randomX = (int)rand()%(WIDTH);
int randomY = (int)rand()%(HEIGHT);
pNewNPC->SetPos(vector2f(float(randomX),float(randomY)));
pNewNPC->SetScriptName("Escapee_Init");
MANAGER_NPC.AddNPC(pNewNPC);
}

// среди них случайным образом одного делаем догоняющим
int RandomID = (int)rand()%(MANAGER_NPC.GetCountNPC()-1);
CNpc* RandomNPC = MANAGER_NPC.GetNPC(RandomID);
MANAGER_NPC.SetCatcher(RandomNPC);
RandomNPC->SetScriptName("Catcher_Init");
...
// ЦИКЛ
// апдейтим
MANAGER_NPC.Update(int(dwDT));
...
// КОНЕЦ ПРОГРАММЫ
// освобождение менеджера NPC
MANAGER_NPC.Clear();


Конечные автоматы (finite state machine) - технология, которая несмотря на свою простоту (а мы в этом убедились) оказывается очень мощной и применяется во многих играх.