Поиск оптимального маршрута юнита к цели на неизвестной карте — одна из самых сложных задач при разработке игры. К счастью, существует некоторое количество алгоритмов, которые решают эту задачу. Есть и отличная библиотека PathFinding.js с поддержкой 11 таких алгоритмов.
Библиотеку легко интегрировать в любую веб-игру. Говорят, она отлично оптимизируется под конкретные архитектуры, при этом производительность возрастает на порядок.
По адресу http://qiao.github.com/PathFinding.js/visual есть онлайн-демо с симпатичной визуализацией выполнения алгоритмов. Здесь скорость искусственно занижена (для красоты).
Сейчас поддерживается 11 алгоритмов:
-
AStarFinder
* -
BreadthFirstFinder
* -
BestFirstFinder
-
DijkstraFinder
* -
BiAStarFinder
-
BiBestFirstFinder
-
BiDijkstraFinder
* -
BiBreadthFirstFinder
* -
JumpPointFinder
* -
OrthogonalJumpPointFinder
* -
Trace
Для алгоритмов реализованы три эвристики расчёта расстояния: Manhattan (расстояние городских кварталов), евклидова метрика и расстояние Чебышёва. Каждая из них использует эвристический анализ, чтобы определить перспективность возможного направления дальнейшего пути, то есть каково расстояние от соседних квадратов до цели, в соответствии с определением расстояния.
Автор: alizar