Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах

CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах

Поделиться

Страницы: 1 2 3 4 ... 15 ... 28 29 30 Следующая

DevilDevilПостоялецwww28 мая 20112:42#0
Репозиторий: https://github.com/d-mozulyov/CrystalPathFinding
Архивом: https://github.com/d-mozulyov/CrystalPathFinding/archive/master.zip
Демо: Demo_x86.zip, Demo_x64.zip

CrystalPathFinding (CPF) - эффективная и простая библиотека с открытым исходным кодом, предназначенная для поиска кратчайших путей по алгоритмам A*/WA* для карт, основанных на тайлах, с 4 (simple), 8 (diagonal/diagonalex) или 6 (hexagonal) соседями.

Особенности библиотеки:
  - Кроссплатформенность: Windows x86/x64, Linux x86/x64, Mac OS, iOS, Android, Windows Mobile, а так же остальные платформы, доступные компиляторам Delphi и FreePascal
  - Экстремально высокая производительность
  - Умное построение пути
  - Лимит 16млн ячеек (например 4000x4000)
  - Секторальный тест
  - На выбор: ООП или процедурный интерфейс
  - Поддержка кеширования и поиска из нескольких стартовых точек
  - До 255 разновидностей тайлов, вес от 0.1 до 100.0
  - Содержит демонстрационные проекты

Изображение
Изображение
Изображение

Правка: 7 сен. 2015 12:17

DevilDevilПостоялецwww28 мая 20112:43#1
ДОКУМЕНТАЦИЯ

Библиотека содержит 2 главных объекта: TTileMap (карта тайлов) и TTileMapWeights (массив весов тайлов). Тайл может принимать любое значение от 1 до 255. Вес тайла указывается в диапазоне от 0.1 до 100.0, если вес тайла от 0.0 до 0.1 - то тайл считается непроходимым. Если при поиске TTileMapWeights не указан, то все веса считаются единичными. Тайл с номером 0 (TILE_BARRIER) считается барьером, проход через который невозможен. Режимы карт mkDiagonal и mkDiagonalEx отличаются тем, как пути огибают тайлы-барьеры.

Параметр SectorTest (секторальный тест) позволяет существенно увеличить производительность поиска если карта поделена на "области", и построить путь из одной области в другую невозможно.

Параметр Caching (кеширование) рекомендуется всегда устанавливать в true, если некоторое время предполагается не менять целевую точку и массив весов.

Большое значение имеет массив исключаемых точек (Excludes). С помощью этого параметра можно организовать сложные поиски, в которых например одни игровые единицы не соприкасаются с другими. В таких случаях рекомендуется перестраивать пути при смене целевой точки, численного состава или местоположения хотя бы одной игровой единицы. Соответственно если интересует не весь путь игровой единицы, а только следующая точка - рекомендуется параметр поиска FullPath указывать false (см. пример ниже).

Базовые типы и константы

  
  typedef unsigned short ushort;
  typedef unsigned char uchar;
  struct TPoint
  {
      long X;
      long Y;
      TPoint(){}
      TPoint(long x, long y):X(x),Y(y){}
  };

  // хендл
  typedef size_t TCPFHandle;

  // тип карты
  typedef uchar TTileMapKind; enum {mkSimple, mkDiagonal, mkDiagonalEx, mkHexagonal}; 

  // результат поиска пути
  struct TTileMapPath
  {
      size_t  Index;  
      TPoint* Points;
      size_t  Count;
      double  Distance;
  };

  // параметры поиска
  struct TTileMapParams
  {
      TPoint* Starts;
      size_t StartsCount;
      TPoint Finish;
      TCPFHandle Weights;
      TPoint* Excludes;
      size_t ExcludesCount;
  };

  // тайл - барьер
  #define TILE_BARRIER 0

Объект массива весов

  
  struct TTileMapWeights
  {
    // конструктор, деструктор
    TTileMapWeights();
    ~TTileMapWeights();

    // хендл
    TCPFHandle Handle; 

    // веса тайлов
    float getValue(uchar Tile);
    void setValue(uchar Tile, float Value);
  }; 

Карта тайлов

  struct TTileMap
  {
    // конструктор, деструктор
    TTileMap(ushort AWidth, ushort AHeight, TTileMapKind AKind, bool ASameDiagonalWeight = false);
    ~TTileMap();

    // хендл
    TCPFHandle Handle; 

    // базовые параметры карты
    ushort Width;
    ushort Height;
    TTileMapKind Kind;
    bool SameDiagonalWeight;

    // важные параметры, которые можно и нужно менять
    bool SectorTest;
    bool Caching;

    // изменение
  void Clear();
  void Update(uchar* Tiles, ushort X, ushort Y, ushort AWidth, ushort AHeight, ptrdiff_t Pitch = 0);
  uchar getTile(ushort X, ushort Y);
  void setTile(ushort X, ushort Y, uchar Value);

    // поиск пути
  TTileMapPath FindPath(const TTileMapParams Params, bool FullPath = true);
  TTileMapPath FindPath(const TPoint Start, const TPoint Finish,
    TCPFHandle Weights = 0, TPoint* Excludes = NULL, size_t ExcludesCount = 0, bool FullPath = true);
  TTileMapPath FindPath(TPoint* Starts, size_t StartsCount, const TPoint Finish,
    TCPFHandle Weights = 0, TPoint* Excludes = NULL, size_t ExcludesCount = 0, bool FullPath = true);
  };

Пример использования

Рассмотрим случай, описанный в статье: http://www.policyalmanac.org/games/aStarTutorial_rus.htm

Изображение

 
  TTileMap Map(8, 6, mkDiagonalEx);

  Map.setTile(4, 1, TILE_BARRIER);
  Map.setTile(4, 2, TILE_BARRIER);
  Map.setTile(4, 3, TILE_BARRIER);

  TPoint Start(2, 2);
  TPoint Finish(6, 2);
  printf("A* Pathfinding [%d, %d] --> [%d, %d]...\n", Start.X, Start.Y, Finish.X, Finish.Y);
  TTileMapPath Path = Map.FindPath(Start, Finish);

  printf("Distance = %0.2f (%d points):\n", Path.Distance, Path.Count);
  for (size_t i = 0; i < Path.Count; i++)
    printf("[%d, %d]\n", Path.Points[i].X, Path.Points[i].Y);
A* Pathfinding [2, 2] --> [6, 2]...
Distance = 6.83 (7 points):
[2, 2]
[3, 3]
[3, 4]
[4, 4]
[5, 4]
[6, 3]
[6, 2]

Пример сложного обновления пути для нескольких ботов

void Game::UpdateBotsPaths()
{
   // очищаем пути для всех ботов   
   for (int i = 0; i < Bots.Count; i++)
     Bots[i].NextPoint = Bots.Point;
   
   // пробегаемся по каждому боту
   // чтобы найти для него путь
   for (int i = 0; i < Bots.Count; i++)
   {
      // собираем исключаемые точки
      vector<TPoint> Excludes;
      for (int j = 0; j < Bots.Count; j++)
      if (i != j)
      {
         Excludes.push_back(Bots[j].Point);

         if (Bots[j].Point != Bots[j].NextPoint)
           Excludes.push_back(Bots[j].NextPoint);
      }
    
      // заполняем параметры, ищем путь
      TTileMapParams Params;
      Params.Starts = &Bots[i].Point;
      Params.StartsCount = 1;
      Params.Finish = this.TargetPoint;
      Params.Weights = NULL/* this.Weights.Handle */;
      Params.ExcludesCount = Excludes.size(); 
      if (Params.ExcludesCount) Params.Excludes = &Excludes[0];
      TTileMapPath Path = this.Map.FindPath(Params, false/* false означает, что нужна только следующая точка */);
      if (Path.Count > 1)
        Bots[i].NextPoint = Path.Points[1];
   }
}

Правка: 3 сен. 2015 11:46

DevilDevilПостоялецwww28 мая 20112:43#2
СПИСОК ОПТИМИЗАЦИЙ (todo)

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

Открытый/закрытый список
Самая слабая часть алгоритма А* - это конечно организация списков, поисков, сортировок. Задачи сами по себе трудоёмкие, а если помножить на реальные условия, то алгоритм в теории чрезвычайно трудоёмкий. Начать я решил с организации главного массива - открытого/закрытого. Суть в том что все узлы меньше текущего - закрытые, остальные - открытые. Текущий узел - всегда самый минимальный из открытых. Оставался сложный процесс - вставки добавленных элементов в сортированный массив. Я выбрал алгоритм вставки сортированного массива в сортированный массив - чтобы все сдивиги делать за раз, а не каждый раз. Размер элементов массива составлял 8 байт - чтобы работа с ним была быстрой.

Но со временем пришлось отказаться от этой идеи. Потому что даже на карте 20x30 легко сделать тест, который будет использовать 300-400 точек. И сортировки каждый раз, даже "сортированный массив в сортированный массив" - работают медленно. Пришлось реализовать двусвязный список - скорость увеличилась в 2-3 раза

Умная вставка
веса добавляемых узлов часто равны весу текущего. Более того, если добавлять свежие узлы ближе к текущему, то цель достигается значительно быстрее. В рамках "умной вставки" ориентация велась на CurrentNode (текущий) и TopNode (первый нод с весом больше текущего). Если вес добавляемого узла равен весу текущего узла - то вставляем его сразу после текущего. Если вес узла <= весу Top узла - то вставляем его перед Top узлом и соответственно меняем Top узел. Все узлы весом больше TopNode сортируются по возрастанию и вставляются после TopNode.

Расчёт пути на CPU
Задача позволяет искать путь не по float весам тайлов, а по int-приближениям. Это значительно экономит процессорное время. Когда путь уже найден - Distance расчитывается уже на FPU. Внутри cpf путь ищется кстати не сначала в конец, а наоборот - из конца в начало. Так проще собирать пройденный путь и не надо потом переворачивать массив найденных точек

Битовое множество
В качестве флага открытый/закрытый было принято использовать битовое множество. Причём в нём так же хранятся excluded точки и точки с нулевым весом тайла. 2 бита на точку. Из минусов - приходится обращаться к "разной памяти". Из плюсов - достаточно просто и экономно отследить состояние выбранной точки. Кстати битовое множество не чистится полностью при каждом расчёте, а чистятся только загрязнённый участок. Это слегка экономит время скажем на больших картах с небольшими расчётными путями - когда чистить нужно только малую часть множества

Хранение ячеек
Каждая ячейка хранит в себе тайл, маску перехода и указатель на узел. Подход с масками перехода существенно упрощает универсализацию гексов, simple карт, избавляет от необходимости проверять dest-ячейку на препятствие и выход за границы. А узел хранится - это для быстрого изменения узлов. Получается 6 байт на клетку - поэтому я и сказал, что cpf - это компромисс между памятью и скоростью. А можно было бы все узлы хранить в карте. Но ушло бы слишком много памяти

Parent-mask оптимизация
Согласно этой оптимизации на ячейку накладывается не только собственная маска, но и "parent маска". Суть заключается в том, что оптимизация позволяет избавить от необходимости добавляемой ячейке рассматривать например ячейку родителя. Кроме родителя так же не рассматриваются от 0 до 4 дополнительных ячеек. Потому что нет необходимости рассматривать ячейки, путь до которых из parent-а всёравно будет быстрее

Расчётный цикл
Я мог бы организовать расчётный цикл на Delphi например или на C++, но так как в мои планы входило выжать максимум скорости из допустимого, то весь расчётный цикл организовал на ассемблере. Весь расчётный цикл - одна сплошная "инлайн" функция. В которой я умно использую регистры и память

Регистры и память
Одно из самых слабых мест современных программ - обращение с памятью. Поэтому была поставлена задача свести обращение к памяти к минимуму, а особенно разной. Пришлось задействовать все регистры по максимуму: eax, edx, ecx, ebx, esi, edi, esp, ebp. Все необходимые переменные адресуются через ebp и хранятся в специальном блоке, выровненном по 64 байта. Кроме того данные там тоже разгруппированы таким образом, чтобы обращение к разным 64 байтным блокам было минимально. Ну а регистры - отдельная песня. В одном к примеру я умудрился хранить 3 переменные и ещё штук 10-12 bool флагов. Это в частности даёт больше свободных регистров и как следствие - меньше обращение к разной памяти

мб что-то ещё

Правка: 18 авг. 2015 19:47

DevilDevilПостоялецwww28 мая 20112:43#3
ТЕСТЫ (todo)

здесь выкладываются официальные сравнительные тесты с другими библиотеками
пока стресстесты ориентировались на карты с одним видом тайлов, вес которых равен 1.. но в будущем возможно и другие варианты попробуем
"соревнование" было пока только с micropather, но ты можешь добавить свою библиотеку, реализовав простой интерфейс (см исходники)
качать здесь: http://devilhome.narod.ru/cpf_tests.zip

Тест собран в Code::Blocks с последним компилятором gcc (4.5.2) и следующими ключами:
-fomit-frame-pointer -DNDEBUG -fno-rtti -fno-exceptions -march=core2 -fno-pic -O3

правда почему-то в настройках у меня эти ключи слетали периодически
на Athlon 1700 кстати пример не пошёл - наверно потому что используются команды от core2. Можешь собрать под свою конфигурацию

а на Intel 3000 (512mb) был следующий скрин
это кстати не означает, что cpf быстрее mp в 20 раз
это лишь показывает, что в cpf хороший умный прогрессивный реллокатор, который работает не только на увеличение, но и на уменьшение. Если выставлять в micropather большой буфер по умолчанию, то разница cpf-micropather будет меньше

screen | CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах

Правка: 18 авг. 2015 19:47

[A][R][T]Постоялецwww28 мая 20119:56#4
cpf не нашел путь на этом изображении в режиме simple
input3
1 frag / 2 deathsУчастникwww28 мая 201112:06#5
Посоны, вот мой ехешник (ничё не оптимизировал).

PathFinder

Короче, суть такова.

При запуске вводим имя бмп-файла.
В файле синий пиксел (строго синий) - это вход, зелёный - выход.
Чёрный - стенка, белый - проходимая зона.
Другие цвета - полупроходимые (время прохода вычисляется по формуле 255*3-(R+G+B)+MinW, где MinW=200).
Пример файла в архиве есть.

Ищет только для 4 соседей. Эвристика - (abs(dx)+abs(dy))*MinW.

Alex_MПостоялецwww28 мая 201112:35#6
C этим изображением cpf проигрывает :(

test | CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах

Правка: 28 мая 2011 12:50

DevilDevilПостоялецwww28 мая 201112:46#7
[A][R][T]
Alex_M

спасибо, будем разбираться

Правка: 28 мая 2011 12:57

DevilDevilПостоялецwww28 мая 201113:25#8
Alex_M
ну это как раз особенности. mp по сути ищет как ему сказали: из зелёной точки в синюю. А cpf ищет наоборот - из синей в зелёную
если ты поменяешь точки местами, то увидишь кардинально противоположную картину )

TarasB
на Athlon 1700 чуть больше секунды
не думаю что это быстро

вот если ты адаптируешь официальный пример и ImageParser к таким изображениям - будет ваще круто

1 frag / 2 deathsУчастникwww28 мая 201113:31#9
Посоны, я исправил один глюк (он просто не прерывал алгоритм когда путь найден), добавил возможность ввода имени через командную строку, 8 направлений (ход по диагонали считается за кореньиздвух раз больше), и вывод не только ответа, но и волны.
PathFinder
Alex_MПостоялецwww28 мая 201114:47#10
DevilDevil
Ясно. Кстати, если в input_1 и input_2 поменять местами синюю и зеленую точки, то cpf не находит diagonal.
DevilDevilПостоялецwww28 мая 201115:16#11
Alex_M
это уже серьёзно
буду искать баг - спасибо что сказал !
RPGmanУдалёнwww28 мая 201115:19#12
DevilDevil
Чесслово, убери из названия темы слова "самый" и "в мире".
Очевидно, что это не так по всем статьям.
Или хотя-бы сделай, как это делается в мире рекламы - "Номер один по версии DevilDevil".

Правка: 28 мая 2011 15:24

1 frag / 2 deathsУчастникwww28 мая 201115:20#13
У меня багов пока нету, кстати?
DevilDevilПостоялецwww28 мая 201115:32#14
RPGman
в этом моя принципиальная позиция
он именно "самый в мире"
есть примеры на которых он может оказаться медленнее - но общая тенденция на "самый быстрый в мире"
с чего ему быть медленнее ?

Страницы: 1 2 3 4 ... 15 ... 28 29 30 Следующая

/ Форум / Программирование игр / Игровая логика и ИИ

2001—2017 © GameDev.ru — Разработка игр