PathFinder : Demo
Предлагаю вашему вниманию, собственную реализацию вспомогательного framework по обнаружению минимального пути в графе. На данном этапе разработки, PathFinder, поддерживает два алгоритма: алгоритм Дейкстры и «А» звезда. Алгоритмы изрядно изменены, для максимальной совместимости с framework, за основу взяты лишь идеи этих алгоритмов.
Достоинства и недостатки реализованных алгоритмов.
Алгоритм Дейкстры:
+ точное обнаружение минимально пути в графах любой сложности;
+ позволяет обнаруживать путь в сложных/запутанных графах;
- в 3 раза медленнее, чем алгоритм «А» звезда;
Алгоритм «А» звезда:
+ быстрый метод обнаружения пути;
+ идеально подходит для графов с принципом построения как у «королевского» графа;
- некорректно находит путь в сложных/запутанных графах;
Зачёт! Как-раз искал реализации не так давно, – ничего путнего не нашёл… Так-что доделывай и выкладывай ::)))
баг
http://s3.amazonaws.com/floomby/1_3_2010/vVNP2w3rL0WQOU2beCs1Fg.png
Это нюанс первой реализации А*. Я отказался от многих нюансов реализации этого алгоритма, осталась лишь главная идея.