forum.boolean.name - A* и способы его оптимизации

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - A* и способы его оптимизации (http://forum.boolean.name/showthread.php?t=1603)

A* и способы его оптимизации

Для тех кто не в теме смотрите эту тему...

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

каждый из этих методов можно реально оптимизировать... обэтом и будет сей топ.

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

дак вот, разобравшись в стратегии действия алгоритма пишем программу:

ИМХО что надо в основном роптимизировать, дак это расстановку чисел, т.е. первый проход... обратный проход по расставленным стоимостям передвижения в большой оптимизации не нуждается поскольку прост как 2 байта... обратный проход мной рассмотрен не будет...

допустим нам надо будет идти из точки А с координатами (15,15)

Код:

Graphics 640,480,32,2



Dim Map(20,20)



ax=15

ay=15



For i=1 To 20

 For j=1 To 20

  Map(i,j)=0

 Next

Next 





Map(5,5)=-1

Map(5,6)=-1

Map(5,7)=-1

Map(5,8)=-1

Map(5,9)=-1

Map(5,10)=-1

Map(5,11)=-1





Map(ax,ay)=1





For i=2 To 19

 For j=2 To 19

  f=10000

  If Map(i,j)>=0 Then

  If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



  If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

  If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

  If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

  If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



  If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

 Next

Next 





For i=1 To 20

 For j=1 To 20

  Text i*15,j*15,Str(Map(i,j))

 Next

Next 



WaitKey()

думаю программу объяснять не надо... просто прочесываем весь массив и выставляем следующую стоимость в следующей пустой клетке...

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

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

можно ведь взять и просто повернуть циклы в обратном направлении..

Код:



Graphics 640,480,32,2



Dim Map(20,20)



ax=15

ay=15



For i=1 To 20

 For j=1 To 20

  Map(i,j)=0

 Next

Next 





Map(5,5)=-1

Map(5,6)=-1

Map(5,7)=-1

Map(5,8)=-1

Map(5,9)=-1

Map(5,10)=-1

Map(5,11)=-1





Map(ax,ay)=1





For i=2 To 19

 For j=2 To 19

  f=10000

  If Map(i,j)>=0 Then

  If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



  If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

  If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

  If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

  If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



  If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

 Next

Next 





For i=19 To 2 Step -1

 For j=19 To 2 Step -1

  f=10000

  If Map(i,j)>=0 Then

  If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



  If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

  If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

  If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

  If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



  If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

 Next

Next 





For i=1 To 20

 For j=1 To 20

  Text i*15,j*15,Str(Map(i,j))

 Next

Next 



WaitKey()



End

теперь после двух проходов у нас получается полностью заполненная стоимостями передвижения карта...

я чуть не подпрыгнул на диване когда придумал такой метод... но вскоре мой пыл утих поскольку у метода есть существенный недостаток а именно:

продлим стенку вниз

Код:



Graphics 640,480,32,2



Dim Map(20,20)



ax=15

ay=15



For i=1 To 20

 For j=1 To 20

  Map(i,j)=0

 Next

Next 





Map(5,5)=-1

Map(5,6)=-1

Map(5,7)=-1

Map(5,8)=-1

Map(5,9)=-1

Map(5,10)=-1

Map(5,11)=-1

Map(5,12)=-1

Map(5,13)=-1

Map(5,14)=-1

Map(5,15)=-1

Map(5,16)=-1

Map(5,17)=-1





Map(ax,ay)=1





For i=2 To 19

 For j=2 To 19

  f=10000

  If Map(i,j)>=0 Then

  If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



  If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

  If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

  If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

  If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



  If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

 Next

Next 





For i=19 To 2 Step -1

 For j=19 To 2 Step -1

  f=10000

  If Map(i,j)>=0 Then

  If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



  If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

  If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

  If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

  If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



  If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

 Next

Next 





For i=1 To 20

 For j=1 To 20

  Text i*15,j*15,Str(Map(i,j))

 Next

Next 



WaitKey()



End

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

еще один недостаток:

если мы загнем наше препятствие снизу, то получим вообще белое пятно которое не рассчитано

Код:



Graphics 640,480,32,2



Dim Map(20,20)



ax=15

ay=15



For i=1 To 20

 For j=1 To 20

  Map(i,j)=0

 Next

Next 





Map(6,5)=-1

Map(6,6)=-1

Map(6,7)=-1

Map(6,8)=-1

Map(6,9)=-1

Map(6,10)=-1

Map(6,11)=-1

Map(6,12)=-1

Map(6,13)=-1

Map(6,14)=-1

Map(6,15)=-1

Map(6,16)=-1

Map(6,17)=-1

Map(5,17)=-1

Map(4,17)=-1

Map(3,17)=-1







Map(ax,ay)=1





For i=2 To 19

 For j=2 To 19

  f=10000

  If Map(i,j)>=0 Then

  If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



  If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

  If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

  If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

  If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



  If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

 Next

Next 





For i=19 To 2 Step -1

 For j=19 To 2 Step -1

  f=10000

  If Map(i,j)>=0 Then

  If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



  If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

  If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

  If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

  If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



  If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

 Next

Next 





For i=1 To 20

 For j=1 To 20

  Text i*15,j*15,Str(Map(i,j))

 Next

Next 



WaitKey()



End

здесь мы видим недостаток... таким образом из угла небыло бы выхода вобще...

посидев и хорошо подумав я всетаки дошел как усовершенствовать свой метод...

все оказалось проще чем я ожидал:

Код:



Graphics 640,480,32,2



Dim Map(20,20)



ax=15

ay=15



For i=1 To 20

 For j=1 To 20

  Map(i,j)=0

 Next

Next 





Map(6,5)=-1

Map(6,6)=-1

Map(6,7)=-1

Map(6,8)=-1

Map(6,9)=-1

Map(6,10)=-1

Map(6,11)=-1

Map(6,12)=-1

Map(6,13)=-1

Map(6,14)=-1

Map(6,15)=-1

Map(6,16)=-1

Map(6,17)=-1

Map(5,17)=-1

Map(4,17)=-1

Map(3,17)=-1







Map(ax,ay)=1





For ij=1 To 2



 For i=2 To 19

  For j=2 To 19

  f=10000

  If Map(i,j)>=0 Then

    If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j) 



    If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

    If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

    If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

    If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



    If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

  Next

 Next 





 For i=19 To 2 Step -1

  For j=19 To 2 Step -1

  f=10000

  If Map(i,j)>=0 Then

    If f>Map(i,j) And Map(i,j)>0 Then f=Map(i,j)



    If f>Map(i+1,j) And Map(i+1,j)>0 Then f=Map(i+1,j)

    If f>Map(i-1,j) And Map(i-1,j)>0 Then f=Map(i-1,j)

    If f>Map(i,j+1) And Map(i,j+1)>0 Then f=Map(i,j+1)

    If f>Map(i,j-1) And Map(i,j-1)>0 Then f=Map(i,j-1)



    If f<>10000 And f<>Map(i,j) Then Map(i,j)=f+1



  EndIf

  Next

 Next 



Next

For i=1 To 20

 For j=1 To 20

  Text i*15,j*15,Str(Map(i,j))

 Next

Next 



WaitKey()



End

просто напросто повторяем эти два прохода (цикл ij) и теперь у нас полноценная карта со стоимостями в любую ее точку

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

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

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

буду рад объективной критике, и конструктивным предложениям (а-ля делитесь опытом)

:)

Re: A* и способы его оптимизации

Цитата:

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

приведи пример когда это нужно?

Цитата:

на списках как я думаю было бы намного дольше.

не знаю что такое "на списках", думаю ты имел в виду поиск в глубину, только рекурсия заменена на стек посещенных клеток, так?
у тебя сложность алгоритма O(N^2), т.е. в примере когда ты считаешь для N=400 (20x20 клеток) это уже долговато получается, если брать "боевые" условия, например походовую стратегию с размером карты 512х512 (N=262144) в несколько проходов - это абзац.
Оптимизации:
двухсторонний поиск - т.е. ищем поочередно с точки отправления и точки назначения
иерархический поиск - бьем карту на взаимно недостижимые части (типа районы города или области страны) и находим глобальный путь на большой карте, и пути к "выходам" на "мальеньких".
ЗЫ: "заступы и вилы";-)

Ответ: A* и способы его оптимизации

ffinder
двухстороний может дать O(2*N^2) :D
иеархический поиск рулз :)

Ответ: A* и способы его оптимизации

Цитата:

приведи пример когда это нужно?

в играх, когда допустим ты не учитываеш третью координату - "воздух" т.е. юниты, боты передвигаются у тебя по плоскости !!
хотя этот алгоритм можна использовать даже в том случае когда боты все таки перемещаются и вверх\вниз (допустим: ступеньки, лифт, ящики) !! Просто усключаем эти условия с алгоритма !! а взаимодействия с ними организовуем другим образом !!

Ответ: A* и способы его оптимизации

2 IGR:
я спрашивал про

Цитата:

высчитывать дорогу до многих мест одновременно располагающихся динамично

2 jimon:

Цитата:

двухстороний может дать O(2*N^2) :D

в данной реализиции - да, но это грубо говоря еще и не поиск пути, а только рассчет расстояний достижимости для всех точек карты. Конкретный маршрут этот алгорритм не дает. Плюс я не уверен что там с ячейками на границах - они считаются или нет?

ЗЫ: и еще - сложность у алгоритма все таки O(2*N), а вот размер данных растет как N^2

Ответ: A* и способы его оптимизации

2 alcoSHoLiK:
я в курсе
просто при сравнениях нескольких версий одного алгоритма желательно знать не как он будет себя вести при бесконечно возрастающих наборах данных, а при конкретных значениях, в этом случае N и 2*N совсем разные вещи, если N = 500000 к примеру

Ответ: A* и способы его оптимизации

2 ffinder
Ну это просто ,мне кажется. Два объекта двигаются , надо найти путь до каждого. Путь ищут сразу до обоих. Допустим когда мы найдём пути до каждого мы выберем куда нам нужнее

Ответ: A* и способы его оптимизации

Копну немного...

Занимаюсь сейчас реализацией поиска путей на основе алгоритма A* для 3D.
Так как я новичек в поиске путей, то появились следующие вопросы:

Что такое иерархический поиск?
Какую эвристическую функцию выбрать для поиска путей в 3D
Стоит ли сортировать открытый список при добавлении вэйпоинтов для просмотра.
Может еще какой совет дадите? :)

Ответ: A* и способы его оптимизации

Жаль что ни у кого нет идей по данным вопросам :(

Ответ: A* и способы его оптимизации

Привет !!
В книге "Artificial Intelligence for Games"
есть описание иерархического поиска !!
я все книгу выложить немогу, да и серфить тоже - у мя ЖПРС !!
по этому вырву пару страниц там где Hierarchcal Pathfinding !!
книга на Английском !!
когда оч нравилось писать всякие АИ-штучки !! то пытался реализовать !! где-то валяются недо-исходники на блице !! но найти чет не получается !!

можешь потом потом найти и скачать всю книгу !! есть что почитать !!
а если найдешь и диск с сорцами - с мну пиво !! ;)

Ответ: A* и способы его оптимизации

IGR
Может _http://github.com/idmillington/aicore ?

Ответ: A* и способы его оптимизации

Хм... многоуровневый A-star ... занимательное чтиво, спасибо! Как приеду домой обязательно найду эту книжку и почитаю. Инстансинг в поиске путей я скорее всего быстро не одолею, но иерархический поиск попробовать в Юнити реализовать вполне реальная задачка...

Ответ: A* и способы его оптимизации

h1dd3n, да вроде бы оно !! Спасибо !!

Ответ: A* и способы его оптимизации

Судя по коду это вовсе не А* а обычный алгоритм заливки (алгоритм Дикстры, точнее его жалкое подобие), причем если вы построите хороший лабиринт, то он не зальет даже карту целиком.
Отличие алгоритма А* от Дикстры в том, что волновой поиск "включается" только при столкновении с препятствием, а до этого он работает как обычный алгоритм приближения.
Алгоритм Дикстры используется когда нужно найти хотя-бы один объект из множества. Пример Dune2 спайса много, харвестер один, пускаем волновую заливку во все стороны пока не наткнемся на спайс. Далее прокладываем путь.
Его можно также наверное использовать чтобы проложить путь от цели к группе юнитов.
А* используется только когда нужно проложить путь для одного юнита.