Information Technology | Studies, essays, thesises » Ziegler Tamás - Valósidejű stratégiai játék komponens alapú fejlesztése

SZAKDOLGOZAT BMF-NIK 2006 ZIEGLER TAMÁS NIK-O-NI-02-204 NEUMANN JÁNOS INFORMATIKAI FİISKOLAI KAR SZAKDOLGOZAT BMF-NIK 2006 ZIEGLER TAMÁS NIK-O-NI-02-204 Budapesti Mőszaki Fıiskola Neumann János Informatikai Fıiskolai Kar Szoftvertechnológia Intézet SZAKDOLGOZAT FELADATLAP Hallgató neve: Törzskönyvi száma: Ziegler Tamás NIK-O-NI-02-204 A dolgozat címe: Valós idejő stratégiai játék komponens alapú fejlesztése Fıiskolai konzulens: Külsı konzulens: Kurdi Zsombor Beadási határidı: 2006. május 15 A záróvizsga tárgyai: Architektúrák Szoftvertervezés és hálózati technológiák A feladat: Tervezzen meg és készítsen el egy valós idejő stratégiai játékot, melyen keresztül bemutatja a komponens alapú fejlesztés módszereit! Ismertesse részletesebben a komponens alapú fejlesztés elméleti hátterét, kiemelve a felhasznált módszereket! A tervezés illetve a kivitelezés során hozott döntéseket indokolja! A program

rendelkezzen grafikus felhasználói felülettel! A dolgozatnak tartalmaznia kell: • • • • • • a feladat leírását, a megvalósítandó feladat tervét, a komponens alapú fejlesztési módszertan átfogó ismertetését, a felhasznált algoritmusok és módszerek leírását, a felhasználói leírást, a programot és a mőködéséhez szükséges adatokat lemezen. Ph. Dr. Tick József intézetigazgató A dolgozatot beadásra alkalmasnak tartom: . külsı konzulens fıiskolai konzulens HALLGATÓI NYILATKOZAT Alulírott szigorló hallgató kijelentem, hogy a szakdolgozat saját munkám eredménye. A felhasznált szakirodalmat és eszközöket azonosíthatóan közöltem Egyéb jelentısebb segítséget nem vettem igénybe. Az elkészült szakdolgozatban talált eredményeket a fıiskola, a feladatot kiíró intézmény saját céljaira térítés nélkül felhasználhatja. Budapest, 2006 . . hallgató aláírása TARTALOMJEGYZÉK 1. BEVEZETÉS,

ÖSSZEFOGLALÁS.3 2. JÁTÉKOK.4 2.1 Számítógépes játékok, kategóriák [1-4]4 2.2 Stratégiai játékok, valós idejő stratégia [1-4]4 2.3 Megjelenítés 5 3. A PROGRAMOZÁSI PARADIGMÁK EVOLÚCIÓJA .8 3.1 Monolitikus programozás [8] 8 3.2 Moduláris programozás [8] 9 3.3 Strukturált programozás [8] 10 3.4 Objektum orientált programozás [8-10]11 3.41 Az objektum orientált programozás fejlıdése11 3.42 Az objektum orientált programozás alapfogalmai12 3.5 Komponens alapú szoftverfejlesztés [5-8] 14 3.6 Szoftver ágensek [15] 16 4. A JÁTÉK FELÉPÍTÉSE.18 4.1 A játékok komplexitásának növekedése [11]18 4.2 A játék alkotóelemei 19 4.21 Mesterséges intelligencia [14] 19 4.22 Grafika és irányítás 21 4.23 Szálkezelés 22 5. A LEHETSÉGES MEGOLDÁSOK .25 5.1 Mesterséges intelligencia 25 5.11 Útvonalkeresı eljárások [12-14, 16]25 5.12 Az alacsony szintő MI további építıelemei 37 5.13 Magas szintő MI - a stratégiai döntéshozó réteg

[14, 17] 37 5.2 Grafika 39 5.3 A komponenskezelési megoldások41 5.4 A párhuzamosság kihasználása 42 6. A KIVÁLASZTOTT MEGOLDÁSOK .44 6.1 Mesterséges intelligencia 44 1 6.11 Alacsony szintő MI 44 6.12 Magas szintő MI 47 6.2 Megjelenítés [18] 49 6.3 Dinamikusan csatolt könyvtárak és szálak kezelése [19-20] 52 7. RÉSZLETES SPECIFIKÁCIÓ .56 7.1 Osztályok felépítése, egymásra épülésük56 7.11 A program felépítése56 7.12 Osztályok leírása57 7.2 Telepítés, szoftver elıkövetelmények63 7.3 A játék kezelése 64 7.3 A pályaszerkesztı kezelése 67 8. MUNKAFÁZISOK, TAPASZTALATOK.70 8.1 Szálkezelés 70 8.2 Útvonalkeresés 70 8.3 Windows API, DLL kezelés71 8.4 DirectDraw 71 8.5 A játék tulajdonságainak fejlesztése, menürendszer implementálása 71 8.6 A pályaszerkesztı kifejlesztése, telepítı létrehozása 72 8.7 A dolgozat megfogalmazása 72 9. TESZTELÉS .73 10. TOVÁBBFEJLESZTÉS LEHETİSÉGEI.74 11. FELHASZNÁLT IRODALOM .75

12. ÁBRAJEGYZÉK.78 13. ZUSAMMENFASSUNG.80 14. ABSTRACT .81 2 1. BEVEZETÉS, ÖSSZEFOGLALÁS Jelen dolgozatban egy valósidejő stratégiai játék komponens alapú fejlesztésén keresztül mutatom be az alkalmazott technikákat, algoritmusokat, valamint magát a szoftverfejlesztés menetét, fejlıdését. Az elsı számítógépes játékok nem sokkal az elsı általános célú, megfizethetı árú személyi számítógépek elterjedése után jelentek meg és kezdték el ma is tartó hódításukat a legkülönbözıbb korosztályokba tartozók óriási körében. Töretlen népszerőségüket a technológia és az alkalmazott algoritmusok gyors fejlıdésének köszönhetik. Míg az elsı játékok egy-egy programozótól származnak, napjainkra ez a módszer számos okból kifolyólag megváltozott. A számítógépes játékok fejlesztése igen nagy iparággá nıtte ki magát. A legmodernebb játékok egyetlen programozó számára átláthatatlanul bonyolultak,

sok, egymástól elütı komponensbıl épülnek fel. Ezen komponenseket külön az adott területre szakosodott programozó csoportok fejlesztik. A gyakran több millió soros programkódok megértése érdekében célszerő a játékokat alkotó fıbb komponensek megismerése. Ugyancsak elengedhetetlen követelmény a programozás módszertanának minél jobb ismerete. E célokat szem elıtt tartva fogalmaztam meg ezt a dolgozatot, felhasználva a területen fellelhetı fontosabb irodalmat, melyek egy része az interneten elérhetı. Ennek oka, hogy a játékfejlesztés, és maga a számítástechnika is rohamosan fejlıdik. A legújabb információk ezért kizárólag elektronikus formában érhetık el. Természetesen azonban feltétlenül fontos megemlíteni az évek folyamán paradigmává vált fejlesztési módszereket, melyek segítségével mind az általános, mind a játék-specifikus programozás átláthatóbbá, hatékonyabbá tehetı, a vétett hibák száma

csökkenthetı. A dolgozatban megtalálható algoritmusok, módszerek a modern játékok építıköveinek mindössze egy részét képezik, hiszen a játék maga rendkívül szerteágazó jelentéssel bír, amely jelentések mindegyike számos komponensbıl épül fel. A komponensek pedig adott esetben egy egész tudománykört takarhatnak le. Példaként említhetı a játékokban alkalmazott mesterséges intelligencia, amely már önmagában is számos részterületre bontható, melyek mindegyikét külön kutatócsoport fejlesztette és fejleszti. Sok esetben szerencsére elegendı az eredeti megoldás egy jelentısen egyszerősített változatát alkalmazni. 3 2. JÁTÉKOK 2.1 Számítógépes játékok, kategóriák [1-4] A játékok az emberi lét alapvetı részét képezik. Nyelvezetük befurakodott beszédünkbe, ahol olyan tevékenységekre, folyamatokra is utalhatnak, melyek valójában nem játékok. A játéknak az élet minden területén való széles elterjedése

két lehetséges akadályt teremt ezen fogalom értelmezése folyamán. Egyrészt, a játék az általános szóhasználatban egy elnagyolt jelentéssel bír. A témához kapcsolódó gondos és kritikus elemzéseket hibásan a tudomány tárgykörébe soroljuk, miközben elsiklunk a játékok tervezésének komplexitása felett. Sok, programozni egyébként jól tudó amatır kezd bele játékfejlesztésbe pusztán a saját, játékprogramokból szerzett tapasztalata alapján. Azok, akik túlbecsülik saját képességeiket, elesnek a tanulás lehetıségétıl. A másik akadály a kétértelmőség. A játék koncepcióját és irányelveit oly széles körben kezdtük el alkalmazni, hogy annak eredeti jelentése meglehetısen elmosódottá vált. Nem létezik egy abszolút letisztult elv, amire rálelhetnénk A játékok tervezıinek nincs olyan jól definiált terminus győjteményük, melynek segítségével egymással kommunikálhatnának. A játékfejlesztésrıl szóló viták

gyakran jelentéstani vitákká alakulnak. Vessünk egy rövid pillantást a játékok fıbb típusaira, melyek a következık: társasjátékok, kártyajátékok, atlétikai játékok, gyermek-játékok, valamint számítógépes játékok. Ezek közül csupán az utolsóra térnék ki A számítógépes játékok igen szerteágazóak. Egy játékot nem lehet egyértelmően egy mőfajba sorolni, hiszen ezen mőfajok absztrakt definíciók. Sokat lehetne vitatkozni magának a mőfajnak a definícióján, de az emberek hajlamosak ugyanazt másféleképp értelmezni, melynek eredményeképpen az évek folyamán a mőfajok kizárólag a használatuk alapján határozhatók meg. Általában a számítógépes játékok típusait azon játékok határozzák meg, amelyek elsıként képviselik az adott kategóriát. Így például, a Wolfenstein 3D1-rıl megjelenésekor a lövöldözıs (Shooter) mőfaj egy új alkategóriájaként beszéltek (first person (3D) shooter). Már a

Wolfenstein elıtt is 1 ID Software, 1992. Készítık: John Carmack, John Romero, platform: PC 4 léteztek olyan játékok, melyek megfeleltek az elıbb említett kategória feltételeinek, azonban a mőfajt ez a játék (valamint utóda, a Doom) határozta meg. A számítógépes játékok fıbb kategóriái a következık: − shooter – lövöldözıs − simulation - szimuláció – labdát kell − computer RPG - szerepjáték pattogtatni, ilyen pl. a Breakout − platform – ugrálós ügyességi (1972, Atari) is − sports − bat & ball − racer - versenyzés − collector - győjtögetıs − video pinball - flipper − puzzle - kirakós − strategy - stratégia − arcade adventure – a kalandés a szerepjáték együttese − rhythm dance – a legújabb kategória, zenére kell reagálni − MMORPG – massive − adventure - kaland multiplayer online role playing − video board game - társasjáték game – több ezer résztvevıs on-

− fighting - verekedıs line szerepjáték A dolgozat címébıl adódóan csak a stratégiai játékot elemzem részletesebben. Ez a kategória valószínőleg a legrégebbi az összes közül. Az elsı ilyen típusú játék a korai 70-es években megjelent szöveg-alapú Star Trek lehetett. Eme mőfaj olyan stratégiai társasjátékokból fejlıdött ki, mint a hetvenes-nyolcvanas évek híres Avalon Hill2 sorozata. A stratégiai játékok fıbb ismérvei a következık: 1. A játékosnak több egységet (vagy egy, de több képességgel rendelkezı egységet) kell irányítania azzal a céllal, hogy legyızze az ellenséget 2. A játékmenet körökre osztott, a játékosnak pedig döntéseket kell hoznia, hogy az aktuális körben mit tegyen az egységeivel A valósidejő stratégia nem kimondottan ebbe a kategóriába tartozik, mivel a játékmenet stílusa talán közelebb áll a szimulációhoz, melynek fıbb jellemzıi, hogy 2 Avalon Hill Company, 1958. Fontosabb

társasjátékok: Gettysburg, Tactics II, D-Day, Waterloo 5 − az ilyen típusú játékok megkísérlik szimulálni egy bizonyos környezet tulajdonságait, legyen az valós (pl. Sim City3), vagy elképzelt (Populus) − ahol erre lehetıség nyílik, ott az erıforrás-menedzsment is szerves részét képezi a játéknak − a játékos több entitás vagy erıforrás irányítását végzi, nem pedig egyetlen karakterét Az elsı szimulációnak nevezhetı játék 1978-ban, az Atari segítségével látott napvilágot, a Skydiver névvel illették és egy egyszerő ejtıernyı-szimulátor volt. Az évek folyamán a szimulációk rendkívül komplexé váltak, jó példa erre az Electronic Arts által 1989-ben kiadott Populus, melyben a Teremtı szemszögébıl irányíthatjuk a játékot („istenjátékok”4 kategóriája). 2.2 Stratégiai játékok, valós idejő stratégia [1-4] A stratégiai játékok középpontjában a gondos tervezés és a jól kidolgozott

erıforrás menedzsment áll. Ezen mőfaj képviselıi lehetnek körökre osztottak, illetve valós idejőek, valamint lehetséges e kettı keveredése is (pl. X-COM5) Bár a kategóriába tartozó programok nagy hányada háborús jellegő, akad jó pár, melynek fókuszában nem a háború áll. Az alternatívák között találkozhatunk például közgazdasági szimulációkkal, épületek, a közlekedés menedzselésével is (Transport Tycoon6). A valós idejő stratégia (real-time strategy – RTS) a fentebb taglalt mőfaj egy olyan alkategóriája, amely nincs körökre osztva, hanem a játékbeli idı megfeleltethetı a valóságban eltelt idınek, így a játékmenet folytonos. Míg maga a stratégia szó eredetileg a magas szintő háborús tervezést jelenti (hadseregek összeállítása, hadjáratok, ill. egész háborúk megtervezése, lebonyolítása), addig a valósidejő stratégiai játékokban az egyes egységeket külön-külön vezérelhetjük. A játékmenet

általában nélkülözhetetlen részét képezik a termelés és a gazdaság különbözı aspektusai, úgy 3 SimCity: 1989, Maxis. egy absztrakt térben lévı, "mindenek feletti" szuperegóként irányítunk egy társadalmi, gazdasági, kulturális evolúcióra képes makroközösséget 5 játék sorozat, mely 1994-ben indult útjára a MicroProse gondozásában 6 1995, MicroProse 4 4 mint a nyersanyag győjtése, épületek elhelyezése, egységek gyártása, stb., és bár a harci összecsapások eme játékok elengedhetetlen részét képezik, mégis ezen részek a valóság általában igen erısen leegyszerősített képét reprezentálják, relatív kis hangsúlyt fektetve a hadviselési taktikák részletes modellezésére, realizálására. Általában a valósidejő stratégiai játékok idıbeni lefutása a következı: 1. A bázisunk és hadseregünk felépítése (gazdaság létrehozása) 2. Erıforrások meglétének biztosítása 3. Az ellenfél

letámadása (erıforrásoktól való megfosztása, infrastruktúrájának megsemmisítése) Ettıl eltérnek a valós idejő taktikai játékok, melyekben az egységek száma, a bázisok elhelyezkedése, felépítése elıre meghatározott, arra kényszerítve a játékost, hogy csak a már birtokában lévı számú egységeket használhatja fel. Bizonyos valósidejő stratégiai játékok magukban foglalhatják a valósidejő taktikai játékok elemeit. Erre láthatunk példát a Command & Conquer-ben is, amikor az adott küldetésben nincs lehetıségünk bázist építeni, hanem csak az induláskor birtokunkban lévı egységekkel harcolhatunk. 2.3 Megjelenítés A számítógépek architektúrájának folyamatos fejlıdése a játékiparban sem maradt nyom nélkül. A fejlıdés egyik mérföldövét a megjelenítés hardveres gyorsítása jelentette. Már a kezdetekben is a megjelenítés gyorsítása volt a cél, ezért volt célszerő egyenesen a videó memóriába írni

az adatokat. Az elsı 3Dfx Voodoo kártya megjelenésével azonban ettıl jóval több mindent elérhettek a játékfejlesztık. Napjainkban a három dimenzionális megjelenítést támogató videó kártyák a jelentıs fejlıdés következtében rendkívül valósághő képszintézist tesznek lehetıvé, természetesen valós idıben (2. ábra) Eme videó kártyák grafikus processzorai legalább olyan komplexitással rendelkeznek, mint egy korszerő központi vezérlı egység. A miniatürizáció segítségével a jelenlegi csúcskategóriát képviselı grafikus gyorsítók 5 több, mint 300 millió tranzisztorból állnak, és annyi dedikált memóriával rendelkeznek, mint amennyit 2-4 évvel ezelıtt egy egész számítógépben találtunk. A játékok megjelenítése alapján nincsenek külön kategóriák meghatározva, alkategóriák azonban kialakulhatnak ezt alapul véve. Ezen módok általánosságban a következık voltak / lehetnek: − szöveges − 2D

− izometrikus − 1st person 3D − 3rd person 3D − 2 ½ D - „two-and-a-half D” Ezek közül az izometrikus megjelenítést taglalnám, mivel a programom ezt használja. Az izometrikus szó egy olyan megjelenítési technikát jellemez, amely párhuzamos egyenesek segítségével alkotja meg a háromdimenziós képet. Az izometrikus koordinátarendszer tengelyein az egységek azonos hosszúságúak. Legáltalánosabb formája, amikor a három tengely mindegyike 120°-os szöget zár be a szomszédaival, mint ahogy az az elsı ábrán látható. Az elsı ilyen megjelenítési módot alkalmazó játék az 1982-ben a Sega/Gremlin által kiadott lövöldözıs Zaxxon volt. 1. ábra: izometrikus koordinátarendszer 6 2. ábra: játékok grafikája régen (maze) és ma (GTR 2) 7 3. A PROGRAMOZÁSI PARADIGMÁK EVOLÚCIÓJA A szoftverfejlesztés kifinomultabbá vált. módszertana Egyrészt, az a egyre számítógépek gyorsabb, fejlıdésével egyre egyre

univerzálisabban programozható központi egységeknek és a növekvı operatív táraknak köszönhetıen lehetıség nyílt egyre komplexebb programozási nyelvek és paradigmák kifejlesztésére. Másrészrıl a számítástechnika gyors térhódításából adódóan egyre nıtt az igény a hatékony, gyors, és kiváló minıségő programok elıállításának lehetısége iránt is. 3.1 Monolitikus programozás [8] A számítástechnika hıskorában a monolitikus programozási módszer volt a jellemzı. A programozás kialakulásakor a program egy egyszerő szekvenciát jelentett, aminek a felhasznált adatok mellett az operatív tárban el kellett férnie. Ezt a szekvenciát nem lehetett, illetıleg igen körülményes volt a fejlesztés közben tesztelni, mivel a programok kezdetben pl. lyukkártyán helyezkedtek el Nagyrészt lineáris felépítésőek voltak, helyenként szelekciót és / vagy iterációt tartalmaztak. Egy program gyakran egy programozó munkájának

eredményét képezte, aki a nem túl bonyolult feladat megoldásának algoritmusát átlátta. Az idı folyamán a realizálandó feladatok bonyolultsága fokozódott, ami rávilágított a módszer hiányosságaira, hátrányaira. Ha egy program egy bonyolult feladatot hivatott megoldani, akkor elkerülhetetlen a program bonyolult felépítése, a fejlesztés több ember közt történı szétosztása. Monolitikus kód esetén nagyon nehéz, illetve egy bizonyos fokú bonyolultság elérése felett gyakorlatilag lehetetlen átlátni egy belsı struktúrával nem rendelkezı programot. Ezt figyelembe véve adott esetben a szoftver továbbfejlesztésére fordított erıforrások jelentıs hányadát emésztheti fel a program mőködésének megismerése, esetleges hibáinak felderítése. Bár a paradigma elavultnak tőnhet, alkalmazásával találkozhatunk még egyszerőbb mikrovezérlık esetében, ahol az igen egyszerő architektúrális tulajdonságokból adódóan más módszer

alkalmazására nincs lehetıség. Fejlesztésre általánosan az 1960-as évek végéig használták. 8 3.2 Moduláris programozás [8] A fejlesztés következı lépcsıfokát a moduláris programozás jelentette. A paradigma lényegét a megoldandó probléma, ill. problémák olyan részfeladatokra történı bontása képezi, amit már egy programozó viszonylag tisztán átlát, és megoldása kézenfekvı. Az ilyen módon képzett modulokat monolitikus módon fejlesztették ki Az egyes modulok közötti együttmőködési felületet - az interfészt – gondosan kellett megtervezni a késıbbi problémák elkerülése érdekében. A feladat egyszerőbb részfeladatokká történı felosztásának két lehetséges módja létezik. Az egyik az ún. „Top-Down” dekompozíciós módszer, amelynek lényege, hogy az eredeti feladatot egyre kisebb részfeladatokra bontjuk. Ezek a részek kizárólag a programozók által jól definiált interfészen keresztül kommunikálhatnak

egymással. Amennyiben bármely két modul közt problémák lépnek fel az interfészt illetıen (például a paraméterek nem illeszkednek megfelelıen a megoldandó feladathoz), két lehetséges utat választhatnak az adott modul fejlesztıi. Az egyik megoldás értelmében úgy értelmezik a modul belsejében az interfészben meghatározott paramétereket, hogy az saját céljaiknak megfeleljen. A másik esetben a két modul közti interfész módosítása szükséges. Az elsı megoldás alkalmazása esetén teljesítmény- és erıforrásbeli problémák léphetnek fel. A második megoldás elınyösebb, mivel az interfészek a módosítás folyamán szabványosak maradnak, a program teljesítménye pedig az optimális közelében tartható. Az összetett feladatot a „Bottom-Top” kompozíciós módszer segítségével is részekre bonthatjuk. Rövid programok esetén érdemes alkalmazni, mivel a fejlesztés folyamán szem elıtt kell tartani a teljes program felépítését.

Lényege, hogy elıször az elemi építıköveket, algoritmusokat írjuk meg, ezekbıl magasabb szintő struktúrákat alkotunk, majd pedig végül összeállítjuk a teljes programot. Ezt a módszert leginkább hardverközeli programok írásakor alkalmazzák. A gyakorlatban a két módszert általában együttesen alkalmazzák. A program vázát a dekompozíció elvén határozzák meg, míg a sebesség-kritikus részeknél a Bottom-Top módszert támogatják a fejlesztık. Általánosságban a moduláris programozás elınyei között említhetjük meg, hogy a szoftver könnyebben, gyorsabban írható meg, tesztelhetı le, mivel a modulok akár párhuzamosan is fejleszthetık. Hibás mőködés esetén a javítás is egyszerőbb, mint a monolitikus elven megírt program esetében. Egy 9 program továbbfejlesztésénél, illetıleg egy másik program írásakor a már kész modulok újrahasznosíthatók, amennyiben azokat szabványosan fejlesztették ki. 3.3 Strukturált

programozás [8] Az 1970 – 1980-as évek uralkodó módszertana a moduláris programozásnál ismertetett Top-Down elvet továbbfejlesztve határozza meg a programírás mikéntjét. Alapvetıen két oldalról közelíthetjük meg a problémát attól függıen, hogy az elkészítendı szoftver adatmodelljét vagy eljárásmodelljét vesszük alapul. A strukturált fejlesztés egy absztrakt leírását Edsger W. Dijkstra fogalmazta meg hierarchikus programozás néven. Lényege, hogy a megoldandó feladathoz a program egy absztrakt programsorozat határértékeként alakul ki. A sorozat következı eleme az ıt megelızı elem egy részfeladatának finomításával, kifejtésével áll elı. Az eljárásmodellt alapul véve Harlan Mills kidolgozta a funkcionális programozás elvét, ahol a feladat határozza meg a program szerkezetét, illetve a probléma tevékenység alapján bontható részproblémákká. Az adatmodell felıli megközelítés esetén találkozunk az

adatorientált programozási módszertannal, melyet Michael A. Jackson és Warnier dolgozott ki Itt a felbontás alapját a program által manipulált adatok szerkezete határozza meg, melynek hátránya, hogy a módszer csak adatfeldolgozási területen életképes. A módszert az 1966-ban Corrado Böhm és Guiseppe Jacopini 1964-ben kiadott, majd 1968-ban Mills által bebizonyított és kiegészített cikkben leírt vezérlési szerkezetek adatokra történı adaptálása alapján dolgozták ki. A cikk lényege, hogy minden algoritmus leírható három vezérlési szerkezet segítségével: − szekvencia = szekvenciális programkód − szelekció = feltétlen és feltételes elágazások − iteráció = ciklusok Mills ezt így egészítette ki: 1. Egy program akkor jó, ha a szerkezete leírható egy szekvenciaként, amely szekvencián belül a fenti három vezérlési szerkezet megengedett. 2. Egy szekvencia elembe a külvilágból egy ponton lehet be-, illetve kilépni 10

3. Ha egy program ilyen, akkor az strukturált Kellemesen dokumentálható, módosítható. A strukturális programozásban a GOTO használata nem megengedett, mert az megsérti a 2-es pontot. Vannak azonban olyan algoritmusok, ahol ennek használata elkerülhetetlen, ilyen például a nem rekurzív quicksort algoritmus7. 3.4 Objektum orientált programozás [8-10] 3.41 Az objektum orientált programozás fejlıdése Az 1970-es évekre a kifejlesztendı szoftverek bonyolultsága eljutott egy olyan szintre, amit az addigi paradigmákkal csak nehézségek árán lehetett kezelni. Világossá vált, hogy az adat- és funkcionális modellek egymástól nem választhatók el. Az adatokat a rajtuk végrehajtandó mőveletekkel együtt kell alkalmazni. Az objektum orientált programozás (a továbbiakban OOP) gyökereinek kutatásakor feltétlenül szólnunk kell Alan Kay-rıl, akit az OOP egyik atyjaként tartanak számon. İ inspirálta a szoftvertörténelem egyik legfontosabb

újítását Az 1950-es évek vége felé a denveri Randolf légi bázison állomásozott, assembly kódokat írt és töltött át mágnesszalagra egy elektroncsöves Burroughs B2208 típusú számítógéphez. Nagy nehézségbe ütköztek a programozók, amikor a Burroughs gépekrıl szerettek volna adatokat mozgatni más kiképzıbázisokra, mivel nem léteztek egységes fájlformátumok. A nyers adatokat ugyan ki lehetett írni egy mágnesszalagra, de a másik számítógép nem tudott mit kezdeni az egyesek és nullák sorozatával, lévén hogy nem volt egy „közös nyelv”, amit beszélhettek volna. A problémára Kay egy szellemes megoldást dolgozott ki: a Burroughs gépre írt programokat, adatokat mini programokká alakította át. A miniprogramok belsejébe elhelyezte az adatokat és az azokat manipuláló kódokat, majd pedig elrejtette a modulok belsejét egy egyszerő interfész mögé, melynek segítségével más számítógépek megérthetik, használhatják a

modult anélkül, hogy tudomásuk lenne a modulok belsejében lévı formátumról. 1961-ben, amikor realizálta elgondolásait, 7 8 Lovász-Gács-féle nem rekurzív quicksort algoritmus 1957, a központi számító egység (CPU) 1800 elektroncsıbıl állt, 10,000 szavas memóriával rendelkezett, a szóhossz 44 bit hosszúságú volt. Kb 50 darab épült az USA-ban, egyenként $640,000 $1,200,000 dollárért 11 még nem volt nyilvánvaló számára, hogy a késıbbiekben ez milyen áttörést jelent majd a szoftverfejlesztésben. Közel hat év alatt az ötlet Alan Kay a Xerox Palo alto-i kutatólaboratóriumában9 végzett munkásságának köszönhetıen átalakult a programozás ma is igen elterjedt, átütı sikerő módszerévé, az objektum orientált programozássá. Munkája során a Simula10 nyelvbıl, és az Ivan Sutherland által írt SketchPad programból is merített ötleteket. A késıbbi fejlıdés a következı állomásokhoz köthetı: − 1972-ben már

konkrét elképzelések voltak egy OOP nyelv specifikációjáról − 1981-ben az EIFFEL, valamint egy pár más eljárás-orientált programnyelvben bevezették az OOP eszközrendszert − az 1980-as évek végén a C nyelv bıvítéseként létrejött a C++, majd a Pascal nyelvet is bıvítették ebbe az irányba (Object pascal) − az 1990-es évek közepén megszületett a Java nyelv, amely teljesen az OOP paradigmáit követi − 1990-es évek vége: minden modern programozási nyelvet kibıvítik az OOP elveinek megfelelıen − 2001-ben megjelenik a Microsoft által kifejlesztett C# . A nyelv már a komponens alapú paradigmát testesíti meg. 3.42 Az objektum orientált programozás alapfogalmai Az OOP legfontosabb pillére az osztály. Az ember az objektumokat automatikusan rendszerezi, s azokat a számára fontos tulajdonságok alapján kategóriákba, osztályokba sorolja. A fejlesztésben sincs ez másként: az azonos attribútumú és metódusú objektumok összessége az

osztály. Az osztályok azt a célt szolgálják, hogy a programozó az adott nyelvbe épített adattípusokkal azonos kényelmi szinten használható új adattípusokat hozhasson létre. Ha egy osztályt példányosítunk, egy objektumot kapunk. Az objektum példányokat viselkedésük szerint osztályokba soroljuk. Egy más szemszögbıl tehát az osztályok tekinthetık típusoknak, az objektumok pedig egy adott típusú változót testesítenek meg. Fontos tulajdonsága, hogy rendelkezik állapottal, amely állapot az 9 PARC – Palo Alto Research Center, 1970, California Simula, programozási nyelv, eredetileg a norvég hadsereg szimulációkhoz alkalmazta, készítık: OleJohan Dahl és Kristen Nygaard 10 12 objektumban lévı adatokat reprezentálja, ezek tetszılegesen komplexek lehetnek. Egy bizonyos feladat után az objektum állapota megváltozhat. A következı megemlítendı fogalom az egységbezárás. A terminus alatt azt értjük, hogy az, hogy egy objektum az

adott feladatot hogyan implementálja, az objektumot felhasználó programozó, vagy egy másik program számára nem releváns, illetıleg az az objektum „magánügye”, ezáltal az objektum specifikációja és implementációja szétválasztható. A bezárás eszközeinek segítségével megadható egy objektumon belüli attribútum vagy metódus hozzáférési módja. Ezek a hozzáférési módok általában a következık lehetnek (ezeken kívül léteznek még láthatósági megnevezések, azonban azok a felsoroltak közti árnyalatokat képezik): − nyilvános (public) – az attribútum vagy metódus kívülrıl (tehát az objektumon kívülrıl) minden további nélkül elérhetı, módosítható (attribútum esetén) − védett (protected) – a jelzés csak az adott osztályban, illetıleg annak gyerekeiben teszi elérhetıvé az adott entitást − privát (private) – az adott attribútumot vagy metódust kívülrıl nem tudjuk sem elérni, sem módosítani

(attribútum esetén) Az osztály és az objektum tisztázása után térjünk rá az öröklıdés fogalmának definiálására. Az öröklıdés azt jelenti, hogy egy osztály örökölhet tulajdonságokat és viselkedésformákat, tehát attribútumokat és metódusokat egy másik osztálytól. Az utód osztályban csak az ısosztálytól való eltéréseket kell megadnunk. Lehetıségünk van az ısosztály metódusainak újra implementálására is. A különbözı programozási nyelvek eltérhetnek a tekintetben, hogy egy utód-osztályt hány ıs-osztályból származtathatunk. Míg a C++ megengedi a többszörös öröklıdést, addig a Java-ban vagy a Pascal-ban csak egyszeres öröklıdést alkalmazhatunk. Ezek alapján az egy-egy kapcsolatot egy fával, míg az egy-sok kapcsolat ábrázolásához már egy gráfra van szükségünk. Az öröklıdéshez kötıdik az interfész fogalma. Az interfész egy olyan definíció, amelyben meghatározott metódusok nincsenek

implementálva. Ez azt jelenti, hogy egy interfésszel megmondhatjuk, hogy egy osztálynak mit kell tudnia, azt viszont nem határozzuk meg, hogy ezt hogyan, milyen módon tegye meg. A polimorfizmus (többalakúság) az, melynek segítségével az OOP elınyei igazán láthatóvá, kézzelfoghatóvá válnak. Lényege, hogy ugyanarra az üzenetre két különbözı 13 objektum különbözıképpen reagálhat. Másképp megfogalmazva a polimorfizmus különbözı típusú objektumpéldányok azon tulajdonságát jellemzi, amely alapján a két objektum ugyanolyan nevő metódusa különbözı eredményt ad ugyanolyan paraméterezés mellett. Minthogy a programozónak, illetıleg a programnak nem szükséges elıre tudnia az objektum pontos típusát, ezért csak a program futtatása során dıl el, hogy az adott üzenet pontosan melyik metódus hívását eredményezi. Ezt késıi kötésnek (late-binding, dynamic-binding) nevezzük. Abban az esetben, ha pontosan ismert az

objektum típusa, a fordító a fordítás során hozzá tudja rendelni az üzenet hívását a megfelelı metódushoz. Ez a korai kötés (static-binding) A polimorfizmus alkalmazásával lehetıség nyílik úgy megírni egy programot, hogy csak absztrakt interfészeket alkalmazunk. Ez az örökölhetı interfészeknek köszönhetı Az objektum-orientált programnyelveknek két lehetséges változata létezik, az egyik, amikor teljesen OOP az egész környezet, minden eszközt egy objektum valósít meg. Ilyen például a C#, ahol például a legelemibb integerként11 deklarált változó is egy objektum, melynek különféle metódusai segítik a programozó munkáját. A másik lehetıség az úgynevezett hibrid nyelvek, melyek ugyan eljárás-orientáltak, de rendelkeznek OOP kiegészítéssel. Ilyen nyelv például a C++, ahol az integerként deklarált változó nem egy külön objektum, mindössze egy egyszerő attribútum. 3.5 Komponens alapú szoftverfejlesztés [5-8] A

komponens alapú programozás módszere az OOP alapján, azt kiegészítve jött létre, azonban attól egy magasabb absztrakciós szintet képvisel. A komponensek használatának ötlete már régóta létezik. Bár sokféle definíció fogalmazódott meg, komponens alatt általában egy újrafelhasználható, hibás mőködés esetén könnyen cserélhetı egységet értünk. Ezt a koncepciót már sikeresen alkalmazzák különféle területeken, így például az autógyártásban is. A számítástechnikában, a szoftverfejlesztésben az utóbbi 6-8 évben jut egyre nagyobb szerephez. Kialakulásának, elterjedésének okai közé sorolhatjuk a programok elkészítésére szánt idı csökkenését (határidık), kitőnı minıségük és gazdaságosságuk iránti igényt, illetve ezen igen gyorsan változó igényekhez való gyors alkalmazkodási képességet. 11 int: általában az adott architektúra szóhosszától függı hosszúságú egész szám. Általában 16,

32 vagy 64 biten ábrázolják 14 A komponensek alapötlete a már említett újrafelhasználhatóság. A cél tehát, hogy egy már elkészített, több helyen is felhasználható szoftver egységet ne kelljen újra és újra kifejleszteni, illetve egy kész alkalmazás esetleges javítása esetén ne kelljen a teljes programot újraírni. Ezen cél elérése érdekében a komponenseknek jól definiált és dokumentált interfésszel kell rendelkezniük. Két különbözı típusú komponens alapú fejlesztést különböztethetünk meg. Az egyik esetben nem csak a programot írjuk meg, hanem azt a komponenst is, amit a programunk használni fog. A módszer elınye abban rejlik, hogy az ily módon elkészített komponens skálázhatóvá válik, saját, késıbbi programjainkba sokkal könnyebb lesz beilleszteni, emellett nem kell aggódnunk a kompatibilitásból adódó problémák miatt sem. Az érem másik oldalát akkor érezhetjük igazán, ha egy komplex komponensrıl van

szó, mivel ilyen esetben a fejlesztés jelentıs erıforrásokat emészthet fel. A komponens alapú fejlesztés másik módszere esetén a tervezés, fejlesztés folyamatában egy új szemléletmódot figyelhetünk meg. Itt ugyanis a programunkat megvásárolható, mások által elkészített komponensekbıl építhetjük fel. Az új szemléletmód abból adódik, hogy a kereskedelemben beszerezhetı komponensek nem pontosan a mi igényeinket elégítik ki, hanem egy átlagos igényt, ezen kívül ezek a komponensek könnyen változhatnak, de ezt a változást is a piacon megjelenı újabb igények okozzák inkább, mint a mi konkrét igényünk. Mivel ezeket a komponenseket megvásároltuk, nem láthatjuk, hogyan vannak implementálva, így a dokumentációra kell hagyatkoznunk. Elıfordulhat azonban, hogy egyes funkciók nem dokumentált mőködést tanúsítanak egyes esetekben, például akkor, amikor más gyártó által készített komponensekkel együtt kívánjuk használni

ıket. Ez a módszer egyértelmő hátrányának tekinthetı. A szoftver komponens definícióját sokan megfogalmazták már, Clemens Szyperski szerint12 például „A szoftver komponens egy kompozíciós egység szerzıdésszerően specifikált interfészekkel, amelyik környezetétıl kizárólag a leírtak szerint függ. Függetlenül telepíthetı, és harmadik fél számára is felhasználható” Egy másik13 megfogalmazásban: „Az újrafelhasználható szoftver komponensek önhordó, világosan azonosítható részek, amelyek specifikus funkciókat írnak le, vagy hajtanak 12 European Conference of Object Oriented Programming (ECOOP), Workshop on Component Oritented Programming(WCOP), 1997 13 Sametinger 15 végre, világos interfészük van, megfelelıen dokumentáltak, és meghatározott újrahasználati státuszuk van.” 3.6 Szoftver ágensek [15] Mindenképp érdemes pár szót szólni az ágensekrıl, hiszen ezek, a mesterséges intelligencia tudományából

származó programegységek is beleilleszkednek a szoftverfejlesztés evolúciójába. Szoftver ágensek alatt azokat a programokat értjük, amelyeket egy, a számítógép által generált környezetbe helyezve feldolgozzák a feléjük érkezı jeleket, és ezen információkat felhasználva vissza tudnak hatni saját környezetükre, aminek változását folyamatosan figyelemmel kísérve döntenek következı lépéseikrıl. Így egy folyamatos visszacsatolás valósul meg Az ágens alapötletét már 1977 augusztusában megfogalmazta Carl Hewitt14 és Henry Baker egy, a programozási koncepciók formális leírásáról szóló konferencián: „Önhordó, interaktív és párhuzamosan végrehajtható objektum, mely rendelkezik belsı státusszal, és kommunikációs képességekkel”. A definícióból jól látszik, hogy az ágensek az objektum orientált szemléletmódból fejlıdtek ki. A szoftver ágenseket igen széles körben alkalmazzák. Segítségükkel

lehetséges különféle szimulációk végrehajtása, modellek leképzése, valamint egyéb szabályozó mechanizmusok tanulmányozása. A játékokban az ágens irányíthatja az ellenfeleinket, az interneten való vásárláskor pedig segíthet kiválasztani a számunkra megfelelı terméket. A felhasználói ágensek rendszerezhetik e-mailjeinket az általunk megadott kritériumok alapján. Egy cég számítógépparkjának állapotának ellenırzését rábízhatjuk a felügyelı ágensekre, az adatbázisokban pedig az ún. „adatbányászó-ágensek” segíthetnek hamarabb elvégezni a feladatainkat. 14 Massachusetts Institute of Technology (MIT) 16 3. ábra: szoftver ágensek kategóriái (forrás: wikipediaorg) 17 4. A JÁTÉK FELÉPÍTÉSE 4.1 A játékok komplexitásának növekedése [11] A számítógépek rohamos fejlıdésüknek köszönhetıen mára a mindennapjaink részévé váltak. Minthogy a játék létünk egyik fontos részét képezi, talán nem

meglepı, hogy a számítástechnikában is jelentıs iparággá nıtte ki magát. A legelsı játékok egyike a Spacewar volt, amely egy PDP-1-es gépen futott. Azóta rengeteg kategória alakult ki, mint ahogy ezt egy korábbi fejezetben már megfogalmaztam. A teljesítmény növekedésével lehetıség nyílt egyre komplexebb folyamatok programozására. Egy modern stratégiai játékban például a bonyolult, összetett mesterséges intelligencia implementációján kívül a játék megjelenítésére is sok gondot fordítanak a játékfejlesztı cégek szakemberei. Napjainkban már nem számít ritkaságnak, ha egy ilyen játékban az egységek, épületek, erdık okozta fény-árnyék hatásokat nem elıre kiszámolt adatok alapján jelenítik meg, hanem a feladatot rábízzák a videó kártyára. Az egységek az ıket körülvevı világ részét képezik, azok ingereire reagálni tudnak. Ezt a játékokban egyre jobban lemodellezett fizika teszi lehetıvé. Jelenleg a

játékok túlnyomó többségében szoftver alapú fizikai motorral találkozhatunk, amelynek számításai a központi processzort terhelik. Ilyen például a széles körben alkalmazott Havok15 cég fizikai motorja. A jelenlegi tendenciák azonban azt mutatják, hogy a fizikát szimuláló szoftvermegoldásokat hamarosan a hardveres megvalósítás fogja felváltani. Az elsı fizikai gyorsítókártya az ageia cég PhysX nevő terméke. A teljesen új hardverelem létrehozása mellett egy másik lehetıség is létezik, ahol a grafikus processzor párhuzamos felépítését és teljesítményét használják fel annak érdekében, hogy a fizikai számítások által okozott többlet feladatokkal ne a központi processzort kelljen terhelni, így a felszabaduló erıforrásokat másra, például a mesterséges intelligencia számításainak elvégzésére lehet használni. 15 Havok, 1998-ban alakult Dublin-ban, ezt a fizikai motort használja például az Age of Empires III, a Half

Life 2 és a F.EAR is 18 4.2 A játék alkotóelemei Amint az elızı fejezetben is olvasható, egy stratégiai játék több részbıl áll össze. A játék fejlesztése során különös figyelmet fordítottam arra, hogy a játékot felépítı komponensek felépítése, mőködése - amennyire ezt a komponens típusa, funkciója megengedi – lehetıleg minél jobban megközelítsék a 3.5-ös fejezetben taglalt komponens definícióját. 4.21 Mesterséges intelligencia [14] Az elsı komponens a mesterséges intelligencia, amellyel nagy valószínőséggel találkozhatunk a játékokban. A játékfejlesztık már régóta ruházzák fel az intelligencia jegyeivel az általuk fejlesztett játékok szereplıit, kezdve a klasszikus arcade Pac Manban felbukkanó szellemektıl az Unreal bot16-jain keresztül napjaink legújabb játékaiig. A mesterséges intelligencia (MI) a számítástudomány azon területét jelenti, amely az intelligens viselkedéssel, a tanulással és a

gépek adaptációjával foglalkozik. A játékokban implementált intelligencia sok esetben nem képes a tanulásra, ezért tulajdonképpen mindössze az intelligencia jelenlétének látszatát kelti a játékosban. Bár sok játéknál ez elegendı, egy jól kidolgozott MI ugyanúgy javíthat a játék élvezhetıségén, akár a részletesen megvalósított fizika, vagy az ámulatba ejtı grafikai effektusok. A játékokban megvalósított MI általánosan két csoportra osztható Ezek a determinisztikus és a nem-determinisztikus mesterséges intelligenciákat jelentik. A determinisztikus csoportba esı implementációk lépései jól elıreláthatóak, nincs bennük semmi véletlenszerőség, éppen ezért ez a típus képezi a játékokban megtalálható MI alapját. Mivel azonban ezek az algoritmusok nem képesek a tanulásra, és szinte biztos, hogy ugyanolyan feltételek teljesülésekor teljesen megegyezı eredményt produkálnak, rövid játék után igen jól

megjósolható az MI következı lépésének eredménye, amely viszont csökkenti a játék élettartamát. Jó példája a determinisztikus viselkedésmódnak az egyszerő követı algoritmus. Teljesen világosan kódolható az az algoritmus, amely az X és Y (valamint 3D esetén Z) koordináták változtatásával a megadott célpont felé mozgatja a karaktert mindaddig, amíg a célpont és a karakter koordinátái meg nem egyeznek. A nem-determinisztikus megoldások nevükbıl adódóan pont az ellentettjük a determinisztikusokénak. Bizonyos mértékő véletlenszerőséget tartalmaznak, és e miatt 16 bot – a robot szóból ered, a játékon belül egy, a gép által irányított karaktert jelent, amely úgy viselkedik, mintha ember irányítaná, jelenthet egy szoftver ágenst is 19 sokkal nehezebb, vagy lehetetlen elıre megjósolni a következı lépés eredményét. A módszer elınyei közé tartozik az, hogy például nem kell a játék minden egyes pályájánál

pontosan meghatározni a gépi játékos mőködését, mivel az úgymond „magától rájön”, hogy mit kell tennie. Emellett pedig az elıre nem látható helyzetekre képes lesz megfelelı módon reagálni az MI. A nem-determinisztikus MI mőködését egy olyan gépi ellenfélen át lehet megérteni, amely képes a játékos harci taktikáját elemezni, azt felhasználva saját, jobb eredményekkel kecsegtetı taktikát kidolgozni. A játékfejlesztı cégek ugyan alkalmazták már a nem-determinisztikus mesterséges intelligenciát játékaikban, azonban az egyre szőkölı határidık, a rövidülı fejlesztési ciklusok hatására a legújabb technológiák teljes megértésére szánt idı rendkívüli mértékben lecsökkent. Egy olyan játék kifejlesztéséhez, melyben tanulni képes mesterséges intelligenciát alkalmaznak, több idı szükséges a hosszabb tesztelési, hibakeresési fázisok miatt, azonban ezzel együtt a játék sokkal hosszabb ideig marad érdekes a

játékos számára. A legoptimálisabb út, ha a fejlesztés során mind a determinisztikus-, mind pedig a nem-determinisztikus módszerbıl merítünk elemeket, azokat megfelelıen alkalmazva. Számos játékfejlesztı alkalmazza ezt a módszert, és a többi MI algoritmussal (döntési fák, neurális hálók és genetikus algoritmusok) ötvözve olyan játékokat alkottak meg, mint például a Creatures17, vagy a híres Black&White18. A játékban megvalósítandó MI két alkotóelemre osztható fel, az alacsony- és a magas szintő intelligenciára. A játékban megtalálható alacsony szintő mesterséges intelligencia feladata, hogy az egységek alap szintő képességeit megvalósítsa. Alacsony szintrıl beszélhetünk abban az esetben például, ha egy egységnek azt az utasítást adjuk, hogy menjen el a jelenlegi pozíciójából egy másikba. Ekkor elvárjuk az egységtıl, hogy a lehetıségekhez mérten megtalálja a legoptimálisabb útvonalat. Ugyancsak ide

sorolhatjuk azt az esetet, amikor az egység a mozgása során egy másik egységgel ütközne. Ekkor természetesen fontos, hogy a két egység észlelje egymást, és ne tudjanak egymáson keresztülhaladni. Ez például jó példája a növekvı teljesítmény kihasználásának, ugyanis a korábbi játékokban (nem feltétlenül a valós idejő stratégiát alapul véve) ezt a tulajdonságot nem mindig implementálták. Egységeinktıl azt is elvárjuk, hogy amennyiben észrevesznek egy ellenséget, akkor arra valami módon reagáljanak. Ennek több lehetséges módja is elképzelhetı Az egyik pl, hogy kezdje el lıni az ellenséget, és folytassa ezt a tevékenységet mindaddig, amíg vagy el nem 17 18 Mindscape Entertainment: Creatures, 1997 Lionhead Studios: Black&White, 2001 20 pusztította azt, vagy az a hatósugarán kívülre nem kerül. Egy másik, adott esetben intelligensebb megoldást az jelentheti, hogy amennyiben az egység egy csoport tagja, akkor jelezze

az ellenség észlelésének tényét a csoportvezetınek, aki ezen információ birtokában vagy eldönti, hogy milyen lépéseket tegyen, vagy amennyiben kapcsolatban áll valamely nagyobb egység irányítójával, az elızı egységhez hasonlóan üzenetet küld annak. Ez a lehetıség azonban már egy erısebb, intelligensebb implementációt igényel A magas szintő intelligencia az egységekkel már csak közvetetten foglalkozik. Míg az alacsony szintet mind a játékos, mind a gépi ellenfél egységeiben megtalálhatjuk, addig a magas szint tulajdonképpen magát a gépi ellenfelet jelenti, akit le kell gyıznünk a játék folyamán. Feladatai közé tartozik a pálya felfedezése, az infrastruktúra megteremtése, az ellenfél (aki ebben az esetben a játékos) felkutatása és megsemmisítése, valamint a tanulás. Tanulás alatt azt értem, hogy például egy adott pályát ne kelljen mindig elölrıl felfedeznie, hanem az egyik játszma folyamán a pályáról szerzett

információit fel tudja használni egy másik játékban (leszámítva természetesen azt az esetet, amikor a leggyengébb fokozatra állítjuk a gépi ellenfelet, ekkor ugyanis a pálya ismerete már elınyt jelentene a számára). A tanulás tárgykörébe sorolható az is, hogy az egyes játékokban a magas szintő intelligencia megjegyzi, hogy mikor és hol találkozott elıször az ellenféllel, az azt követı játékban pedig azt a területet fokozottan figyeli majd, így ha két játékban (amelyet szükségszerően ugyanazon a pályán játszunk) ugyan onnan szeretnénk támadni, a második esetben már nem lesz olyan egyszerő a feladatunk. 4.22 Grafika és irányítás Jelentısen egyszerősíthetjük a késıbbi fejlesztést, ha a játék megjelenítését és irányítását a lehetıségekhez mérten maximálisan elkülönítjük a program többi részétıl. Magát a megjelenítést és az irányítást nem szerencsés ilyen nagy mértékben függetlenné tenni

egymástól, hiszen például már két különbözı kétdimenziós felhasználói felület esetén is lehetnek az irányításban jelentıs eltérések. Sıt, elınyös, ha ezen két komponens között egy erısebb kapcsolatot létesítünk. A grafikai és irányítási modul a program többi részétıl való erıs elhatárolódását a megjelenítési technológiák gyors fejlıdése teszi szükségszerővé. Ezen felül ezzel a megoldással lehetıségünk nyílik pusztán egy mesterséges intelligencia motor kifejlesztésére, aminek ezek után már tetszıleges kinézetet kölcsönözhetünk, 21 megvalósítva így a komponens alapú fejlesztés kritériumait. A módszer alkalmazása tehát minden szempontból indokolt. 4.23 Szálkezelés A processzorok architektúrális fejlıdésében a párhuzamosság az utóbbi 20-25 évben jelentıs szerepet játszik. Az 1980-as évek elejére a pusztán szekvenciális utasításvégrehajtás lehetıségeinek határához ért és

elérkezett az idı a párhuzamosság bevezetéséhez. A párhuzamosság elsı dimenziója az idı, másképpen az idıbeli párhuzamosság. Ez a futószalag-elvő utasítás feldolgozást jelenti. Lényege, hogy az elemi utasítások végrehajtásánál különbözı fázisokat definiálunk, párhuzamosan hajthatók végre (4. árba) amely fázisok egymással A következı fı fázisok alkotják a futószalagot: utasításlehívás (F), utasítás dekódolása (D), utasítás végrehajtása (E) valamint az eredmény visszaírása az operatív tárba (W/B). I1 I2 I3 F D E W/B F D E W/B F D E W/B fc 4. ábra: futószalag elvő utasítás-feldolgozás menete A módszer alkalmazásával elméletileg négyszeres sebességnövekedés érhetı el. A gyakorlatban azonban a különbözı függıségek (adat-, vezérlés- és erıforrásfüggıségek) fellépése miatt ez nem érhetı el. Az 1980-as évek végére kimerültek a futószalag elvő utasítás

feldolgozásban rejlı lehetıségek. A párhuzamosság második dimenzióját a térbeli párhuzamosság jelenti, ezek a szuperskalár processzorok, melyek a futószalag processzorokkal ellentétben egy órajel ciklus alatt egynél több utasítást is képesek kibocsátani. Ezen utasítások pedig párhuzamosan végrehajthatóak (5. ábra) 22 I1 F I2 I3 D F E D F I1 W / E D W / E W / E1 I2 I3 F D F E D F W / E D W / E W / fc E2 5. ábra: szuperskalár utasítás végrehajtás A következı fejlesztési lehetıséget az utasításokon belüli párhuzamosság jelentette, amely 1998-ban hozott elıször gyorsulást a processzorok teljesítményében. A párhuzamosság harmadik dimenziójának lényege, hogy SIMD utasításokat alkalmazunk, amelyek lehetıséget nyújtanak több, ugyanolyan típusú mővelet egy órajelciklus alatti végrehajtására (6. ábra) fc 6. ábra: utasításon belüli párhuzamosság Napjaink jellemzı fejlıdési

irányát a többszálú, többmagos processzorok jellemzik. Az egy processzoron belüli párhuzamosság lehetıségeit kiaknázva, a teljes processzor többszörözésével jelentıs sebesség növekedést értek el a tervezımérnökök. Két módja alakult ki ennek az elmúlt években, az egyik az SMT19, amikor minimális (510%) hardvertöbblettel egy processzoron belül két szálon fut a végrehajtás. Ezt a processzort az operációs rendszer két független processzornak tekinti. A módszer alkalmazásával a futtatott program támogatásától függıen 20-30%-os teljesítmény növekedés érhetı el. A másik lehetséges utat az SMP20 jelenti Ebben az esetben a hardver ráfordítás jelentıs mértékben emelkedik, azonban az így elért teljesítmény az eredeti 50-60%-át is elérheti. A számítástechnika jelenleg ebbe az irányba fejlıdik Amint azt a fejlıdés vázlatos bemutatása is mutatja, elkerülhetetlen egy modern architektúrát kihasználó játékban a

szálkezelés, melynek természetesen számtalan elınye van. Egyik például az, hogy amikor egy egységnek egy útvonal-keresési 19 20 simultaneous multithreading, példa: intel, HyperThreading, intel P4 3.06GHz HT, 2002 IDF symmetric multiprocessing, példa: AMD Athlon X2 3800+, 2005 23 algoritmust kell végrehajtania, azt egy külön szálon teheti meg. Így elérhetı, hogy egyrészt - amennyiben többprocesszoros rendszerrıl van szó – sokkal gyorsabban lefut a kód, másrészt pedig a játékosnak nem kell megvárnia, míg ezek elkészülnek, hanem az adott utasítás kiadása után rögtön mással tud foglalkozni. Ez tehát a válaszidı csökkentését jelenti. 24 5. A LEHETSÉGES MEGOLDÁSOK 5.1 Mesterséges intelligencia Amint azt az elızı fejezetben láthattuk, a játékban megvalósítandó intelligencia két fı egységre bontható. A minden egységben megtalálható alacsony szintő intelligencia egyik építıköve az útvonalkeresés, melyre sok

lehetséges megoldás létezik. 5.11 Útvonalkeresı eljárások [12-14, 16] Az útkeresés, útvonaltervezés a mesterséges intelligencia egyik legrégebbi problémáját testesíti meg. A játékokban a legegyszerőbb útkeresés az üldözés A cél, amelyet meg szeretnénk valósítani az, hogy például az ellenfél, amelyet a számítógép irányít, legyen képes követni a mi karakterünket. Ehhez nem kell mást tennünk, mint minden egyes elemi lépés folyamán megvizsgálni a gép, valamint a saját karakterünk koordinátáit. Amennyiben a gép által vezérelt karakter X koordinátája kisebb, mint a mi karakterünké, akkor ezt a változót megnöveljük, ellenkezı esetben csökkentjük 1-el. Az algoritmust az Y koordinátákra kiegészítve azt tapasztalhatjuk, hogy a gép által irányított karakter folyamatosan egyre közelít felénk, egészen addig, míg pontosan ugyan azok nem lesznek a koordinátái, mint az általunk irányított karakteré. Ennek egy

javított változata az összeláthatóság (line-of-sight, LOS) alapján mőködik, melynek eredményeképpen egy természetesebb, egyenesebb útvonalat kapunk. 7. ábra: egyszerő üldözés és az összeláthatóságot alkalmazó, javított verzió Amint az a 7-ik ábrán is látható, a gép által irányított karakter a fenti algoritmust alkalmazva figyelmen kívül hagyja az akadályokat. Ezen igen egyszerően javíthatunk, 25 mindössze úgy kell módosítani az összeláthatósági algoritmust, hogy amikor a gép „rálát” a célpontra, akkor egyenes vonalon közelít felé, ha pedig nem lát rá, akkor egy véletlenszerően kiválasztott irányba mozog. Ez a megoldás ugyan nagyon egyszerő, azonban nem igazán hatékony, és a gép által vezérelt karakter mozgása sem lesz igazán természetes. Egy újabb kiegészítéssel azonban ez a probléma is megoldható A start pont legyen a gép által irányított egység koordinátája, a cél pedig a mi helyzetünk.

Ekkor az algoritmus pszeudo-kódja a következı: HA nincs akadály a start és cél közt, AKKOR növeld vagy csökkentsd az X-Y koordináták értékét úgy, hogy közelítsünk a célhoz EGYÉBKÉNT menj végig az akadály mentén egészen addig, amíg szabad rálátásod nem lesz a célra, ekkor kezd a ciklust elölrıl 8. ábra: az összeláthatósági eljárással kiegészített „akadály-kikerülı” módszer eredménye Minthogy az eddig taglalt algoritmusok a gyakorlatban csak nagyon egyszerő esetekben vezetnek jó, elfogadható megoldásra, szükség van egyéb, bonyolultabb módszerekre is. Ezek közé tartozik a hullámfront-terjesztés, amely algoritmust a robotikában is alkalmazzák. Ahhoz, hogy az eljárást alkalmazni tudjuk, fel kell osztanunk a pályát, ami ebben az esetben egy síkon elhelyezkedı téglalapot jelent. A legegyszerőbben úgy kezelhetjük a problémát, ha a síkot négyzetekre bontjuk, az így kapott négyzethálót pedig egy tömbben

tároljuk. A tömb elemei egész számok lesznek A célpontnak megfelelı indexő elem a nulla értéket kapja. Az összes szomszédos cellának 1 lesz az értéke. Innentıl kezdve azon cellák, amelyeknek még nincs értékük (kezdetben például -1–et adtunk nekik), a velük szomszédos cellák értékénél egyel nagyobb számot kapnak. Az akadályokat olyan számokkal jelöljük meg, amelyek a 26 folyamat során biztosan nem fordulnak majd elı a vizsgálni kívánt cellákban. Például, ha egy 10x10-es tömbben vizsgálódunk, akkor biztosak lehetünk benne, hogy ha az akadályoknak a 254-es értéket adjuk, a célnak a 0-át, a start pontnak pedig a 255-öt, nem fogunk problémákba ütközni a megoldás közben. Az algoritmus futásának végezetével egy olyan tömböt kapunk eredményül, melyben a cellák értéke (leszámítva az akadályokat) a start ponttól a cél koordinátái felé egyre csökkennek. Ezt kihasználva nem kell mást tennünk, mint egyszerően a

kezdıponttól indulva megkeresni a célpont irányába esı olyan cellát, amely a legkisebb értékkel rendelkezik. Elınyösebb azonban, ha az eljárást fordítottan hajtjuk végre, és a célponttól kiindulva keressük meg az egyre kisebb cellák értékét, mivel ilyenformán egy esztétikusabb, nem annyira szögletes utat kapunk. Ez a kritérium egy, a Marsot kutató robot szempontjából nem releváns, mivel a megtett út hossza minden esetben megegyezik, tehát azonos mennyiségő erıforrást igényel, azonban egy játékprogramban a felhasználóban egy esztétikusabb mozgási pályával a mesterséges intelligencia jelenlétének érzését fokozhatjuk. 9 8 8 8 8 8 9 8 7 7 7 7 254 7 7 7 9 8 7 6 6 6 254 6 6 6 9 8 7 6 5 5 5 5 5 5 9 8 7 6 5 4 4 4 4 4 9 8 7 254 5 4 3 3 3 3 9 8 7 254 5 4 3 2 2 2 9 8 7 254 5 4 3 2 1 1 9 8 7 254 5 4 255 8 7 254 5 4 3 3 2 1 0 2 1 1 8 8 8 8 9. ábra: az alap hullámkiterjesztés módszere Mivel azonban ez

a megoldás kis valószínőséggel határozza meg a legoptimálisabb útvonalat, kisebb javításokat kell alkalmaznunk az algoritmuson. A legszembetőnıbb hiba az, hogy nem távolságok alapján adunk értékeket az egyes celláknak, így vízszintes és függıleges mozgás esetén még jó eredményeket kapunk, de az ettıl különbözı, átlóban megtett lépésekkor már nem a valódi távolságokat látjuk. Ennek oka igen egyszerő, ugyanis míg a négyzet oldalai egységnyi hosszúságúak, addig 27 átlójuk az egység 2 -szeresével egyezik meg. Az eljárás mőködésének javítása tehát azzal érhetı el, ha a tömb elemeit a távolságot figyelembe véve töltjük fel, természetesen ebben az esetben már lebegıpontos számokat használva a pontosabb eredmény érdekében. Egy újabb módosítással elérhetjük, hogy az útvonalkeresı algoritmus a biztonságot tartsa szem elıtt, azaz az akadályoktól a lehetı legmesszebb helyezze el a lépéseket. Ennek

elérése érdekében a hullámfront kiterjesztését nem célponttól kezdjük el, hanem az akadályoktól, illetıleg a vizsgálni kívánt terület szélétıl. Ezt mindaddig folytatjuk, amíg egy cellába két különbözı értéket kellene elhelyeznünk, ami azt jelenti, hogy két különbözı kiindulópontból érkezı hullám ütközött. A továbbiakban az adott cellát megjelöljük, és nem folytatjuk onnan a hullámfront-kiterjesztési eljárást. Az ily módon végrehajtott algoritmus eredményéül egy olyan tömböt kapunk, melyben a megjelölt cellák az akadályoktól azonos távolságra helyezkednek el. A következı lépésben a megjelölt cellákon alkalmazunk egy alap hullámfront-kiterjesztési algoritmust, melynek eredményes lefutása esetén az útvonalat követı egységek messzirıl el fogják kerülni az akadályokat. 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 1 254 1 2,2 1 1 2 3 3 3 1 254 1 2,2 1 1 2,2 2 2 2,2 1 1 1 2,2 1 1 2,2 1

1 1 2,2 2 2 2,2 1 1 2,2 1 254 1 2 3,3 3 2 1 1 2,2 1 254 1 2 3,3 3 2 1 1 2,2 1 254 1 2 3 3,3 2 1 1 1 1 254 1 2 2 2 2 0 255 1 1 254 1 1 1 1 1 1 10. ábra: a legbiztonságosabb utat keresı hullám-kiterjesztéses algoritmus Az eddig bemutatott algoritmusok alkalmazásával már meglehetısen jól meghatározható egy útvonal a pálya két pontja között. A játékokban azonban nagy valószínőséggel találkozhatunk olyan útvonal-tervezési problémákkal, melyekre ezek a 28 módszerek jó eredményt adnak, ennek eléréséhez viszont sok erıforrásra van szükségük. A másik lehetıség, hogy a feladatot az algoritmus a meghatározott elvek szerint ugyan elvégzi, de az eredmény messze nem az lesz, mint amit vártunk volna. A felsorolt problémák kiküszöbölése érdekében egy olyan algoritmust érdemes implementálni a játékokban, amely a kívánt eredményt képes elérni. Egy ilyen algoritmus a széles körben

alkalmazott A*. Az algoritmus elterjedtségét annak köszönheti, hogy a legoptimálisabb utat adja eredményül, teljesen függetlenül attól, hogy milyen jellegő akadályok vannak a pályán, illetıleg hol vannak a kiindulóés a célpont koordinátái. Mindemellett hatékony is A heurisztikus becslést felhasználó módszert elıször Peter Hart, Nils Nilson és Bertram Raphael dolgozta ki 1968-ban. Az algoritmus azért kapta az A* nevet, mert ez egy korábbi, „A” nevő algoritmus optimalizált változata. Az algoritmus mőködése során addig keresi a startpontból induló utakat, amíg nem találja meg azt, amelyik a célhoz vezet. Azonban mint minden informált keresı algoritmus, ezek az utak csak látszólag vezetnek a célhoz. Annak érdekében, hogy ezekbıl az A* eljárás ki tudja választani a megfelelıt, az útvonal minden pontja és a cél közti távolságra vonatkozó heurisztikus becslést végez. Ez a becslés két pont közti egyenes szakasz hosszára

vonatkozik, azonban ezzel a közelítéssel is megfelelı eredmény érhetı el. function A*(start,goal) var closed := the empty set var q := make queue(path(start)) while q is not empty var p := remove first(q) var x := the last node of p if x in closed continue if x = goal return p add x to closed foreach y in successors(p) if y not in closed enqueue(q, extend path(p,y)) return failure 11. ábra: az eredeti, gráfokra vonatkozó A* algoritmus (forrás: wikipedia.org) Az eredetileg egy gráfon belüli útvonalkeresésre szánt módszer kis átalakítással egy tömbben reprezentált, akadályokkal teli pályára is alkalmazható. Az átalakítás csupán azt jelenti, hogy a gráfot ennek a tömbnek feleltetjük meg. A síkban elhelyezkedı, téglalap alakú pályát elsı lépésben a korábbiakhoz hasonló módon 29 négyzetekre kvantáljuk. Minden egyes négyzetet egy kétdimenziós tömb megfelelı pozíciójában lévı számnak feleltetünk meg. Ez a legegyszerőbb esetben

egyesek és nullák halmaza is lehet, ahol az egyes jelenti az akadályt. Az átalakított A* pszeudokódja a következı: a kezdıpont hozzáadása a nyílt listához AMÍG a nyílt lista nem üres { aktuális csúcs = a nyílt lista legalacsonyabb költséggel rendelkezı csúcsa HA aktuális csúcs = cél csúcs AKKOR az útvonal elkészült EGYÉBKÉNT { az aktuális csúcs hozzáadása a lezárt listához az aktuális csúcs minden szomszédjának megvizsgálása FOR minden aktuális csúccsal szomszédos csúcs{ HA nincs a nyílt listában ÉS HA nincs a zárt listában ÉS HA nem akadály AKKOR az aktuális szomszéd hozzáadása a nyílt listához, és a költség kiszámítása } } } Az algoritmusban szereplı nyílt lista tartalmazza azokat a csúcsokat, amelyeket a feldolgozás folyamán meg kell vizsgálnunk. Az algoritmus indulásakor egyetlen elem van a nyílt listában, ez a kiindulási csúcspont. Jelen értelmezésben a csúcs a négyzetekre osztott

pálya egy egységét jelenti. A vizsgálat során azt kell elemeznünk, hogy az aktuális csúcsból mely szomszédos csúcsba léphet tovább a karakterünk. Ha az aktuális csúcs éppen vizsgált szomszédja megfelel a kritériumoknak, akkor amennyiben nincs még a nyílt listában, illetıleg a zárt listában sem szerepel, hozzáadjuk a nyílt listához. Így egy késıbbi lépésben majd ezt a csúcsot fogjuk közelebbrıl megvizsgálni 30 Az imént említett, és az algoritmusban is látható zárt listában azok a csúcsok találhatóak, melyeket már teljesen megvizsgáltunk. Egy csúcsot alapvetıen akkor tekintünk teljesen megvizsgáltnak, ha az összes szomszédját megvizsgáltuk. Ahhoz, hogy a módszerrel eredményt érjünk el, szükségünk van arra az információra, hogy melyik csúcsból melyik csúcsba léptünk, más szóval ismernünk kell az adott csúcs ısét. Mint ismeretes, az algoritmus a heurisztikus távolság-becslést alkalmazza. Erre akkor kerül

sor, amikor az aktuális csúcs egyik szomszédját vizsgáljuk. Az adott csúcs költségét kiszámító összefüggés a következı: f(x) = g(x) + h(x) A képletben szereplı f(x) az éppen vizsgált csúcs költségét jelöli. A g(x) az a költség, amely a startponttól a jelenlegi csúcsig tartó út folyamán keletkezett, a h(x) pedig a heurisztikus becslés, amellyel azt sejtjük meg, hogy a pillanatnyi pozíciónkból milyen messze helyezkedik el a célpont. 12. ábra: példa az A* algoritmus mőködésére (1) A 12. ábrán látható példában éppen az (6,5) pozícióban lévı csúcsot vizsgáljuk Amint látható, az adott csúcs ıse az (5,6) koordinátáknál található csúcsra mutat. Mivel 31 négyzetekbıl épül fel a térkép21, ezért egy csúcs 8 szomszédos csúccsal rendelkezik, így mind a 8-at meg kell vizsgálnunk. Azért esett a választás a (6,5)-ön lévı csúcsra, mivel a kiindulópontból nézve (helyesebben az ısétıl tekintve, csak

éppen jelen esetben az aktuális csúcs ıse és a kezdıpont megegyezik) ez esik a cél irányába (ezt különösebb problémák nélkül ismerhetjük, hiszen tudjuk a cél és a start koordinátáit, ebbıl kiszámítható az irány). A vizsgálandó csúcsok tehát ezen csúcs szomszédjai Az (5,4), (6,4) és (7,4)-es csúcsokkal nem kell foglalkoznunk, hiszen ezeken a koordinátákon akadály helyezkedik el. Az (5,5) és (6,6)-os pozíciókat már korábban felvettük a nyílt listára, ezért most ezeket is figyelmen kívül hagyjuk. Az (5,6)-os csúcs a zárt listában van, mivel onnan indultunk el, tehát annak a csúcsnak a feldolgozásával már végeztünk. Mindössze két új csúcsot találtunk ebben a ciklusban, ezek a (7,5) és a (7,6) koordinátáknál találhatóak. Mindkét csúcs ısének az aktuális csúcsot állítjuk be, ezt jól mutatják az ábrán látható nyilak. Lássuk közelebbrıl a (7,5)-ös pozíción lévı csúcs adatait! A fenti képletben

szereplı g(x) értéke 2, mivel két lépésre van szükségünk ahhoz, hogy a startponttól idáig eljussunk (az átlós lépést az egyszerőség kedvéért engedélyezzük). A h(x) értéke 3, hiszen cély – aktuálisy = 5 – 2 = 3 Az x koordinátával nem kell foglalkoznunk, mivel ugyanabba az oszlopba esik mindkét csúcs. Ezen értékek ismeretében tehát megkapjuk a csúcs költségét, ami így 5 lesz A (7,6)-os pozíción található csúcs költségeként az elıbbi eljárást végrehajtva 6-ot adhatunk meg. A 14 ábrán egy teljes futás részletes eredménye látható A nyílt listában szereplı csúcsok zölddel, a zárt listában szereplık pedig kékkel vannak jelölve. Az akadályt értelemszerően a kékkel kitöltött egységek jelképezik. A startpont a zölddel, a cél pedig a pirossal kitöltött négyzettel jelölt koordinátáknál található. Az egyes csúcsok leírására pedig szolgáljon eme kis ábra: 21 A térkép felosztása nem minden esetben

négyzeten alapszik, használhatunk hexagonális, háromszög alakzatokat is, ezen felül tulajdonképpen szinte bármilyen szabálytalan formát is alkalmazhatunk, ebben az esetben azonban nagyon bonyolulttá válhat az algoritmus felépítése 32 költség, f(x) az aktuális csúcs ısére mutat a starttól megtett út, g(x) a heurisztikus becslés, milyen messze van a cél h(x) 13. ábra: jelmagyarázat a 14 ábrához 14. ábra: az A* algoritmus mőködése (2) A bemutatott A* algoritmus mellett említést kell tenni egy másik módszerrıl is, amely mőködési mechanizmusait a biológia témakörébıl meríti. A keresési algoritmust 33 találóan „ant search”-nek, hangya alapú keresésnek hívják, tekintettel arra, hogy futása során a hangyák viselkedését alapul véve jut eredményre. Az algoritmus gyökereit keresve igen messzire tekinthetünk vissza az idıben. A Dél-amerikai Eugène Marais (1872-1936) volt az elsı, aki mélyebben foglalkozott a

hangyák, pontosabban a termeszhangyák22 életével. A témában írt könyvét („The Soul of the White Ant”) halála után, 1937-ben adták ki. Ebben részletesen ecseteli a dolgozó hangyák és az emberi test között fellelhetı párhuzamokat. Az „ant search” tehát a hangyák természetes mozgását hivatott szimulálni. A hangyák a kezdetben véletlenszerő bolyongást a feromon nevő hormon segítségével idıvel átformálják egy rendezett mozgássá, amely mozgás az adott terület sajátosságainak megfelelı legoptimálisabb útvonalain zajlik. A hangyák haladásuk során feromont bocsátanak ki, ilyenformán megjelölve azt, hogy merre jártak. Ezen nyomot követve vissza tudnak találni a bolyhoz is. A cél természetesen az élelem felfedezése. Ha egy hangya élelemre bukkant, akkor onnan visszatér a bolyba, ezzel erısítve a feromon által megjelölt útvonalat. Mivel amennyiben egy hangya feromon nyomra bukkanva azt nagy valószínőséggel követni

fogja, ezért egyre több hangya juthat el az élelemig. Mivel ugyanazon az útvonalon egyre több hangya jár, és mindegyik feromon nyomot hagy maga után, bizonyos idı elteltével ez az út lesz a hangyák által leginkább preferált útvonal, ezáltal a kezdeti rendezetlen mozgást felváltja egy rendezett. A természetben megfigyelhetı magatartás számítógépes felhasználása érdekében bizonyos megkötéseket kell meghatároznunk. Egyrészt, nagy számú hangyára van szükség annak érdekében, hogy a keresés viszonylag gyorsan eredményre vezessen. Azonban a nagy számosság miatt az egyes hangyák felépítése, a szabályok, ami alapján tevékenykednek egyszerőnek kell lenniük, ellenkezı esetben az algoritmus futása során az erıforrások szők keresztmetszetet jelenthetnek. Ezen feltételeknek megfelelıen a következı szabályoknak kell eleget tenniük az egyes hangyáknak az algoritmus23 futása során: − minden hangya egyszerre egy egységnyit tud

lépni a 4 szomszédos mezıre − minden hangya minden lépésben feromonnyomot hagy maga után 22 23 A kutató idejében fehér hangyáknak nevezték a termeszhangyákat. Jelen algoritmus egy négyzetrácsos, síkbeli térképet használ (forrás: [12.]) 34 − a hangyák a továbbhaladási irányukat a környezetükben érzékel nyomvonalak (feromonnyomok) erısségének függvényében, a véletlen bevonásával választják − a hangyák elınyben részesítik az egyenes vonalú mozgást − a hangyák a visszafelé mutató irányt kisebb valószínőséggel választják − a hangyák nem mehetnek át az akadályokon Az eddig bemutatott algoritmusok nem használták a gráfok által nyújtott lehetıségeket. A gráf alapú útvonalkereséseknél azzal a problémával kerülünk szembe, hogy a gráfnak léteznie kell, hiszen máskülönben értelmetlen lenne benne keresni. A nehézséget ez alapján tehát a gráfok felépítése jelenti. Sok valós idejő stratégiai

játék alkalmazza a gráfban keresı eljárásokat azok sebességük miatt. Az egyszerőbb megoldásokat alkalmazó játékokban a keresésre szolgáló gráfokat fixen a programba kellett ültetni a gyors és jó mőködés érdekében. Ennek több lehetséges módja van, a legalapvetıbb, de e miatt igen idıigényes megoldás a gráf manuális felépítése. Adott esetben természetesen elınyös lehet, hiszen a pálya alkotójaként sokkal jobb, több információval rendelkezünk a gráfokat automatikusan felépítı algoritmusokkal szemben. Ilyen algoritmus például a térfelosztó eljárások közül a látható csomópontok módszere. Ennél a módszernél eredményül egy olyan gráfot kapunk, melynek csúcsai az akadályok sarkaitól meghatározott távolságra helyezkednek el. Két csúcsot akkor kötünk össze, ha azok „látják egymást”, tehát nincs közöttük akadály. A módszert a 15 ábra szemlélteti 15. ábra: a látható csomópontok módszere (point of

visibility, PoV) A valamilyen módon elkészített gráfban történı útvonalkeresésre számtalan algoritmust alkalmazhatunk. A módszerek alapját általánosságban két lépéssel lehet leírni. Az elsıben meghatározzuk a gráf egy minimális feszítıfáját, amelyet 35 felhasználva a második lépésben megvizsgáljuk, hogy a startcsúcs és a célcsúcs közt létezik-e út. Az elsı lépés elvégzéséhez használhatjuk például a szélességi bejárást. Az algoritmus célja, hogy minden csúcs egyszeri érintésével járja be a teljes gráfot, figyelve a kezdıponttól való távolságra. Ha a gráf nem összefüggı, akkor egy pontjából kiindulva nem érhetı el az összes csúcsa. Ilyenkor a módszer csak a gráf azon részében végzi a mőveleteket, amelyben a kiinduló pont van, ha pedig a cél nem esik bele ebbe a szegmensbe, akkor az algoritmus azzal tér vissza, hogy nem létezik út a kiinduló és a cél csúcs között. CIKLUS minden SZÍN(U) =

D(U) = π(U) = U∈V[G]-ra fehér végtelen NIL D(S) = 0 // inicializáljuk a gráfot // a startpont önmagától való // távolsága nulla BELETESZ(Q,S) CIKLUS amíg Q nem üres U = ELSİELEM(Q) CIKLUS minden V∈SZOMSZÉD[U]-ra HA SZÍN(V) = fehér AKKOR SZÍN(V) = szürke D(V) = D(U) + 1 π(V) = U BELETESZ(Q,V) ELÁGAZÁS VÉGE CIKLUS VÉGE KIVESZ(Q) SZÍN(Q) = fekete CIKLUS VÉGE Az algoritmusban szereplı Q egy FIFO adatszerkezet megvalósító változó. Az egyes csúcsok színeinek jelentése a következı lehet: − fehér: olyan csúcs, melyet még nem érintettünk − fekete: minden szomszédját és ıt magát is feldolgoztuk Második lépésként az algoritmus futásának eredményét alkotó fában megkeressük a kiinduló csúcspontot. Mivel a fában található elemek a fa gyökere felé mutatnak, ezért elég követnünk a mutatókat, annak érdekében, hogy eljussunk a gyökérelemig, ami a 36 célcsúcsot jelenti. A gráfok felhasználásával jelentıs

teljesítménynövekedés érhetı el az útvonalkeresésben. 5.12 Az alacsony szintő MI további építıelemei Az alacsony szintő intelligencia a nélkülözhetetlen útvonalkeresı algoritmusokon felül még számtalan lehetséges modullal kiegészíthetı. Egyszerősíthetıek a magasabb absztrakciós szinten található módszerek, ha az olyan funkciókat, mint például az egységek ütközésének felügyeletét, vagy azok rangjának nyilvántartását már itt kezeljük. A kiegészítések célja tulajdonképpen egy olyan egység létrehozása, melynek képességei jól skálázhatóak. Ekkor ugyanis lehetıségünk nyílik különbözı tudású egységeket létrehozni és kezelni annak ismerete nélkül, hogy valójában az adott egység hogyan is „mőködik”. Ez a fajta megoldás a játék komponens alapú fejlesztését is elısegíti, hiszen teljes mértékben az objektum orientált programozás eszközeit használja fel. 5.13 Magas szintő MI - a stratégiai

döntéshozó réteg [14, 17] Csakúgy, mint a valós életben, a valós idejő stratégiai játékokban is megtalálhatóak azok a mechanizmusok, melyek felhasználásával a számítógép által irányított ellenség mindent megtesz a gyızelem érdekében. Ezek a mechanizmusok, algoritmusok gyakran használják fel a mesterséges intelligencia által nyújtott lehetıségeket. Napjainkban a legújabb valósidejő stratégiai játékok rendkívül komplex megoldásokat tartalmazhatnak. Az egyik legegyszerőbb megoldás a determinisztikus véges állapotú automaták alkalmazása. Ezen automaták véges sok állapottal rendelkeznek, melyekbıl bizonyos feltételek teljesülése esetén az automata egy másik állapotba lép át. A módszert már a számítógépes játékok történelmének kezdetétıl fogva alkalmazzák, mivel egyszerően meg lehet valósítani, valamint a hibakeresés sem bonyolult. Példaként említhetjük a Pac Man nevő játékot, melynek szellemei is egy

ilyen állapotgép alapján cselekedtek. Az egyik állapotban bolyongtak a labirintusban, egy másik állapotban követték a játékost, egy harmadikban pedig menekültek. Állapotátmenetre a következı példát hozhatjuk fel: a szellem épp üldözi a játékost. Ekkor a játékos felszed egy, az erejét megnövelı tablettát. Ez az esemény kielégíti azt a feltételt, melynek hatására a szellem üldözésibıl a menekülési állapotba vált át. Ezzel a metódussal olyan játékok készíthetıek, melyek 37 még ma is megállhatják a helyüket, bár használatakor még nem beszélhetünk mesterséges intelligenciáról. Egy komplexebb, általánosabb lehetıséget nyújtanak az intelligencia szimulálására a szabály alapú algoritmusok, melyeket egyszerő IF-THEN-ELSE szerkezetekbıl építhetünk fel. Ennek ellenére meglehetısen bonyolult összefüggések modellezésére is alkalmas, de természetesen vannak bizonyos határvonalak, melyek átlépésére

más módszereket kell keresnünk. A korábban említett véges állapotú automatát is egy ilyen rendszerrel írhatjuk le. A hatékony fejlesztéshez különféle módszerek állnak rendelkezésünkre. Az egyik ilyen a következtetés használata, melyet elıre- és hátrafele láncolással valósíthatunk meg. Elıre láncoláskor a hierarchiában alul elhelyezkedı elemek megléte esetén valószínősíthetjük az azokra épülı elemek meglétét, ebben azonban nem lehetünk teljes mértékben biztosak. Hierarchia alatt egy olyan fát, illetve gráfot kell érteni, mely meghatározza, hogy az adott játéknak megfelelı technológia hogyan épül fel. Így például a tanknak az ıse a tankgyár, mivel amíg nem építettünk tankot gyártó épületet, nincs lehetıségünk tankok használatára (kivéve a már meglévı egységeinket). A hátrafele történı láncoláskor a hierarchia magasabb pozícióiban lévı elemekbıl következtetünk arra, hogy az az alatt lévı

elemeknek már létezniük kell. A tank példájánál maradva tehát, ha tudjuk, hogy az ellenségnek vannak tankjai, akkor rendelkeznie kell tankgyárral is (nem számítva most egyéb eseteket). Lehetıségünk van a szabályokat a fuzzy logika elemeivel összeolvasztani. Ekkor a tagsági függvények alkalmazásával rugalmasabbá tehetjük a gép intelligenciáját, legalábbis annak a szimulációját. Hasonló eredményeket érünk el, ha valószínőségeket is adunk bizonyos eseményekhez, lehetıségekhez. Ezen módszerek együttes alkalmazásával már igen komplex problémák is leírhatókká válnak. Ettıl eltekintve azonban a játékos egy, a programozó által elıre meghatározott, jól definiált szabályokon alapuló rendszer ellen küzd, amely rendszer egy bizonyos szituációra nagy valószínőséggel mindig ugyanazt a választ adja. Ezt felismerve relatív egyszerővé válik a gépi ellenfél legyızése. A legjobb eredmények elérése érdekében azonban

már összetettebb megoldásokkal kell dolgoznunk. Ilyenek lehetnek a genetikus algoritmusok, melyek például több különbözı taktika közül a játék folyamán döntik el, hogy melyik a leghatékonyabb az adott helyzetben. Egy másik lehetıség a neurális hálók alkalmazása, azonban ezeket be kell tanítani a helyes mőködés érdekében, ami egy olyan szerteágazó problémakörnél, mint a stratégia, meglehetısen idıigényes. Emellett egy neurális háló 38 tesztelése és hibakeresése jelentıs erıforrásokat emészthet fel. Így meggondolandó, hogy gazdasági szempontból nem kifizetıdıbb-e, ha egy egyszerőbb megoldást választunk. Kétségtelen viszont, hogy a neurális hálók tanulási képességüket tekintve rendkívüli elınnyel bírnak a más, egyszerőbb megoldásokkal szemben. A tanulás az egyszerőbb módszereknél is megoldható, de csak sokkal nagyobb ráfordítás ellenében, mint egy ilyen rendszerben. Amint az tehát látható, a

játékok magas szintő intelligenciájának kérdése meglehetısen nagy területet jelent, melyben felhasznált algoritmusok, metodikák napjainkra túlnyomó többségben az általános mesterséges intelligencia eszköztárából származnak. 5.2 Grafika A számítógépes játékok grafikája a kezdetektıl fogva fejlıdött. Napjainkra a játékfejlesztés és a grafikus gyorsító kártyák tervezése között fennálló kapcsolat jelentısen megerısödött. Egyre komplexebb, a matematikából és a fizikából származó összefüggések alapján a fejlesztıknek lehetıségessé vált a valósághoz rendkívül közeli képszintézis megvalósítása. Ez természetesen annak is köszönhetı, hogy a hardvertámogatottság az elmúlt 10 évben hihetetlen fejlıdésen esett át Azelıtt például a HDRR24 technológia elképzelhetetlen volt, hiszen a processzor és a grafikus kártya egyszerően nem rendelkezett a mainak megfelelı teljesítménnyel. 16. ábra: HDRR

alkalmazásával készült pillanatkép a Half Life 2 – Lost Coast nevő játékból (forrás: wikipedia.org) 24 HDRR – High Dynamic Range Rendering, egy újfajta megvilágítási modell, melynek segítségével rendkívül realisztikus képszintézis érhetı el, amint a 16. ábra is mutatja 39 Minthogy a játékok túlnyomó többségét Microsoft Windows platformra fejlesztették, ezért nem térnék ki a más operációs rendszerek által nyújtotta lehetıségekre (mint például a Linux X Window System). Windows-ban a képszintézis legegyszerőbb formáját a Form-ok használatával érhetjük el. A megoldás ugyan egyszerő, de emiatt valójában inkább csak tesztelésre használható. Egyszerő alakzatok egyszeri kirajzolásánál még megfelelı végeredmény érhetı el, azonban a játékok megjelenítési algoritmusai ennél általában többet igényelnek. A sebesség hiányának egyik oka az, hogy a programozó a videómemóriát csak közvetett módon éri el.

Ha például egy, a merevlemezrıl betöltött képet szeretnénk megjeleníteni a képernyın, akkor elsı lépésként be kell töltenünk az adott képet. Ezt a Windows hajtja végre, és általában nincs rá lehetıségünk, hogy meghatározzuk azt a memóriaterületet, ahova a kép adatait be szeretnénk tölteni. Így az operációs rendszer nagy valószínőséggel nem a videómemóriába fogja betölteni a képünket, hanem a rendszer operatív tárába, ami értelem szerően jóval lassabb elérést biztosít, mint a videokártyán található memóriachipek. A Microsoft DirectX felhasználásával a korábban bemutatott problémák felszámolásán túl jelentısen javíthatunk az elıállított kép minıségén is. A DirectX nem más, mint egy alkalmazást programozó felületekbıl (API25) álló komponens csoport, melynek segítségével lehetıségünk nyílik a hardverközeli programozásra. Ezen felületek használatával a pontos specifikációk ismerete nélkül

programozhatjuk a hardvereket. Módunkban áll a 2D-s megjelenítés felgyorsítására a DirectDraw alkalmazásával, elérhetjük az összes, hardver által gyorsított 3D-s függvényt a Direct3D segítségével. A hang kezelésében a DirectSound API-ját használhatjuk, amellyel akár 3D hatású hangzások is elıállíthatóak. A Musical Instrument Digital Interface (MIDI) formátum támogatásához a DirectMusic komponens áll rendelkezésünkre. Legújabb verziója a DirectX 9.0c, azonban a Microsoft Windows Vista megjelenésével újabb változat várható (D3D10, Windows Graphic Foundation 1.0) Egy másik lehetséges megoldást az OpenGL használata jelentheti. Az OpenGL egy nyílt szabványú alkalmazás programozó felület (open standard API, Open Graphic Library). A Microsoft Direct3D-hez képest annyi elınnyel rendelkezik, hogy platformfüggetlen, a legtöbb modern operációs rendszer támogatja a használatát. Az OpenGL egy specifikáció, ami több mint 250

függvényt definiál. A definíciónak 25 API – application programming interface 40 megfelelı implementáció a videokártya gyártók feladata. Míg a DirectX kétdimenziós, addig az OpenGL-t sokkal inkább a háromdimenziós képszintézisnél alkalmazzák. Legújabb verziója az OpenGL 2.0, melyben már a fentebb említett HDRR technológiát megvalósítani képes árnyaló nyelvvel (OpenGL Shading Language) is találkozhatunk. 5.3 A komponenskezelési megoldások Egy modern szoftver, legyen szó akár játékról akár szövegszerkesztırıl, komponensekbıl épül fel. Ezeket a komponenseket különféle szemszögbıl másmásféleképpen értelmezhetjük Az objektum orientált programozás megjelenése az addig monolitikus, majd strukturális program változóinak és függvényeinek kezelését egyszerősítette. Ez az egyszerősítés fıként a programozó számára látható, hiszen a sok osztályból felépülı szoftver a végfelhasználóhoz továbbra is egy

egységként érkezhet meg. Ekkor ugyan a program javítása, kiegészítése már nem olyan komplex feladat, azonban az adott szoftver frissítése esetén az egész programegységet felül kell írni. Erre nyújt megoldást a DLL-ek alkalmazása. Dinamikus csatolású könyvtárak (Dynamic Linked Library) használata esetén a hibás programrészlet javítását követıen elegendı a hibás DLL fájl végfelhasználónak történı küldése, illetve felülírása. Egy ilyen könyvtárba tetszıleges kombinációban ötvözhetjük a kódot, az adatokat valamint az egyéb erıforrásokat, például képet, hangot, stb. A dinamikusan csatolható könyvtárak megjelenésének alapvetı okai közé sorolhatjuk mind a memóriában, mind pedig a háttértárolón rendelkezésre álló terület maximális kihasználásának szükségességét. Mivel egy DLLben tárolt erıforrások több program által is használhatók, ezért ezeket a funkciókat nem kell minden egyes programhoz

mellékelni. Jó példa erre a DirectX, vagy az OpenGL, melyek tulajdonképpen ilyen megosztott könyvtárak győjteményébıl állnak. Lehetıségünk van a komponensek szétválasztásakor távoli eljárások használatára is, ez a módszer azonban fıként csak az elosztott rendszereknél terjedt el. A távoli eljárások hívásakor rendkívül sok tényezı van befolyással programunk sebességére, ami természetesen egy játék esetében jelentısen lekorlátozza az így megvalósítható komponens-kezelési lehetıségek körét. Napjainkra a játékok egyre nagyobb hányada képes a program futása során az internet használatára. Egyrészt több játékosnak 41 lehetısége nyílik közösen játszani az interneten keresztül, komponens szempontból azonban ez nem releváns. Másrészt viszont a játékosoknak lehetıségük van számtalan információ elérésére a játékon belül. Ilyen adatokat jelenthetnek például egy szimulációs-játék egyik

versenypályán elért rekordok. A harmadik alkalmazási területet a reklámok jelentik. Míg korábban a játékokban megtalálható reklámok statikus tartalommal bírtak, céljuk nem a hirdetés, hanem a dekoráció volt. Napjainkra azonban a játékokon belüli reklámok szerepe jelentıs változásokon esik át. A fejlesztések az internetrıl letöltött, dinamikus tartalommal rendelkezı hirdetések, reklámok felé mutatnak. Ekkor tehát például egy futballmérkızés közben a pálya szélén látható reklámokat a játékszoftver egy távoli eljárás segítségével folyamatosan frissíti, így a játék grafikai megjelenése akár a fejlesztés lezártával is változhat. 5.4 A párhuzamosság kihasználása Az intel processzoraiban 2002-ben megjelent Hyper Threading Technology (HTT) az általános párhuzamos feldolgozás széleskörő elterjedésének elsı lépcsıfokát jelentette. Az SMT26 implementációval elérhetı többlet teljesítmény akár a 30%-ot is

elérte, miközben a processzort minimális mértékben, mindössze 5 százalékkal nagyobb ráfordítás árán valósították meg. A teljesítmény növekedéséhez azonban természetesen szükségszerő a szoftverek megfelelı kialakítása is. Ha ez nem történik meg, akkor bizonyos esetekben elıfordulhat, hogy egy SMT-re képes processzoron az alkalmazás lassabban fog futni. A processzorok fejlıdési iránya egyértelmően a párhuzamosság felé mutat, hiszen jelenleg a többmagos processzorok korát éljük. Egy szoftvert többféle módon alakíthatunk ki a párhuzamosság kihasználása érdekében. Az egyik lehetséges megoldás értelmében a programot több, külön-külön futtatható kisebb részekre bontjuk. Ekkor egyszerre több folyamatot hozhatunk létre, amely folyamatok további szálakat tartalmazhatnak. A módszer hátrányát a részegységek közti nehézkes kommunikáció jelenti, ezért ezt akkor célszerő alkalmazni, mikor az összetevık jól

elkülöníthetıek egymástól, lehetıség szerint nincs kommunikáció közöttük. A másik módszer egy folyamaton alapszik, azonban több 26 SMT – Simultaneous Multi-Threading 42 szálat alkalmaz. Elınye, hogy jelentıs mértékben egyszerősödik a párhuzamosan futó részegységek közti kommunikáció megvalósítása. Más szemszögbıl közelítve a problémát, újabb két lehetséges módszerrıl tehetünk említést. Az elsı esetben a program elindítja az adatok feldolgozását végzı szálat, és rögtön folytatja a végrehajtást. A szál indulását követıen végrehajtja a megfelelı utasításokat, majd leáll. A második esetet feltételezve a folyamat a szál indítása után azzal közösen mőködik tovább a szál által feldolgozott adatokat használva. A fı folyamat futásának befejezésekor a hozzá tartozó szálak mőködését is meg kell szüntetni. Lehetıségünk van erıszakkal leállítani az adott szálat, azonban ez a

megvalósítási forma bizonyos esetekben okozhat nem várt eredményeket, emellett pedig elképzelhetı, hogy a szál terminálását végzı utasítás végrehajtása, és a szál tényleges megállása között jelentıs idı telik el. Ezért érdemesebb a kilépési mechanizmust a szál mőködésébe integrálni. Ekkor a szálat megvalósító függvény vagy osztály számára elegendı egy terminálási szignált küldenünk. Ezt követıen a szál a program felépítésének megfelelıen rövid idın belül (optimális esetben azonnal), komplikációk nélkül befejezi a mőködését, és megszőnik. A párhuzamosság megjelenésével tehát mind a processzorok, mind a programok felépítése bonyolultabbá válik, azonban cserébe adott esetben jelentıs sebességnövekedést, válaszidıbeli csökkenést tapasztalhatunk az alkalmazások futása során. 43 6. A KIVÁLASZTOTT MEGOLDÁSOK Egy valós idejő stratégiai játék komponens alapú fejlesztése

folyamán több olyan részfeladattal is találkozunk, melyek megvalósítási módozatai igen szerteágazóak lehetnek. Természetesen elınyös minél több módszer ismerete annak érdekében, hogy a végeredmény megfelelıen hatékony, és élvezhetıvé váljon. Az eddig alkalmazott módon a játék fıbb részegységein végighaladva mutatom be az kiválasztott technikákat. 6.1 Mesterséges intelligencia 6.11 Alacsony szintő MI A réteg alapvetı funkcionalitásai közé tartozik az útvonalkeresés hatékony és gyors megvalósítása. A fejlesztés során a legoptimálisabb megoldás érdekében nem hagyatkozhatunk egyetlen módszerre. Az algoritmust úgy kell kialakítani, hogy a kiválasztott eljárások lehetıség szerint minél nagyobb mértékben egészítsék ki egymást. Ha egy bizonyos probléma az egyik megoldás hátrányokkal rendelkezik, azonban egy másikkal ezeket ki lehet küszöbölni, akkor e probléma feldolgozásakor a két algoritmus kombinációja

használata ajánlott. Az algoritmusok kombinációjának tökéletes példáját ismerhetjük fel az útvonalkeresı eljárások kiválasztásánál. A LOS27 algoritmus rendkívül egyszerő és gyors megoldás, azonban csak az akadály létezésének ténye állapítható meg a segítségével. Az A*28 algoritmus minden esetben megadja a legrövidebb útvonalat, azonban több hátrányos tulajdonsággal is rendelkezik. Ezek közé tartozik, hogy bonyolultabb pálya esetén az algoritmust megvalósító függvény futási ideje irreálisan nagy, amely egy olyan játéknál, amely „valós idejő” jelzıvel van illetve, nem elfogadható. Ugyancsak a módszer hátrányai között tarthatjuk számon, hogy a meghatározott útvonal ugyan valóban a legrövidebb, azonban esztétikailag nem a legkedvezıbb, hiszen a felhasználó számára túlságosan tördeltnek tőnhet. A gráfok29 27 LOS – Line of Sight – összeláthatósági algoritmus, 5.11 fejezet, 25 oldal A*

útvonalkeresı algoritmus, 5.11 fejezet, 29 oldal 29 gráf-algoritmusok, 5.11 fejezet, 35 oldal 28 44 alkalmazásával a valós idejő feldolgozást elérhetjük, azonban a gráfban keresı algoritmusok elıfeltétele egy összefüggı gráf megléte. Ezen gráf felépítése nem triviális, hiszen a gráf csúcsainak optimális elrendezése, azok közötti élek megfelelı elhelyezése alapvetıen meghatározza az algoritmus által eredményül adott útvonal hatékonyságát, tehát azt, hogy mennyire rövid, optimális, illetve, hogy a korábban említett esztétikai feltételeknek milyen mértékben felel meg. Tisztán látható, hogy ezen algoritmusok ésszerő kombinációjával a pálya felépítésétıl függetlenül hatékony útvonal határozható meg. A kiválasztott három algoritmus kombinálásával a következı algoritmust készítettem el: Tételezzünk fel egy általános állapotot a játékban. Egy ilyen állapot látható a 17. ábrán Az algoritmus feladata

tehát a képen látható egység és az erdı túloldalán megjelölt pozíció között egy hatékony útvonal keresése, amennyiben ez létezik. 17. ábra: a játék egy általános állapota Elsı lépésként megvizsgáljuk a LOS algoritmus segítségével, hogy az induló- és a célkoordináták között van-e akadály. Ha nincs, akkor a startot a céllal összekötı szakasz lesz a keresett út. Ha van, akkor második lépésként alkalmazzuk a bonyolultabb eljárásokat. Az ekkor végrehajtandó utasítássorozat elsı elemeként információt győjtünk arról, hogy a régióban fellelhetık-e gráf csúcsok. Egyrészt a kiindulópont bizonyos sugarú környezetét vizsgáljuk, másrészt a célpont koordinátáinak ugyanilyen sugarú környezetébe esı gráfpontokat keressük. 45 Amennyiben találtunk ilyeneket, akkor kiválasztjuk azt, amelyik a legközelebb esik a starthoz, valamint azt, amelyik a legközelebb esik a célhoz. A kiválasztáskor tekintettel kell

lennünk arra, hogy a legközelebbi olyan csúcspontot válasszuk ki, melyre szabad rálátásunk van. Így tehát két olyan gráfpontot kapunk, amelyek a lehetı legközelebb esnek a kiinduló- és a célponthoz. Megkeressük a két gráfpontot összekötı útvonalat, amennyiben ez létezik. Ekkor a gráf éleinek súlyozásával érhetjük el, hogy nagy valószínőséggel a legrövidebb utat kapjuk eredményül. Ha nem találtunk a feltételeknek megfelelı gráfpontokat, akkor kénytelenek vagyunk az A* algoritmust alkalmazni, és nem lehetünk tekintettel az algoritmus futási idejére. Az algoritmus futásának eredményéül kapott koordinátákat továbbítjuk az egység felé, amely ezután végig tud haladni az útvonalon. A megfelelı gráfpontok létezése esetén a kiindulóponttól az ahhoz legközelebb esı látható gráfpontig, majd onnan a gráf megfelelı csúcsait érintve a célponthoz legközelebb esı, látható gráfpontig, végül pedig a célpontig

haladhatunk. Megfelelı gráfpontok hiányában a pálya méretétıl függıen általában jelentısen több olyan koordinátát küldünk az egység felé, amelyen végig kell haladnia. Az A* algoritmus mőködéséhez két fogalmat kell definiálnunk. Elsı esetben az A* keresésben szereplı heurisztikus tag értékét szükséges meghatároznunk. Ez esetünkben a célpontot az aktuális csúccsal összekötı szakasz hosszát jelenti. A második definiálandó fogalom a pályának azt a legkisebb egységét jelenti, amelyre a keresést még érdemes kiterjeszteni. Míg egy egyszerőbb platform játék esetén a játékosnak jól meghatározott pozíciója van, addig egy stratégiai játékban szereplı egység helyzete nem feltétlen írható le egész számokkal. Elsı elgondolásra két lehetséges megoldás kínálkozik a probléma elhárítására, de egyik választás sem használható igazán. Az elsı esetben lebegıpontosan ábrázoljuk az egységek helyzetét, ekkor

azonban rendkívül nehézkessé válik az A* algoritmus implementálása, ezért ez a módszer csak közvetett módon alkalmazható. A másik esetben pedig egyszerően több nagyságrenddel megnöveljük a vizsgálandó terület méretét. Így elérhetjük azt a látszatot, hogy az egység nagyon kis lépésenként mozog, tehát a felhasználó számára a mozgása folyamatosnak tőnik. A megoldás nagy hátránya, hogy az amúgy is lassú A* algoritmusnak ebben az esetben még nagyobb területen kell vizsgálódnia, ami rendkívül lelassíthatja a program futását. A játékos számára ebbıl az látszik, hogy a játék, illetıleg az adott egység egyszerően nem reagál semmiféle ingerre. 46 A megoldást az jelenti tehát, ha a vizsgálandó területet felosztjuk bizonyos részterületekre. A felosztás legegyszerőbb, legkézenfekvıbb módja a pálya négyzetekre való bontását jelenti. A heurisztikus tag értéke ezen négyzetegységeken alapszik A módszer lényege,

hogy az mozgáshoz szükséges koordináták nem határozzák meg egyértelmően az egység valódi helyzetét, csupán azt az n x n-es négyzetet, amelyben éppen tartózkodik. A négyzeten belül definíció szerint nem határozunk meg akadályokat, azok csupán a négyzetnek megfelelı terület darabokra értelmezettek. Ekkor egy négyzet vagy akadály, vagy szabadon átjárható területet jelöl. A négyzeten belül mindössze az egységek ütközését kell megakadályoznunk. A négyzet méretének növelésével egyenes arányosságban nı az egységek mozgásának részletessége. Az egységek mozgása azonban implementációtól függıen más és más sebességgel történhet. Ha pusztán megnöveljük minden egyes ciklusban a koordinátákat, akkor különbözı sebességő számítógépeken az egység különbözı sebességgel fog mozogni. Ezt kiküszöbölhetjük, ha a koordináták növelését a két ciklus közt eltelt idı függvényében végezzük. Ekkor

lehetıségünk nyílik arra is, hogy pontosan meghatározhassuk az egységek típusonkénti sebességét. Az ily módon implementált megoldás a számítógép sebességétıl függetlenül mindig azonos sebességgel mozgatja az egységet. 6.12 Magas szintő MI A magas szintő mesterséges intelligenciát megvalósító függvények egyik feladata a tanulási folyamat implementálása. Ebbe sorolhatjuk egy adott pálya felfedezését A felfedezés jelen értelmezésben a pályához tartozó gráf automatikus felépítését jelenti. A felépítés folyamata nem egy idıpillanat alatt hajtódik végre, hanem a játszma során folyamatosan. A gráf felépítése azért nevezhetı tanulásnak, mert az útvonalkeresés folyamán a gráfot alkalmazva egyrészt jelentısen felgyorsulhat a játékban implementált intelligencia által irányított játékos egységeinek útvonalkeresése, másrészt a gráfban eltárolhatunk olyan információkat is, melyek egyéb, a stratégiai, taktikai

döntések során játszhatnak fontos szerepet. Erre példa, amikor egy gráfpont esetén eltároljuk azt az információt is, hogy a gráfpont mekkora sugarú környezetében nincsenek akadályok. Ezt felhasználva lehetıségünk nyílik például a bázis optimális elhelyezésére. A feladat megoldásakor szükségünk van az alacsony szintő intelligenciával való kapcsolatra. Miután útvonalkeresı algoritmusok végrehajtását kértük az alacsony szinttıl, az eredményül kapott koordináta sorozaton különféle mőveleteket kell 47 véghezvinnünk. Mivel tanulásról, gráf építésérıl beszélünk, nagy valószínőséggel állítható, hogy az adott pályához még nem létezik gráf, vagy az nem fedi le a teljes pályát, így bıvítésre szorul. Minthogy pedig nem létezik a vizsgált régióban gráf, az alacsony szint az A* útvonalkeresı algoritmust fogja alkalmazni. Errıl tudjuk, hogy bizonyos esetekben nem ad esztétikus útvonalat, ami miatt az útvonal

koordinátáit követı egység mozgása nem lesz természetes. Ezt egy magas szinten implementált algoritmus segítségével kijavíthatjuk. Nem kell mást tennünk, mint a koordinátasorozat által leírt útvonalat „kiegyenesítenünk”. A megoldás folyamán az útvonal azon koordinátáit határozzuk meg, melyek között nincs akadály, ennél fogva kiiktathatjuk a felesleges koordinátákat. Eredményként egy esztétikusabb utat kapunk, amely kevesebb koordinátát tartalmaz. A mővelet eredménye a 18 ábrán tekinthetı meg A sárga négyzetek az eltárolandó adatként szereplı koordinátákat, a kék négyzetek a futás menetén kiszámolt koordinátákat (ezáltal tárolásuk szükségtelenné válik) jelentik. 18. ábra: az A* algoritmus eredményének optimalizálása A fenti eljárás hasznosságát azonban nem csak az útvonal formájának javítása bizonyítja, hanem a tanulást jelentı gráf-építés lehetısége is. Amint az a 18 ábrán is látható, az

algoritmus futása után kapott pár koordinátát mint gráfpontokat hozzáadhatjuk a gráfhoz. Ezen koordináták nem csak egymással lesznek kapcsolatban (tehát él húzható két-két pont között), hanem az új gráfpontokon végighaladva, a többi gráfpontra páronként egy összeláthatósági algoritmust alkalmazva ezen gráfpontok beintegrálhatóak a gráfba. A mechanizmus mőködésekor az intelligencia számára ismeretlen pálya minden egyes útvonalkereséssel könnyebben átláthatóvá válik. A stratégiai döntéseket, az infrastruktúra létesítését és karbantartását, védelmét, az egységek irányítását elsı körben egy egyszerő szabály alapú rendszer vezérli. Ennek a megvalósítása viszonylag egyszerő, ettıl függetlenül jó eredményeket lehet elérni a segítségével. A szabály alapú rendszer alapján mőködı intelligencia tanulási képességei elegendınek tekinthetıek. A megvalósítás során például minden ciklusban 48

ellenırizhetjük azt, hogy mikor és hol találkoztunk ellenséges egységekkel, illetıleg a bázisunkat mikor, melyik oldalról támadták meg, mekkora haderıvel. Ezen információk alapján egy késıbbi játszmában lehetıségünk nyílik egyszerő védekezési taktikák kialakítására, így például megpróbálunk a bázisunk veszélyeztetett pontjaira még az elıtt védelmet telepíteni, mielıtt a támadások várhatóan elkezdıdnének. 6.2 Megjelenítés [18] A programom a megjelenítés során a Microsoft DirectX 7-es verziójának DirectDraw7 komponensének lehetıségeit használja fel. A DirectDraw alkalmazásával a videokártya memóriájához való közvetlen hozzáférésnek köszönhetıen a képszintézis sebessége drasztikusan felgyorsítható a hagyományos, Windows Forms alapú megjelenítéshez képest. A DirectDraw mőködéséhez szükségünk van egy ablakra, amiben a képszintézis fog történni. A folyamatosabb megjelenítés érdekében

mindenféleképpen célszerő alkalmaznunk a dupla puffereléses (double buffering) eljárást. Ennek lényege, hogy nem közvetlenül arra a memóriaterületre készítjük el a képkockát, amelyik éppen látható, hanem egy másik területen dolgozunk, majd pedig az megjelenítendı memóriaterület kezdıcímére mutató mutatót megváltoztatjuk, hogy az a kész képre mutasson. Így egy teljesen villogás mentes, folyamatos képszintézis érhetı el. A mőködéshez alapvetıen három fajta memóriaterület lefoglalására van szükségünk Ezen memóriaterületek a videokártyára integrált memóriamodulokban helyezkednek el, elısegítve ezzel a lehetı leggyorsabb feldolgozást, hiszen ezek a memóriamodulok akár nagyságrendekkel gyorsabbak lehetnek a rendszermemóriánál30. Két, azonos mérető memóriaterület a double buffering megvalósításához szükséges. Ezek mérete az aktuális felbontástól és színmélységtıl függ, tehát például ha 1024 x 768 pixel

nagyságú, pixelenként 32 bites (16.7 millió szín) megjelenítést alkalmazunk, akkor ezen pufferek egyenként 3 megabájt tárterületet igényelnek. A DirectDraw-ban ezeket a tárterületeket surcface-eknek nevezzük. A gyors mőködés érdekében minden olyan képet, amelyet a képkockák elkészítésénél használni kívánunk, ilyen surface-ekben kell eltárolnunk a videomemóriában. 30 Egy modern számítógép rendszermemóriájának sebessége (DDR2, dual channel, 2x64 bit): 7-8GB/s , míg egy modern videokártyán lévı modul sebessége (pl. ATi Radeon X1900XT, 256bit): 25-50GB/s 49 A játékos a játék mőködése folyamán a meghatározott alkotóelemekbıl felépített képkockák sorozatát látja. Az emberi szem a másodpercenkénti 25 képkockát már mozgóképnek észleli. Szerencsére a mai modern processzorok és grafikus kártyák még az általam alkalmazott technológiáktól jelentısen bonyolultabb számítások esetén is képes elérni ezt az

értéket. Kivételt képeznek a felbontás, vagy a nagyítás/kicsinyítés bizonyos szélsıséges beállításai. Ekkor drasztikusan lecsökkenhet a teljesítmény, azonban ez természetesen függ az alkalmazott hardver sebességétıl is. Egy képkocka alapvetıen két lehetséges módon épülhet fel. Az egyszerőbb eset a menürendszer megjelenítése, hiszen ekkor pusztán karaktereket és vonalakat kell a megfelelı pozícióban kirajzolni. Ettıl bonyolultabb a játszma során látható kép felépítése. Ennek egyik oka, hogy a szintetizált kép több alkotóelembıl épül fel Ilyen például maga a pálya kirajzolása, a térkép megrajzolása és egyéb, a játékmenethez tartozó információk megjelenítése. A megjelenítés legbonyolultabb részét a pálya izometrikus kialakítása képezi. Amint azt már egy korábbi fejezetben említettem, az izometrikus megjelenítés egy három dimenzióhoz közeli ábrázolásmód, azonban nem rendelkezik perspektívával. Míg

a három dimenziós képszintézis esetén térbeli koordinátákkal, mátrixokkal és egyéb számításigényes mőveletekkel kell foglalkozni, addig az izometrikus ábrázolásnál elegendı a koordinátarendszer-transzformáció és az elıre megszerkesztett bitképek másolásának alkalmazása. A felszínt alkotó bitképeket az angol megfelelıje alapján csempéknek hívjuk. A 19 ábrán figyelemmel kísérhetjük a felszín kirajzolásához szükséges transzformációkat. A csempék alapértelmezett mérete 2n x n, ami alapesetben 128x64 pixeles bitképeket jelent. A csempék térben elforgatott négyzeteket ábrázolnak Ezek a négyzetek megfeleltethetık az intelligencia mőködéséhez szükséges felosztásnak, így például az A* algoritmus egy egységének egy csempét feleltelhetünk meg. A térkép koordinátarendszerébıl a megjelenítendı kép koordinátarendszerébe történı transzformáció a következı: x = x⋅ tileWidth tileHeight − y ⋅ 2 2 y =

x⋅ tileWidth tileHeight + y ⋅ 2 2 A képletben szereplı tileWidth és tileHeight az alapértelmezett csempe pixelekben mért szélességét és magasságát – a korábban említett n-t és 2n-t - jelenti. A 19 ábrán és 50 a képletben látható x és y a képernyı koordinátarendszerének, míg az x’ és y’ a pálya koordinátarendszerének tengelyeit határozzák meg. Az alapcsempe nagyított képén szereplı x, y és z koordináták az izometrikus ábrázolásmód tengelyeit jelentik. Ezen tengelyek egymással páronként 120°-os szöget zárnak be. x’ x 2n y’ z n y x y 19. ábra: a játékban alkalmazott izometrikus megjelenítés Amint az jól látható, a képszintézis végeredményében számunkra a világoskékkel jelölt területek zavaróak. Mivel a memóriában egy téglalap alakú bitkép leképzése jelentısen egyszerőbb, mint egyéb alakzatoké, így a nem téglalap alakú képeket is a befoglaló téglalappal együtt kell

eltárolnunk. Annak érdekében, hogy a megjelenítéskor azonban csak az információt hordozó zöld terület jelenjen meg, meg kell adnunk a DirectDraw számára, hogy az adott képben melyik színt vegye átlátszónak. Ha átlátszó színként a világoskéket határozzuk meg, és másoláskor bebillentjük a megfelelı bitet, amely jelzi a DirectDraw felé, hogy vegye figyelembe az átlátszóságot a másolás közben, akkor csak a zöld terület fog átmásolódni. Értelemszerően olyan átlátszó színt szükséges meghatározni, ami egyik képen sem jelenik meg értékes információként. Általánosságban az intenzív lila és rózsaszín színeket alkalmazzák, mivel ezek a színek nagyon ritkán fordulnak elı a megjeleníteni kívánt képekben. A programomban a fekete 51 színt választottam, mivel a képekben pixelenként 24 biten ábrázoljuk31 a színeket, és az átlátszósági szín meghatározásánál nem tartományt, hanem egy pontos értéket adunk

meg. Tehát amikor egy képen a fekete szín használata indokolt, akkor az a valóságban nem lesz teljesen fekete, ezt az árnyalatbeli különbséget azonban az emberi szem nem képes érzékelni. A programot úgy alakítottam ki, hogy az különbözı mérető csempékkel is használható legyen. Ez azt jelenti, hogy a felhasználó maga készítheti el a játékban megjelenítendı csempéket, ezáltal a játék teljes kinézetét megváltoztathatja. Új csempék szerkesztése folyamán bizonyos szabályokat be kell tartani, egyéb esetben a megjelenített kép nem várt eredményt mutathat. Az egyik ilyen alapvetı szabály a csempék alapértelmezett mérete: legyen kétszer olyan hosszú, mint magas. 6.3 Dinamikusan csatolt könyvtárak és szálak kezelése [19-20] Ahhoz, hogy a megtervezett játék minél jobban kielégítse a komponens alapú fejlesztés által meghatározott követelményeket, a dinamikusan csatolt könyvtárak (DLL) alkalmazását láttam indokoltnak. A

DLL-ekben alapvetıen olyan megosztott függvényeket, adatokat tartalmaznak, melyeket több program is felhasználhat, illetıleg fejlesztés, hiba esetén egységenként cserélhetıek. A DLL-ben tárolt erıforrásokat az azokat felhasználó programból egy jól meghatározott interfészen keresztül lehet elérni. Amennyiben az interfészt megtartjuk, de a függvények implementációját megváltoztatjuk, akkor – amennyiben hibátlanok a frissített függvények – a DLL-t használó program változatlanul mőködni fog. A mőködés módja megváltozhat, hiszen bizonyos függvényeket átírtunk. Mivel az interfész elsısorban a függvények neveit, ill belépési pontjait definiálja, ezért alapesetben függvényeket tárolhatunk a DLL-ben. A komponens alapú fejlesztés elıfeltétele azonban az objektum orientált programozás, melyben az osztályok játsszák a fıszerepet, nem pedig az egyszerő függvények, tehát egy magasabb absztrakciós szintre van

szükségünk. Az OOP képességeit felhasználva lehetıségünk van egy osztály eltárolására a DLL-ben. Ezt az objektum orientált programozásból ismert interfészekkel érhetjük el, melyek absztrakt osztálydeklarációkat tartalmaznak. A megoldásomat a 20 ábrán tettem közzé 31 24 bit = 8 bit piros + 8 bit zöld + 8 bit kék 52 CThread OSZTÁLY DWORD Start(void * arg) DWORD Stop(bool forceKill) protected virtual DWORD Run (LPVOID) [.] ThreadDLLInterface INTERFÉSZ virtual bool Init() virtual bool Release() virtual DWORD StartThread(void *arg) virtual DWORD StopThread(bool forceKill) ThreadDLLClass OSZTÁLY bool Init() bool Release() DWORD StartThread(void *arg) { Start(arg); } DWORD StopThread(bool forceKill) { Stop(forceKill); } DWORD Run (LPVOID) { thread main } HRESULT DLL API GetThreadDLLInterface HRESULT DLL API FreeThreadDLLInterface Dinamikusan csatolt könyvtár ThreadDLLClass OBJEKUPÉLDÁNY Alkalmazás 20. ábra: DLL és szálkezelés

integrációja A programomban egyesítettem a szálkezelést a dinamikusan csatolt könyvtárak használatával. A szál kezelését a CThread osztály végzi Az osztályt örökölve létrehozhatjuk a számunkra megfelelı mőködéssel bíró osztályt. A számunkra megfelelı mőködést a CThread ısosztály Run virtuális metódusát felüldefiniálva implementálhatjuk. A szál indításáért és leállításáért a StartThread és StopThread függvények felelısek. Amint azt korábban már említettem, egy DLL-bıl nem lehet közvetlenül egy osztályt exportálni, pusztán függvényeket, ezért olyan függvényeket exportálunk, amelyek eredményül egy ThreadDLLClass osztály példányának címét adják. Ily módon ugyan csak függvényeket exportáltunk, azonban képesek vagyunk a DLL-ben implementált osztály példányosítására, valamint az osztályban meghatározott szál mőködtetésére. A 20 ábrán látható alkalmazásban a DLL-ben tárolt osztályt úgy

53 példányosíthatjuk, hogy az interfészt implementáló osztályt példányosítjuk, erre szükségünk van természetesen a megfelelı interfészre. A gyakorlatból származó példa a következı: adott a megjelenítést végzı szál implementációja. Az ehhez tartozó interfész: struct DisplayDLLInterface { virtual bool Init(GameDataClass *newGameData) = 0; virtual bool Release(void) = 0; virtual DWORD StartThread(void *arg) = 0; virtual DWORD StopThread(bool bForceKill) = 0; }; #ifdef DLL EXPORT #define DLL API declspec(dllexport) #else #define DLL API declspec(dllimport) #endif extern "C" { HRESULT DLL API GetDisplayDLLInterface(DisplayDLLInterface * pDisplayDLLInterface); typedef HRESULT (*GET DISPLAY DLL INTERFACE)(DisplayDLLInterface pDisplayDLLInterface); HRESULT DLL API FreeDisplayDLLInterface(DisplayDLLInterface * pDisplayDLLInterface); typedef HRESULT (*FREE DISPLAY DLL INTERFACE) (DisplayDLLInterface pDisplayDLLInterface); } A fenti kód

alapján tehát a dinamikus csatolású könyvtárból két függvényt exportálunk, a GetDisplayDLLInterface és a FreeDisplayDLLInterface nevőeket. Az elsı segítségével tudjuk példányosítani az DisplayDLL osztályt. Mivel a fenti kód egy header fájlban található, a fıprogram fejlesztése folyamán beemeljük a kódba, így a DisplayDLLInterface struktúra is elérhetıvé válik, ami nem más, mint maga az interfész. A felhasználást egyszerősíti a DLL API nevő definíció, amely a DLL EXPORT definiálása esetén azt az értéket veszi fel, melynek segítségével a DLLbıl exportálhatunk függvényeket. Ellenkezı esetben a fıprogramba emeltük be az ezt tartalmazó header fájlt, ekkor a meghatározott DLL-bıl importálnunk kell a függvényeket. Mivel a fıprogramban nem definiáltuk a DLL EXPORT-ot, ezért ebben az esetben is jól fog mőködni a program. Az interfészt megvalósító osztály kódja vázlatosan a következı: class DisplayDLLClass: public

DisplayDLLInterface, public CThread { public: DisplayDLLClass(); ~DisplayDLLClass(); bool Init(GameDataClass *newGameData); 54 bool Release(void); DWORD StartThread(void *arg); DWORD StopThread(bool bForceKill); }; Amint látható, az osztály megvalósítja a hozzá tartozó interfészt, miközben örökli a CThread szálkezelı osztály tulajdonságait is. Ezzel egy olyan osztályt kaptunk, melynek segítségével egy külön szálat kezelı egységet egy DLL-ben tudunk tárolni. Ezzel egy igen jól kezelhetı komponenst kaptunk, amit rendkívül könnyedén megváltoztathatunk, mindössze arra kell tekintettel lennünk, hogy az interfész által elıírt funkciókat teljesítsük. Végül pedig, ha a fıprogramban használni kívánjuk ezt a komponenst, akkor a következıt kell tennünk: #include ".DisplayDLLDisplayDLLInterfaceh" [] DisplayDLLInterface *pDisplayDLLInterface; HINSTANCE hDisplayDLL; GET DISPLAY DLL INTERFACE GetDisplayDLLInterface; [] hDisplayDLL =

LoadLibrary("bin\Display.dll"); [] GetDisplayDLLInterface = (GET DISPLAY DLL INTERFACE)GetProcAddress(hDisplayDLL,"GetDisplayDLLInterface"); [] HRESULT hr = GetDisplayDLLInterface(&pDisplayDLLInterface); [] pDisplayDLLInterface->Init(gameData); pDisplayDLLInterface->StartThread(NULL); [] Elsı lépésként beemeljük az interfész deklarációját, majd definiáljuk a szükséges változókat. Ezt követıen az ismert módon betöltjük a dinamikusan csatolható könyvtárat a memóriába, és a definiált változóhoz rendeljük a könyvtár megfelelı függvényét. A sikeres hozzárendelés után kiadjuk azt az utasítást, amivel példányosítjuk a DLL-ben tárolt osztályt. Ez a függvény a paraméterként átadott változóhoz hozzárendeli a létrehozott objektumpéldány címét. Ha mindez sikerült, nem kell mást tennünk, mint használni a DLL-ben tárolt osztályunkat, a fenti esetben inicializáljuk, majd elindítjuk az osztály által

megvalósított szálat. A leírt módon elkészített komponens rendkívül rugalmas felhasználási lehetıségeket kínál, pusztán az interfész minden pontjának implementációjára van szükségünk. Hibás mőködés esetén a hiba viszonylag könnyen azonosítható még egy összetettebb kód esetén is. 55 7. RÉSZLETES SPECIFIKÁCIÓ 7.1 Osztályok felépítése, egymásra épülésük 7.11 A program felépítése A program a Microsoft VisualStudio .NET 2003, valamint a VisualStudio 2005-ös verziójával készült C++ nyelven, elıtérbe helyezve az objektum orientált, valamint a komponens alapú fejlesztési paradigmákat. A tervezés folyamán a legegyszerőbb osztályoktól haladtam az egyre összetettebbekig, melyek részben tartalmazzák az addig kialakított egyszerőbb osztályokat. A program alapvetı felépítését a 21 ábrán láthatjuk A felosztás lényege, hogy a fıprogram a futtatható állomány (EXE fájl), amely az elsı szálon fut, ez

reprezentálja magát a folyamatot is, és innen indítjuk a többi szálat. Az irányítás egy külön DLL-be került, azonban ugyanabban a szálban fut, amiben a fıprogram is. A megjelenítés is külön DLL-ben kapott helyet, viszont szoros kapcsolatban áll az irányítással. Ennek oka, hogy ha akár kis mértékben is megváltoztatjuk a megjelenítési részt, nagy valószínőséggel változtatni kell az irányításon is. A megjelenítés azonban már a második szálon fut A negyedik, jól elkülöníthetı egységet a mesterséges intelligencia alkotja. Minthogy jól elkülöníthetı, ezért külön DLL-ben tároljuk, és külön szálon is fut. Az ábrán a nyilak a kapcsolatok helyét és irányát jelzik. Egy teljesen külön egységet alkot a pályaszerkesztı, amely azonban a program szerves részének tekinthetı. Pályaszerkesztı irányítás megjelenítés mesterséges intelligencia fıprogram 21. ábra: a program felépítése futási szempontból 56

7.12 Osztályok leírása Az osztályok elnevezésének módja: <osztálynév>Class, pl. DisplayDLLClass Az interfészek elnevezésének módja: <interfésznév>Interface, DisplayDLLInterface A fıprogram legelemibb osztályai a következık: FIFOClass Felhasznált osztályok: nincs Leírás: Egy FIFO adatszerkezetet valósít meg egy duplán láncolt lista segítségével. Lehetıségünk van a funkciójának megfelelı mőveleteken túl a lista bármely elemének módosítására is, ez a késıbbi felhasználás során játszik fontos szerepet. PathClass Felhasznált osztályok: nincs Leírás: Használatával kétdimenziós koordinátasorozat tárolására és kezelésére van lehetıségünk. Az x és y koordinátákat egy-egy integer típusú fix hosszúságú tömbben tárolja, melynek nagyságát a konstruktorban adhatjuk meg. A játék adatait és az azokat kezelı függvényeket tartalmazó osztályok a következık: MapClass Felhasznált osztályok: PathClass

Leírás: Ez az osztály tartalmazza a pálya adatait. Függvényei között megtaláljuk a betöltés és a mentés implementációit is. Az osztályban helyezkedik el az A* algoritmus megvalósítása, mely egy PathClass típusú változónak adja át a kiszámolt útvonal koordinátáit. Az algoritmust a mesterséges intelligenciát tartalmazó AI.DLL-bıl hívom meg, külön szálon A pálya szélessége és hosszúságán kívül az osztályban megtalálható az az attribútum is, amely a pálya felosztásának mértékét adja meg. Amint azt egy korábbi fejezetben leírtam, az útvonalkeresés egyszerősítése érdekében a pályát négyzet alakú 57 területekre célszerő felbontani. A tileSize attribútum egy ilyen négyzet oldalhosszát adja meg. GraphClass Felhasznált osztályok: PathClass, FIFOClass Leírás: Egy gráf tárolására, és az abban történı útvonalkeresésre alkalmas. A gráf tetszılegesen módosítható, háttértárról betölthetı,

elmenthetı. Minden játékosnak külön gráffal rendelkezik, hiszen más és más helyrıl indulnak a pályán. Amennyiben pedig még nem ismerik, akkor a kiinduló helyükrıl kezdve fogják feltérképezni azt. Ily módon bizonyos idı elteltével a játszmában résztvevı játékosoknak mind különbözı „tudásuk” lesz a pálya kinézetérıl. A gráfban való keresés eredményét egy PathClass típusú változóban kapjuk meg. UnitClass Felhasznált osztályok: PathClass Leírás: A játszma folyamán elıforduló összes egységet egy-egy ilyen osztály reprezentál. Ennek megfelelıen a tárolt adatok között megtalálható az egység lebegıpontos számmal ábrázolt pozíciója, sebessége, elfordulása. A pozíció számításánál szerepet játszik a MapClass osztály tileSize attribútuma. Különféle egyéb segédinformációk mellett egy PathClass típusú nyilvános változóban az egység aktuális mozgásához szükséges koordináták találhatóak meg.

Az osztály egyik talán legfontosabb metódusa a moveOneStep(), melynek segítségével az egység egy elemi lépéssel közelebb kerül a célhoz. Az elemi lépés a MapClass osztály tileSize attribútumától függ. PlayerClass Felhasznált osztályok: GraphClass, UnitClass Leírás: Egy játékos adatait és az azokat módosító metódusokat tartalmazza. Az osztály alkalmazásával megadhatjuk, hogy egy adott játékos mely egységei legyenek az adott pillanatban kiválasztva, és ezeknek milyen feladatokat végezhetünk el. Ezek közé tartozik, hogy a kiválasztott egységeknek egy új célpontot adunk meg. A játékos összes egységét mozgathatjuk a moveUnitsOneStep() metódus 58 segítségével. Az osztályok felépítésének köszönhetıen a metódus implementálása során figyelmen kívül hagyhatjuk az egységek különbözı sajátosságaiból adódó viselkedési különbségeket, mivel azokat már egy alacsonyabb absztrakciós szinten kezeltük.

GameDataClass Felhasznált osztályok: MapClass, PlayerClass Leírás: A összes játékos adatain kívül olyan fontos attribútumokat is tartalmaz, melyek segítségével a szálak közti kommunikáció lebonyolítható. Elsıdleges feladata tehát a program különbözı részeit alkotó komponensek közötti kapcsolat biztosítása. Mivel ebben az osztályban található meg a játék futásához szükséges összes fontosabb függvény, így a különbözı szálakon futó komponensek ennek az osztálynak a megfelelı függvényeit hívják meg. Ily módon a játék logikája egy egységet alkot, futási idıben azonban külön-külön szálakra bontható, növelve ezzel a játék sebességét, csökkentve a program reakcióidejét. GameWindowClass Felhasznált osztályok: GameDataClass, ControlsDLLInterface, DisplayDLLInterface, AIDLLInterface Leírás: A játékprogram alapját képezı osztály. Mőködésének elsı fázisában, azaz a konstruktorában inicializálja a

GameDataClass osztályból létesített objektumpéldányt, és beállítja annak fıbb attribútumait (ilyen például a játék ablaka), csatolja a dinamikus könyvtárakat, és meghívja azok inicializáló függvényeit. E függvények hívásakor paraméterként adja meg a gameData változót, megteremtve ezzel a komponensek közti kapcsolatot. Végül pedig 1es értékre állítja a GameDataClass runLevel attribútumát, jelezve, hogy a játék fımenüjét kívánjuk megjeleníteni. Mőködésének második szakaszában az osztály a Windows üzeneteit dolgozza fel, illetve továbbítja az irányítást végzı komponens felé. Az osztály a program befejezésekor felszabadítja a lefoglalt erıforrásokat (dinamikusan csatolt könyvtárak, a játék összes adatát tartalmazó gameData objektumpéldány, stb.) 59 A megjelenítést végzı komponens osztályai a következık: BitmapClass Felhasznált osztályok: nincs Leírás: Az osztály feladata egy 24 bites bitkép

tárolása a videomemóriában. Segítségével a képszintézis során a bitképek másolása egyszerősödik. TileClass Felhasznált osztályok: BitmapClass Leírás: A játék megjelenítési algoritmusa csempékbıl felépített izometrikus képet alkot. Ezek a csempék különféle típusokba csoportosíthatóak Ábrázolhatnak vizet, fákat vagy füvet. Az osztály feladata egy ilyen csoportba tartozó összes bitkép menedzselése. Mivel az osztály a lehetıségekhez mérten megfelelıen univerzális felépítéső, így széles körben alkalmazható. MenuClass Felhasznált osztályok: BitmapClass Leírás: A játékban látható menük tárolására szolgál. Megvalósítja mind a játék indulásakor látható fımenüt, mind a játszma során az adott entitásra vonatkozó beállítási lehetıségeket felsoroló grafikus menüt32. DisplayControlConnectionClass Felhasznált osztályok: MenuClass, GameDataClass Leírás: A megjelenítés és az irányítás között lévı

szorosabb kapcsolat miatt szükséges eme osztály definiálása. Alkalmazásával többek között a menük használata jelentısen egyszerősödik. DisplayDLLInterface Felhasznált osztályok: DisplayControlConnectionClass, GameDataClass 32 Pillanatnyilag még nincs implementálva (2006. 04 24) 60 Leírás: Segítségével megvalósítható a dinamikusan csatolt könyvtárban eltárolt osztály33, amely a játék megjelenítéséért felel. DisplayDLLClass Felhasznált osztályok: DisplayDLLInterface, DisplayControlConnectionClass, GameDataClass, TileClass Leírás: Az osztály a játék képszintéziséért felelıs. A DirectDraw felhasználásával izometrikus képet állít elı, ill. megjeleníti a menüket Az osztály a Display.DLL-ben található meg Az irányításért felelıs komponens osztályai a következık: ControlsDLLInterface Felhasznált osztályok: DisplayControlConnectionClass, GameDataClass Leírás: Segítségével megvalósítható a dinamikusan

csatolt könyvtárban eltárolt osztály, amely a játék irányításáért felel. ControlsDLLClass Felhasznált osztályok: ControlsDLLInterface, DisplayControlConnectionClass, GameDataClass Leírás: Az osztály a játék irányításáért felelıs. Feladatai közé sorolható az egységek kiválasztásához szükségek algoritmus megvalósítása, vagy a billentyőzetrıl érkezı parancsok felismerése. Az osztály a ControlsDLL-ben található meg 33 Lásd a 20. ábrát 61 Az intelligenciát kezelı szál osztályai a következık: AIDLLInterface Felhasznált osztályok: GameDataClass Leírás: Segítségével megvalósítható a dinamikusan csatolt könyvtárban eltárolt osztály, amely az intelligenciát kezelı szálat tartalmazza. AIDLLClass Felhasznált osztályok: AIDLLInterface, GameDataClass, PathClass Leírás: Az osztály a játékban alkalmazott intelligencia kezeléséért felelıs. Feladatai közé sorolható az egységek útvonalkeresésének

futtatása. Az osztály az AI.DLL-ben található meg A függıségi kapcsolatokat a 22. ábra mutatja FIFO Path Graph Unit Bitmap Map Tile Menu Player GameData DisplayControlConnection DisplayDLLInterface DisplayDLL ControlsDLLInterface ControlsDLL AIDLLInterface AIDLL GameWindow 22. ábra: függıségi kapcsolatok A kékkel jelölt osztályok külön DLL-ben helyezkednek el. 62 7.2 Telepítés, szoftver elıkövetelmények Elsı lépésben a programot telepíteni kell. A játék Microsoft Windows XP operációs rendszeren lett fejlesztve, más, korábbi verziójú Windows rendszereken a futás nem garantált. A program mőködéséhez szükséges a Microsoft NET 20, vagy késıbbi verziója, valamint a Microsoft DirectX legalább 7-es kiadása. A telepítést a mellékelt setup.exe állomány indításával kezdhetjük meg A telepítı üdvözlı képernyıje (23. ábra) után a NET telepítésére kerül sor, amennyiben a rendszerben nem található meg a

megfelelı verzió. Ezt követıen a telepítı felajánlja a lehetıséget a program könyvtárának megadására (24. ábra) 23. ábra: a telepítı üdvözlı képernyıje A következı képernyın a telepítés folyamatát követhetjük nyomon, majd pedig a telepítı jelzi, hogy elkészült a munkával (25. ábra) A telepítést követıen a programot mind a start menüben, mind az asztalon megtalálható ikon segítségével indíthatjuk el. 63 24. ábra: célkönyvtár megadása 25. ábra: a telepítés folyamata és befejezése 7.3 A játék kezelése A játék indulását követıen a program fımenüjét láthatjuk a képernyın. Innen a beállítások menüpontra való kattintással érhetjük el a játék fıbb jellemzıit (26. ábra) Átállíthatjuk többek között a nyelvet és a felbontást, módunkban áll a játék naplózási tevékenységének szabályozására is. A ciklusonkénti várakozásnál azt az idıegységet határozhatjuk meg milliszekundumos

lépésközönként, amely a játék futása folyamán két elemi ciklus közt helyezkedik el. Minél nagyobb ez az érték, annál lassabb lesz a játék futása, azonban ennek megfelelıen egyre kevesebb erıforrást is igényel. Ha ez az érték nulla, akkor a játék az adott hardver sebességét teljesen kihasználva lassítás nélkül fut. Ekkor a mai modern gépek esetében a játék irányíthatatlanná válik. A naplózás (log) nulla értéke esetén a program csak nagyon minimális információkat ír ki a háttértárra a futás közben. Nagyobb értékeknél egyre frekventáltabb információrögzítést 64 tapasztalhatunk. A harmadik szintet már csak azon felhasználóknak ajánlom, akik mély betekintést szeretnének kapni a program mőködésébe. Ezen a szinten a játék szinte játszhatatlanná válik, és a naplófájl (wair log.htm) mérete is igen gyors mértékben növekedik, rövid idın belül elérheti a több megabájtot is. A beállított

naplózási szinttıl függetlenül a hibák mindig rögzítésre kerülnek hibajavítás céljából. 26. ábra: a játék beállítási lehetıségei A fımenüben a játék létrehozása menüponttal kezdhetünk meg egy új játékot. Ekkor ki kell választanunk azt a pályát, amelyiken játszani szeretnénk. A játszmát a Játék indítása gomb megnyomásával indíthatjuk el (27. ábra) 27 ábra: a játék indítása 65 A játék indulását követıen és a játszma folyamán a 28. ábrán látható kezelıfelületet használhatjuk. Mivel a pályák általában jelentısen nagyobbak, mint amennyi még optimálisan megjeleníthetı, ezért szükséges a kép görgetésének alkalmazása. Ha az egérmutatót a képernyı megfelelı széléve mozgatjuk, a kép a megfelelı irányú folyamatos görgetésbe vált át. A mutató a képernyı szélérıl való elmozgatásával a görgetés megszőntethetı. A képernyınek a pályához mért pozícióját a képernyı jobb

felsı sarkában látható térképen követhetjük nyomon. Módunkban áll a képernyı mozgatását a billentyőzetrıl is vezérelni, ehhez pusztán a megfelelı nyíl nyomva tartása szükséges. Hibakeresési és statisztikai információk Kijelölı téglalap Kijelölt egység Térkép, és a kép aktuális pozíciója 28. ábra: a játék kezelıfelülete A képernyı nagyításához illetve kicsinyítéséhez a billentyőzet számtömbjénél található plusz és mínusz gombokat használhatjuk. 66 Az egységek irányítása a más, hasonló játékoknál megszokott módon történik. Egy egység kiválasztásához az egérmutatót mozgassuk az egység fölé, majd kattintsunk az egér bal gombjával. Ekkor a 28 ábrán is megfigyelhetı kék keret veszi körül az egységet, ami a kiválasztás sikerességét jelzi. Lehetıségünk van természetesen egyszerre több egység szimultán kiválasztására is. Ehhez az egér bal gombjának nyomva tartása mellett egy,

a kiválasztandó egységeket befoglaló jelölınégyzet megrajzolására van szükségünk. Amint feleresztjük az egér bal gombját, a jelölınégyzetben elhelyezkedı összes egységet a már ismertetett funkciójú kék keret veszi körül. A kiválasztási módszerek további lehetıségeihez a billentyőzetet is használnunk kell. Ha a meglévı szelekcióhoz kívánunk további egységeket főzni, akkor ezt a control gomb nyomva tartása mellett tehetjük meg a már említett módozatokon. Egy vagy több egységet eltávolíthatunk a szelekcióból, ha a shift gombot nyomva tartjuk. A kiválasztott egységeknek új útvonalat határozhatunk meg, ha egy olyan helyre kattintunk az egér bal gombjával, amelyik az egységek által bejárható. A szelekció megszüntetésére két lehetıségünk van. Az elsınél az egér jobb gombjával kell kattintanunk, míg a másodiknál egy olyan kijelölı téglalapot kell rajzolnunk, melyben nincsenek egységek. A „g” bető

megnyomásával a keresést segítı gráfot tehetjük láthatóvá. Újbóli megnyomása esetén kikapcsolhatjuk a játék eme tulajdonságát. Az ESC gomb hatására a játékot szüneteltetjük, és a megjelenı menübıl kiválaszthatjuk a számunkra fontos opciót. Az összes menüre érvényes, hogy az ESC gomb megnyomása esetén egy szinttel feljebb lévı menübe ugorhatunk át. Ha elértük az alap szintet, akkor a programból léphetünk ki a segítségével. 7.3 A pályaszerkesztı kezelése A játékban fellelhetı összes pályát a pályaszerkesztı segítségével hozhatjuk létre. Egy új pálya létrehozásához a File menü New map opcióját használjuk. Itt megadható a korábbi fejezetekben ecsetelt tileSize értéke is. Egy már meglévı pálya adataihoz a File menü Map properties menüpontján át juthatunk el. A pálya kialakításához szükséges csempék a jobb oldalon található Tiles fül alatt lelhetık fel. A Random tiles a csempék egyszerőbb

szerkesztését segítik elı. A kiválasztott típusból véletlenszerően rakhatunk 67 így le csempéket, emelve ezzel a pálya színvonalát (eredményül egy változatosabb pályát kapunk). A Graph fülre kattintva a pályához tartozó gráf, gráfok szerkeszthetıek. Az Add nodes gomb segítségével a gráfhoz további csúcspontok adhatóak, míg a Delete node alkalmazásával a kiválasztott gráfpont az összes hozzá tartozó éllel együtt törölhetı. Az Add connection használatával lehetıségünk nyílik két csúcs közé élet elhelyezni, míg a Remove connection esetén törölhetjük ezeket. A szerkesztendı pálya Térkép a navigációhoz A rendelkezésre álló csempék Kiválasztott csúcspont Gráf-kezelı felület 29. ábra: a pályaszerkesztı felépítése 68 A gráfpontokat a pályán is kiválaszthatjuk, használhatjuk azonban a gráfpontok listáját is. A Load graph és Save graph gombokkal betölthetünk, illetve elmenthetjük a

szerkesztett gráfot. A gráf összes csúcsát és élét egy kattintással, a Clear graph segítségével törölhetjük. A skin menü használatával az alkalmazott csempéket változtathatjuk meg. A Use skin menüpont segítségével beállíthatjuk a csempék tárolására szolgáló könyvtárat. 69 8. MUNKAFÁZISOK, TAPASZTALATOK 8.1 Szálkezelés Az elsı fázisban a szálkezelési megoldások megismerése és megvalósítása volt a cél. Az itt szerzett tapasztalat alapján úgy valósítottam meg a szálkezelést, hogy a feldolgozás magját képezı while ciklusok minden egyes iterációjukban bizonyos idıegységet várakozással töltsenek el. Ennek elınye, hogy a processzor kihasználtsága jelentısen csökkenthetı, miközben a felhasználó nem vesz észre semmi különbséget a program futása során. A munkafázist a Threads nevet viselı projekt valósítja meg, amely a többi fázist megvalósító projekttel együtt a mellékelt CD-n található meg. 8.2

Útvonalkeresés A szakdolgozat eljárásokat ismertem megvalósításának meg közelebbrıl, második és lépéseként az választottam ki útvonalkeresı a számomra legoptimálisabbnak mutatkozó megoldást. A fázis elsı lépcsıfokaként az A* algoritmust valósítottam meg Microsoft VisualStudio .NET 2003 Visual C++ 7-es környezetben, melynek köszönhetıen közelebbrıl megismerkedtem a C++ és a .NET kapcsolatával. Az algoritmus kis mértékő optimalizálása után derült fény arra, hogy egy nagyobb pályán történı útvonalkeresés esetén a keresésre fordított idı nem teljesíti a „valós idejő” jelzıt, így szükséges volt egy másik algoritmus kiválasztása is. A gráfok használatának kombinálása a meglévı eljárásokkal már a várt eredményt hozta. A program tesztelése folyamán nyilvánvalóvá vált, hogy amikor nincs akadály a start és a cél között, teljesen felesleges az erıforrás-igényes algoritmusok használata,

így az útvonalkeresı algoritmus csoport következı tagjaként a LOS34 került a programba. A megfelelı programok a PathFinder projektben találhatóak meg. 34 LOS – Line of Sight – összeláthatósági algoritmus, 5.11 fejezet, 25 oldal 70 8.3 Windows API, DLL kezelés A fejlesztés harmadik szakaszában a késıbbi munkát megkönnyítendı, a Windows alkalmazás-programozói felülettel („winAPI”) ismerkedtem meg. Ekkor alakítottam ki a késıbbi játék alapját képezı fıbb osztályokat, valamint a fıprogram struktúráját, elmélyülve az OOP rejtelmeiben. Ebben a fázisban tértem át egy újabb fejlesztıkörnyezet, a Microsoft VisualStudio 2005 használatára és ismertem meg a dinamikusan csatolt osztályok alkalmazásának módozatait. A munkafázist dokumentáló programkódok a Winapi test projektben találhatóak meg. 8.4 DirectDraw A következı lépés a megjelenítés hatékonyságának, minıségének növelése volt. Amint az a

pályaszerkesztı vagy a PathFinder mőködésekor is jól megfigyelhetı, a Windows Forms, illetıleg a .NET által nyújtott grafikai lehetıségek meglehetısen gyenge eredményt mutatnak. Ennek javítása érdekében ismerkedtem meg közelebbrıl a Microsoft DirectX alkalmazás programozó felületével, ezen belül a DirectDraw komponens használatával. A Windows API korábbi fázisból örökölt ismerete jelentısen egyszerősítette a munkámat, hiszen a DirectX használata ennek, és az OOP beható ismerete nélkül nem lehetséges. A DirectDraw alkalmazásával felszabadult erıforrások egy részét a bonyolultabb képszintézis számítására tudtam felhasználni, így lehetıségem nyílt a korábbi, egyszerő felülnézeti megvalósítás izometrikus ábrázolásmódba történı átültetésére. A megjelenítési technológia fejlesztésének eredményei a wAIr elsı két verziójában nyilvánul meg a leglátványosabban. 8.5 A játék tulajdonságainak

fejlesztése, menürendszer implementálása Az ötödik fázistól kezdıdıen a programban található különbözı technológiák elérték azt a minıséget és mőködési megbízhatóságot, amely alapján a játékot tovább lehetett fejleszteni. Ezen fejlesztések közé tartozott például a felhasználói felület létrehozása és finomítása, így az egységek kiválasztásának és irányításának 71 megvalósítása is. A játék színvonalát jelentısen emelı menürendszer is ebben a fázisban került elıször a programba. Ennek fejlıdését a wAIr 05 verziójú projekttıl kezdve figyelhetjük meg. A wAIr 0.2 – wAIr 0.4 verziójú projektekben megfigyelhetı az egységek mozgásának javuló tendenciája. 8.6 A pályaszerkesztı kifejlesztése, telepítı létrehozása A soron következı fejlesztési fázis kiváltó oka a pályán elhelyezhetı objektumok számának növekedése volt. Mivel korábban a pályát tároló fájl csak azt volt képes

tárolni, hogy az adott pozíción van-e akadály, vagy nincs, így szükségszerővé vált a pálya fájlformátumának fejlesztése. Ily módon azonban a pálya már nem volt kompatibilis a PathFinder projektben megtalálható szerkesztı által generált formátummal, tehát célszerőnek látszott ezen új részegység implementálása is. A fejlesztés során a .NET új, 20-ás változatát használtam fel, melynek segítségével ugyan meglehetısen egyszerően alkothatunk megnyerı kinézető programokat, azonban amint az a mőködés folyamán tapasztalható, a grafikai megvalósítás meglehetısen nehézkes. A fejlesztés jelenlegi szakaszában már szükségessé vált egy megfelelı telepítı modul kialakítása. Szerencsére a VisualStudio minden segítséget biztosít egy magas színvonalú telepítı csomag létrehozásához, amely a telepítés folyamán ellenırzi a szükséges szoftverek meglétét, és amennyiben ezek nem találhatók meg, telepíti ıket. 8.7 A

dolgozat megfogalmazása A munka utolsó szakaszában a játékprogram bizonyos tulajdonságainak fejlesztése mellett ezt a dolgozatot fogalmaztam meg az irodalomkutatás során fellelt források segítségével. A játékprogram legfrissebb verziója jelenleg a wAIr 053 nevő projektben található meg. 72 9. TESZTELÉS A fejlesztés során rendkívül fontos szerepet játszik a tesztelés. Az az alkalmazás, amelyet az implementációja folyamán nem tesztek, nagy valószínőséggel hibás lesz. Az elızı fejezetben meghatározott munkafázisok mindegyikében folyamatosan ellenıriztem a program mőködését különbözı teszt adatokkal. A 30 ábrán látható teszt során például az derült ki, hogy a hasonló alakzatok esetében az A* algoritmus futási ideje drasztikusan megnı. Ennek enyhítése érdekében szükséges alkalmazni az ábrán is megfigyelhetı gráfot, melynek segítségével az alakzat belsejébe való útvonaltervezés ideje az eredeti töredékére

csökkenthetı. A folyamatos tesztelésnek köszönhetıen a játékprogram egységei mindig a megfelelı útvonalat választják, felhasználva a rendelkezésükre álló erıforrásokat. A tesztelést célszerő a lehetı legnagyobb mértékben kiterjeszteni, hiszen a programozó sok esetben akkor is az elvárt mőködést észleli, amikor valójában nem ez történik. Egy másik személy azonban, aki a programot csak bizonyos fázisokban látja, rendkívül gyorsan rátalál az esetleges hibákra. 30. ábra: az útvonalkeresés tesztelése a PathFinder projektben 73 10. TOVÁBBFEJLESZTÉS LEHETİSÉGEI A fıiskolán hallgatott egyik elıadáson az elıadó nagyon találóan az építészetet hasonlította össze a szoftverfejlesztéssel. Míg egy felhıkarcoló tervezésére a projekt idıtartamának jelentıs részét szánják, maga az építkezés pedig viszonylag hamar kivitelezhetı, addig egy komolyabb szoftver esetén annak életciklusának jelentıs részét az

alkalmazás megjelenése utáni javítgatás teszi ki. Ennek igen egyszerő oka, hogy a beton 21 nap alatt megköt, a szoftver használata során viszont elıbb-utóbb minden olyan hiba kiderül, amely a mindennapi használat folyamán kiderülhet. Ezt szem elıtt tartva a továbbfejlesztés egyik modulját a játék használata során fellelt hibák javítása alkotja. A továbbfejlesztés másik fontos területe a játékprogram újabb verzióinak kidolgozása. Ebbe a témakörbe rendkívül sok minden beletartozik A legkézenfekvıbb fejlesztési irány a grafika és az irányítás területén található meg, hiszen a komponens alapú építkezésnek köszönhetıen a játék viszonylag egyszerően átültethetı egy háromdimenziós rendszerbe. Ekkor természetesen a kétdimenziós megjelenítésnél alkalmazott irányítási módszerek nem alkalmazhatóak, ezért újak kifejlesztése szükséges. Minden modern játék rendelkezik hangeffektusokkal, aláfestı zenével. Mivel a

programban jelenleg nincs implementálva olyan komponens, amely ezt lehetıvé tenne, ezért ez a fejlesztési irány a teljes program módosítását igényli. Ez azonban az OOP alapú felépítésnek köszönhetıen nem jelent nagy akadályt. A háromdimenziós képszintézishez hasonlóan egy modern játékban megtalálható audio elemek bonyolult matematikai összefüggéseken alapulnak. Ezek számításában a hangkártya hardveres segítséget képes nyújtani, ehhez például a Microsoft DirectX alkalmazás programozó felület DirectSound komponensének mélyebb szintő ismerete elengedhetetlen. A mesterséges intelligencia igen széles területet ölel fel, melynek a programomban csak egy nagyon kis töredékét alkalmaztam. A fejlesztés célját képezheti a számítógép által irányított egységek, játékosok intelligenciájának fejlesztése. Ide sorolható például a tanulási képesség fokozása, melyet például genetikus algoritmusok, vagy neurális hálózatok

segítségével is elérhetünk. A játékélmény növelése érdekében a hálózati játék lehetıségét is célszerő biztosítani. Ehhez például a TCP/IP protokoll ismerete szükséges 74 11. FELHASZNÁLT IRODALOM [1.] Crawford, C (1982) The Art of Computer Game Design http://www.vancouverwsuedu/fac/peabody/game-book/Coverpagehtml 2006. március [2.] International Hobo (2004) A Guide to Computer Game Genres http://www.ihobocom/gaming/genresshtml 2006. március [3.] wikipediaorg (2006) Real-time strategy http://en.wikipediaorg/wiki/Real time strategy game 2006. március [4.] wikipediaorg (2006) Computer and video game genres http://en.wikipediaorg/wiki/Computer and video game genres 2006. március [5.] Szyperski, C (1997) Component Software: Beyond Object-Oriented Programming [6.] Marossy, K, Dr Charaf H (2003) Komponens alapú programozás COM+ és NET környezetben http://nws.iifhu/ncd2002/docs/ehu/28/indexhtml 2006. április [7.] Charaf H, Kondorosi K, László Z (2003)

Komponens alapú szoftverfejlesztés Szoftvertechnológiai Fórum, BME [8.] Fábián Zoltán (2005) Módszeres programozás avagy programozási módszertan http://fz.szilyhu/download/M%C3%B3dszeres%20programoz%C3%A1spdf 2006. április [9.] Knud van Eeden (2005) OOP: What were the origins of object-oriented programming? http://www.faqtscom/knowledge base/viewphtml/aid/12287 2006. április 75 [10.] wikipediaorg (2006) Polymorfism in object-oriented programming http://en.wikipediaorg/wiki/Polymorphism in object-oriented programming 2006. április [11.] CompOffice-R Kft (2006) Az elsı számítógépes játék http://www.rentithu/corkfthu/jutai elsojatekhtm 2006. április [12.] Csorba Kristóf (2003) Speciális útkeresı algoritmusok és alkalmazásaik modern játékokban. BME, TDK 2003 http://simonyi.schbmehu/files/tdk/anyagok/Csorba Kristof TDK2003pdf 2006. április [13.] Csató Lehel (2005) Mesterséges Intelligencia Babes-Bolyai Tudományegyetem, Kolozsvár

http://www.csubbclujro/~csatol/mestint/pdf slides/mi slidespdf 2006. április [14.] David M Bourg, Glenn Seeman (2004) AI for Game Developers O’Reilly 2006. április [15.] wikipediaorg (2006) Software agent http://en.wikipediaorg/wiki/Software agent#endnote agency 2006. április [16.] David Gordon (2002) Collective Intelligence in Social Insects AI Depot http://ai-depot.com/Essay/SocialInsectshtml 2006. április [17.] David J Burbage (2000) COMPAIGAMES – frequently asked questions http://www.gamedevnet/reference/articles/article200asp#sec0 2006. április [18.] (2006) DirectX programozás http://directxprog.uwhu 2006. április 76 [19.] Microsoft (2005) What is a DLL? http://support.microsoftcom/?kbid=815065 2006. április [20.] Arun N Kumar (2001) A Generic C++ Thread Class http://www.codeprojectcom/threads/genericthreadclassasp 2006. április [21.] wikipediade (2006) Computerspiel http://de.wikipediaorg/wiki/Computerspiel 2006. április 77 12. ÁBRAJEGYZÉK 1. ábra:

izometrikus koordinátarendszer6 2. ábra: játékok grafikája régen (maze) és ma (GTR 2) 7 3. ábra: szoftver ágensek kategóriái (forrás: wikipediaorg) 17 4. ábra: futószalag elvő utasítás-feldolgozás menete 22 5. ábra: szuperskalár utasítás végrehajtás 23 6. ábra: utasításon belüli párhuzamosság 23 7. ábra: egyszerő üldözés és az összeláthatóságot alkalmazó, javított verzió 25 8. ábra: az összeláthatósági eljárással kiegészített „akadály-kikerülı” módszer eredménye .26 9. ábra: az alap hullámkiterjesztés módszere27 10. ábra: a legbiztonságosabb utat keresı hullám-kiterjesztéses algoritmus28 11. ábra: az eredeti, gráfokra vonatkozó A* algoritmus (forrás: wikipedia.org)29 12. ábra: példa az A* algoritmus mőködésére (1).31 13. ábra: jelmagyarázat a 14 ábrához 33 14. ábra: az A* algoritmus mőködése (2).33 15. ábra: a látható csomópontok módszere (point of visibility, PoV)35 16. ábra: HDRR

alkalmazásával készült pillanatkép a Half Life 2 – Lost Coast nevő játékból (forrás: wikipedia.org)39 17. ábra: a játék egy általános állapota45 18. ábra: az A* algoritmus eredményének optimalizálása .48 19. ábra: a játékban alkalmazott izometrikus megjelenítés 51 20. ábra: DLL és szálkezelés integrációja 53 21. ábra: a program felépítése futási szempontból56 22. ábra: függıségi kapcsolatok A kékkel jelölt osztályok külön DLL-ben helyezkednek el. 62 23. ábra: a telepítı üdvözlı képernyıje63 24. ábra: célkönyvtár megadása 64 25. ábra: a telepítés folyamata és befejezése 64 26. ábra: a játék beállítási lehetıségei 65 27 ábra: a játék indítása .65 28. ábra: a játék kezelıfelülete66 78 29. ábra: a pályaszerkesztı felépítése68 30. ábra: az útvonalkeresés tesztelése a PathFinder projektben 73 79 13. ZUSAMMENFASSUNG In meiner Diplomarbeit stelle ich durch die Entwicklung eines auf

Komponenten basierten Echtzeit-Strategiespiels die angewandten Technologien, Algorithmen, sowie die Evolution der Software-Entwicklung vor. Die ersten Computerspiele sind kurzer Zeit nach der Verbreiterung der ersten für jedermann erschwinglichen Computer erschienen. Seitdem verändern sie zunehmend die Freizeitgestaltungsformen aller Altersschichten. Der Siegeszug der Computerspiele wurde durch die Entwicklung der Technologien und der angewendeten Algorithmen ermöglicht. Wurde die Programmierung anfangs meist noch von einen einzelnen Programmierer in relativ kurzer Zeit vollbracht, so arbeiten heutzutage mehrere Dutzend Entwickler in manchen fällen Jahre lang um ein Spiel fertig zu stellen. Der Grund dafür liegt an der Komplexität der modernen Spiele. Sie bestehen aus mehreren unterschiedlichen Komponenten, die ein einzelner Programmierer kaum noch überblicken kann. Deswegen werden diese Komponenten von solchen EntwicklerTeams geplant und programmiert, die auf Ihrem Gebiet

Spezialisten sind Um sich von den oft aus mehreren Millionen Code-Zeilen bestehenden Programmen ein überblick zu verschaffen zu können, ist es unumgänglich die Komponenten die in den meisten Spielen vorzufinden sind, und deren Programmier-Methodik näher zu erörtern. Das Ziel meiner Diplomarbeit ist es diese Themen mit Hilfe der relevantesten Fachlektüren vorzustellen. Diese sind teilweise wegen des rasanten Fortschritts sowohl in der SpielEntwicklung als auch der unterschiedlichen Technologien nur im internet auffindbar Verständlicher Weise muss man die inzwischen schon zu Paradigmen gewordenen Programmier-Methoden erwähnen, mit dessen Hilfe man sowohl die allgemeine als auch die Spiel-spezifische Programmierung effizienter gestalten kann. Die in dieser Diplomarbeit vorgestellten Algorithmen und Methoden decken nur einen kleinen Teil der Bausteine ab, die in der Spiel-Industrie angewendet werden. Diese decken meist riesige Bereiche der Wissenschaft ab. Als Beispiel kann man die

Künstliche Intelligenz(KI) erwähnen, die ein wichtiger Teil von Computerspielen ist. Unter dem begriff verbirgt sich ein enorm Grosses bereich. In vielen fällen ist es aber doch ausreichend, wenn man nur eine stark vereinfachte Version der Original-Methodik anwendet. 80 14. ABSTRACT In this paper I am going to present by way of developing a component based realtime strategy game the applied technologies, algorithms, and the evolution of software engineering itself. The first computer games appeared soon after the spreading of general purpose, affordable computers, and began their persistent conquest among every age-group. Thanks to the fast advance of technology and applied algorithms their popularity has not only been broken, but it is increasing. While many of the earliest computer games ran on university mainframes in the United States and were developed by individual users who programmed them in their idle time, today there is a continually growing industry concerned with

the developing of computer games. Most of the modern games are nearly impossible to understand for just one programmer due to a games huge complexity. Specialized teams are developing the building parts of the game called components. For the sake of comprehending these programs often containing several millions of source code-lines it is expedient to get acquainted with the components of a game, and the methodology of software development. With this end in view I composed this thesis using the most relevant references which a part of can only be found on the internet. Due to the dizzying advance of game developing and the fast growth of the computer itself, the latest informations are presented only in electronical form. Of course, it is absolutely necessary to mention those one developing techniques that became a programming paradigm in the last decades. By using those, it is easier to write more efficient, more fail-safe code. The techniques and algorithms described in this paper are

just a small piece of the components modern games are based of. These components may cover a whole research branch. The artificial intelligence is a perfect example, due to its several sub-branches like path finding or neural networks. However, in many cases it is sufficient the use of the strong simplified version of the original solution. 81