Как мне реализовать алгоритм поиска пути A * с затратами на перемещение для каждого языка программирования?

Question

Можем ли мы заставить людей публиковать код простых, оптимизированных реализаций алгоритма поиска пути A * на каждом языке?

Это в основном для развлечения и для игры с тем, на что способен сам stackoverflow ... хотя я на самом деле заинтересован в получении версии ActionScript 3.

Но идея в том, что этот «Вопрос» будет постоянно обновляться в будущем, даже если будут созданы разные языки программирования!

Я не знаю ни одного другого места в Интернете, где можно увидеть псевдокод, «переведенный» на многие (гораздо реже) языки. Похоже, что это полезный ресурс, и хотя он не обязательно предназначен для этого сайта, нет ничего плохого в том, чтобы попробовать его и посмотреть, окажется ли он полезной вещью, для которой можно использовать stackoverflow!

Answer 1

Вот реализация JavaScript вместе с исходным кодом и онлайн-демонстрацией , которую я сделал как хобби / исследовательский проект.

Это очень просто, но вы можете изменить некоторые параметры (размер сетки, количество стен, вкл / выкл отладочной информации). Он покажет вам рассчитанные значения f (x), g (x) и h (x) для каждого проверяемого узла.

Реализация демонстрационной страницы использует jQuery.

Answer 2

Вот реализация C ++. Он довольно хорошо протестирован и используется в коммерческих видеоиграх и различных проектах AI.

http://code.google.com/p/a-star-algorithm-implementation/

И есть учебник, который я написал первым:

http://www.heyes -jones.com / astar.html

Answer 3

Вот реализация C # , выполненная одним из людей, создающих язык.

Answer 4

Исходные коды и демонстрационные версии на разных языках программирования:

Список демоверсий для каждого языка:

C++: 1
Java: 3
Processing: 1
Actionscript 3 (Flash): 4
Flex (Flash): 1
Javascript: 6
C#: 1
Ruby: 1
Prolog: 1
Unity: 1
Lua: 1

Демо Pathfinding на разных языках

Наслаждайтесь:)

Answer 5

Исходный код Python и C ++ вместе с интерактивным учебным пособием . Код написан для работы с графами в целом и не является специфичным для сеток (как вы найдете во многих примерах A * в сети). Он использует двоичные кучи для очереди приоритетов (и в Python, и в C ++ есть двоичные кучи в своих стандартных библиотеках). У меня есть поиск в ширину, алгоритм Дейкстры и A * на этой странице. Код достаточно короткий (короче, чем большинство примеров кода A *, которые я нахожу).

Answer 6

Не реализация, но я обнаружил, что http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html является особенно четким объяснением алгоритма. Имеет псевдокод, который делает его очень простым для реализации, наряду с расширенным обзором различных структур данных, которые могут использоваться для реализации открытых и закрытых множеств, обсуждение различных эвристик, применимых в разных ситуациях, модификаций эвристики для получения специфических поведений (например, получение аппроксимаций прямых линий в системах, которые поддерживают только ограниченные углы движения), распространенные ошибки (например, использование эвристики с масштабом, отличным от фактических затрат на движение), и некоторые оптимизации (например, работа с областями с одинаковыми затратами, а не с сетка).

Answer 7

A Clojure реализация, основанная на примере, приведенном в PAIP .

Answer 8

Пример AS 3 ... http://www.dauntless.be/astar/

Answer 9

Я реализовал A * в C как способ изучения C, поэтому я не могу обещать, что это прекрасно, но это работает! Я использовал его для решения Project Euler # 83, и он работал на двух тестовых примерах.

https://github.com/PeterMitrano/A-star-Pathfinding/blob/master/problem_83.c

Answer 10

Оптимизированная Java-реализация доступна в GraphHopper.