Pathfinding (A* + nav. mesh/waypoint)

[Deluxe]

Tak sem si s pomoci tohoto nejak napsal pathfinding na pravidelny mrizce.
Akorat mi neni uplne jasny jak by mnela vypadat funkce g(n). Mnela by asi vyjadrovat cenu nodu n od zacatku cesty.
Dalsi vec je co musim upravit, abych mohl A* pouzit na nepravidelnou sit waypointu (kromne heuristicke funkce h(n), ktera asi bude prima vzdalenost od cile).
A podobne nevim jak to prizpusobit pro nav. mesh. U nej bych se chtel pokusit o jeho automaticky generovani. Tam zhruba vim jak na to, rozdelim si povrch na mrizku, najdu si pruchozi ctverce a tim si vytvorim nejakej n-gon.
Tady mam problem stim, ze nevim jak ho potom rozrezat na konvexni polygony.
Budu rad za jakoukoli radu/link co se neceho z tohohle tyka.

[OndraSej]

Vsak cely A* je o tom, ze si tu g(n) napocitavas... g(start) = 0, a pak je g(n) pocet kroku (resp. delky cest) ze startu do daneho uzlu. Vzdycky kdyz prehazujes nejaky uzel z open do closed, tak pro nej to g(n) zafixujes (na zaklade g(n) nejakeho drive zpracovaneho uzlu a delky cesty z tohohle uzlu do n).
Pro nepravidelnou mrizku je ten zakladni algoritmus uplne stejny a je to jenom o tom, jak ten graf mas reprezentovany (takze o uprave datovych struktur).
_________________
http://trionteam.net

[Deluxe]

OndraSej: Dik, nebyl sem si jistej, jestli to ma byt to samy co h(n), ale od startu k n, nebo "delka" uz "projite" cesty.
No a pri pouziti toho nav. meshe bych mnel brat jako uzel spolecnou hranu 2 polygonu?

[OndraSej]

Deluxe> typicky g(n) je delka "uz ujite" cesty a h(n) je odhad zbyvajici cesty do cile. A pokud to neni takhle, tak naopak. Pri pouziti meshe bych bral spis polygon jako uzel a hranu mezi polygony jako hranu.
_________________
http://trionteam.net

[nou]

a aby si dostal spravne vysledky tak ti musi h(n) splnat dve podmienky. v ciely musi vracat 0 a odhad vzdialenosti do ciela musi byt mensi nanajvys rovny skutocnej vzdialenosti.
_________________
Najjednoduchšie chyby sa najtažšie hľadajú.

[OndraSej]

nou> to je jenom jedna podminka
_________________
http://trionteam.net

[Deluxe]

OndraSej: Takze musim pouzit heuristiku pro oblast? nebo by stacilo i zvolit treba jen stred toho polygonu a pocitat to k nemu?

[OndraSej]

Deluxe: nerozumim dotazu. Tu heuristiku pouzivas vzdycky pro uzel navigacniho grafu. Pokud vytvaris uzel pro kazdy polygon, tak ta heuristika bude definovana pro ten konkretni polygon (at uz to znamena cokoliv).

Jinak ta heuristika nemusi byt kdovijak genialni, pokud splnuje podminky co napsal nou, tak to s ni bude fungovat. Typicky jde pouzit treba euklidovska vzdalenost do cile.
_________________
http://trionteam.net

[Deluxe]

Myslel jsem to udelat tak jak pisou tady:

[OndraSej]

To moc nechapu. Co mysleji tim "nearby spots"?
_________________
http://trionteam.net

[Deluxe]

Tohle bylo spis pro "grid maps" takze pokud je mi jedno ke kterymu policku se dostanu z nejaky skupiny tak muzu pouzit tohle. Tak mne napadlo ze by se to mozna dalo pouzit i v pripade polygonu, ale asi je to blbost.