Ezen a héten egy teljesen új képességgel bővült az engine nevezetesen az útkereséssel. Első terveim között egy egyszerű waypoint rendszer kiépítése szerepelt, amelyet természetesen külön szerkeszteni kellett volna.
Szerencsére ennél már létezik jóval hatékonyabb és automatikusan elkészíthető alternatíva, amit navigation meshnek hívnak. Ennek az elkészítéséhez elérhető egy ingyenes és nyílt forráskódú könyvtár, ami recast névre hallgat - http://code.google.com/p/recastnavigation/
(ez pedig egy jó összefoglaló miért érdemes waypoint helyett navmesht használni - http://www.ai-blog.net/archives/000152.html)
Egy egyszerű háromszöghalmazból képes elkészíteni a navigation mesht, amire az alábbiak jellemzők:
- mindig konvex poligonokból álló mesht készít
- ezekhez a poligonokhoz tárolja a szomszédosság információt
- vagyis egy gráfot épít fel, amelynek pontjai az egyes konvex poligonok
- lehet szabályozni, hogy milyen típusú felületek vegyen figyelembe - amin lehet járni, mászni, lépcsőzni stb
A navigation mesht mint gráfot felhasználva A* algoritmus segítségével gyors útvonalkeresésre használhatjuk. Az A* algoritmus egy szemléletes leírása rácshoz: http://www.policyalmanac.org/games/aStarTutorial.htm
A legnagyobb problémát azonban az út elkészítése jelenti az A* segítségével kapott poligonlistából. Az utat egy egyszerű pontsorozattal tudjuk ábrázolni - e pontsorozat előállítása okozza az igazi fejtörést...
