Nagyon sokáig gondot okozott számomra, hogy hogyan képes egy játék eltárolni, kezelni, mozgatni, "élővé" tenni nagy területeket. Számtalan 3d engine létezik a világban, de a legtöbbjük megreked a betöltök-egy-modellt-és-nyomok-rá-effektet állapotban. A szerencsésebbek egy kisebb, egy játékra alkalmas engine-ig jutnak el, de általában a folytatáshoz az egész engine ujratervezése-ujraírása lenne szükséges.
Vajon mi lehet ennek az oka; azt hiszem alapvetően két probléma merül fel ezzel a kérdéssel kapcsolatban.
Az egyik a tapasztalat hiánya, mivel aki még nem készített enginet nem valószínű, hogy tudja mi mindenre lesz majd még szüksége a későbbiekben, milyen módon lehet a kódot "legszebben" és "legjobban" megírni - magyarán, hogy három hónap mulva is megértse, hogy mit és miért úgy kódolt le ahogy ott van. Ilyenkor lehet hasznos a kommentezés.
A másik probléma, a (hosszútávú) tervezés hiánya vagyis hiába egy remek koncepció, ha az nem lesz elég gyors, nem elég általános és pár hónap múlva már gyorsabb ujraírni, mint kijavítani, mert hemzseg a bugoktól, néha itt-ott-elszáll-de-nem-tudom-miért, nálam-pedig-nem-fagyott-eddig stb.
A tapasztalatok begyűjtése az egyik leghasznosabb módja a tanulásnak, hiszen felesleges feltalálni a spanyolviaszt sokadszorra is (ami ráadásul nem 1-2 nap terméke, hanem jóval több), amikor az már régen készen van. Persze újítani mindig érdemes, de csak akkor, ha az ember biztosan tudja arról, hogy mikor lehet, mikor nem lehet azt használni és nem balladai homály takargatja az algoritmus működési elvét vagyis nem a véletlennek köszönheti a működését.
Akiket esetleg érdekel, hogy jutottam el oda, ahol most vagyok nekik szól a következő rész.
Tapasztalataim az enginem jelenetkezeléséről nagyvonalakban bevezetésként egy csipetnyi játéktörténelemmel.
Nagyon régen a 3d játékok jelenetei alapvetően 2 részre oszlottak aszerint, hogy külső, nyílt terepen vagy belső, zárt helyszíneken játszódtak-e és általában a két tipust vegyíteni nem igazán lehetett. A jelenet-típusok eme alapvető megkülönböztetése programozási, algoritmizálási és teljesítmény problémák miatt volt szükséges, mely utobbi a teljesítmény fokozatos növekedésével elvesztette jelentőségét így a kétféle helyszín vegyítése lehetségessé vált anélkül, hogy az a bizonyos "loading" felirat előkerült volna.
Az enginem első verziója brute force technikával oldotta meg a jelenetkezelést, amelynek sebességbeli hátránya elég hamar a felszínre bukkant ugyhogy lapozzunk tovább a híres-neves Quake3 .bsp pályaformátumára. A bsp sikerét mi sem bizonyítja jobban, hogy az első wolfeinstein játéktől a quake4ig bizony számos játék ezt az elvet/formátumot használta szóval nekem is kötelező volt ezt kipróbálnom.
Első menetben megelégedtem a .q3bsp geometria rendereléssel, aztán jött mellé a bsp fa felhasználása még később a pvs információk kezelése így egy teljes értékű bsp megjelenítő állt rendelkezésemre (az már csak hab a tortám, hogy még még később vagyis mostanában kezelem le a q3bspben tárolt spline-okat).
Azonban csak belső térben játszódó játék manapság már kevésbé izgalmas és ez a formátum csak kiegészítésekkel tud domborzatokat támogatni és azok sem világmegváltó-méretűek.
Következő lépésem volt tehát egy domborzat kezelő készítése. Először 128*128 méretben probálkoztam, amely reális szemmel nézve nevetségesen kicsi, de a terület nagyságával és felbontásával együtt növekedett a sebesség csökkenés is. Ekkor találtam magam szemben a terrain lod problémájával, amelyekből számos létezik, én a chunked lodnál horgonyoztam le.
Utolsó lépésként megprobáltam kiterjeszteni/egyesíteni ezt a technikát belső tér kezeléssel így jutottam el a bvh-ig.
Most pedig lássuk általában mik lehetnek az alapvető követelmények egy 3d engine-nel szemben.
- szükséges tárolni, hogy kik/mik szerepelnek a jelenetben és közöttük milyen viszony áll fenn. Néhány példa - egy szereplő tart a kezében a fegyvert, amely rendelkezhet még extra felszereléssel; a szereplő ülhet egy járműben, amelyhez szintén tartozhat fegyver ill. a szereplőhöz is; a szereplő lángolhat esetleg meg is gyújthatja környezetét; a szereplő tagja lehet egy csapatnak stb... Ezt hívjuk jelenet-fának.
- szükséges tárolni, hogy a jelenet részei milyen térbeli viszonyban állnak egymással. A legtöbb esetben ez a tér-fa a leghasznosabb!
- érdemes tárolni, hogy a jelenet melyik részét milyen technikával rendereljük elkerülendő ezzel a felesleges állapotváltásokat. Azonban pl az átlátszó felületeknél erősen ajánlott. Ez a megjelenítési-fa;
A játék futása közben általában igaz az, hogy a jelenet-fa legalább egy részét mindenképp be kell járni. Például az épp aktív szereplőknek (ide tartozik legtöbbször a főszereplő is) cselekedniük kell.
A tér-fa egyik alapvető vizsgálata a frustum cull vagyis amikor az egész! jelenetet átvizsgáljuk megkeresve az összes, a frustumot metsző elemeket. De akkor is ezt használjuk, amikor meg akarjuk tudni, hogy egy adott fényforrás mely elemekre hat. Ha meg szeretnénk tudni, hogy milyen szereplők vannak a főszereplőnk körül akkor is ez lesz a segítségünkre
A frustum cullhoz szorosan kapcsolódik a megjelenítési-fa elkészítése/bejárása is. Itt választhatunk 2 lehetőség között hiszen
- vagy mindig bejárjuk az egész fát, amely renderelési technika alapján van rendezve és csak a látható elemeket rendereljük
- vagy mindig dinamikusan ujra elkészítjük a látható elemek és azok renderelési technikája alapján - én ez utobbit használom.
Tapasztalatom alapján a jelenet-fa és a megjelenítési-fa legjobb implementációi a láncolt listák (természetesen a jelenet-fából először ki kell gyűjteni az éppen aktív szereplőket), míg a tér-fa implementációjánál nagyon megfontoltnak kell lennünk! Az implementáció már önmagában is eldöntheti, hogy milyen tipusú jelenetet (külső tér/belső tér/vegyes) leszünk képes kezelni. Talán a legfontosabb kritérium, hogy a keresés hatékonysága minél jobb legyen hiszen ezt a fát többször is be fogjuk járni egy frame alatt!
- A keresések legegyszerűbb módszere a lineáris keresés (vagyis az elemeket mindössze egy rendezetlen listába gyűjtjük), de mivel a keresés ideje az elemek számával arányos nő ezért használata nem javasolt.
- A keresés egy hatékonyabb megoldása ha uniform gridbe (egyenletes rácsba) rendezzük a jelenetet. Ebben az esetben egy, a jelenetet teljesen befoglaló 2D v 3D rácsot készítünk, amelyek teljesen szabályos térrészekre (cellákra)osztják a jelenetet. Ezen cellákhoz (mivel a cellák méretei állandók) egyszerű osztások segítségével hozzá tudjuk rendelni a jelenet dinamikus és statikus elemeit. Hátránya, hogy nagy a tárigénye és bizonyos keresések lassuk (pl. frustum cull esetén a frustum nagyon precíz raszterizálását igényli a rácsra, hiszen egyetlen cella kihagyása is grafikailag elfogadhatlan eredményt ad) valamint lod-technikára kevésbé alkamazható.
- A keresések leghatékonyabb módszere, ha valamilyen elv alapján rendezzük azt a halmazt, amiben a keresést végre kívánjuk hajtani. Ennek a követelménynek legjobban a körmentes összefüggő gráfok( röviden fa) felelnek meg.
Számos fa létezik, amellyel sikeresen feloszthatjuk a teret, de alapvetően kétféle tipusuk létezik: a síkkal és térfogattal rendezők.
A síkkal rendezők csoportja meghatározott síkokkal osztja fel és rendezi a teret egy fába; alapvetően 3 tipusuk létezik:
-bsptree és ennek speciális esete a kd-tree, amely egy térrészt egy síkkal két részre oszt
-quadtree, amely egy térrészt két síkkal négy részre oszt
-octree, amely egy térrészt három síkkal nyolc részre oszt
az osztás mélységének kritériumai jobbrészt a felhasználástól függenek:
-a bsptreek esetén gyakori kritérium, hogy a fák levelei konvex térrészek legyenek és a térnek teljesen zártnak kell lennie (ha jól tudom); ezeket használták régen belső terekhez
-más esetekben a cél az, hogy a levél ne tartalmazzon "túl" sok elemet a jelenetből és a fa ne is legyen tulzottan mély
- az octree-ket leggyakrabban nagy terepek megjelenítéséhez használják
- a quadtreeket pedig olyan helyen, ahol a "felfelé dimenzió" nincs teljesen kihasználva, ilyenek pl bizonyos rpg játékok
Ezen fákat a számításigényük miatt a felhasználás előtt szokták elkészíteni.
A térfogattal rendezők csoportja a jelenet elemeinek térben elfoglalt helye és mérete alapján rendezi őket egy fába. Ebben a fában a jelenet elemei alkotják a leveleket, míg magát a fát absztrakt térfogatok (cellák) képviselik, a fa gyökere pedig egy olyan cella, amely az egész jelenetet magába foglalja (egy adott szintbe tartozó cellák a levelék felé eső cellákat tartalmazzák, a levelektől távol eső cellák pedig őket tartalmazzák)
Attól függően, hogy milyen térfogatokkal rendezzük a fát beszélhetünk
-spheretreeről, mely esetében a fa elemeit gömbökkel rendezzük
-aabbtreeről (népszerűbb nevén bvh), mely esetében a fa egyes elemét, az azt befoglaló, a világ koordinátarendszer tengelyeivel párhuzamos oldalu téglatesttel rendezzük
-oobbtreeről, mely esetében a fa elemeit, az azt befoglaló, a fa elemének koordinátarendszerének tengelyeivel párhuzamos oldalu téglatesttel rendezzük
Számomra a bvh tűnik a legszimpatikusabbnak, hiszen jobban illeszkednek a téglatestek a gömböknél egy adott térfogatra és gyorsabban vizsgálhatóbb, mint egy a világhoz képest elforgatott téglatesösszességében. Úgy tűnik, hogy a bvh a jelenlegi legáltalánosabb és leghatékonyabb térfelosztó módszer mivel generálása jóval gyorsabb, mint bármelyik síkkal osztó fáé, nagyon gyorsan lehet benne keresni valamint lod technikákkal könnyen kombinálható.
Összeségében tehát érdemes 3 fát karbantartanunk ahhoz, hogy egy jól működő és jól terhelhető 3d enginet kapjunk hiszen a különböző feladatok végrehajtásához rendelkezésre állnak a hatékony és specializált tároló adatszerkezetek így ezen feladatok cpu igényét a minimálisra tudjuk csökkenteni. Mindezekből kiindulva lehet gondolkozni a grafikai, fizikai, hang engineken, a játék logikai egységein valamint a mesterséges intelligencián, amelyekről majd későbbiekben írok némi zöldséget:]
