|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
29.09.2006, 20:32
|
#1
|
Администратор
Регистрация: 03.09.2005
Сообщений: 2,408
Написано 301 полезных сообщений (для 996 пользователей)
|
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) и теперь у нас полноценная карта со стоимостями в любую ее точку
в результате, чем сложнее будет путь, тем больше раз надо будет повторять проходы...
у меня в гаме не будет сложнее пути чем за два угла... таким образом я решил сделать два прохода по два вложенных цикла!
самое главное преимущество сего метода состоит в том, что теперь по полученному массиву можно определить до какой цели будет самый краткий путь, просто брать значение ячейки массива и сравнивать...
буду рад объективной критике, и конструктивным предложениям (а-ля делитесь опытом)
__________________
Как минимум я помог многим (с)
|
(Offline)
|
|
12.01.2008, 21:25
|
#2
|
Дэвелопер
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений (для 1,460 пользователей)
|
Re: A* и способы его оптимизации
я взял реализацию на двумерных массивах, поскольку нужно было высчитывать дорогу до многих мест одновременно располагающихся динамично...
|
приведи пример когда это нужно?
на списках как я думаю было бы намного дольше.
|
не знаю что такое "на списках", думаю ты имел в виду поиск в глубину, только рекурсия заменена на стек посещенных клеток, так?
у тебя сложность алгоритма O(N^2), т.е. в примере когда ты считаешь для N=400 (20x20 клеток) это уже долговато получается, если брать "боевые" условия, например походовую стратегию с размером карты 512х512 (N=262144) в несколько проходов - это абзац.
Оптимизации:
двухсторонний поиск - т.е. ищем поочередно с точки отправления и точки назначения
иерархический поиск - бьем карту на взаимно недостижимые части (типа районы города или области страны) и находим глобальный путь на большой карте, и пути к "выходам" на "мальеньких".
ЗЫ: "заступы и вилы";-)
|
(Offline)
|
|
12.01.2008, 22:05
|
#3
|
|
Ответ: A* и способы его оптимизации
ffinder
двухстороний может дать O(2*N^2) :D
иеархический поиск рулз
|
|
|
12.01.2008, 22:27
|
#4
|
Blitz's Shame !!
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений (для 2,013 пользователей)
|
Ответ: A* и способы его оптимизации
приведи пример когда это нужно?
|
в играх, когда допустим ты не учитываеш третью координату - "воздух" т.е. юниты, боты передвигаются у тебя по плоскости !!
хотя этот алгоритм можна использовать даже в том случае когда боты все таки перемещаются и вверх\вниз (допустим: ступеньки, лифт, ящики) !! Просто усключаем эти условия с алгоритма !! а взаимодействия с ними организовуем другим образом !!
|
(Offline)
|
|
13.01.2008, 12:36
|
#5
|
Дэвелопер
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений (для 1,460 пользователей)
|
Ответ: A* и способы его оптимизации
2 IGR:
я спрашивал про
высчитывать дорогу до многих мест одновременно располагающихся динамично
|
2 jimon:
двухстороний может дать O(2*N^2) :D
|
в данной реализиции - да, но это грубо говоря еще и не поиск пути, а только рассчет расстояний достижимости для всех точек карты. Конкретный маршрут этот алгорритм не дает. Плюс я не уверен что там с ячейками на границах - они считаются или нет?
ЗЫ: и еще - сложность у алгоритма все таки O(2*N), а вот размер данных растет как N^2
|
(Offline)
|
|
13.01.2008, 12:44
|
#6
|
Дэвелопер
Регистрация: 17.01.2006
Сообщений: 1,512
Написано 78 полезных сообщений (для 110 пользователей)
|
Ответ: A* и способы его оптимизации
O(a*N) = O(N). Констанста иррелевантна. Зависимость показывается лишь степенью операнда. Так, любое O(a*N) предпочтительней, чем O(N^2).
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
13.01.2008, 14:21
|
#7
|
Дэвелопер
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений (для 1,460 пользователей)
|
Ответ: A* и способы его оптимизации
2 alcoSHoLiK:
я в курсе
просто при сравнениях нескольких версий одного алгоритма желательно знать не как он будет себя вести при бесконечно возрастающих наборах данных, а при конкретных значениях, в этом случае N и 2*N совсем разные вещи, если N = 500000 к примеру
|
(Offline)
|
|
16.01.2009, 03:39
|
#8
|
Разработчик
Регистрация: 08.03.2007
Сообщений: 530
Написано 31 полезных сообщений (для 36 пользователей)
|
Ответ: A* и способы его оптимизации
2 ffinder
Ну это просто ,мне кажется. Два объекта двигаются , надо найти путь до каждого. Путь ищут сразу до обоих. Допустим когда мы найдём пути до каждого мы выберем куда нам нужнее
|
(Offline)
|
|
05.07.2010, 11:56
|
#9
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: A* и способы его оптимизации
Копну немного...
Занимаюсь сейчас реализацией поиска путей на основе алгоритма A* для 3D.
Так как я новичек в поиске путей, то появились следующие вопросы: - Что такое иерархический поиск?
- Какую эвристическую функцию выбрать для поиска путей в 3D
- Стоит ли сортировать открытый список при добавлении вэйпоинтов для просмотра.
- Может еще какой совет дадите?
|
(Offline)
|
|
07.07.2010, 23:51
|
#10
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: A* и способы его оптимизации
Жаль что ни у кого нет идей по данным вопросам
|
(Offline)
|
|
10.07.2010, 00:59
|
#11
|
Blitz's Shame !!
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений (для 2,013 пользователей)
|
Ответ: A* и способы его оптимизации
Привет !!
В книге "Artificial Intelligence for Games"
есть описание иерархического поиска !!
я все книгу выложить немогу, да и серфить тоже - у мя ЖПРС !!
по этому вырву пару страниц там где Hierarchcal Pathfinding !!
книга на Английском !!
когда оч нравилось писать всякие АИ-штучки !! то пытался реализовать !! где-то валяются недо-исходники на блице !! но найти чет не получается !!
можешь потом потом найти и скачать всю книгу !! есть что почитать !!
а если найдешь и диск с сорцами - с мну пиво !!
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо IGR за это полезное сообщение:
|
|
10.07.2010, 01:38
|
#12
|
Бывалый
Регистрация: 19.06.2008
Сообщений: 679
Написано 264 полезных сообщений (для 450 пользователей)
|
Ответ: A* и способы его оптимизации
IGR
Может _http://github.com/idmillington/aicore ?
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо h1dd3n за это полезное сообщение:
|
IGR (10.07.2010), pax (10.07.2010)
|
10.07.2010, 01:45
|
#13
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: A* и способы его оптимизации
Хм... многоуровневый A-star ... занимательное чтиво, спасибо! Как приеду домой обязательно найду эту книжку и почитаю. Инстансинг в поиске путей я скорее всего быстро не одолею, но иерархический поиск попробовать в Юнити реализовать вполне реальная задачка...
|
(Offline)
|
|
10.07.2010, 02:19
|
#14
|
Blitz's Shame !!
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений (для 2,013 пользователей)
|
Ответ: A* и способы его оптимизации
h1dd3n, да вроде бы оно !! Спасибо !!
|
(Offline)
|
|
21.01.2011, 23:25
|
#15
|
Разработчик
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 422
Написано 68 полезных сообщений (для 100 пользователей)
|
Ответ: A* и способы его оптимизации
Судя по коду это вовсе не А* а обычный алгоритм заливки (алгоритм Дикстры, точнее его жалкое подобие), причем если вы построите хороший лабиринт, то он не зальет даже карту целиком.
Отличие алгоритма А* от Дикстры в том, что волновой поиск "включается" только при столкновении с препятствием, а до этого он работает как обычный алгоритм приближения.
Алгоритм Дикстры используется когда нужно найти хотя-бы один объект из множества. Пример Dune2 спайса много, харвестер один, пускаем волновую заливку во все стороны пока не наткнемся на спайс. Далее прокладываем путь.
Его можно также наверное использовать чтобы проложить путь от цели к группе юнитов.
А* используется только когда нужно проложить путь для одного юнита.
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 11:07.
|