Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 29.09.2006, 20:32   #1
SubZer0
Администратор
 
Аватар для SubZer0
 
Регистрация: 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
ffinder
Дэвелопер
 
Аватар для ffinder
 
Регистрация: 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
jimon
 
Сообщений: n/a
Ответ: A* и способы его оптимизации

ffinder
двухстороний может дать O(2*N^2) :D
иеархический поиск рулз
 
Ответить с цитированием
Старый 12.01.2008, 22:27   #4
IGR
Blitz's Shame !!
 
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений
(для 2,013 пользователей)
Ответ: A* и способы его оптимизации

приведи пример когда это нужно?
в играх, когда допустим ты не учитываеш третью координату - "воздух" т.е. юниты, боты передвигаются у тебя по плоскости !!
хотя этот алгоритм можна использовать даже в том случае когда боты все таки перемещаются и вверх\вниз (допустим: ступеньки, лифт, ящики) !! Просто усключаем эти условия с алгоритма !! а взаимодействия с ними организовуем другим образом !!
(Offline)
 
Ответить с цитированием
Старый 13.01.2008, 12:36   #5
ffinder
Дэвелопер
 
Аватар для ffinder
 
Регистрация: 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
alcoSHoLiK
Дэвелопер
 
Регистрация: 17.01.2006
Сообщений: 1,512
Написано 78 полезных сообщений
(для 110 пользователей)
Ответ: A* и способы его оптимизации


O(a*N) = O(N). Констанста иррелевантна. Зависимость показывается лишь степенью операнда. Так, любое O(a*N) предпочтительней, чем O(N^2).
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
HolyDel (10.07.2010)
Старый 13.01.2008, 14:21   #7
ffinder
Дэвелопер
 
Аватар для ffinder
 
Регистрация: 10.09.2007
Сообщений: 1,442
Написано 793 полезных сообщений
(для 1,460 пользователей)
Ответ: A* и способы его оптимизации

2 alcoSHoLiK:
я в курсе
просто при сравнениях нескольких версий одного алгоритма желательно знать не как он будет себя вести при бесконечно возрастающих наборах данных, а при конкретных значениях, в этом случае N и 2*N совсем разные вещи, если N = 500000 к примеру
(Offline)
 
Ответить с цитированием
Старый 16.01.2009, 03:39   #8
CRASHER
Разработчик
 
Регистрация: 08.03.2007
Сообщений: 530
Написано 31 полезных сообщений
(для 36 пользователей)
Ответ: A* и способы его оптимизации

2 ffinder
Ну это просто ,мне кажется. Два объекта двигаются , надо найти путь до каждого. Путь ищут сразу до обоих. Допустим когда мы найдём пути до каждого мы выберем куда нам нужнее
(Offline)
 
Ответить с цитированием
Старый 05.07.2010, 11:56   #9
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: A* и способы его оптимизации

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

Занимаюсь сейчас реализацией поиска путей на основе алгоритма A* для 3D.
Так как я новичек в поиске путей, то появились следующие вопросы:
  1. Что такое иерархический поиск?
  2. Какую эвристическую функцию выбрать для поиска путей в 3D
  3. Стоит ли сортировать открытый список при добавлении вэйпоинтов для просмотра.
  4. Может еще какой совет дадите?
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Старый 07.07.2010, 23:51   #10
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: A* и способы его оптимизации

Жаль что ни у кого нет идей по данным вопросам
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Старый 10.07.2010, 00:59   #11
IGR
Blitz's Shame !!
 
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений
(для 2,013 пользователей)
Ответ: A* и способы его оптимизации

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

можешь потом потом найти и скачать всю книгу !! есть что почитать !!
а если найдешь и диск с сорцами - с мну пиво !!
Вложения
Тип файла: pdf CUT Hierarchcal Pathfinding.pdf (268.9 Кб, 991 просмотров)
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо IGR за это полезное сообщение:
h1dd3n (10.07.2010), pax (10.07.2010)
Старый 10.07.2010, 01:38   #12
h1dd3n
Бывалый
 
Аватар для h1dd3n
 
Регистрация: 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
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: A* и способы его оптимизации

Хм... многоуровневый A-star ... занимательное чтиво, спасибо! Как приеду домой обязательно найду эту книжку и почитаю. Инстансинг в поиске путей я скорее всего быстро не одолею, но иерархический поиск попробовать в Юнити реализовать вполне реальная задачка...
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Старый 10.07.2010, 02:19   #14
IGR
Blitz's Shame !!
 
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений
(для 2,013 пользователей)
Ответ: A* и способы его оптимизации

h1dd3n, да вроде бы оно !! Спасибо !!
(Offline)
 
Ответить с цитированием
Старый 21.01.2011, 23:25   #15
Evgen
Разработчик
 
Аватар для Evgen
 
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 419
Написано 68 полезных сообщений
(для 100 пользователей)
Ответ: A* и способы его оптимизации

Судя по коду это вовсе не А* а обычный алгоритм заливки (алгоритм Дикстры, точнее его жалкое подобие), причем если вы построите хороший лабиринт, то он не зальет даже карту целиком.
Отличие алгоритма А* от Дикстры в том, что волновой поиск "включается" только при столкновении с препятствием, а до этого он работает как обычный алгоритм приближения.
Алгоритм Дикстры используется когда нужно найти хотя-бы один объект из множества. Пример Dune2 спайса много, харвестер один, пускаем волновую заливку во все стороны пока не наткнемся на спайс. Далее прокладываем путь.
Его можно также наверное использовать чтобы проложить путь от цели к группе юнитов.
А* используется только когда нужно проложить путь для одного юнита.
Миниатюры
Нажмите на изображение для увеличения
Название: pathfind.jpg
Просмотров: 976
Размер:	200.1 Кб
ID:	12436  
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Способы уменьшить вес PNG-картинок Sanya MidletPascal 13 09.05.2009 14:25
Способы сжатия графики Phantom FAQ 26 12.10.2008 20:24
Достижения Оптимизации johnk 3D-программирование 42 19.08.2007 13:46
Способы отметить новый год jimon Юмор 1 23.11.2006 23:53
Методы оптимизации MiXaeL FAQ 21 04.10.2006 08:44


Часовой пояс GMT +4, время: 14:08.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com