Алгоритмы поиска путей на JavaScript

Поиск оптимального маршрута юнита к цели на неизвестной карте — одна из самых сложных задач при разработке игры. К счастью, существует некоторое количество алгоритмов, которые решают эту задачу. Есть и отличная библиотека PathFinding.js ^[1] с поддержкой 11 таких алгоритмов.

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

По адресу http://qiao.github.com/PathFinding.js/visual ^[2] есть онлайн-демо с симпатичной визуализацией выполнения алгоритмов. Здесь скорость искусственно занижена (для красоты).

Сейчас поддерживается 11 алгоритмов:

• AStarFinder *
• BreadthFirstFinder *
• BestFirstFinder
• DijkstraFinder *
• BiAStarFinder
• BiBestFirstFinder
• BiDijkstraFinder *
• BiBreadthFirstFinder *
• JumpPointFinder *
• OrthogonalJumpPointFinder *
• Trace

Для алгоритмов реализованы три эвристики расчёта расстояния: Manhattan ^[3] (расстояние городских кварталов), евклидова метрика ^[4] и расстояние Чебышёва ^[5]. Каждая из них использует эвристический анализ, чтобы определить перспективность возможного направления дальнейшего пути, то есть каково расстояние от соседних квадратов до цели, в соответствии с определением расстояния.

Автор: alizar

Источник ^[6]