Pathfinding

[koso]

Prosim o radu. Ake sposoby pathfindingu sa pouzivaju pre orientaciu a pohyb v 3D. Viacmenej ide len o clenity teren takze v podstate by slo len o orientaciu v dvoch osiach. Ak poznate, mohli by ste hodit nejake linky alebo nieco. Pokial mozno nejaka metoda ktora nieje zalozena na GRID rozdeleni mapy pricom kazdy objekt na mape predstavuje 1 policko.

dakujem

koso

[OndraSej]

Pathfinding a navigace ve 3D (a obecne ve spojitem prostoru) je vcelku problem, obvykle reseni je rozdelit to na 2 vicemene oddelene ulohy:

1) Samotny pathfinding, tedy nalezeni cesty z bodu A do bodu B
2) Navigace podel teto cesty (s ohledem na terenni prekazky, nepratele po ceste, ...

Vyhoda takoveho reseni je, ze nalezena cesta z bodu (1) nemusi byt dokonale presna (takze jde spocitat celkem rychle). Navic diky rozdeleni muze reagovat i na necekane udalosti, vyhybat se nepratelum, ...

Pokud jde o samotne hledani cesty, tak se pouzivaji stejne algoritmy jako ve "2d" (resp. jako na ctvereckove mape, resp. v grafu) - Dijkstruv algoritmus, resp. A* (nebo nektera z jejich variant). Potud je vsechno jednoduche - jenze aby to slo ve 3D udelat, je potreba nejak postavit uvnitr 3d prostredi ten graf. Na to se pouzivaji ruzne techniky od rucniho umisteni waypointu, pres jejich automaticke rozmisteni, hledani cesty pres povrch polygonu, ...

Navigace pak uz muze byt celkem jednoducha (pohyb po spojnicich mezi waypointy, pripadne s vyhlazovanim).

Ve tvem pripade to chapu tak, ze mas v podstate vlnitou placku, takze metoda s navigaci po povrchu polygonu by pro tebe mohla fungovat docela dobre (tj. vyrobit graf tak, ze kazdy polygon je jeden vrchol a hrana je mezi polygony, ktere maji spolecnou hranu).

Pokud jde o literaturu, z hlavy nevim, ale zkus prolistovat Game AI Programming Wisdom (pokud se k nim nekde dostanes - idealne v nejake univerzitni knihovne).
_________________
http://trionteam.net

[koso]

teraz ma napadlo ze som mal vymysleny zatial len teoreticky system ktory vyuzival polohu okolitych objektov. vlastne to spocivalo v tom ze z pola sa zistovaly pozicie(do pola sa zapisali pri inicializacii mapy z textoveho suboru). dany objekt potom nasiel v poli poziciu bodu B(ktory bol reprezentovany nejakym objektom napr. nepriatelom)vypocital priamu drahu a pocas "presunu" kontroloval pozicie objektov v okoli a pripadne upravoval drahu. absolutne by sa to nehodilo na navigaciu v budovach ale na otvorene priestranstva na ktorych je par stromov by to asi postacovalo. a okrem toho saom to zavrhol lebo by to bolo zbytocne narocne na vypocet- v kazdom loope kontrolovat pozicie okolitych objektov. asi mi zostavaju len tie waypointy.

v tom pripade ako by sa dali riesit presuny po otvorenych preistranstvach? aby tam nebolo len par ciest po waypointoch?

ako priklad uvediem napr stalkera. vedeli by ste mi zjednodusene interpretovat aky system bol pouzity na navigaciu tak ako to vidiet v tej hre?

tj. viem si to predstavit tak ze v kludovom stave tie NPC chodia po spojniciach waypointov(hliadkuju a pod). ale potom ked su v boji tak len popri strelbe rozne ukracuju pripadne pokial sa hrac rozhodne pre utek tak ho prenasleduju. a toto mi nejde do hlavy. ako nasleduju hraca? alebo je pouzite take mnozstvo waypointov aby ho nasledovali po jeho trase?

[koso]

Ked nad tym tak rozmyslam vymyslel som toto:

Po celom povrchu oblasti (ale len v 2D rovine) sa vytvori siet Waypointov, s rozostupom napr 20 bodov. Tato siet by fungovala podobne ako mapa(kazdy waypoint by predstavoval kvazi policko na mape) po zadani ciela by bol pouzity A* algoritmus na najdenie cesty k waypointu najblizsiemu k cielu.
moze byt?

[OndraSej]

Pokud jde o tu navigaci "po polygonech" - tam typicky staci mit jeden waypoint na polygon. Navigace v ramci jednoho polygonu je trivialni, staci jit po primce. No a na slozitejsi cesty staci "hruba" aproximace pomoci polygonove site.

pokud jde o rozmisteni waypointu co 20 bodu, tak by to (teoreticky) mohlo fungovat, ale samozrejme nevim, co znamena 20 bodu a jestli takova sit nebude prilis husta nebo prilis ridka. Obecne, pokud nemas v tom terenu nejaka bludiste, tak by asi mela stacit celkem ridka mrizka.

Pokud jde o pronasledovani ve Stalkerovi, tak nevim, jak presne to tam maji resene. Ale plati, ze pronasledovani na kratkou vzdalenost neni tak slozite, obvykle potrebujes jenom sledovat trajektorii hrace, pripadne se vyhybat prekazkam, zadne slozite planovani, zadne waypointy.
_________________
http://trionteam.net

[koso]

takze asi bude najlepsia ta navigacia po polygonoch.

[OndraSej]

Jj, pokud se po vetsine polygonu "da chodit", tak to bude asi nejlepsi reseni. Resp. takove, ktere budes mit nejrychleji hotove.
_________________
http://trionteam.net

[koso]

Tak ma napada ze ako potom efektivne riesit kolizie, respektive vyhybanie sa objektom? Napr. ked budem mat na tej "zvlnenej placke" stromy alebo nejake objekty.

[OndraSej]

Tady je asi klicove slovo steering.

Teda zalezi na tom, jestli programujes real-time strategii nebo spis nejakou akcni/RPG hru na sirych planich a jestli budes mit sem tam strom, nebo huste nepruchozi lesy.
_________________
http://trionteam.net

[koso]

no malo by to byt take univerzalne ale skor pre nejaku akcnu/RPG hru. mohol by si povedat nieco o tom "steeringu", co je to za technika a tak?

diki

[Ladis]

Něco o tom steeringu jsem našel tady:

http://www.google.cz/search?q=steering+path+finding
_________________
Award-winning game developer

[KoudyDev]

nehodilo by se treba tohle?

http://code.google.com/p/recastnavigation/

[koso]

pozna niekto ten recast?
skusim sa v tom pohrabat ale neviem si predstavit ako to integrovat do mojho projektu.

[Quiark]

Prezentace o state-of-the art steeringu v Left 4 Dead viz http://www.ceske-hry.cz/forum/viewtopic.php?t=1983
_________________
Mám strach

[koso]

presne to som si vcera cital