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) - технология, которая несмотря на свою простоту (а мы в этом убедились) оказывается очень мощной и применяется во многих играх.

<< Назад | Оглавление | Вперед >>