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

Question

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

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

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

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

Answer 1

Вот C# implementation, сделанный одним из людей, которые строят язык.

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

Вот JavaScript implementation, наряду с source code и online demo я сделал в качестве хобби/исследовательского проекта.

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

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

Оптимизированный Java implementation доступен в GraphHopper.

Answer 9

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

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

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 Demo in different languages

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

Answer 10

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

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

Answer 11

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