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

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

Для этого нам потребуется отредактировать нашу функцию "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;
   }   
}

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

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