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

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

Это в основном для удовольствия и для игры с тем, что может сделать сам stackoverflow... хотя мне действительно интересно получить версию ActionScript 3 этого.

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 3

Здесь реализация С#, сделанная одним из людей, которые строят язык.

Ответ 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 на разных языках

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

Реализация VB6.

http://www.gandraxa.com/pathfinding_with_a_star.xml

Это особенно полезно, потому что вы можете пройти через этот процесс и получить хорошее представление о том, как работает алгоритм. Это может быть весьма полезно при преобразовании алгоритма на другой язык.

Ответ 10

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

Ответ 11

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

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