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

в 13:30, , рубрики: game development, javascript, path-finding, Алгоритмы, поиск пути

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

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

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

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

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

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

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

Автор: alizar

Источник

Поделиться

* - обязательные к заполнению поля