Scripter's Blog | AI programming

Life is Feudal: Forest Village

noreply@blogger.com (Scripter) — Sat, 25 Jun 2016 10:42:00 +0000

Life is Feudal: Forest Village is a feature-rich, town building simulator strategy game with engaging survival aspects. Lead your people: a small group of refugees who were forced to start again on an unknown island.

Terraform land and build houses, pastures, orchards, farms, windmills and many other buildings. Forage in the forest, hunt for prey, grow crops and domestic animals for food. Stock up with enough firewood, charcoal and warm clothes to survive an upcoming harsh winter. Lack of certain vitamins in villagers’ rations may lead to disease and can even totally wipe out your village!

You can rule your village from a birdseye view or possess one of your villagers to perform tasks in a first person view to speed things up or just to wander around.

Here some of the most exciting features:
Advanced farming system. Different crops and fruit trees require different amount of moisture, man labour and time to ripen ready for harvest. Your pastures and hens require the attention of hunters in order to protect them from forest predators.

Real time weather and seasons system. Drought will force your farmers to water your crops and rainy days will force them to dig trenches. Winter will require firewood and warm clothes for your villagers.

Diseases, food rations and vitamins. Diseases will spread faster in cold weather, especially if your villagers lack warm clothes or their ration is too monotonous and lacks certain vitamins. Try to stock all types of food possible (meat, fish, bread, vegetables and fruits).

Switch between birdseye and first person views. You can play your game in a birdseye view and issue strategic orders or you can posses a villager and play from a first person perspective performing everyday tasks along with your villagers.

Dynamic ecosystem. Villagers that are constantly walking in the surrounding woods will scare wildlife deeper into forest. Excessive farming or woodcutting can lead to flora and fauna extinction thus lowering the flow of meat, hides, mushrooms, berries and medical herbs to your stocks.

Terraforming and pavement. Terraform land around your settlement to enable construction of larger buildings. Pave roads to speed up the movement of your villagers and thus improve the economy of your settlement.

Morale and increasing population Keep your villagers happy and their families will grow, granted their needs are being met. :) Living in overcrowded hostels, always in need and witnessing recent deaths of neighboring villagers will reduce their morale and their productivity.

Disasters. Lightning will hit your tall buildings that are standing on hilltops. Tornados can leave a devastating trail of destruction across your settlement. Earthquakes can destroy your houses and even topple trees. Are your sure that you’re ready to face those challenges?

Mod friendly. Our game is designed to be modder friendly. Game modders will have access to AI, animations, task and resource management, navigation, sounds and many other game systems. Those systems and assets can be completely changed through game scripts written in LUA.

Balloon Shooter

noreply@blogger.com (Scripter) — Sun, 03 Aug 2014 00:21:00 +0000

Balloon Shooter - это новая игра в жанре тайм-киллера.

Особенности проекта:
- уничтожайте шары в двух режимах игры
- собирайте разнообразные бонусы
- смена дня и ночи

Google Play: скачать

Устанавливайте новые рекорды!

Finite-state machine

noreply@blogger.com (Scripter) — Sun, 18 Mar 2012 16:23:00 +0000

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

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

Rule Based Systems

noreply@blogger.com (Scripter) — Tue, 07 Jun 2011 17:28:00 +0000

Rule Based Systems (cистема, основанная на правилах) - это система контроля не игровых персонажей (Non-Player Character — NPC), состоящая из ситуаций и действий (ЕСЛИ - ТО). RBS относится к рефлексивным детерминированным методам, а значит можно полностью предсказать реакцию поведения. Это, пожалуй, самый простой способ реализации ИИ в играх. Так как он прост, то и задача, с которой он должен справляться, тоже должна быть проста.

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

Давайте сформулируем очень простую задачу:

Нашими NPC будут квадратики.
Врагом NPC будет курсор.
Как только враг будет в поле зрения, NPC будет убегать от него, пока не упрется в преграду.

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

Перейдем к реализации. Так как мы будем использовать LUA для скриптинга, то давайте с ним ознакомимся. Его исходники можно скачать тут, так же нам потребуется LuaBind. Я не буду рассказывать, как их собирать и подключать, это можно найти на других сайтах, поэтому перейдем сразу к делу.


   // создаем состояние lua
   lua_State* pLua = lua_open();
   // инициализация luabind
   luabind::open(pLua);
   // функция, которая открывает все стандартные библиотеки
   luaL_openlibs(pLua);
   // если ошибка при создании
   if (NULL == pLua)  
   {  
      printf("Error Initializing lua\n");  
      return;  
   } 
   // загружает указанный файл
   luaL_dofile(pLua, "ai.lua");
   // эта функция расшаривает функции и классы С++,
   // которые мы будем использовать в скрипте
   LuaShareNPC(pLua);

Функцию "LuaShareNPC", которую мы использовали выше, мы рассмотрим позже. Так же не забудьте в конце программы, использовать функцию, которая закроет состояние lua:

lua_close(pLua);

Создадим новый класс "CNpc", который мы унаследуем от "CPathUser" (этот класс отвечает за перемещение, смотрите его реализацию в предыдущих статьях).

class CNpc: public CPathUser
{
private:
   // необходимое время для паузы
   int m_iPouseNeed;
   // сколько времени уже прошло с последнего апдейта
   int m_iPouseNow;
   // имя скрипта
   std::string m_sScriptName;
public:
   CNpc(void); 
   ~CNpc(void);
   // установка имени скрипта
   void SetScriptName(std::string sScriptName);
   // установка времени для паузы между обновлением AI
   void SetPauseTime(int iMilliSecond);
   // видим ли врага
   bool IsSeeEnemy(vector2f Target);
   // рассчитываем путь, чтобы убежать от врага
   void RunFromEnemy(vector2f EnemyPos);
   // функция обновления
   void Update(int iDeltaMilliSeconds);
};

Конструктор, деструктор, установка времени для паузы и имени скрипта.

CNpc::CNpc()
{
   m_iPouseNow = 0;
   m_iPouseNeed = 1000;
}

CNpc::~CNpc()
{
}

void CNpc::SetPauseTime(int iMilliSecond)
{
   m_iPouseNeed = iMilliSecond;
}

void CNpc::SetScriptName(std::string sScriptName)
{
   m_sScriptName = sScriptName;
}

Следующая функция возвращает true, если враг виден. VIEW_RADIUS - это радиус взора нашего NPC, устанавливаем значение этого параметра по своему желанию (у меня он равен 200).

bool CNpc::IsSeeEnemy(vector2f EnemyPos) 
{ 
   vector2f Diff = GetPos() - EnemyPos;
   float Len = length(Diff);  
   if (Len < VIEW_RADIUS)
      return true;
   return false;
}

Функция задания нового пути, следуя по которому, мы будем убегать от врага.

void CNpc::RunFromEnemy(vector2f EnemyPos) 
{ 
   vector2f Diff = normalize(GetPos() - EnemyPos);
   SetWay(Diff*CHUNK_SIZE*2 + GetPos());
}

Функция обновления нашего NPC. Обратите внимание, что скрипт срабатывает не каждый кадр, а в зависимости от параметра m_iPouseNeed, значение которому мы устанавливаем опять же по желанию (у меня это 300 миллисекунд). Таким способом мы уменьшаем нагрузку на наш компьютер и создаем иллюзию того, что NPC "думает" перед принятием решения. При такой реализации нам придется функцию передвижения использовать не в скрипте (иначе он бы у нас ходил раз в 300 миллисекунд).

void CNpc::Update(int iDeltaMilliSeconds)
{
   m_iPouseNow += iDeltaMilliSeconds;
   if (m_iPouseNow > m_iPouseNeed)
   {
      if (myLua)
         // вызываем функцию из скрипта
         luabind::call_function< void >(myLua, m_sScriptName.c_str(), this, CurPos);
         m_iPouseNow = 0;
   }
   // передвигаемся
   Move(iDeltaMilliSeconds);
}

Давайте рассмотрим функцию, которая расшаривает классы и функции для их использования в скриптах. Так как задача у нас простая, то нам потребуется всего две функции класса "CNpc", и сам класс "vector2f".


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

      class_< vector2f >("vec2")
   ];
}

И наконец, наш скрипт. Он очень прост: если мы видим врага (ситуация), находим новый путь (действие), чтобы от него удалиться, в противном случае ничего не делаем.


function Update(npc, enemy)
   if npc:IsSeeEnemy(enemy) then
      npc:RunFromEnemy(enemy)
   end
end

Мы убедились, что это достаточно примитивный и простой способ для организации простого ИИ в играх. При большом объеме поставленных задач для ИИ, этот способ крайне неэффективен. В нашем примере всего одно условие и одно действие, как бы одна частичка (по поставленным изначально задачам, нам больше и не надо). При объединении этих частиц получается - автоматизированная система, основанная на правилах (проверках). Как только одно из условий этой цепи возвращает истину, выполняется его действие и выход из системы.

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

Очередь на поиск пути

noreply@blogger.com (Scripter) — Wed, 01 Jun 2011 20:55:00 +0000

Очередь на поиск путей позволит избежать случая, когда за один кадр ищется путь для большого количества объектов, что может вызвать лаг. Эта статья будет теоретической по двум причинам. Во-первых, реализация этого метода очень проста. А во-вторых, алгоритм нахождения пути, который мы разобрали, дает задержку в одну секунду при одновременном поиске 10000 путей за раз. Даже если у нас будет десять тысяч солдат в игре, то вряд ли мы ощутим такой лаг, так как они будут искать путь в разное время. Но все же давайте рассмотрим такой случай.

Чтобы избежать такой задержки, мы создадим очередь на поиск путей в виде массива. Каждый объект, которому нужно будет получить новый путь, будет записываться в эту очередь. Теперь нам надо каждый кадр брать часть запросов (или все запросы, если их мало) и находить для них путь. Но сколько запросов брать для обработки? Я бы не советовал указывать какое-то конкретное число и не стал бы распределять это количество в зависимости от FPS. «Тогда как?» - спросите вы (а если не спросите, то можете двигаться к следующей статье). А все просто, отведем, скажем, время в 100-200 миллисекунд на эту процедуру, после каждого найденного пути проверяем общее потраченное время за этот кадр, и если оно больше нашего заранее определенного, то продолжаем работу программы, а другие «счастливчики» будут ждать следующий кадр.

По своему опыту скажу честно, такого мне делать не приходилось, но если вам это все-таки понадобится, то не забудьте удалять из очереди запросы тех объектов, которые, скажем, погибли.

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

Передвижение по точкам

noreply@blogger.com (Scripter) — Tue, 31 May 2011 16:32:00 +0000

Если у нас есть путь из одной точки в другую, который мы нашли с помощью алгоритма А-звездочка (смотрите в предыдущих статьях), то почему бы нам не реализовать перемещение по этому пути?

Чтобы найти путь, который прошел наш объект, нам надо умножить потраченное время на скорость объекта. Скорость объекта мы будем задавать сами, а время будем вычислять разницей времени между кадрами.

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

первая точка будет являться положением объекта в пространстве;
пройденные точки будут удаляться

Для удобства я удалил ранее созданную структуру "MapPoint" и заменил её на vector2f. Чтобы использовать vector2f, потребуется подключить Configurable Math Library. Как видно из названия это двухмерный вектор, где каждый элемент имеет тип float.

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

Давайте взглянем на наш класс, который сможет передвигаться.

class CPathUser
{
private:
  // скорость
  float m_Speed;
  // вектор наших точек пути
  std::vector< vector2f > m_Way;
public:
  CPathUser(void);
  ~CPathUser(void);
  // установка скорости
  void SetSpeed(float Speed);
  // прошли ли мы заданный путь
  bool IsWayFinished();
  // перемещение
  void Move(int iDeltaMilliSeconds);
  // возвращение позиции
  vector2f GetPos();
  // установка позиции
  void SetPos(vector2f Pos);
  // установка пути
  bool SetWay(vector2f EndPos);
};

Предлагаю взглянуть на код примитивный функций, который я не буду комментировать - тут и так все ясно.

CPathUser::CPathUser()
{
   m_Speed = 0;
}

CPathUser::~CPathUser()
{

}

void CPathUser::SetSpeed(float Speed)
{
   m_Speed = Speed;
}

bool CPathUser::IsWayFinished() 
{ 
   if (m_Way.size() > 1)
      return false;
   return true;
}

void CPathUser::SetPos(vector2f Pos)
{
   m_Way.clear();
   m_Way.push_back(Pos);
}

vector2f CPathUser::GetPos()
{
   return m_Way[0];
}

Рассмотрим детально нашу функцию передвижения.

void CPathUser::Move(int iDeltaMilliSeconds)
{
   // если мы уже прошли путь выходим
   if (IsWayFinished())
      return;
   // находим пройденный путь
   float WayLen = iDeltaMilliSeconds * m_Speed;
   // пока у нас есть точки, между которыми можно перемещаться
   while(m_Way.size() > 1)
   {
      // находим вектор между двумя точками
      vector2f vDir = m_Way[1] - m_Way[0];
      // находим длину полученного вектора
      float fLen = vDir.length();
      // находим разницу длины между точками 
      // и длины пути, который мы успели пройти
      float fDelta = fLen - WayLen;
      // если разница отрицательная
      if (fDelta <= 0)
      {
         // отнимаем от пройденной длины, длину между точками
         WayLen = abs(fDelta);
         // удаляем пройденную точку
         m_Way.erase(m_Way.begin());
      }
      // если положительная
      else
      { 
         // так как мы где то между точками
         // найдем наше местоположение
         vector2f NewPos = m_Way[0] + vDir.normalize()*WayLen;
         // сохраним его в первую точку пути
         m_Way[0] = NewPos;
         return;
      }
   }
}

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

bool CPathUser::SetWay(vector2f EndPos) 
{ 
   // так как мы сейчас можем находиться между двумя 
   // точками, сохраним наше местоположение
   vector2f PosNow = m_Way[0];
   // рассчитываем новый путь
   bool ValidWay = Pathfinding.GetWay(m_Way[0], EndPos, &m_Way);
   // если путь не найден
   if (!ValidWay)
   {
      // добавляем точку, в которой мы сейчас
      // находимся, так как путь очищен
      m_Way.push_back(PosNow);
      return false;
   }
   // находим направление движения
   vector2f Diff = m_Way[1] - m_Way[0];
   if (Diff[0])
      Diff[0] = Diff[0]/abs(Diff[0]);
   if (Diff[1])
      Diff[1] = Diff[1]/abs(Diff[1]);

   // правим первую точку пути для правильного движения
   m_Way[0]= m_Way[0]+Diff*20;
 
   // вставляем сохраненную точку, где мы сейчас есть
   m_Way.insert(m_Way.begin(), PosNow);
   return true;
}

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

Оптимизация найденного пути

noreply@blogger.com (Scripter) — Tue, 24 May 2011 14:01:00 +0000

В чем заключается оптимизация найденного пути? Все очень просто: мы должны убрать точки лежащие на одной прямой. Но у меня идея получше: в момент построения пути не будем добавлять лишние точки.

Для этого нам потребуется отредактировать нашу функцию "CPathfinding::GetWay".

Как мы узнаем, что точки лежат на одной прямой? Так как у нас все клетки карты хранятся в одномерном массиве и имеют свой уникальный номер, то просто давайте найдем разницу между номерами добавляемых в карту клеток. И если при следующем добавлении разница совпадает, то эту клетку мы добавлять не будем.

Итого, вот так выглядит наш кусок кода, который в конце ищет точки пути и добавляет его:


while (ID != iMasterID) 
{
   ID = iMasterID;
   iMasterID = GetMasterID(ID);
   PointOfWay.x = ID % WayMap->GetGridWidth()* WayMap->GetChunkSize();
   PointOfWay.z = ID / WayMap->GetGridWidth()* WayMap->GetChunkSize();

   int iDelta = abs(ID-iMasterID);
   if (iDelta != iSaveDelta) 
   {
      Way->insert(Way->begin(), PointOfWay);
      iSaveDelta = iDelta;
   }   
}

Вот и все, теперь наш путь оптимизирован и не будет содержать лишних ненужных точек.

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

Стоимость передвижения в A star

noreply@blogger.com (Scripter) — Mon, 23 May 2011 16:07:00 +0000

В прошлых примерах мы рассматривали только два типа проходимости, где можно пройти и где нельзя. Давайте исправим ситуацию и рассмотрим реализацию, когда каждая клетка имеет разную степень проходимости, или как ещё говорят имеют разный вес. Мы просто раздадим разным клеткам разный вес в зависимости от рельефа. Чем темнее у нас будет клетка, тем больше времени она будет отнимать у "путника", который будет по ней идти.

Как же это реализовать? А все очень и очень просто! В структуре CMapChunk (смотрите прошлые статьи) мы введем дополнительный параметр RankPassability, который будет хранить вес проходимости.

Я, например, заполнил так, что в середине карты у меня получилась синусоида, как будто тропа между холмами :)

Сейчас вы наверно подумали, опять будет куча расчетов и нудятины, а вот и ничего подобного!

Как один из вариантов: мы просто в оценке пути при расчете F (F это сумма G и H) умножаем его результат на вес клетки:

Chunk.F = (Chunk.H + Chunk.G) * WayMap->GetRankPass(Chunk.ID);

Если вам эта строка ни о чем не говорит, и вы не знаете что такое F, H и G, то вы не читали мои прошлые статьи. А зря :)

ДА! И это все :) Вот результат:

Но внезапно на нашем пути появилась китайская стена :)

Ну и последний пример:

Таким образом можно задать болота, реки, рельеф и другие типы местности на карте.

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

A star в картинках

noreply@blogger.com (Scripter) — Mon, 23 May 2011 09:53:00 +0000

В прошлой статье мы рассмотрели алгоритм поиска пути A star, как на теории, так и на практике. Но было бы не плохо ещё разобраться наглядно не используя ни формулы ни код.

Представим, что у нас есть карта 6 на 5 клеток, итого 30, и нам надо попасть из клетки с номером 6 в 22.

Зеленым квадратиком, я буду обозначать, что эта клетка находится в открытом списке.

Синим - в закрытом.

Я выбрал именно это расположение стартовой, конечной точек и преград, потому что мне показался этот случай интересным. Как мы видим мы сразу добавили нашу стартовую клетку в открытый список. Напомню, открытый список служит для хранения клеток, которые нужно проверить, закрытый хранит уже проверенные ячейки.
Давайте взглянем на то, как я буду записывать данные ячейки:
Напомню обозначения из прошлого урока:

ID - номер ячейки в сетке;
mID - её родитель;
G - стоимость передвижения из стартовой клетки к данной. В моем примере каждое передвижение по горизонтали и вертикале будет стоить 10 единиц, а по диагонали 14. Так вот G это сумма единиц пройденного расстояния от начала до конкретно рассматриваемой точки;
H - стоимость передвижения от данной клетки до конечной по методу Манхеттена (Manhattan method). Этот метод состоит в том что мы рассчитываем расстояние только по горизонтали и вертикали, игнорируя препятствия и диагональные перемещения.
F - сумма G и H;

Так как в открытом списке у нас лишь одна клетка 6, то мы берем её для анализа.

Мы добавили её проходимых соседей в открытый список, оценили их путь и нашу клетку отправили в закрытый список. Теперь нам надо выбрать клетку с наименьшим значением F (цифра верхнего левого уголка) для анализа. Так как мы начинали искать соседей слева направо, то первая клетка с наименьшим F у нас будет 12.

Опять у нас спорный момент между клетками 7 и 18, но 7 была добавлена раньше. Значит, ищем её соседей.

Клетка под номером 18 была добавлена раньше.

Уже видно два пути, которых наш алгоритм пытается сравнить и выявить наименьший. Хоть нам и ясно какой из них будет верным, продолжим наше наглядное исследование. Ищем соседей для клетки 8.

Следующая клетка, соседей которой мы будем оценивать, это клетка 19. И она будет последним анализируемым звеном в не самом коротком пути (но я вам этого не говорил).

В порядке очереди выбираем клетку 9.

На данном этапе, у нас появилась одна единственная клетка с наименьшим F, и она под номером 16.

Добавляя соседей для клетки 16, мы так же добавили нашу конечную точку, а значит, пора останавливать нашу рутинную процедуру :) Теперь нам надо найти по клеткам, находящимся в закрытом списке наш путь. Так как мы храним их номера родителей (master ID, правая верхняя цифра в квадратике), то двигаясь с конца по родительским клеткам дойдем до стартовой, это и будет наш путь.

Ну и вот так выглядит наш путь найденный алгоритмом A*.

Думаю теперь, когда мы "разжевали" алгоритм поиска пути A star (на теории, на картинках, на практике), недопонимания и вопросов не осталось ни у кого. Теперь мы легко можем найти кратчайший путь из одной точки в другу.

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

Алгоритм поиска пути A*

noreply@blogger.com (Scripter) — Sat, 21 May 2011 21:38:00 +0000

В этой статье мы рассмотрим поиск пути. Говорят, что алгоритм A* (или А звездочка, или A star) сложен для новичков, ну что ж, пусть так говорят :)

Давайте же на теории пройдемся по этапам поиска пути по алгоритму A*, а потом закрепим это на практике.

У нас будет два списка, которые будут хранить номера клеток. В первом будут клетки, которые нужно проверить, во втором - клетки, которые уже проверены. Первый список обычно называют "открытый", второй - "закрытый".

Мы добавляем стартовую точку в наш открытый список.
Находим точку с наименьшим оцененным путем в открытом списке (как будем оценивать, написано ниже) и ищем для неё проходимых соседей. Найденные новые точки мы оцениваем путь и добавляем их в открытый список. А исследуемую точку мы удаляем из открытого списка и добавляем в закрытый, чтобы больше её не проверять.
Повторяем предыдущий пункт до тех пор, пока не найдем конечную точку (а не найти мы её не сможем из-за "островного" разделения закрытых друг от друга зон, которое мы рассмотрели в прошлой статье).
По закрытому списку строим наш путь.

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

Для начала немного подправим класс "CWayMap", который мы рассмотрели в прошлом уроке.

class CWayMap
{
private:
   ...
public:
   ...
   // эту функцию мы просто перенесли из private в public
   bool CheckDiagonals(int iNeighborX, int iNeighborZ, int iMasterX, int iMasterZ);
   // функция, возвращает true если из одной точки можно пройти в другую
   bool IsCanWay(int iStartID, int iEndID);
   // возвращаем ширину сетки
   int GetGridWidth() {return m_iGridWidth;}
   // возвращаем размер ячейки сетки
   int GetChunkSize() {return m_iChunkSize;}
};

Тут вроде ничего серьезного кроме "IsCanWay", но комментарии в коде дают нам понять, что можно смело двигать дальше, не тратя времени на ерунду.

bool CWayMap::IsCanWay(int iStartID, int iEndID)
{
   // не равны ли начальная и конечная точки пути
   if (iStartID == iEndID)
      return false;
   // проверяем, сможем туда попасть или нет, за счет разделения зон
   if (m_Grid[iStartID].Passability != m_Grid[iEndID].Passability)
      return false;
   // проверив одну из точек, мы сразу отсекаем случаи:
   // конечная точка - препятствие
   // начальная точка - препятствие
   if (!m_Grid[iEndID].Passability)
      return false;
   return true;
}

Я ещё ввел структуру "MapPoint", она будет хранить позиции ячеек сетки в экранных координатах, но можно обойтись и без неё.

struct MapPoint
{
   int x;
   int z;
};

Так же у нас появится ещё одна структура "WayChunk". Она пригодится для оценки пути определенной клетки. Давайте взглянем на неё:

struct WayChunk
{
   int ID; 
   int MasterID;
   int G;
   int H;
   int F;
};

ID - номер ячейки в сетке;
MasterID - её родитель;
G - стоимость передвижения из стартовой клетки к данной. В моем примере каждое передвижение по горизонтали и вертикале будет стоить 10 единиц, а по диагонали 14. Так вот, G -это сумма единиц пройденного расстояния от начала до конкретно рассматриваемой точки;
H - стоимость передвижения от данной клетки до конечной по методу Манхеттена (Manhattan method). Этот метод состоит в том, что мы рассчитываем расстояние только по горизонтали и вертикали, игнорируя препятствия и диагональные перемещения.
F - сумма G и H;

Теперь становится ясно, что каждый раз, мы будем искать точку с наименьшем значением F.

Давайте же взглянем на объявление нашего класса:

class CPathfinding
{
private:
   // стоимость передвижения по горизонтали и вертикали
   #define WeightLine 10
   // стоимость передвижения по диагонали
   #define WeightDiag 14
   // возможные результаты
   enum 
   { 
      SEARTH_COMPLETED = -1, 
      NOT_FIND_END = -2,
      FIND_END = -3 
   };
    // наша карта
   CWayMap* WayMap;
   // Список, который надо проверить
   std::vector < WayChunk > m_aOpenList;
   // Проверенный список
   std::vector < WayChunk > m_aCloseList;

   // точка, до куда мы должны найти путь
   int iEndX;
   int iEndZ;

   // возвращает клетку с наименьшим F
   int GetMinWayChunk();
   // проверяем клетку, ищем её соседей
   bool DoSearchStep(int iChunkNum);
   // поиск в открытом списке
   int FindInOpenList(int iChunkID);
   // поиск в закрытом списке
   int FindInCloseList(int iChunkID);
   // возвращаем мастер клетку по ID
   int GetMasterID(int iChunkID);
public:
   CPathfinding(int iWidth, int iHeight, int iSize); 
   ~CPathfinding(void);
   void DrawGrid(HDC dc);
   // наша функция, которой мы будем пользоваться
   bool GetWay(MapPoint From, MapPoint To, std::vector< MapPoint >* Way); 
};

Не стоит пугаться, здесь большинство функций работают с нашими списками, и ничего сложного в них нет. Я даже не буду их комментировать, просто пробежимся по ним, но только после конструктора и деструктора :)

CPathfinding::CPathfinding(int iWidth, int iHeight, int iSize)
{
   WayMap = NULL;
   // создаем нашу карту
   WayMap = new CWayMap(iWidth, iHeight, iSize);
}

CPathfinding::~CPathfinding(void)
{
   SafeDelete(WayMap);
}
// ищем в закрытом списке клетку по ID 
// и возвращаем его мастера
int CPathfinding::GetMasterID(int iChunkID)
{
   for (unsigned int i=0; i < m_aCloseList.size(); i++)
   {
      if (m_aCloseList[i].ID == iChunkID) 
         return m_aCloseList[i].MasterID;
   } 
   return -1;
}
// есть ли в закрытом списке клетка с указанным ID 
int CPathfinding::FindInCloseList(int iChunkID)
{
   for (unsigned int i=0; i < m_aCloseList.size(); i++)
   {
      if (iChunkID == m_aCloseList[i].ID) 
         return i;
   }
   return -1;
}
// есть ли в открытом списке клетка с указанным ID 
int CPathfinding::FindInOpenList(int iChunkID)
{
   for (unsigned int i=0; i < m_aOpenList.size(); i++)
   {
      if (iChunkID == m_aOpenList[i].ID) 
         return i;
   }
   return -1;
}

Функция "GetMinWayChunk" ищет в открытом списке клетку с наименьшим F для её дальнейшего анализа (возвращает порядковый номер открытого списка!).

int CPathfinding::GetMinWayChunk()
{
   // если открытый список пуст, то мы не нашли путь
   if (!m_aOpenList.size()) 
      return NOT_FIND_END;

   // ищем в открытом списке клетки с наименьшим F
   int iMinWay = m_aOpenList[0].F;
   int ID = 0;
   for (unsigned int i=0; i < m_aOpenList.size(); i++)
   {
      if (m_aOpenList[i].F < iMinWay) 
      {
         iMinWay = m_aOpenList[i].F;
         ID = i;
      }
   } 
   // если H этой клетки не 0, то это не конец пути
   if (m_aOpenList[ID].H != 0)
      return ID;
   else
   {
      // иначе добавляем конечную точку и сообщаем об этом
      m_aCloseList.push_back(m_aOpenList[ID]);
      return FIND_END;
   }
}

"DoSearchStep" получает номер элемента открытого списка, из которого определяет ID клетки, для которой будем искать проходимых соседей. Каждого "хорошего" мы добавляем в открытый список, оценивая его путь. В конце анализирующую клетку, с которой работали, удаляем из открытого списка и добавляем в закрытый.

bool CPathfinding::DoSearchStep(int iChunkNum)
{
   // Родительский ID, для которого ищем соседей
   int iMasterID = m_aOpenList[iChunkNum].ID;

   // вычисляем по номеру ячейки ширину и высоту в сетке
   int iMasterX = iMasterID % WayMap->GetGridWidth();
   int iMasterZ = iMasterID / WayMap->GetGridWidth();
   // проходимся по всем соседям
   for (int i = -1; i <= 1; i++)
   {
      for (int j = -1; j <= 1; j++)
      {
         // если это и есть ячейка, соседей которых мы ищем, то пропускаем
         if (!j && !i)
            continue;

         int iNeighborX = iMasterX+i;
         int iNeighborZ = iMasterZ+j;
         // проверка на диапазон и проходимость клетки
         if (WayMap->CheckPassability(iNeighborX, iNeighborZ))
         {
            // если он является диагональным, то можно ли
            // пройти в него не срезав углы
            if (WayMap->CheckDiagonals(iNeighborX, iNeighborZ, iMasterX, iMasterZ))
            {
               // по ширине и высоте находим номер соседа в сетке
               int iNeighborID = WayMap->GetIDByPos(iNeighborX, iNeighborZ);
               
               // если клетка проверялась, пропускаем
               if (FindInCloseList(iNeighborID) > -1)
                  continue;
  
               // начинаем оценивать путь этой точки
               WayChunk Chunk;  
               // устанавливаем ID клетки
               Chunk.ID = iNeighborID;
               // устанавливаем родителя клетки
               Chunk.MasterID = iMasterID;
               // стоимость передвижения Манхеттена
               Chunk.H = (abs(iNeighborX - iEndX) + abs(iNeighborZ - iEndZ)) * 10;

               // рассчитываем длину пути от начальной точки до нынешней
               int iDiffX = abs(iMasterX - iNeighborX);
               int iDiffZ = abs(iMasterZ - iNeighborZ);
               int iDiag = min(iDiffX, iDiffZ);  
               int iDirect = max(iDiffX, iDiffZ) - min(iDiffX, iDiffZ);
               Chunk.G = iDiag*WeightDiag + iDirect*WeightLine + m_aOpenList[iChunkNum].G;
               // вычисляем наш F
               Chunk.F = Chunk.H + Chunk.G; 

               // есть ли наша клетка в открытом списке
               int iNumChunk = FindInOpenList(Chunk.ID);
               if (iNumChunk == -1)
                  // если нет, то добавлем
                  m_aOpenList.push_back(Chunk);
               else
               {  
                  // если есть, то не короче ли наши новые расчеты
                  if (m_aOpenList[iNumChunk].G > Chunk.G)
                     m_aOpenList[iNumChunk] = Chunk;
               }
            }
         }
      }
   }
   
   // после того как с нашей точкой мы поработали, пора её перенести в другой список
   m_aCloseList.push_back(m_aOpenList[iChunkNum]);
   m_aOpenList.erase(m_aOpenList.begin() + iChunkNum);
   return true;
}

Ну и последняя функция, которая собирает все части пазла. В неё мы передаем начальную точку, конечную и указатель на вектор, который мы наполним точками найденного пути. Мы будем анализировать каждый раз клетку с наименьшим F, пока не добавим конечную точку в открытый список. Далее мы будем следовать с конца через мастер точки, добавляя их в путь, до тех пор, пока не дойдем до стартовой точки. Это и будет наш путь.

bool CPathfinding::GetWay(MapPoint From, MapPoint To, std::vector< MapPoint >* Way)
{
   // очищаем вектор, который мы передали в функцию, вдруг он не пустой
   Way->clear();

   // переводим стартовую точку в координаты сетки
   int iStartX = From.x/WayMap->GetChunkSize();
   int iStartZ = From.z/WayMap->GetChunkSize();
   // проверяем, есть ли такая точка на карте
   if (!WayMap->CheckRange(iStartX, iStartZ))
      return false;

   // переводим конечную точку в координаты сетки
   iEndX = To.x/WayMap->GetChunkSize();
   iEndZ = To.z/WayMap->GetChunkSize();
   // проверяем, есть ли такая точка на карте
   if (!WayMap->CheckRange(iEndX, iEndZ))
      return false;

   // находим их ID
   int iIDFromChunk = WayMap->GetIDByPos(iStartX, iStartZ);
   int iIDToChunk = WayMap->GetIDByPos(iEndX, iEndZ);
   // если туда добраться нельзя, возвращаем false
   if (!WayMap->IsCanWay(iIDFromChunk, iIDToChunk))
      return false;
   // добавляем в открытый список стартовую точку
   WayChunk Chunk;
   Chunk.ID = iIDFromChunk;
   Chunk.MasterID = iIDFromChunk;
   Chunk.G = 0;
   Chunk.H = (abs(iStartX - iEndX)+abs(iStartZ - iEndZ))*WeightLine;
   Chunk.F = Chunk.G + Chunk.H;
   m_aOpenList.push_back(Chunk);
    
   // находим номер элемента, у которого минимальный F
   int iNumInOpenList = GetMinWayChunk();
   // до тех пор пока поиск не завершится, делаем анализ клетки с минимальным F
   // а после опять ищем новую клетку с минимальным F
   for (; iNumInOpenLis > SEARTH_COMPLETED; iNumInOpenLis = GetMinWayChunk())
   {
      DoSearchStep(iNumInOpenLis);
   }
   
   bool bDone = false;
   // если конечная точка найдена
   if (iNumInOpenLis == FIND_END)
   {  
      // добавляем конечную точку в наш вектор пути
      MapPoint PointOfWay;
      PointOfWay.x = iEndX * WayMap->GetChunkSize();
      PointOfWay.z = iEndZ * WayMap->GetChunkSize();
      int ID = -1;
      int iMasterID = WayMap->GetIDByPos(iEndX, iEndZ); 
      // до тех пор пока мы в обратном порядке на найдем стартовую точку
      // через мастер точки движемся с конца в начало, добавляя путь в вектор
      while (ID != iMasterID) 
      {  
         ID = iMasterID;
         iMasterID = GetMasterID(ID);
         PointOfWay.x = ID % WayMap->GetGridWidth()* WayMap->GetChunkSize();
         PointOfWay.z = ID / WayMap->GetGridWidth()* WayMap->GetChunkSize();
         Way->push_back(PointOfWay);
      }
      bDone = true;
   }
   // очищаем наши открытый и закрытый списки
   m_aCloseList.clear();
   m_aOpenList.clear();
   return bDone;
}

Путевая точка, находящаяся на пересечении. Этот вариант реализован в коде данной статьи.
Путевая точка, находящаяся в центре квадрата. Чтобы реализовать этот вариант, вам надо к каждой путевой точке добавить половину размера клетки карты по x и z. Именно этот вариант я буду использовать в дальнейшем.
Вот мы и заполнили вектор точками найденного пути. В общем все просто! А ещё говорят, что алгоритм поиска пути A* сложен для новичков. Стоит обратить внимание на то, что мы в наш путь добавляем все путевые точки подряд, что совсем не правильно. В дальнейшем мы рассмотрим способ добавления путевых точек, пропуская при этом лишние. А следующая статья будет посвящена опять таки алгоритму A star, но только уже в виде картинок, для полного понимания и закрепления наших знаний.

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

Пространство поиска пути

noreply@blogger.com (Scripter) — Fri, 13 May 2011 17:39:00 +0000

Пространство поиска пути - это территория разделенная на части, где будет искаться путь из одной точки в другую.

Существует множество способов разделить пространство поиска пути. Это клетки, шестиугольники, путевые точки (waypoints) и полигонная сетка (navigation mesh). Для простоты я буду использовать клетки.

Мы создадим пространство поиска пути в виде прямоугольника и разделим его на квадратики (такой квадрат называют ещё - chunk), но это задача легкая, поэтому усложним её. Так как в дальнейшем мы будем рассматривать алгоритм поиска пути A* (A star), хотелось бы отметить главный из его недостатков. Он состоит в том, что для нахождения пути к недоступному участку, алгоритм будет искать путь на всей карте, потратив много времени. Этого можно избежать, если разделить карту на закрытые участки (недоступные друг для друга). Об этом мы и поговорим.

Итого наша задача не только создать "карту" пути, но и сделать так, чтобы она делилась на зоны ("острова").

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

Как вы заметили по видео, если был изменен цвет в какой то области, то там происходила проверка либо на существование отделенных друг от друга зон, либо на их слияние.

Давайте пройдемся по этапам нашего алгоритма:

Указываем номер области, для которой нужно сделать проверку.
Ищем элемент карты, совпадающий с указанным номером, и добавляем его в массив для обработки. Этот квадрат будет являться частью новой зоны.
Берем первый элемент из массива клеток, которые нам нужно проверить, и ищем для него проходимых соседей, которые будут добавляться в тот же массив. После чего элементу, который мы проанализировали, мы присваиваем новый номер зоны и удаляем его. Этот этап мы повторяем до тех пор, пока наш массив не станет пустым.
Повторяем пункт №2 до тех пор, пока совпадений по заданному номеру области не будет обнаружено.

Пора переходить к практике. Создадим класс поиска пути с именем «CWayMap», который потом будет использоваться и для алгоритма А* (A star).

class CWayMap
{
private:
   // структура, которая будет являться каждой ячейкой сетки
   struct CMapChunk
   {
      // проходимость
      int Passability;
   };
   // тип переменной для проходимости, означающий что нужна проверка
   #define NO_INIT -1
   // освобождение памяти
   #define SafeDelete(b) if (b) { delete b; b = NULL;}

   // cетка, которая состоит из наших клеток
   CMapChunk * m_Grid;
   // ширина сетки
   int m_iGridWidth;
   // высота сетки
   int m_iGridHeight;
   // размер чанка (клетки)
   int m_iChunkSize;
   // счетчик зон
   int m_iCountZone;

   // разделение клеток с определенным типом проходимости на зоны
   void SplitZones(int iPassabilityType);
   // создание зоны
   void CreateZone(int iChunkID, int NewZone);
   // проверки на воможность перемещения по диагонали
   bool CheckDiagonals(int iNeighborX, int iNeighborZ, int iMasterX, int iMasterZ);
public:
   CWayMap(int iWidth, int iHeight, int iSize);
   ~CWayMap(void);
   // проверка существует ли клетка с указанной шириной и высотой в сетке
   bool CheckRange(int iChunkX, int iChunkZ);
   // смена значения проходимости клетки
   void ChangePassability(int x, int z);
   // возвращаем ID клетки по его ширине и высоте
   int GetIDByPos(int iChunkX, int iChunkZ);
   // проверка на диапазон и проходимость клетки
   bool CheckPassability(int iChunkX, int iChunkZ);
};

Passability у нас будет отвечать за проходимость каждой ячейки сетки. Так же ячейку сетки я буду называть – клетка и чанк. Таким образом, сравнив значение Passability стартовой и конечной точки пути, можно будет сразу узнать – можно туда попасть или нет. А если оно равно нулю, то эта зона не проходима, таким образом можно легко это будет проверить:

Если (Passability) То можем_пройти;

Начнем с конструктора:

CWayMap::CWayMap(int iWidth, int iHeight, int iSize)
{
   // запоминаем размер ячейки
   m_iChunkSize = iSize;
   // вычисляем кол-во ячеек в ширину
   m_iGridWidth = iWidth/iSize;
   // вычисляем кол-во ячеек в высоту
   m_iGridHeight = iHeight/iSize;

   m_Grid = NULL;
   // создаем нашу сетку с нужным кол-ом ячеек
   m_Grid = new CMapChunk[m_iGridWidth*m_iGridHeight];
   // проходимся по всем ячейкам и выставляем им одну зону
   for (int x = 0; x < m_iGridWidth*m_iGridHeight; x++)
   {
      m_Grid[x].Passability = NO_INIT;
   }
   // у нас пока 0 зон, указываем это
   int m_iCountZone = 0;
   // делим нашу сетку на зоны, если они есть
   SplitZones(NO_INIT);
}

Тут все просто… мы передаем в функцию размеры нашей игровой карты и размер ячейки, на которые будет разбита эта карта. Разбиваем карту, сохраняем нужные нам параметры и присваиваем каждой созданной ячейке значение NO_INIT. Указываем, что у нас на данный момент нет зон, и используем функцию «SplitZones», которая проверяет клетки с типом проходимости NO_INIT и разделяет их на зоны, если они есть, но об этом позже.

В деструкторе освобождаем память, которую выделяли для нашей сетки.

CWayMap::~CWayMap(void)
{
  // освобождение памяти
   SafeDelete(m_Grid);
}

Функция «CheckRange» проверяет, существует ли указанная ячейка в диапазоне нашей сетки, это понадобится при поиске соседей у клетки. Ведь на границе карты у нашей клетки может отсутствовать несколько соседей.

bool CWayMap::CheckRange(int iChunkX, int iChunkZ)
{
   // если ширина ячейки меньше 0 или больше ширины сетки, возвращаем false,
   // с высотой так же.
   if ( iChunkX < 0 || iChunkZ < 0 || iChunkX > m_iGridWidth-1 || iChunkZ > m_iGridHeight-1)
      return false;
   return true;
}

Функция «GetIDByPos» возвращает номер клетки по высоте и ширине сетки.

int CWayMap::GetIDByPos(int iChunkX, int iChunkZ)
{
   return iChunkZ*m_iGridWidth + iChunkX;
}

«CheckDiagonals» проверяет, является ли найденный сосед (клетка находящаяся рядом с исследуемой) «мастер» клетки диагональным, и если да, то можно ли туда переместиться, не срезав углы недоступных клеток. В моем примере я решил не допускать срезы углов (рис.1).

Рис.1 неразрешенный срез угла недоступной ячейки, красная точка – мастер точка, зеленая точка – её диагональный сосед.

В эту функцию мы передаем «координаты» соседа и его хозяина.

bool CWayMap::CheckDiagonals(int iNeighborX, int iNeighborZ, int iMasterX, int iMasterZ)
{
   // вычисяем разницу в ширине между соседем и «хозяином»
   int iDiffX = iNeighborX - iMasterX;
   // вычисяем разницу в высоте между соседем и «хозяином»
   int iDiffZ = iNeighborZ - iMasterZ;
   // если сосед является диагональным
   if (iDiffX && iDiffZ)
   {
      // находим первого соседа для соседа соприкасающимся с «хозяином»
      int iContact1X = iMasterX + iDiffX;
      int iContact1Y = iMasterZ;
      // если найденный сосед не проходимый, возвращаем false
      if (!m_Grid[GetIDByPos(iContact1X, iContact1Y)].Passability)
         return false;
      // находим второго соседа для соседа соприкасающимся с «хозяином»
      int iContact2X = iMasterX;
      int iContact2Y = iMasterZ + iDiffZ;
      // если найденный сосед не проходимый, возвращаем false
      if (!m_Grid[GetIDByPos(iContact2X, iContact2Y)].Passability)
         return false;
   }
   // в противном случае сосед «мастера» проходимый
   return true;
}

«CheckPassability» проверяет, существует ли такой чанк в диапазоне нашей сетки и если существует, то является ли он проходимым.

bool CWayMap::CheckPassability(int iChunkX, int iChunkZ)
{
   // если сосед существует в нашем диапазоне
   if (CheckRange(iChunkX, iChunkZ))
   {
      // если этот сосед ещё не проверялся и является проходимым
      if (m_Grid[GetIDByPos(iChunkX, iChunkZ)].Passability)      
         return true;    
   }
   return false;
}

«CreateZone» это функция непосредственного создания зоны. В неё мы передаем номер клетки, с которой начнется исследование по определению закрытой зоны, а так же новый номер зоны, который мы будем присваивать.

void CWayMap::CreateZone(int iIDChunk, int iNewZone)
{
   // вектор номеров ячеек, для которых надо найти всех соседей
   std::vector  aListForCheck;
   // добавляем туда номер ячейки из параметра функции
   aListForCheck.push_back(iIDChunk);

   // до тех пор пока наш вектор не пуст
   while(aListForCheck.size() != 0)
   {
      // вычисляем по номеру ячейки его ширину и высоту в сетке
      int iChunkX = aListForCheck[0] % m_iGridWidth;
      int iChunkZ = aListForCheck[0] / m_iGridWidth;
      // проходимся по всем соседям
      for (int i = -1; i <= 1; i++)
      {
         for (int j = -1; j <= 1; j++)
         {
            int iNeighborX = iChunkX+i;
            int iNeighborZ = iChunkZ+j;
            // проверка на диапазон и проходимость клетки
            if (CheckPassability(iNeighborX, iNeighborZ))
            {
               // по его ширине и высоте находим номер в сетке
               int iNeighborID = GetIDByPos(iNeighborX, iNeighborZ);
               if (m_Grid[iNeighborID].Passability != iNewZone)      
               {
                  // если он является диагональным, то можно ли
                  // пройти в него не срезав углы
                  if (CheckDiagonals(iNeighborX, iNeighborZ, iChunkX, iChunkZ))
                  {
                     // устанавливаем ему новую зону
                     m_Grid[iNeighborID].Passability = iNewZone;
                     // добавляем его в вектор, для поиска его соседей
                     aListForCheck.push_back(iNeighborID);
                  }
               }
            }
         }
      }
   // удаляем из вектора проверенную ячейку
   aListForCheck.erase(aListForCheck.begin());
   }
}

Суть такова: мы добавляем номер ячейки в вектор, в котором каждый элемент проверяется на возможных проходимых соседей, которые тоже потом добавляются в вектор. И так до тех пор, пока количество элементов в векторе не будет равно нулю. А это значит, что функция будет искать всех соседей и метить их до тех пор, пока мы не найдем закрытую зону.

Ну и вот наша главная функция «SplitZones», которая использовалась в конструкторе:

void CWayMap::SplitZones(int iPassabilityType)
{
   // пробегаемся по всем ячейкам сетки
   for (int x = 0; x < m_iGridWidth*m_iGridHeight; x++)
   {
      // если это та зона, которую нужно проверить
      if (m_Grid[x].Passability == iPassabilityType)
      {
         // увеличиваем наши зоны
         if (++m_iCountZone > INT_MAX -1)
            // ошибка, счетчик переполнится и будет баг
            showerror("ошибка, счетчик переполнится и будет баг");
         // создаем новую зону
         CreateZone(x, m_iCountZone);
      }
   }
}

Наверно уже понятно как она работает. Мы указываем номер зоны, который надо проверить (в конструкторе это NO_INIT), при первом поиске элемента с нужной зоной, функция «CreateZone» находит всех её соседей... потом соседей соседей… и так далее, присваивая им новое значение зоны… Но если мы потом опять в цикле встретим указанный номер зоны для проверки, то эта зона отделена от первой и проделываем для неё тоже самое. Ну и так далее пока не найдем все отделенные друг от друга зоны.

Как же быть, если произошли изменения на карте? Я сделал так:

если ячейка изменилась на непроходимую, то проверяю, сколько у неё таких же непроходимых соседей, если больше 1 (не включая её саму), то делаю проверку на разделение той зоны, в которой появилась новая «стенка».

если же «стенка» наоборот убралась, я устанавливаю новую зону всем её уникальным по зонам соседям, и делаю проверку этой новой общей зоны.

void CWayMap::SetPassability(int x, int z)
{
   // x и z это оконные координаты клика мыши, по ним находим ширину и высоту
   // в сетке ячейки на которую тыкнули
   int iChunkX = int(x)/m_iChunkSize;
   int iChunkZ = int(z)/m_iChunkSize;
   // по ширине и высоте ячейки находим её номер в сетке
   int iChunkID = GetIDByPos(iChunkX, iChunkZ);

   // запоминаем значение проходимости, так как мы его изменим
   int iChangePassability = m_Grid[iChunkID].Passability;
   // если мы убираем препятствие
   if (!iChangePassability)
   {
      // указываем что нужна проверка
      iChangePassability = NO_INIT;
      m_Grid[iChunkID].Passability = NO_INIT;
   }
   else
      // меняем на непроходимую
      m_Grid[iChunkID].Passability = 0;

   // вектор зон, которые возможно соединятся
   std::vector< int > aZoneForSplit;

   // кол-во найденных непроходимых соседей
   int iCountBlock = 0;
   // пробегаемся по соседям
   for (int i = -1; i <= 1; i++)
   {
      for (int j = -1; j <= 1; j++)
      {
         // если это и есть ячейка, соседей которых мы ищем, то пропускаем
         if (!j && !i)
            continue;

         int iNeighborX = iChunkX+i;
         int iNeighborZ = iChunkZ+j;
         // по ширине и высоте находим номер в сетке
         int iNeighborID = GetIDByPos(iNeighborX, iNeighborZ);
         // проверка на диапазон и проходимость клетки
         if (CheckPassability(iNeighborX, iNeighborZ))
         {
            // если по клику мыши мы убрали «стену»
            if (iChangePassability == NO_INIT)
            {
               // уникальна ли зона
               bool bNewSplitZone = true;
               for (unsigned int i = 0; i < aZoneForSplit.size(); i++ )
               {
                  // если зона уже есть в списке, то она не уникальна
                  if (aZoneForSplit[i] == m_Grid[iNeighborID].Passability)
                     bNewSplitZone = false;
               }
               // если зона уникальная, то добавляем
               if (bNewSplitZone)
                  aZoneForSplit.push_back(m_Grid[iNeighborID].Passability);
    
               // меняем цвет зоны, где убрали стенку, на цвет соседа 
               m_Grid[iChunkID].Passability = m_Grid[iNeighborID].Passability;
            }
         }
         // иначе увеличиваем счетчик «плохих» соседей
         else
            iCountBlock++; 

         // если найденных непроходимых соседей больше 1
         if (iCountBlock > 1)
         {
            // если по клику мыши мы убрали «стену»
            if (iChangePassability == NO_INIT)
            {
               // пробегаемся по всем ячейкам и из всех зон в aZoneForSpli
               // делаем одну общую
               for (int x=0; x < (m_iGridWidth * m_iGridHeight); x++)
               {
                  for (unsigned int i = 0; i < aZoneForSplit.size(); i++ )
                  {
                     if (aZoneForSplit[i] == m_Grid[x].Passability)
                     {
                        m_Grid[x].Passability = NO_INIT;
                        break;
                     }
                  }
               }
            }
            // перепроверяем и делим зону, если это требуется
            SplitZones(iChangePassability);
            return;
         }
      }
   }
}

Вот и все! Мы создали и разделили пространство поиска пути на клетки, по которым сможем искать путь. Так же реализовали "островную" систему, которая автоматически разделяет и делает слияние непроходимых зон на нашей карте. И теперь мы можем сразу определить до поиска пути: можно ли добраться из одной клетки в другую или нет?

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

Искусственный интеллект

noreply@blogger.com (Scripter) — Wed, 11 May 2011 20:04:00 +0000

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

1. Искусственный интеллект и его понятие.

2. Главные проблемы.

3. Задачи.

4. Технологии создания.

1. Искусственный интеллект и его понятие.

Искусственный интеллект (ИИ, Artificial intelligence, AI) — набор программных методик, которые используются в компьютерных играх для создания иллюзии интеллекта в поведении персонажей, управляемых компьютером. Его применяют для контролирования неигровых персонажей (Non-player character, NPC).

Искусственный интеллект является не просто частью игры, а одним из самых главных её составляющих. Кто то может представить себе игру без врагов? С кем нам сражаться и воевать, если их не будет?

Даже тетрис становится интересней, если компьютер будет играть параллельно с нами в каком-нибудь уголку окна, ведь появляется дух соперничества. Но не только вражеские интеллектуалы доставляют радость в играх. К большому сожалению, не во всех играх разработчики на сторону игрока ставят дружественных объектов «с мозгами». Постоянно бегать/летать/скакать одному очень угнетает, а когда кто-то рядом уже не так страшно, да и намного интересней.

2. Главные проблемы

Многие наверно скажут, что главная проблема, это то, что искусственный интеллект никогда не заменит человека. А ведь в компьютерных играх этого совсем и не нужно. Кто захочет перестреливаться с вражеским юнитом в какой-нибудь FSP (First-person shooter) десятки минут? Для этого вполне подойдет игра по сети.

По мне, две главные проблемы это – «сверхглупые» и «сверхумные» враги. В первом случае игрок довольно быстро заскучает, во втором обидится, а это приведет к тому, что игра будет закрыта. А кому нравится проигрывать? Целью искусственного интеллекта является вовсе не обыгрывать игрока.

Супер пупер врага наверно легче написать, чем глупого, так как у них нет погрешности при стрельбе, он знает куда надо стрелять (чтобы сразу попасть в голову), он имеет данных больше чем игрок, поэтому его от них надо ограничить. Можно сделать проверку, которая скажет виден ли враг для нашего NPC или нет, можно сделать ему разброс при стрельбе, способов подпортить его читерские способности навалом.

3. Задачи

Теперь, когда мы знаем понятие искусственный интеллект и где он применяется, хотелось бы узнать его задачи. Пустышкам, наделенных "электронным мозгом", обычно приходится решать в ходе игры такие же задачи, что и игрокам. А значит, мы сами ставим им задачи и учим их самостоятельно с ними справляться. Примерами таких задач являются следующие категории:

Движение (нахождение пути, патрулирование, перемещение, преследование, уклонение и др.);
Атака (стрельба, перезарядка, бросок гранаты, установка мины и др.);
Взаимодействие с предметами (включить/выключить свет, пнуть предмет, попавшийся на пути, подобрать боеприпасы и др.);
Связь с другими NPC (переговоры по рации, включение сигнализации, запуск сигнальной ракеты и др.)

Полно других очень и очень даже интересных задач.

4. Технологии создания ИИ в играх

Теперь ознакомимся с некоторыми самыми популярными технологиями создания игрового ИИ.

Система, основанная на правилах (Rule Based Systems).

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

Пример вражеского патрулирующего NPC:

Если наши жизни < 20%, то убегаем.
Если враг в зоне нашей атаки, то атакуем.
Если мы видим врага, бежим к нему.
Если наши силы = 100%, патрулируем.
Стоим.

Как видно из примера, последнее действие не имеет условия. Достаточно примитивный и простой способ для организации ИИ в простых играх. При большом объеме поставленных задач для ИИ, этот способ крайне неэффективен.

Конечные автоматы (Finite State Machine).

Эта система, описывающая поведение объекта, используют заранее подготовленные состояния, выбирая нужное. Для удобства рассмотрим пример выше, у нас получатся следующие состояния: стоять, патрулировать, преследовать, атаковать, убегать. Мы находимся в том или ином состоянии до тех пор, пока не произойдет некое событие.

Например: в состоянии патрулирования, если мы увидели врага, мы переходим в состояние «атаковать», а в случае если устали, то в состояние «стоять».

Конечные автоматы бывают детерминированными и недетерминированными. Детерминированные это те конечные автоматы, переход состояний которых определен строго. Недетерминированные же имеют некую случайность. Скажем, мы можем и вовсе не входить в состояние убегать, а воевать до победного конца или смерти. А так же мы можем «случайно» не увидеть врага, которого бы увидели в детерминированном конечном автомате.

Нейронные сети (Neural Network).

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

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

Интересные цитаты

noreply@blogger.com (Scripter) — Thu, 28 Apr 2011 10:17:00 +0000

Ошибка - не грех. Неспособность к обучению на основе ошибок - вот что такое грех.

Макконнелл.

Если вы не недостаточно любопытны для того, чтобы не отставать от изменений, вы рискуете разделить участь динозавров.

Макконнелл.

Требования подобны воде. Опираться на них легче, если они заморожены.

Аноним.

Если вы не можете объяснить что-то шестилетнему ребенку, значит, вы этого сами не понимаете.

Энштейн.

Мы пытаемся решить проблему, максимаьно ускоряя процесс проектирования, чтобы в конце работы над системой у нас осталось достаточно времени на нахождение ошибок, допущенных из-за слишком быстрого проектирования.

Мейерс.

Я никогда не встречал человека, желающего читать 17000 страниц документации, е если бы встретил, то убил его бы его, чтобы он не портил генофонд.

Костелло.

Если для понимания того, что происходит, нужно увидеть реализацию, это не абстракция.

Плоджер.

Неработающая программа обычно приносит меньше вреда, чем работающая плохо.

Энди Хант и Дейв Томас.

Если бы строители возводили здания так, как программисты пишут программы, первый же дятел уничтожил бы цивилизацию.

Вайберг.

Программы - не люди, а ошибки не микробы: программа не может нахвататься ошибок, общаясь с другими дефектными программами. Ошибки всегда допускают программисты.

Миллз.

Отлаживать код вдвое сложнее, чем писать. Поэтому, если при написании программы вы используете весь свой интеллект, вы по определению недостаточно умны, чтобы её отладить.

Карниган.

Никогда не отлаживайте программу стоя.

Вайнберг.

Все удачные программы изменяются.

Брукс.

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

Вайнберг.

Крупномасштабный рефакторинг - путь к катастрофе.

Бек.

Необдуманная оптимизация - корень всего зла.

Кнут.

Любой дурак может написать код, понятный компьютеру. Хорошие программисты пишут код, понятный людям.

Фаулер.

Пишите код, исходя из того, что все программсты, которые будут сопровождать вашу программу, - склонные к насилию психопаты, знающие, где вы живете.

Аноним.

Любой дурак способен отстаивать свои ошибка - большинство дураков именно так и делают.

Карнеги.

Цитаты взяты из книги "Совершенный код" С.Макконнелл.

Nick Parser v0.1

noreply@blogger.com (Scripter) — Wed, 20 Apr 2011 13:24:00 +0000

Тыкнуть для скачивания

Nick Parser v0.1 - универсальный парсер любой информации с форумов.

Шаг 1.
Указываем низкий уровень форума.
Пример:

forum.[site].ru/viewtopic.php?t=

Жмем "check".

Шаг 2.
Указываем начало и конец html кода, за который сможем зацепиться при парсинге.
Пример:
Рассмотрим неудобный вариант, где рядом с ником хранится разный id :

<a name="205366"></a><b>Admin</a>

Поле1:

<a name=

Поле2:

</a>

Шаг 3.
Запускаем, нажав на "start"

Шаг 4.
Как ясно из названий кнопок: поставить на паузу, снять с паузы, завершить.

[!] Программа создаст папку с именем сайта в директории .exe файла приложения. В ней вы найдете сохраненную информацию.
[!] После 500 сохраненных ников, программа прекратит работу и так же нет возможности сохранения шага.
[!] Программа написана в ознакомительных целях, автор не несет ответственности.

___________________________________________

Предположим я получил следующую информацию:

"78626"><b>Гость

"2"><b>kaj

"78626"><b>;Гость

"3"><b>Кот

"82667"><b>BestDen

"2"><b>kaj

"78626"><b>Гость

"3"><b>Кот

"82667"><b>BestDen

"4"><b>Venomch

"5"><b>Кот

Тут нам понадобится Generator Pro
Используем "Spacekiller" и с помощью "Замена" заменяем одинаковые символы во всех строчках на ";"

"78626">;Гость

"2">;kaj

"78626">;Гость

"3">;Кот

"82667">;BestDen

"2">;kaj

"78626">;Гость

"3">;Кот

"82667">;BestDen

"4">;Venomch

"5">;Кот

Устанавливаем символ ";" на разделитель и жмем "Y;X", следом "X", а в конце используем "Clonekiller".
В итоге у нас выходит:

Гость

kaj

Кот

BestDen

Venomch

BestDen

Готово!

Docs translate v0.1

noreply@blogger.com (Scripter) — Sun, 17 Apr 2011 21:31:00 +0000

1. Указываете директорию.
2. Выбираете с какого на какой язык хотите перевести.
3. Запускаете.

Программа переведет все .txt файлы в указанной директории и сохранит их в отдельную папку.

Перевод осуществляется с помощью Google Translate.

Тыкнуть для скачивания

GeneratorPro

noreply@blogger.com (Scripter) — Sun, 17 Apr 2011 21:21:00 +0000

Возможности:
Генерирование по диапазону с одним или несколькими паролями.
Генерирование из файла с одним или несколькими паролями.

Имеются такие функции:
- Cортировка
- Clonekiller (удаление повторов)
- Spacekiller (удаление пробелов)
- Удаление Y из X;Y при любом разделителе
- Обмен местами X;Y на Y;X
- Быстрая замена
- Anti mass changer (замена разделителя на случайный знак)

! Работа как в окне программы, так и с .txt файлом

Тыкнуть для скачивания

Spot light

noreply@blogger.com (Scripter) — Sun, 17 Oct 2010 20:22:00 +0000

Сделал spot light, он же конусный источник света (к примеру фонарик).

dot light + Ambient light

Возможность менять дальность:

Возможность менять точность:

Возможность менять диаметр:

Возможность менять яркость:

Возможность задавать цвет:

Dot light

noreply@blogger.com (Scripter) — Sat, 16 Oct 2010 22:47:00 +0000

Сделал dot light, он же точечный источник света (к примеру лампочка).

dot light + Ambient light

Возможность менять дальность:

Возможность менять яркость:

Возможность задавать цвет:

Directional light

noreply@blogger.com (Scripter) — Sat, 16 Oct 2010 20:50:00 +0000

Сделал directional light, он же направленный источник света (к примеру солнце).

directional light + Ambient light

Возможность менять яркость:

Возможность задавать цвет:

Квады

noreply@blogger.com (Scripter) — Thu, 14 Oct 2010 16:05:00 +0000

Поразмыслил о том какие могут быть квады, а точнее по "деформации".

1) ширина и высота в координатах
2) ширина и высота в процентах
3) ширина в процентах, высота в координатах
4) высота в координатах, ширина в процентах
5) сохранение пропорции

Пункт 1.
Высота и ширина квада статичны, и не изменяются, скажем подходит для GUI, HUD'ов и тд.

До деформации:

После деформации:

Пункт 2.
Ширина и высота зависят от размеров окна, и всегда вычисляются в процентах.

До деформации:

После деформации:

Пункт 3.
Ширина п2, высота п1.

До деформации:

После деформации:

Пункт 4.
Ширина п1, высота п2.

До деформации:

После деформации:

Пункт 5.
Когда ширина и высота сохраняют, некую пропорцию (например квад для вывода видео).

До деформации:

После деформации:

Квады - начало

noreply@blogger.com (Scripter) — Thu, 07 Oct 2010 21:29:00 +0000

Ух сделал квады, размеры которых составляют процент от окна.

Возможность зависимости ширины от высоты и наоборот отсутствует, пока что, так как пока необходима.

А так же сделан рендер видео в текстуру, в прошлом у меня рендер шел в окно, а там были свои неудобные нюансы :)

Вот я проигрываю видео в текстуре (на прошлом скрине она черная)

Intro

noreply@blogger.com (Scripter) — Thu, 12 Aug 2010 23:42:00 +0000

Создал заставку для движка

Конец Delphi

noreply@blogger.com (Scripter) — Tue, 10 Aug 2010 00:12:00 +0000

Вот и настало время переводить мой главный проект. Ещё раз немного полюбуемся скринами :)

И так что у меня есть на данный момент:
* Создание девайса со всевозможными настройками
* Возобновление потерянного девайса
* Подсчет ФПС
* Вывод ошибок / логирование
* Менеджер ресурсов (пока что создает только текстуры, вершинные и пиксельные шейдеры, декларации)
* Сохранение скриншота всей области или отдельной части по имени или по дате
* Смена режима полноэкранный / оконный
* Стандартный текст (закомментирован ибо уг, нужно писать свой)
* Настройка курсора (свободный в рабочей области или невидимый в центре)
* Чтение из файла / архива
* Вычисление md5 файла или файла в памяти
* Настройка приложения в Settings.ini
* Рендер в отдельном модуле, для удобства
* Камера от 3его и от первого лица
* Инверсия мыши для камеры

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

AntiChat Tetra v1.1

noreply@blogger.com (Scripter) — Mon, 26 Jul 2010 14:44:00 +0000

Готово обновление:

[!] Исправлен баг из-за которого была синяя полоска на скриншоте;
[+] Теперь есть подсветка (прозрачная), которая указывает, куда падают кубики (на выбор желтая/красная);
[+] Теперь каждая фигура имеет различный цвет;
[+] Скорость мыши теперь можно изменять;
[+] Сделана настойка для включения инверсии мыши;
[+] Сделано табло, на котором отображается следующая фигура;
[+] Для каждой из 4 зон камеры, теперь своё управление;
[+] Готов MatrixMod, возможность останавливать время, при котором можно вращат ьи двигать фигурки (изначально 30 сек + за каждое сжигание 30 сек)
[+] Появилась возможность отключать АА для старых компьютеров;
*AntiAliasing — технология, использующаяся в обработке изображений с целью делать границы кривых линий более гладкими, убирая «зубцы», возникающие на краях объектов.

Скачать можно тут:
http://rapidshare.com/files/409183238/Update.zip
http://slil.ru/29502128

AntiChat Tetra v1.0

noreply@blogger.com (Scripter) — Fri, 23 Jul 2010 02:40:00 +0000

Скачать можно тут:
http://slil.ru/29492110
http://rapidshare.com/files/408516216/AntiChat_Tetra.zip