Здравствуйте, Tankist, Вы писали:
T>Помогите найти реализацию алгоритма A* или другого на c++.
T>Или помогите найти путь из пункта А в пункт Б в поле с произвольно раставленными стенками...никогда раньше этим не занимался и не знаю что делать
((
Тут выше правильно сказали про метод волны, но куда оптиматьнее алгоритм Дейкстры.
Его я бы порекомендовал применять, если условия прохода через каждую точку разные(вода и земля — проще пройти по земле, чем плыть).
Все эти алгоритмы можно найти в любом учебнике, FAQ и т.д. по графам.
Раз речь пошла про волну, то алгоритм крайне прост.Расскажу, не касаясь теории графов.
Пусть у тебя есть пространство, описанное графом(клеточный вид — частный случай).
Мы находимся в точке A:
шаг 1: Находим все точки, в которые мы можем попасть из текущей точки, и помечаем их
(удобно помечать номером итерации)
шаг 2: если среди них оказалась точка B, то завершаем работу алгоритма,
иначе для каждой точки i-того уровня(найденные точки на текущей итерации)выполняем шаг 1 и шаг 2
Всё.
Мы придем из A в B за число шагов равное кол-ву волн. И всего-то.
Если у тебя 3В пространство с комнатами, стенами, то можно и не связываться с клеточным представлением, а указать узлы пространства, и построить на основе их граф.
Помогите найти реализацию алгоритма A* или другого на c++.
Или помогите найти путь из пункта А в пункт Б в поле с произвольно раставленными стенками...никогда раньше этим не занимался и не знаю что делать
((
Здравствуйте, Tankist, Вы писали:
T>Помогите найти реализацию алгоритма A* или другого на c++.
T>Или помогите найти путь из пункта А в пункт Б в поле с произвольно раставленными стенками...никогда раньше этим не занимался и не знаю что делать((
если нет возможности построить заранее граф достижимости — один из наиболее эффективных алгоритмов это волновой обход... но это — при условии разбиения пространства на клетки... насколько я помню, его можно адаптировать и к неразбитым пространствам...
... << RSDN@Home 1.1 beta 2 >>
Если при компиляции и исполнении вашей программы не происходит ни одной ошибки — это ошибка компилятора :)))
Здравствуйте, Tankist, Вы писали:
T>Помогите найти реализацию алгоритма A* или другого на c++.
T>Или помогите найти путь из пункта А в пункт Б в поле с произвольно раставленными стенками...никогда раньше этим не занимался и не знаю что делать((
Скорее всего реализацию алгоритма придется писать самому. Главное знать, в чем состоит алгоритм!
Почитай про это дело на dtf.ru. Там в статьях, вроде для разработчиков.
Алгоритм А* (), насколко я определил, является самым гибким. Его описание и реализации посмотрите здес:
http://www.geocities.com/jheyesjones/oldastar.html
Если условия прохождения обьекта однородные — то быстрее будут работать специальные алгоритмы. Я могу кинуть их описание вам, если нужно. Мне самому понадобился именно А*.
Здравствуйте, Nicolay, Вы писали:
N>Тут выше правильно сказали про метод волны, но куда оптиматьнее алгоритм Дейкстры.
Все зависит от конкретных особенностей задачи. Если игровое поле 256x256, условия прохода через каждую точку разные, и считать надо для каждого юнита... То мощности CPU может и не хватить
.
