Csoportos útkeresés

OData támogatás
Konzulens:
Rajacsics Tamás
Automatizálási és Alkalmazott Informatikai Tanszék

Az útvonalkeresés nagy szerepet játszik a valós idejű stratégiai játékokban (Real-Time Strategy - RTS). A játékos jó pár egységnek ad parancsokat, és a parancsok többsége igényli, hogy az egység A pontból eljusson B pontba anélkül, hogy ütközne a pályán lévő objektumokkal, beleértve más egységeket is. Ezért szükségessé válik egy olyan útkereső algoritmusnak az alkalmazása, amely képes megtalálni egy ütközésmentes utat a kiindulási pontból a célba, és egy másik algoritmusnak az alkalmazása, amely képes végigkísérni az egységet a megadott úton. Ezen algoritmusokat valós időben kell tudni kiértékelni, így a hatékonyság kulcsfontosságú ebben a problémában. Sajnos a megoldás nem olyan egyszerű, mert több egység is keresi az útját, és megy rajta végig ugyanabban az időben. Ebben az esetben ennek, az úgynevezett naiv megközelítésnek van néhány teljesítmény- és viselkedésbeli problémája, így más algoritmusokat is figyelembe kell vennünk a tervezés során.

Ebben a dolgozatban megmutatjuk a probléma lehetséges részfeladatait, és hogy hogyan próbálták mások ezeket megoldani. Ezután ezen források segítségével mutatunk egy módszert, amely az egységek, mint csoportok sokasága szerint tervezi meg azok útvonalait a virtuális világunkban. Ezek után szabályokat fektetünk le az egységeknek azzal kapcsolatban, hogy hogyan használják a tervezett útvonalat a céljaik elérése érdekében. Nemcsak a probléma megoldása az egyetlen dolog, amit figyelembe kell venni, hanem az is lényeges, hogy az összes algoritmusnak valós időben kell szolgáltatni az eredményeit. Ez azt jelenti, hogy lehetőség szerint az időigényes számításokat offline kell végezni.

Végezetül megadunk néhány metrikát a kifejlesztett algoritmus hatékonyságának mérésére. Ezen mérőszámok segítségével össze tudjuk majd hasonlítani az algoritmust a naiv implementációval, amelyről megmutatjuk majd, hogy rosszabbul teljesít, mint a csoport alapú útkeresés.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.