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



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

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

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

    Сейчас поддерживается 11 алгоритмов:
    • AStarFinder *
    • BreadthFirstFinder *
    • BestFirstFinder
    • DijkstraFinder *
    • BiAStarFinder
    • BiBestFirstFinder
    • BiDijkstraFinder *
    • BiBreadthFirstFinder *
    • JumpPointFinder *
    • OrthogonalJumpPointFinder *
    • Trace

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

    Подробнее
    Реклама
    Комментарии 14
    • +6
      А сейчас появилась и отличная библиотека

      Сейчас появилась??? Я этой библиотекой пользовался ещё гдето 2 года тому назад. А первый коммит на гитхабе вообще датирован 2011 годом.
      • –11
        А теперь все будут пользоваться! :)
        • +7
          так и надо «А сейчас появилась моя заметка про отличную библиотеку...»
          • 0
            Я думал это новая библиотека, извините.
            • +1
              даже не заглядывая в комменты, просто на странице проекта промотать вниз и там видим "© 2011-2012 Xueqiao Xu".
              • +5
                Да, в следующий раз буду внимательнее.
              • +2
                утверждать не буду, но о ней кстати даже пост на хабре был. ну или у этого поста очень похожая картинка.
                • 0
                  Библиотека года 2 назад в одном дайджесте проскакивала. Без картинки.
                  • +2
                    ну картинку я тоже помню. там же, кстати, и ссылка на эту визуализацию
                    habrahabr.ru/post/162915/#comment_5599595

                    возможно из этой статьи я на нее и наткнулся
        • 0
          А есть там эффективный алгоритм для прокладывания красивого сглаженного маршрута на карте со стороной не в десятки клеток, а в десятки тысяч? :) Лет 6 назад решал такую задачу на Java, но в некоторых случаях всё равно перемещаемый объект цеплялся за близкие стены. Надо было ещё и учёт радиуса добавлять, но проект накрылся раньше, чем маршрутизатор был допилен.
          • +2
            Вот такая штука как D* гораздо круче, так как может в реальном времени устойчиво работать в динамических и неизвестных средах. Широко применяется в робототехнике, а в играх, наверное, такие навороты просто не нужны.
            • 0
              А что за алгоритм «Trace»?
              • 0
                Надо бы к этому ещё распознавание карт прикрутить и будет идеальный инструмент для спортсменов-ориентировщиков.
                • +3
                  А я надеялся (пока автора не разглядел), что будет длинная красивая статья про алгоритмы, а тут реклама библиотеки.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.