Можем ли мы заставить людей публиковать коды простых, оптимизированных реализаций алгоритма поиска A * на всех языках?
Это в основном для удовольствия и для игры с тем, что может сделать сам stackoverflow... хотя мне действительно интересно получить версию ActionScript 3 этого.
Но идея состоит в том, что этот "Вопрос" будет по-прежнему постоянно обновляться в будущем, даже когда будут созданы разные языки программирования!
Я не знаю ни одного другого места в Интернете, где вы можете увидеть псевдокод, "переведенный" на многие (и намного меньше) разные языки. Похоже, что это полезный ресурс, и, хотя он и не обязательно был предназначен для этого сайта, нет никакого вреда в его проверке и, если окажется, что это будет полезно для использования stackoverflow!
Вот реализация JavaScript, а также исходный код и онлайн-демонстрация Я сделал это как хобби/исследовательский проект.
Это очень просто, но вы можете изменить некоторые параметры (размер сетки, количество стен, отладка информации вкл/выкл). Он покажет вам рассчитанные значения f (x), g (x) и h (x) для каждого проверяемого node.
В реализации демонстрационной страницы используется jQuery.
Здесь реализация С++. Он довольно хорошо протестирован к настоящему времени и используется в коммерческих видеоиграх и различных проектах AI.
http://code.google.com/p/a-star-algorithm-implementation/
И вот учебник, который я на самом деле написал первым:
Здесь реализация С#, сделанная одним из людей, которые строят язык.
Исходные коды и демонстрации на разных языках программирования:
Список демо для каждого языка:
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 на разных языках
Наслаждайтесь:)
Пример AS 3... http://www.dauntless.be/astar/
A Clojure реализация, в значительной степени основанная на примере, приведенном в PAIP.
Не реализация, но я нашел http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html, чтобы быть особенно ясным объяснением алгоритма. Имеет псевдокод, который делает его очень простым в реализации, а также расширенный обзор различных структур данных, которые могут быть использованы для реализации открытых и закрытых множеств, обсуждение различных эвристик, которые применимы в разных ситуациях, изменения эвристики для получения определенного поведения (например, получение аппроксимаций прямых линий в системах, которые поддерживают только ограниченные углы перемещения), общие ошибки (например, с использованием эвристики с разным масштабом до фактических затрат на перемещение) и некоторые оптимизации (например, работа с областями однородной стоимости, сетка).
исходный код Python и С++, а также интерактивное руководство, Код написан для работы на графиках в целом и не является специфичным для сеток (как вы найдете во многих примерах A * в Интернете). Он использует двоичные кучи для очереди приоритетов (оба Python и С++ имеют двоичные кучи в своих стандартных библиотеках). У меня есть Breadth First Search, Dijkstra Algorithm и A * на этой странице. Код достаточно короткий (короче, чем большинство примеров кода A *, которые я нахожу).
Реализация VB6.
http://www.gandraxa.com/pathfinding_with_a_star.xml
Это особенно полезно, потому что вы можете пройти через этот процесс и получить хорошее представление о том, как работает алгоритм. Это может быть весьма полезно при преобразовании алгоритма на другой язык.
Оптимизированная реализация Java доступна в GraphHopper.
Я реализовал A * в C как способ узнать C, поэтому я не могу обещать это красиво, но он работает! Я использовал его для решения Project Euler # 83, и он работал над двумя тестовыми примерами.
https://github.com/PeterMitrano/A-star-Pathfinding/blob/master/problem_83.c