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