Алгоритм обхода препятствий
Я расматривал два алгоритма, Волновой(алгоритм Ли) и А*. Для меня проще волновой, но он требует много памяти для исполнения, не у каждого телефона будет достаточно памяти чтобы подсчитывать путь для 50 юнитов(+ еще 50 у противника). А* оптимальнее, но я не знаю как это реализовать на паскале, может кто-нибудь написать хотябы псевдокод :rolleyes:
|
Ответ: Алгоритм обхода препятствий
Легко, правда моя рекурсия не корректно строила пути.
Код:
Var После заполнения Массива Карты B, сдвигаем юнита на ячейку с меньшим значением. Вот и все. Так двигался мой бот. На ранних этапах проект работал корректно, но после поиск стал идти кругами, что и логично в общем. Поэтому интересно услышать что нибудь по-поводу рекурсии поиска, и что собственно не так. |
Ответ: Алгоритм обхода препятствий
Вложений: 1
Бот бегает по карте и собирает квадратики.
Вот версия того что описано выше, но без рекурсии( зы. Раньше ни как не получалось ее сделать), здесь зациклен поиска пути, но это не эффективно в плане быстродействия. |
Ответ: Алгоритм обхода препятствий
Спасибо, я примерно таким же способом хотел, но это сильно ударит по памяти( размер мира массив[0..55,0..60] это максимальный размер). Может для экономии памяти просто сделать так: если точка слева от юнита уменьшать Х если на пути препятствие, то сменить направление вверх(тогда точка слева внизу) и приблежать юнита к точке, если опять препятствие, то снова сменить направление.
|
Ответ: Алгоритм обхода препятствий
Тоже мучаюсь с этой проблемой, недавно наткнулся на ссылку алгоритмы поиска пути и заинтересовался методом Best-First Search, на мой взгляд он самый оптимальный, но не как не получается написать код на паскале, то кругами идёт, то стоит, кто-нибудь помогите.:SOS:
|
Ответ: Алгоритм обхода препятствий
Цитата:
|
Ответ: Алгоритм обхода препятствий
Цитата:
Если точка слева вверху от юнита, то просто идём к ней, если на пути встречается препятствие смотрим на лево и на право в радиусе двух клеток. Самую ближайшую свободную клетку назначаем временной точкой. После назначения юнит подходит к временной точке, вр. точка :=0; Идём к основной точке, если опять препятствие, то повторяем процедуру и так пока не доберётся до неё. Сейчас компьютер не рядом, завтра кину код. |
Ответ: Алгоритм обхода препятствий
Если мир динамичный, то следует взять тот же астарс. Но расчет вести не от юнита к цели, а наоборот. В этом случае не придется вносить в память стоимость пути и родительские клетки. Получается что мы расчитываем не полностью короткий путь, а последовательно с каждым циклом находим клетку куда он должен идти. В последствии пройдет ровно такой же путь как и астарс, плюс спокойная реакция на изменения на карте
|
Ответ: Алгоритм обхода препятствий
Вот алгоритм:
1.Движемся к точке. 2.Если препятсвтие, то... 3.Сканиреуем мир в радиусе двух клеток от юнита на препятствия. 4.Затем, среди каждого проходимого блока ищем точку наимение удалённую от координат дома.(с этим проблем нет) 5. Координаты полученные в п.4 запоминаем и передвигаем юнита к этой точке 6. Продолжаемся двигаться к точке, указанной в п.1, если опять препятсвие повторяем. Проблема в том, что могут возникнуть препятсвие даже между этой временной точкой. Я присваивал блоку в п.4 значения не проходимого блока и опять запускал процедуру уже не расматривая этот блок, но юнит то стоит на месте, то идет вообще непонятно куда. PHP код:
|
Часовой пояс GMT +4, время: 18:42. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot