NavMesh :: Funnel Algoritmus

[VODA]

Zdravím,

byl by tady někdo tak ochotnej a vysvětlil by mi polopaticky, jak tenhle algoritmus funguje?
Já už se to 2 týdny snažím dát dohromady, ale vždy najdu u mého řešení takový mesh, u kterého to nefunguje. Pravděpodobně to bude tím, že to zcela nechápu.

Našel jsem toto:
http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html
http://www.gamedev.net/community/forums/topic.asp?topic_id=560218

Už mě to docela žere, protože bez navmeshe se vážně neobejdu. A navíc bych rád, aby ty cesty, popř. směr pohybu byl optimální...

Díky
_________________
Opravdovost se pojí s trýzní...

[VODA]

Už je to týden a stále nic...
To tu není nikdo, kdo by měl pro mě nějakou radu?
To teda čumím...
_________________
Opravdovost se pojí s trýzní...

[Deluxe]

Snad by mohlo trochu pomoct tohle: http://www.gdcvault.com/play/1013425/Crowds-In-A-Polygon-Soup.
Myslim ze ten jejich "Next corner" by mohlo byt to samy. Ale moc tam toho o tom neni (37 - 49 snimek).

[Vilem Otte]

Hm... kde přesně je problém, já jsem se zatím přímo s navmeshem nesetkal (dávám přednost trošku jiným metodám, neříkám však, že nemají s navmeshem nic společného)?

Nejdůležitější je podle mě postavit správný samotný mesh navmeshe, tedy první otázkou ode mě je, jak jej stavíš?
Zbytek algoritmu je už celkem jednoduchý a pouze "jdeš" po hranách, než najdeš optimální cestu.
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

[VODA]

Mám 2D navmesh, složen z trianglů (ne polygony), každá hrana má nejvíce 2 triangly...vygeneruji si graf, vypočtu tabulku, uložím si portálové hrany.
Když zadám hledání cesty z A do B, získám portály na této trase...atd...

Chození po středech trianglů je hnus, po středech portálu je to lepší, kolmé průměty na portály celkem ujdou, ale je to moc cik-cak a nechce se mi příliš smoothovat, pak jsou ještě další lepší postupy, ale pořád mě to neuspokojuje...ten funnel hazí to co bych bral...

To Deluxe:
Jj, to je to samé, ale pořád mi nejde do hlavy jak vlastně nakonec určím ten apex (corner)...jestli to mám brát jako poslední validní navštívený bod...
Ale díky, to mě trochu popostrčilo...
_________________
Opravdovost se pojí s trýzní...

[VODA]

Ach jo, tak já nevím.
Dokážu určit hranu (portál) na které bude ležet ten corner (apex), ale pořád nějak nevím, jak rozhodnu, který z těch dvou bodů portálu to bude...

Jako na obrázku v tom ppt to zrovna vychází, ale dokážu si vymyslet takové případy, kde se strojově neumím rozhodnout...(samozřejmně, že člověk koukne a vidí, ale počítač je blbej...)

Zbytek je snadnej...

Já ani nepotřebuji celou cestu, mě stačí optimální směr pohybu (normalizovaný) a ten už jen přenásobím rychlostí, kterou má urazit za dt a je to...a protože je funnel velmi rychlej, tak si mohu dovolit volat ho i několikrát za sebou jen s malou ztrátou str. času...

Zkrátka jen teď neumím naučit pc aby určil ten správný roh...
_________________
Opravdovost se pojí s trýzní...

[Deluxe]

No, jen takovej napad (moc sem nadtim nepremyslel)...
Nestacilo by jednoduse pouzit ten co je bliz k cili cesty?

[VODA]

No právě že ne...teď to mám nakreslené na tabuli:

Červeně zvýrazněná hrana je tu co najdu pomocí funnelu, a černý puntík je požadovaný bod...

Tomuhle případu by spíše odpovídal kolmý průmět počátku na hranu a pak vzít bližší z bodů toho portálu...jenže...

PS: Zelených a modrých čar si vůbec nevšímejte...důležité je místo, kde je napsáno apex...
_________________
Opravdovost se pojí s trýzní...

[VODA]

Tak jsem ještě trochu přemýšlel...


V případech A,B,C,D,F to vypadá, že délka "start-apex-end" musí být co nejmenší, takže výběr správného bodu není problém.
V případě E nebyla nalezena žádná hrana, funnel došel až k end pointu, není co řešit...přímá cesta
Problém je akorát v případě G. Tady se nabízí průsečík úsečky "start-end" a úsečky portál, jenže si nejsem jistý, zda-li to klapne vždy. V některých případech tedy nebude cesta úplně přímá, ale na kratší vzdálenosti by to mělo fungovat tak jak potřebuji.

Až se mi to (doufám) povede zprovoznit, tak sem napíši přesně jak to funguje, ať z toho také něco máte vy.
_________________
Opravdovost se pojí s trýzní...

[Vilem Otte]

Hm... jak to tady kreslíš, tak mi to připomíná známého (AI programmer), který použil pro pathfinding a výpočet ideální tratě přímo ray tracing (pamatuju si to, protože používal moji knihovnu). Vím, že došel k celkem kvalitním výsledkům pathfindingu (ty algoritmy ale nebyly zrovna jednoduché afaik). Bohužel přesný algoritmus neznám - ale zkusím ho někde zastihnout.
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

[Crusty]

http://www.cs.wustl.edu/~suri/cs506/projects/sp.html
_________________
http://www.2ox.cz

[VODA]

Jo tohle už jsem taky našel. Jenže je z toho prd vidět...
A navíc mu tam nefunguje 100% ta triangulace...
_________________
Opravdovost se pojí s trýzní...

[Crusty]

aha, no ma tam i zdrojaky (kdyz odmazes sp.html) tak treba z toho neco vykoukas, poupravis a bude

a musi to byt mesh? nemuzes to pak treba prevest na bitmapu a hledat uz jen v ni?
_________________
http://www.2ox.cz

[VODA]

Musí to být mesh. Nemám co dalšího dodat...
_________________
Opravdovost se pojí s trýzní...

[VODA]

Má někdo nějaké zkušenosti s Recast & Detour?
Nějak pořád nemohu dát dohromady inteligentní navmesh, tak jsem si říkal, že bych mohl použít už něco hotového, přesněji Detour na hledání cesty ve vlastním navmeshi, ale nějak se v tom nemohu vůbec vyznat...
Díky
_________________
Opravdovost se pojí s trýzní...