forum.boolean.name - ПП по Вейпоинтам

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

- 2D-программирование (http://forum.boolean.name/forumdisplay.php?f=13)

- - ПП по Вейпоинтам (http://forum.boolean.name/showthread.php?t=3122)

В общем вопрос в следующем.
в чем состоит принцип действия ПП по вейпоинтам.
можно дать ответ в виде статьи.

да кстати А* я реализовал
поступила инфа, что алгоритмы похожи.
чем они отличаются,?

Re: ПП по Вейпоинтам

Для каждого жанра - свой алгоритм ПП. И нада его реализовывать самому ручками...на статью не расчитывай...так как ПП в 2д ничем не отличается ПП в 3д...единственное - это различия в типе сетки.

Re: ПП по Вейпоинтам

Цитата:

да кстати А* я реализовал
поступила инфа, что алгоритмы похожи.
чем они отличаются,?

Ничем.
"Алгоритм путенахождения" и "структура карты путей" - это просто разные понятия, и термины "сходство"/"различие" при их сопоставлении мало уместны. С точки зрения значительной части алгоритмов, реализация карты путей регулярной сеткой (двухмерная матрица, массив) или вейпоинтами (нерегулярная сетка, расставленные "вручную" точки с назначенными им вручную же связями) вообще мало отличается.
...
Не растекаясь мыслию по древу, хочу посоветовать:
1. Запустить в Поиск по форуму слова "путенахождение" и, пардон, "путенах": полагаю, многочисленные обсуждения темы многое разьяснят.
2. Зайти в раздел Библиотек для Блица и взглянуть на мою библиотечку ДЕкзейк: несмотря на то, что она предназначена исключительно для работы с регулярными сетками, может оказать некоторую прикладную пользу.
3. Поискать в архивах старого Блицгеймса (тут существует соотв. тема) или спросить у Джимона: возможно где-то еще сохранились исходники моих старых тестов путенаха по вейпоинтам.

Re: ПП по Вейпоинтам

а если реализовал a*, то мне кажется вейпойнты это ничто иное как клетки по которым возможно передвижение, а остальные клетки - препятствия.
))

Re: ПП по Вейпоинтам

ИМХО:
Иррегулярная сетка предпочтительней в случаях:
А - больших пронстранств
Б - простой геометрии поля (т.е. большие однородные участки, в противоположность тому - запустанные лабиринты (в этом случае я думаю регулярная сетка предпочтительней)).

Re: ПП по Вейпоинтам

насчет поиска пути курим доклад Андрея Плахова с КРИ 2003 =)

Re: ПП по Вейпоинтам

Нерегулярная сетка - применяется наоборот в играх со сложной формой и конфигурацией ландшафта, препятствий....(так как все препятствия - будет проблематично привязать к регулярной сетке...)

Re: ПП по Вейпоинтам

у мну поиск по вейпоинт карте идет волновым путем :)
просто карты у меня обычно маленькие (вейпоинт карты - не больше 120 обычно) и применять A* смысла нету

Re: ПП по Вейпоинтам

Всем спасибо за ответы.

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

сначала в памяти сохраняем множество карт путей по алгоритму Флойда. расположенных рядом друг с другом.(много карт потому что по флойду время высчитывание самих карт и объем карт в кубической зависимости от кол-во вейпоинтов)
доставание карт из памяти составляем очень и очень мала времени так как все пути уже прописаны.
ну вот создаем множество квадратных карт рядом и одну общюю карту на все. если точка оправки и назначения у движимого объекта находятся в одном квадрате то поиск пути осуществляем в нем если в разных то поиск пути осуществляем сначала в общем квадрате который на всю карту а потом как точки (прибытия и отправки) будут находиться в одном маленьком квадрате поиск осуществляем по нему.

думаю понятно.

Re: ПП по Вейпоинтам

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

ЗЫ: Джокх - была необходимость)

Re: ПП по Вейпоинтам

протестил еще раз дикзейк..
подумал что не флойд все таки... слишком долго. и вейпоинтов много.
но баги теже....

тоесть эффект практически тот же(всего в 500 раз медленнее(это нормально если учесть что флойд за секунду 100000 найдет путь)) но вейпоинтов раз в 500 больше можно поствить.

Re: ПП по Вейпоинтам

2 Лейто:

0. В DExeik ней вейпоинтов. В DExeik используется регулярная сетка aka двухмерный массив. Упоминания тождества неуместны.

1. В DExeik не используется поиск по Флойду.

2. Смею преискреннейше заверить, что Ваш покорный ни в коей мере не настаивает на использовании DExeik с его многочисленными недостатками, огрехами, глюками, багами и крайне низкой производительностью вообще, и его использовании г-ном Лейто в частности. Ежели г-ну Лейто преблагоугодно использовать алгоритм Флойда, или даже алгоритм Уоршолла, то Ваш покорный не вправе упрекать г-на Лейто в таковом предпочтении, поелику обратное было бы прямым ущемлением прав г-на Лейто.

3. Засим, имею смелость нижайше попросить г-на Лейто облагодетельствовать комьюнити своей реализацией поиска пути с применением алгоритма Флойда (или любого другого алгоритма), которая в соответствии с обещанием г-на Лейто проводила бы корректный расчёт среднесложного пути в 500 (или хотя бы в 250) раз быстрее, чем это делает DExeik.

P.S. Ссылка в тему:
http://gamesanatomy.ru/index.php?nam...er=asc&start=0
Мне почему-то неосознанно вспомнился профессор Выбегалло. Интерсно, почему бы это?..

Re: ПП по Вейпоинтам

Дипломат.

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

сейчас практически доделал ПП.
тоесть то, что я сделал хуже чем алгоритм флойда, но допустим чтобы по флойду создать 1600 вейпоинтов нада минут 14 а с моим алгоритмом за 5 секунд. правда эффект чуть хуже на дальних расстояниях. на близких тот же.

Re: ПП по Вейпоинтам

а что мешает создавать вейпойнты по флойду еще на этапе создания карты (в редакторе)?
там 14 минут не критично.

Re: ПП по Вейпоинтам

Цитата:

Сообщение от HolyDel

а что мешает создавать вейпойнты по флойду еще на этапе создания карты (в редакторе)?
там 14 минут не критично.

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

Re: ПП по Вейпоинтам

а что мешает спланировать процесс разработки игры так чтобы генерировать карту приходилось только один раз ?
все же рендер в 3д максе больших сцен делают зачастую только один раз, и никто не ворчит что он проходит от 12 часов до 3 суток :-)
а для дебаг версии мона зделать простой алгоритмик

Re: ПП по Вейпоинтам

Цитата:

а для дебаг версии мона зделать простой алгоритмик

или малюсенькую карту, скажем на 127 вейпойнтов.

Re: ПП по Вейпоинтам

вот моя недоделанная прога с той системой что я задумал.

сначала создаем препятствия - левая кнопка мыши - начало
второй щелчок - конец

потом жмем пробел - один раз за всю работу проги
потом ставим правой кнопкой мыши начало и конец пути

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

потом жмем Интер
ищет правда не всегда, потому что недоделанный алгоритм.)

Код:

Dim passmap(2000,2000)



Dim mainpassmap(2000,2000)



Dim passmap2(2000,3)



Dim mainpassmap2(2000,3)



Dim way(1500,3)



Global a1,a2,b1,b2,a,QW,QP,time#,ok$,QO,x,y,QMP



Dim WayH(2000,2000)



Dim WayC(2000,2000)



Dim WayMH(2000,2000)



Dim WayMC(2000,2000)



Dim TempQP(100)



;Dim WayT(1500,1500)



Dim obs(100,5)



Graphics3D 1024,768,16,1



SetBuffer BackBuffer()



Global font = LoadFont("palatino linotype",18)



Global font22 = LoadFont("palatino linotype",22)



SeedRnd (MilliSecs())



Repeat

Cls

Color 0,0,255



If MouseHit(1)

x1=MouseX()

y1=MouseY()

If x1>=100 And x1<=699 And y1>=100 And y1<=699

If x=0

x=Int((MouseX()-100)/15)+1

y=Int((MouseY()-100)/15)+1

Else

nx=Int((MouseX()-100)/15)+1

ny=Int((MouseY()-100)/15)+1

If nx<x

a=x:x=nx:nx=a

End If

If ny<y

a=y:y=ny:ny=a

End If

QO=QO+1

obs(QO,1)=x:obs(QO,2)=nx:obs(QO,3)=y:obs(QO,4)=ny

x=0:y=0:nx=0:ny=0

End If

End If

End If

If MouseHit(2)

x1=MouseX()

y1=MouseY()

If x1>=100 And x1<=699 And y1>=100 And y1<=699

x1=Int((MouseX()-100)/15)+1

y1=Int((MouseY()-100)/15)+1 

If passmap(x1,y1)<>0

If a=0

a=1:a1=x1:b1=y1

Else

If a=2

a1=0:a2=0:b1=0:b2=0:a=0

Else

a=2:a2=x1:b2=y1

End If

End If

End If

End If

End If

For i=1 To 41

For j=1 To 41

If passmap(i,j)<>0

For n=i*15-0 To i*15+1

For m=j*15-0 To j*15+0

Line n+85,m+85,n+85,m+85

Next

Next

End If

Next

Next

Color 0,255,0



;For j=1 To QP

; If WayC(1,j)=10 Or WayC(1,j)=14 Line passmap2(1,1)*15+85,passmap2(1,2)*15+85,passmap2(j,1)*15+85,passmap2(j,2)*15+85

;Next

;For i=1 To QP

; For j=1 To QP

; If WayC(i,j)=10 Or WayC(i,j)=14 Line passmap2(i,1)*15+85,passmap2(i,2)*15+85,passmap2(j,1)*15+85,passmap2(j,2)*15+85

; Next

;Next



Color 0,255,0



For i=1 To QMP

For j=1 To QMP

If WayMC(i,j)=10 Or WayMC(i,j)=14 Line mainpassmap2(i,1)*15+85,mainpassmap2(i,2)*15+85,mainpassmap2(j,1)*15+85,mainpassmap2(j,2)*15+85

Next

Next

Color 200,0,0



If x<>0

Line (x+1)*15+100,(y+1)*15+100,MouseX(),(y+1)*15+100

Line (x+1)*15+100,(y+1)*15+100,(X+1)*15+100,MouseY()

Line MouseX(),(y+1)*15+100,MouseX(),MouseY()

Line (x+1)*15+100,MouseY(),MouseX(),MouseY() 



End If

 

If QW<>0

Color 128,0,0

For i=0 To QW-1

Line way(i,1)*15+85,way(i,2)*15+85,way(i+1,1)*15+85,way(i+1,2)*15+85

Next

End If

If a1<>0

Color 128,128,0

For i=a1*15-2 To a1*15+2

For j=b1*15-2 To b1*15+2

Line i+85,j+85,i+85,j+85

Next

Next

End If

If a2<>0

Color 0,128,0

For i=a2*15-2 To a2*15+2

For j=b2*15-2 To b2*15+2

Line i+85,j+85,i+85,j+85

Next

Next

End If

If KeyHit(57)

CreateWay(4,10)



End If

If KeyHit(28)

SearchWay(a1,b1,a2,b2,4,10)



End If

Color 0,0,128



For i=1 To QO

Rect (Obs(i,1)-1)*15+100,(Obs(i,3)-1)*15+100,(Obs(i,2)-Obs(i,1))*15,(Obs(i,4)-Obs(i,3))*15,1



Next

 

Color 255,0,0



SetFont Font



Color 255,255,255



Text MouseX()-StringWidth("*")/2,MouseY()-StringHeight("1")/2,"*"



SetFont Font22



Text 260,747,"Leito Software Company presents the mini-program search of way "



Text 0,0,"Time: "+time#



Text 10,30,ok$



Flip

Until KeyHit(10) Or KeyHit(1)



End

Function SearchWay(x1,y1,x2,y2,n,m)



If (x1-1)/10=(x2-1)/10 And (y1-1)/10=(y2-1)/10

p1=passmap(x1,y1)

p2=passmap(x2,y2)

QW=0

way(QW,1)=x1

way(QW,2)=y1

While p1<>p2

QW=QW+1 

p1=wayH(p1,p2)

way(QW,1)=passmap2(p1,1)

way(QW,2)=passmap2(p1,2)

If QW>1000 p1=p2

Wend

Else

p1=mainpassmap(x1/4,y1/4)

p2=mainpassmap(x2/4,y2/4)

QW=0

way(QW,1)=x1

way(QW,2)=y1

e=0

While e=0

QW=QW+1 

p1=wayMH(p1,p2)

way(QW,1)=mainpassmap2(p1,1)

way(QW,2)=mainpassmap2(p1,2)

If QW>1000 p1=p2

If (way(QW,1)-1)/10=(x2-1)/10 And (way(QW,2)-1)/10=(y2-1)/10 e=1

Wend

p1=passmap(way(QW,1),way(QW,2))

p2=passmap(x2,y2) 

While p1<>p2

QW=QW+1 

p1=wayH(p1,p2)

way(QW,1)=passmap2(p1,1)

way(QW,2)=passmap2(p1,2)

If QW>1000 p1=p2

Wend 

End If

End Function

Function CreateWay(n,m)



time#=MilliSecs()



maxlen=n*m

maxqp=n*m*m*n+1



For i=1 To maxlen

For j=1 To maxlen

passmap(i,j)=maxqp

Next

Next

For k=1 To QO

For i=obs(k,1) To obs(k,2)

For j=obs(k,3) To obs(k,4)

passmap(i,j)=0

Next

Next 

Next

For i=1 To m

For j=1 To m

If passmap(i*n,j*n)<>0

k1=i*n:k2=j*n

QMP=QMP+1 

mainpassmap(i,j)=QMP

mainpassmap2(QMP,1)=i*n

mainpassmap2(QMP,2)=j*n

p1=1:p2=1:p3=1:p4=1:p5=1:p6=1:p7=1:p8=1

For k=1 To n

If passmap(i*n-k,j*n-k)=0 p1=0

If passmap(i*n-k,j*n)=0 p2=0

If passmap(i*n-k,j*n+k)=0 p3=0

If passmap(i*n,j*n-k)=0 p4=0

If passmap(i*n,j*n+k)=0 p5=0

If passmap(i*n+k,j*n-k)=0 p6=0

If passmap(i*n+k,j*n)=0 p7=0

If passmap(i*n+k,j*n+k)=0 p8=0 

Next

If p1=1

WayMC(QMP,mainpassmap(i-1,j-1))=14

WayMC(mainpassmap(i-1,j-1),QMP)=14



; WayMC(QMP,mainpassmap(j-1,i-1))=14

End If

If p2=1

WayMC(QMP,mainpassmap(i-1,j))=10

WayMC(mainpassmap(i-1,j),QMP)=10 



; WayMC(QMP,mainpassmap(j,i-1))=10

End If

If p3=1

WayMC(QMP,mainpassmap(i-1,j+1))=14

WayMC(mainpassmap(i-1,j+1),QMP)=14 



; WayMC(QMP,mainpassmap(j+1,i-1))=14

End If

If p4=1

WayMC(QMP,mainpassmap(i,j-1))=10

WayMC(mainpassmap(i,j-1),QMP)=10



; WayMC(QMP,mainpassmap(j-1,i))=10

End If

If p5=1

WayMC(QMP,mainpassmap(i,j+1))=10

WayMC(mainpassmap(i,j+1),QMP)=10



; WayMC(QMP,mainpassmap(j+1,i))=10

End If 

If p6=1

WayMC(QMP,mainpassmap(i+1,j-1))=14

WayMC(mainpassmap(i+1,j-1),QMP)=14



; WayMC(QMP,mainpassmap(j-1,i+1))=14

End If

If p7=1

WayMC(QMP,mainpassmap(i+1,j))=10

WayMC(mainpassmap(i+1,j),QMP)=10 



; WayMC(QMP,mainpassmap(j,i+1))=10

End If

If p8=1

WayMC(QMP,mainpassmap(i+1,j+1))=14

WayMC(mainpassmap(i+1,j+1),QMP)=14 



; WayMC(QMP,mainpassmap(j+1,i+1))=14

End If

End If

Next

Next



QP=0



For k=1 To n*n

l=0



; ll=0

For i=1 To m

For j=1 To m

p1=i+Floor((k-1)/n)*m

p2=j+((k-1) Mod n)*m



; Cls

; Text 0,0,"p1 = "+p1+" p2 = "+p2+ " k = "+k

; Flip

; If p1=1 Or p2=1

; While Not (KeyHit(57) Or KeyDown(28))

; ll=1

; Wend

; End If

If passmap(p1,p2)<>0

QP=QP+1

passmap(p1,p2)=QP

passmap2(QP,1)=p1

passmap2(QP,2)=p2

If l=0

TempQP(k)=QP

l=1

End If

If i<>1

If passmap(p1-1,p2)<>0

WayC(QP,passmap(p1-1,p2))=10

WayC(passmap(p1-1,p2),QP)=10

End If

End If

If i<>m

If passmap(p1+1,p2)<>0

WayC(QP,passmap(p1+1,p2))=10

WayC(passmap(p1+1,p2),QP)=10

End If

End If

 

If j<>1

If passmap(p1,p2-1)<>0

WayC(QP,passmap(p1,p2-1))=10

WayC(passmap(p1,p2-1),QP)=10

End If

End If

If j<>m

If passmap(p1,p2+1)<>0

WayC(QP,passmap(p1,p2+1))=10

WayC(passmap(p1,p2+1),QP)=10

End If

End If

If i<>1 And j<>1

If passmap(p1-1,p2-1)<>0

WayC(QP,passmap(p1-1,p2-1))=14

WayC(passmap(p1-1,p2-1),QP)=14

End If

End If

If i<>1 And j<>m

If passmap(p1-1,p2+1)<>0

WayC(QP,passmap(p1-1,p2+1))=14

WayC(passmap(p1-1,p2+1),QP)=14

End If

End If

If i<>m And j<>1

If passmap(p1+1,p2-1)<>0

WayC(QP,passmap(p1+1,p2-1))=14

WayC(passmap(p1+1,p2-1),QP)=14

End If

End If

If i<>m And j<>m

If passmap(p1+1,p2+1)<>0

WayC(QP,passmap(p1+1,p2+1))=14

WayC(passmap(p1+1,p2+ 1),QP)=14

End If

End If

End If

Next

Next

Next



TempQP(n*n+1)=QP+1



For i=1 To QP

For j=1 To QP

If WayC(i,j)=0

WayH(i,j)=0

WayC(i,j)=100000

Else

WayH(i,j)=j

End If

Next

Next

 

For p=1 To n*n



; p1=Floor((p-1)/n)*m+1

; p2=((p-1) Mod 3)*m+1

; p1=passmap(p1,p2)

; p3=Floor((p-1)/n)*m+m

;; p4=((p-1) Mod 3)*m+m

; p2=passmap(p3,p4)

p1=TempQP(p):p2=TempQP(p+1)-1



; Cls

; Text 0,0,"?? "+p1+" ?? "+p2+ " p = "+p

; Flip

; While Not KeyHit(57)

; ll=1

; Wend

If p1>0 And p2>0

For i=p1 To p2

For j=p1 To p2

For k=p1 To p2

If i<>j And WayC(j,i)<>100000 And i<>k And WayC(i,k)<>100000 And (WayC(j,k)=100000 Or WayC(j,k)>WayC(j,i)+WayC(i,k))

WayH(j,k)=WayH(j,i)

WayC(j,k)=WayC(j,i)+WayC(i,k)

End If

Next 

Next

Next

End If

Next

For i=1 To QMP

For j=1 To QMP

If WayMC(i,j)=0

WayMH(i,j)=0

WayMC(i,j)=100000

Else

WayMH(i,j)=j

End If

Next

Next

For i=1 To QMP

For j=1 To QMP

For k=1 To QMP

If i<>j And WayMC(j,i)<>100000 And i<>k And WayMC(i,k)<>100000 And (WayMC(j,k)=100000 Or WayMC(j,k)>WayMC(j,i)+WayMC(i,k))

WayMH(j,k)=WayMH(j,i)

WayMC(j,k)=WayMC(j,i)+WayMC(i,k)

End If

Next 

Next

Next



time#=MilliSecs()-time#



ok$="Construction of ways is completed"



End Function

Re: ПП по Вейпоинтам

оно вообще неищет ... алгоритм не то что не доделан ... он не рабочий

Re: ПП по Вейпоинтам

ищет, ищет, ты пробел сначала нажми, для создания сетки.

Re: ПП по Вейпоинтам

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

Re: ПП по Вейпоинтам

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