eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra po£íta£·
Bakalá°ská práce
Jádro strategické 2D hry
Jan Baier
Vedoucí práce:
Ing. Ji°í Smítka
Studijní program: Elektrotechnika a informatika, strukturovaný, Bakalá°ský
Obor: Výpo£etní technika
3. £ervna 2009
iv
v
Pod¥kování Tímto bych rád pod¥koval Ing. Ji°ímu Smítkovi za vedení mé práce a také v²em ostatním, kte°í m¥ v mé práci podporovali.
vi
vii
Prohlá²ení Prohla²uji, ºe jsem práci vypracoval samostatn¥ a pouºil jsem pouze podklady uvedené v p°iloºeném seznamu. Nemám závaºný d·vod proti uºití tohoto ²kolního díla ve smyslu 60 Zákona £. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zm¥n¥ n¥kterých zákon· (autorský zákon).
V eské Líp¥ dne 3. 6. 2009
.............................................................
viii
Abstract This bachelor work deals with design and implementation of a kernel of 2D strategic game. It analyzes possible problems with routing of great number of units on big map and tries to suggest a solution of this problems. Several common used path nding algorithms and theirs strong points and weaknesses are described in this work. One part of this work is to show working implementation using one speci c searching algorithm.
Abstrakt Tato bakalá°ská práce se zabývá návrhem a implementací jádra pro 2D strategickou hru. Rozebírá moºné problémy spojené se sm¥rováním velkého mnoºství jednotek na velké map¥ a snaºí se navrhnout °e²ení t¥chto problém·. V práci jsou popsány n¥které £asto pouºívané algoritmy pro vyhledávání cest a jejich kladné a záporné stránky. Sou£ástí práce je ukázat také konkrétní funk£ní implementaci za pouºití jednoho zvoleného vyhledávacího algoritmu.
ix
x
Obsah 1 Úvod 1.1
1.2
1
Strategické hry
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
Budovatelské strategie . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.2
Vále£né strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.3
Tahové strategie
2
1.1.4
Strategie v reálném £ase . . . . . . . . . . . . . . . . . . . . . . . .
Herní mapa
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Popis problému, speci kace cíle
3 3
5
2.1
Poºadavky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2
Vzory pro projekt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1
FreeCiv
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2
Warcraft 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.3
Red Alert 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Shrnutí
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Analýza a návrh °e²ení
7
9
3.1
Herní mapa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.2
Jednotka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.3
Sm¥rování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4
3.5
9
3.3.1
Vyhledání cesty . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3.2
Úhybné manévry . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
Vyhledávací algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.4.1
Náhodné odrazy
10
3.4.2
Dijkstr·v algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.4.3
Best- rst algoritmus
12
3.4.4
A* algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.4.5
Hierarchický anotovaný A* algoritmus
. . . . . . . . . . . . . . . .
14
e²ení kolizí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Realizace
17
4.1
Pouºité technologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4.2
Základní rozd¥lení
17
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1
MainWindow
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4.2.2
Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4.2.3
Tile
18
4.2.4
Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.2.5
PathThread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
xii
OBSAH
4.3
4.2.6
Pomocné t°ídy
4.2.7
Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.2.8
Viewer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
D·leºité metody
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.3.1
Nová ºádost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.3.2
Spu²t¥ní vlákna . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.3.3
A* algoritmus hledání
. . . . . . . . . . . . . . . . . . . . . . . . .
21
4.4
Shrnutí funkce modulu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.5
Uºivatelské rozhraní
24
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Testování 5.1
27
M¥°ení rychlosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5.1.1
Princip testu rychlosti
. . . . . . . . . . . . . . . . . . . . . . . . .
27
5.1.2
Testovací sestavy . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5.1.3
Výsledky testování rychlosti . . . . . . . . . . . . . . . . . . . . . .
28
5.2
Vliv velikosti mapy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.3
Srovnání . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
6 Záv¥r
31
Literatura
33
A Seznam pouºitých zkratek
35
B Instala£ní a uºivatelská p°íru£ka
37
B.1
Kompilace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
B.2
Parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
B.3
Ovládání . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
C Obsah p°iloºeného CD
39
Seznam obrázk· 1.1
Obrázek z budovatelské strategie Caesar 3 . . . . . . . . . . . . . . . . . .
1.2
Obrázek z vále£né strategie Sins of a Solar Empire
. . . . . . . . . . . . .
2
1.3
Obrázek z tahové strategie Battle for Wesnoth . . . . . . . . . . . . . . . .
2
1.4
Obrázek z realtimové strategie Age of Empires 3
. . . . . . . . . . . . . .
3
2.1
Obrázek ze strategie FreeCiv
. . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2
Obrázek ze strategie Warcraft 3 . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Obrázek ze strategie Red Alert 3
7
3.1
Pseudokód algoritmu náhodných odraz·
. . . . . . . . . . . . . . . . . . .
10
3.2
Pseudokód Dijkstrova algoritmu . . . . . . . . . . . . . . . . . . . . . . . .
11
3.3
Pseudokód best- rst algoritmu
. . . . . . . . . . . . . . . . . . . . . . . .
12
3.4
Pseudokód A* algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.1
Rozvrºení t°íd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.2
Ukázka z GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
5.1
Graf závislosti pot°ebného £asu na velikosti mapy . . . . . . . . . . . . . .
29
. . . . . . . . . . . . . . . . . . . . . . .
xiii
1
xiv
SEZNAM OBRÁZK
Seznam tabulek 5.1
Výsledky testování rychlosti . . . . . . . . . . . . . . . . . . . . . . . . . .
xv
28
xvi
SEZNAM TABULEK
Kapitola 1
Úvod 1.1
Strategické hry
Strategické hry jsou takové hry, které pro dosaºení vít¥zství poºadují d·kladné promý²lení akcí a plánování.[10] Ve v¥t²in¥ strategických her se na celý herní sv¥t díváte z pta£í perspektivy a je vám dána moºnost ovládat kaºdou herní jednotku. Svým zp·sobem si tak vlastn¥ hrajete na boha. Oblast strategický her se dá rozd¥lit na r·zné podºánry. Rozd¥lovat se dá podle herních cíl·, míry reality, £asu a místa, ve kterém se hra odehrává, a v neposlední °ad¥ také podle plynutí herního £asu.[8]
1.1.1 Budovatelské strategie V tomto druhu her máte pod kontrolou ur£ité území a va²im úkolem je stav¥t budovy a starat se o správný chod. V¥t²inou zde bývá kladen velký d·raz na ekonomiku a pon¥kud mén¥ se zde setkáte s taktickým vál£ením.
Obrázek 1.1: Obrázek z budovatelské strategie Caesar 3
1
2
KAPITOLA 1.
ÚVOD
1.1.2 Vále£né strategie Tento druh vyniká d·razem na taktiku boje. Ekonomická stránka hry bývá redukována na t¥ºbu n¥kolika surovin, n¥kdy je dokonce eliminována úpln¥. Ve vále£ných strategiích hrají roli zku²enosti a schopnosti hrá£e koordinovat pohyby jednotek a vyuºívat jejich silných stránek.
Obrázek 1.2: Obrázek z vále£né strategie Sins of a Solar Empire
1.1.3 Tahové strategie V tahových strategiích (TBS) nedochází ke klasickému plynutí £asu tak, jak ho známe z reálného sv¥ta. as je zde kvantován do herních tah·. Kaºdá jednotka m·ºe za jeden tah vykonat jen ur£itý po£et akcí a na konci tahu se provede vyhodnocení v²ech událostí, které b¥hem tahu nastaly. Díky moºnosti mít neomezený £as na promy²lení postupu jsou v tahových strategiích velice £asto náro£né a detailn¥ propracované ekonomické, diplomatické a technologické modely. Hrᣠtak ne°e²í pouhý boj, ale zabývá se i spoustou vedlej²ích problém·.
Obrázek 1.3: Obrázek z tahové strategie Battle for Wesnoth
1.2.
HERNÍ MAPA
3
1.1.4 Strategie v reálném £ase Pro tyto strategie se téº pouºívá termín realtimové strategie (RTS). as zde plyne normálním zp·sobem a hrᣠtak musí dávat pozor na celou herní oblast a pozorn¥ sledovat d¥ní. V t¥chto strategiích je kladen d·raz na d·kladné koordinování pohyb· jednotlivých jednotek, kde má ov²em po£íta£em °ízený hrᣠnotnou výhodu, jelikoº na rozdíl od £lov¥ka jsou po£íta£ové algoritmy schopny sledovat a reagovat na v²echny podn¥ty najednou. U realtimových strategií bývá £asto mén¥ realisticky provedena ekonomická £ást a bývá up°ednost¬ována ak£ní stránka.
Obrázek 1.4: Obrázek z realtimové strategie Age of Empires 3
1.2
Herní mapa
Mapa je vizuální reprezentace oblasti symbolické vyjád°ení zd·raz¬ující vztahy mezi jejími elementy.[19] Jako mapu lze ve strategických hrách s úsp¥chem vyuºít sou°adnicových sítí. Nejjednodu²²í sítí, a také nej£ast¥ji vyuºívanou, je sí´ £tvercová.[6] Vyuºívá klasických kartézských sou°adnic a má ortogonální osy. Sou°adnicový systém se v závislosti na úhlu pohledu nem¥ní. Druhá nejpouºívan¥j²í je oby£ejná hexagonová sí´. Jak jiº název napovídá, jedná se o sí´, jejíº základním stavebním kamenem je pravidelný ²estiúhelník.[3] Tato sí´ se vyuºívá nej£ast¥ji v tahových strategiích, kde je kladen velký d·raz na správné po£ítání vzdáleností, jelikoº na rozdíl od klasické £tvercové sít¥ má mén¥ nediagonálních soused· a nejsou tolik zkreslené vzdálenosti mezi jednotlivými poli.
4
KAPITOLA 1.
ÚVOD
Kapitola 2
Popis problému, speci kace cíle 2.1
Poºadavky
Cílem je vytvo°it modul pro server jednoduché 2D strategické hry, který by °e²il sm¥rování jednotek v terénu. Je pot°eba, aby modul byl dostate£n¥ rychlý a mohl tak sm¥rovat velké mnoºství jednotek i na velké a náro£né map¥ v reálném £ase. Musíme vy°e²it problém s výpo£tem cesty z výchozího do cílového bodu tak, aby výsledná cesta nebyla p°íli² dlouhá a zárove¬ musíme jednotku po této trase bezpe£n¥ odnavigovat.
2.2
Vzory pro projekt
2.2.1 FreeCiv Jedním ze vzor· pro tento problém je nap°íklad projekt FreeCiv[13].
Obrázek 2.1: Obrázek ze strategie FreeCiv
5
6
KAPITOLA 2.
POPIS PROBLÉMU, SPECIFIKACE CÍLE
Jedná se o voln¥ dostupnou verzi tahové strategie s otev°eným kódem na motivy staré hry Civilization. Hra se odehrává v náhodn¥ vygenerovaném sv¥t¥, pro jehoº reprezentaci se pouºívá £tvercová mapa. Kaºdé pole obsahuje n¥jaký druh terénu. Kaºdá jednotka má svou rychlost, která se po£ítá v polích za tah. Kaºdý druh jednotek má navíc na n¥kterých terénech tuto rychlost zm¥n¥nou (nap°íklad pozemní jednotky se v lese pohybují pouze polovi£ní rychlostí) a na n¥které terény se jednotka nem·ºe dostat v·bec (nap°íklad lod¥ nemohou na pevninu). Ná² modul by m¥l podobn¥ jako tato hra vyhledávat cesty pro jednotky v terénu, ale na rozdíl od ní by v²e m¥lo probíhat v reálném £ase.
2.2.2 Warcraft 3 Druhý vzor je realtimová strategie z fantasy prost°edí jménem Warcraft 3.[18]
Obrázek 2.2: Obrázek ze strategie Warcraft 3
Obsahuje mimo jiné i propracovaný editor map, ve kterém se dá docílit pomocí r·zných skript· nové funk£nosti. Jeden takový p°íklad je realizace herního módu Tower Defense[17]. V tomto módu je dob°e vid¥t práce herního enginu p°i sm¥rování jednotek a obcházení hrá£em umíst¥ných budov. Hra je bohuºel komer£ní, tudíº nemohu nahlédnout na zp·sob implementace. Ná² modul by m¥l sm¥rovat podobn¥ jako v této h°e, jen na v¥t²ích mapách a s v¥t²ím po£tem jednotek.
2.2.3 Red Alert 3 Posledním vzorem je nám komer£ní realtimová strategie Red Alert 3.[16] Tato hra je z prost°edí studené války a hrᣠzde má za úkol vybudovat vojenskou základnu a dostatek bojových jednotek ke zni£ení nep°ítele. Hra je op¥t komer£ní a moºnosti studovat zp·sob implementace jsou tak velice omezené. V této strategii je pro sm¥rování jednotek pouºit hierarchický anotovaný A* algoritmus, více o n¥m v 3.4.5.
2.3.
7
SHRNUTÍ
Obrázek 2.3: Obrázek ze strategie Red Alert 3
2.3
Shrnutí
Spolu s p°ihlédnutím k jiº existujícím strategickým hrám lze zadání rozloºit na n¥kolik bod·.
•
Modul bude sm¥rovat jednotku z místa A do místa B
•
Na jednom herním poli nem·ºe být sou£asn¥ více jednotek
•
Modul musí °e²it moºné kolize jednotek
•
Modul musí zvládat sm¥rování velkého po£tu jednotek
•
Modul musí být schopen pracovat s velkou mapou
•
Modul vyhledá cesty v reálném £ase
•
Mapa obsahuje více druh· terénu
•
GUI není sou£ástí práce
•
Sí´ový modul není sou£ástí práce
8
KAPITOLA 2.
POPIS PROBLÉMU, SPECIFIKACE CÍLE
Kapitola 3
Analýza a návrh °e²ení 3.1
Herní mapa
Pro reprezentaci mapy je vhodné zvolit klasickou £tvercovou sí´. Výhodou je zde její jednoduchá implementace a p°ehlednost. Kaºdý £tverec p°edstavuje jedno pole mapy. Kaºdé pole má informaci o svém umíst¥ní v map¥ a o své pr·chodnosti terénu. Kaºdé herní pole, krom¥ okrajových, bude mít pouze £ty°i sousedy. Diagonální pohyby jsou zakázané. Mapa musí um¥t poskytnout informace o poli na ur£itých sou°adnicích a také ur£it sousedy pro libovolné pole.
3.2
Jednotka
Po celé map¥ se pohybují jednotky, kaºdá jednotka obsazuje práv¥ jeden £tverec na herní map¥. Tato pozice je jedine£ná, tzn. na stejném poli nemohou být v jednu chvíli dv¥ jednotky. Kaºdá jednotka, kterou hrᣠposlal na n¥jaké místo, by m¥la znát cíl své cesty a také trasu, po které se k cíli dostane, bude tedy obsahovat odkaz na n¥jakou posloupnost sou°adnic, které ji dovedou k cíli. Navrhujeme server pro realtimovou strategii, takºe kaºdá jednotka, která je na cest¥, se v pravidelných £asových intervalech posune o jedno pole. B¥hem pohybu nesmí dojít ke kolizím, stále platí, ºe v jednom okamºiku smí být na jednom hracím poli jen jedna jednotka. Atributy jednotky nesouvisející s navigováním jsou pro nás nepodstatné a budeme je proto zanedbávat, lze je p°idat kdykoliv v pozd¥j²ích vylep²eních.
3.3
Sm¥rování
Celé sm¥rování jednotek lze rozd¥lit na dv¥ fáze. Pro ob¥ je d·leºitá správná volba vyhledávacího alogirtmu. Poºadavky na správný algoritmus jsou rychlost, malá pam¥´ová náro£nost a pokud moºno minimálnost nalezených cest. 9
10
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
3.3.1 Vyhledání cesty V této fázi se server snaºí vyhledat cestu z místa A do místa B. Nebere ohled na ostatní jednotky, kouká jen na terén mapy a snaºí se najít nejoptimáln¥j²í cestu. Pokud je úsp¥²n¥ nalezena cesta, je jednotce p°edána posloupnost sou°adnic. Jejich následováním se jednotka dostane na poºadované místo. Je d·leºité, aby toto vyhledávání bylo velice rychlé, jelikoº probíhá pro kaºdou jednotku, které je zadán pohyb.
3.3.2 Úhybné manévry Jednotky mající n¥jakou cestu jsou v pravidelných intervalech p°esouvány. Zárove¬ se kontroluje blízkost okolních jednotek. K úhybnému manévru dojde pouze v p°ípad¥, ºe bude zji²t¥na moºná kolize dvou jednotek na jednom herním poli. Kolize se vy°e²í spu²t¥ním nového vyhledávání na omezeném úseky mapy, které jiº bude dávat pozor na rozmíst¥ní jednotek. Nov¥ nalezená cesta nahradí starý kolizní úsek v p·vodní cest¥. Vzhledem k situaci, ºe kaºdá jednotka se m·ºe za£ít v libovolném okamºiku pohybovat, nedají se kolize p°edpovídat dlouho p°edem. Toto °e²ení nabízí reakci na poslední moºnou chvíli, tedy p°esn¥ p°ed provedením kroku na obsazené pole, a zat¥ºuje tak server dal²ím hledáním jen pokud je to opravdu nezbytné. Vyhledává se jen krátká cesta, takºe by vyhledávání nem¥lo trvat p°íli² dlouhou dobu.
3.4
Vyhledávací algoritmus
3.4.1 Náhodné odrazy Algoritmus náhodných odraz· (Random Bounce) je velice jednoduchý na pochopení i implementaci. Algoritmus hledá od po£áte£ního bodu sm¥rem k cíli a vºdy, kdyº narazí na p°ekáºku, provede krok pry£.[2]
while(nejsem_v_cili) { otocit_se_smerem_k_cili(); if (stojim_pred_prekazkou) { krok_nahodnym_smerem(); } else { krok(); } } Obrázek 3.1: Pseudokód algoritmu náhodných odraz·
Výhody algoritmu •
Jednoduchá implementace
3.4.
VYHLEDÁVACÍ ALGORITMUS
11
Nevýhody algoritmu •
Nebere ohled na cenu uzlu
•
M·ºe být £asov¥ náro£né
•
Není zaru£eno, ºe se dosp¥je k cíli
•
Není zaru£ena nejkrat²í cesta
Vzhledem k nevýhodám je tento algoritmus pro vyhledávací modul nepouºitelný.
3.4.2 Dijkstr·v algoritmus Dijkstr·v algoritmus slouºí k vyhledání nejkrat²í cesty v grafu s ohodnocenými hranami (ºádná hrana nesmí být záporn¥ ohodnocena).[7] Na po£átku se v²echny uzly, krom¥ startovního nastaví na nedostupné a uloºí se do fronty otev°ených uzl·. Následn¥ probíhá iterace, ve které se z fronty otev°ených uzl· vybere takový, který má nejmen²í hodnotu, uzav°e se a v²em soused·m se nastaví spo£tená hodnota nejkrat²í cesty. Algoritmus pracuje tak dlouho, dokud nejsou v²echny uzly uzav°eny. Pro p°ípad vyhledávání cesty se tento algoritmus ukon£í p°ed£asn¥ ve chvíli, kdy se z fronty otev°ených uzl· vybere cílový uzel. Výkonnost Dijkstrova algoritmu lze ovlivnit zp·sobem implementace prioritní fronty otev°ených uzl·.
fronta.vloz(startovni_uzel); while(!fronta.je_prazdna()) { uzel = fronta.vyber_min(); if (uzel == cilovy_uzel) return; foreach(uzel.sousedi as soused) { soused.vzdalenost = minimum(soused.vzdalenost, uzel.vzdalenost + vzdalenost); fronta.vloz(soused); } } Obrázek 3.2: Pseudokód Dijkstrova algoritmu
Výhody algoritmu •
Zohled¬uje cenu uzlu
•
Vºdy vyhledá nejkrat²í cestu, pokud existuje
12
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
Nevýhody algoritmu •
M·ºe být £asov¥ náro£né
Tento algoritmus by byl z hlediska kvality vyhledávání pro modul dobrou volbou, nicmén¥ vzhledem k poºadavku na rychlost nebudeme algoritmus v této podob¥ pouºívat.
3.4.3 Best- rst algoritmus Tento algoritmus pat°í mezi takzvané informované algoritmy. Funguje tak, ºe ze seznamu otev°ených uzl· vybírá ten nejlep²í podle p°edem daného pravidla. Toto pravidlo je realizováno heuristickou funkcí, která ur£uje ohodnocení uzlu v n¥jaké ²ir²í závislosti.[8] Pokud by se heuristická funkce de novala jako sou£et ohodnocení hran od po£áte£ního uzlu k aktuálnímu, choval by se tento algoritmus stejn¥ jako Dijkstr·v. ast¥j²í v²ak je nastavení heuristické funkce jako nap°íklad po£et hran mezi aktuálním a cílovým uzlem, algoritmus se pak snaºí najít cestu, která má nejmen²í po£et hran.
fronta.vloz(startovni_uzel); while(!fronta.je_prazdna()) { uzel = fronta.vyber_min(); if (uzel == cilovy_uzel) return; foreach(uzel.sousedi as soused) { soused.cena = ohodnod_uzel(); fronta.vloz(soused); } } Obrázek 3.3: Pseudokód best- rst algoritmu
Výhody algoritmu •
Zohled¬uje cenu uzlu
•
Rychlé vyhledání cesty
•
Dobrá modi kovatelnost pomocí heuristické funkce
Nevýhody algoritmu •
Není zaru£ena nejkrat²í cesta
Algoritmus spl¬uje nároky na rychlost, nicmén¥ vzhledem k pot°eb¥ vyhledávat co moºná nejkrat²í cesty je lep²í tento algoritmus nevyuºít.
3.4.
VYHLEDÁVACÍ ALGORITMUS
13
3.4.4 A* algoritmus Kombinuje Dijkstr·v a Best- rst algoritmus. Ohodnocení uzlu je rovno sou£tu ohodnocení hran mezi startovním a aktuálním uzlem plus hodnota heuristické funkce pro aktuální uzel.[8] P°i nízkém koe cientu heuristické funkce, kdy se tato uplat¬uje pouze minimáln¥, se chování A* algoritmu blíºí Dijkstrovu algoritmu. V opa£ném p°ípad¥, p°i vysokém koe cientu heuristické funkce, je chování algoritmu více podobné Best- rst vyhledávání. Vhodnou volbou heuristické funkce a jejího koe cientu je moºné dosáhnout velice dobrých výsledk·.[9]
fronta.vloz(startovni_uzel); while(!fronta.je_prazdna()) { uzel = fronta.vyber_min(); if (uzel == cilovy_uzel()) return; foreach(uzel.sousedi as soused) { if (je_novy_uzel(soused)) { soused.cena = uzel.cena + vzdalenost + k * spocti_cenu(); soused.rodic = uzel; fronta.vloz(soused); } else { nova_cena = uzel.cena + vzdalenost + k * spocti_cenu(); if (nova_cena < soused.cena) { soused.cena = nova_cena; soused.rodic = uzel; fronta.vloz(soused); } } } } Obrázek 3.4: Pseudokód A* algoritmu
Výhody algoritmu •
Zohled¬uje cenu uzlu
•
Lze upravit pro konkrétní pot°ebu pomocí heuristické funkce
•
Umí vyhledat nejkrat²í cestu
•
Umí rychle vyhledávat
Nevýhody algoritmu •
Náro£n¥j²í implementace
14
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
•
V¥t²í pam¥´ové nároky
•
Nemusí najít nejkrat²í cestu
•
P°i ²patných podmínkách m·ºe být vyhledávání pomalé
Po d·kladném zváºení vý²e uvedených vlastností vychází jako nejlep²í moºnost pouºít pro oba druhy sm¥rování A* algoritmus. Jako heuristickou funkci zvolíme, s p°ihlédnutím k pouºití £tvercové mapy, Manhattanskou vzdálenost. Správným nastavením váhy heuristiky se dají docílit co moºná nejminimáln¥j²í cesty s velice krátkou dobou vyhledávání. V implementaci A* algoritmu je mnoho prostoru pro dal²í experimenty a optimalizace. Do budoucna je moºné experimentovat i se samotnou heuristickou funkcí a jejím vylep²ením je²t¥ zrychlit A* algoritmus.[9]
3.4.5 Hierarchický anotovaný A* algoritmus Jedná se, jak uº název napovídá, o klasický A* algoritmus vylep²ený o dv¥ v¥ci.[5] Za prvé pouºívá anotace. To znamená, ºe ke kaºdému poli si pamatuje nejen jeho cenu, ale i dal²í údaje. V p°ípad¥ strategie Red Alert 3 (2.2.3) to je nap°íklad maximální moºná velikost jednotky, která je schopná daným polem projít. P°i vyhledávání je pak navíc pot°eba p°edávat parametr ur£ující velikost jednotky a v procházení grafem se otevírají jen ty uzly, které jsou vhodné pro danou velikost jednotky. Druhým vylep²ením je pak pouºívání hierarchického hledání. Nevyhledává se po celé map¥. Mapa je rozd¥lena na men²í úseky, ve kterých jsou p°edvyhledány nejlep²í pr·chody mezi sousedními úseky. P°i hledání výsledné cesty se pak vyhledává cesta mezi t¥mito pr·chody.
Výhody algoritmu •
Zohled¬uje cenu uzlu
•
Umí zohlednit více faktor· (nap°íklad velikost jednotky)
•
Lze upravit pro konkrétní pot°ebu pomocí heuristické funkce
•
Umí vyhledat nejkrat²í cestu
•
Umí rychle vyhledávat
•
Rychlej²í neº A* algoritmus
Nevýhody algoritmu •
Náro£ná implementace
•
V¥t²í pam¥´ové nároky
•
Nemusí najít nejkrat²í cestu
•
P°i ²patných podmínkách m·ºe být vyhledávání pomalé
Tento algoritmus je pro ná² sm¥rovací modul p°íli² sloºitý, neº abychom se ho snaºili implementovat. V jednom z budoucích vylep²eních je v²ak moºné z oby£ejného A* algoritmu p°ejít na tento a zrychlit tak vyhledávání.
3.5.
3.5
EENÍ KOLIZÍ
15
e²ení kolizí
Vzhledem k podmínce, ºe na jednom herním poli nesmí být více jak jedna jednotka, je pot°eba p°i sm¥rování jednotky hlídat, aby nevkro£ila na jiº obsazené pole. Kolize budeme detekovat aº v poslední moºné chvíli, tedy t¥sn¥ p°ed tím, neº jednotka provede krok vp°ed. V ten okamºik zkontrolujeme obsazenost pole, na které chce jednotka vstoupit. Pokud je pole jiº obsazené, je pot°eba tuto situaci vy°e²it. Krok se odvolá a úsek cesty p°es obsazené pole se zru²í. Zárove¬ dojde k výpo£tu cesty mezi aktuálním polem a nejbliº²ím dal²ím volným polem p·vodní cesty. Touto nov¥ nalezenou cestou se pak nahradí vymazaný úsek. Jedná se o vyhledání cesty p°es n¥kolik málo polí a tudíº nebude v porovnání s naplánováním celé cesty nikterak £asov¥ ani pam¥´ov¥ náro£né. Toto °e²ení má v²ak také stinnou stránku a tou je hloupost takto sm¥rované jednotky. Jednotka se nedívá moc daleko dop°edu a o p°ekáºce v podob¥ cizí jednotky se dozví teprve ve chvíli, kdy do ní bude tém¥° naráºet. Tento problém by se dal napravit zv¥t²ením pole, ve kterém jednotka testuje p°ítomnost jiné jednotky, coº by ale vedlo k neºádoucímu zpomalení celého sm¥rování. Proto tento problém nebudeme °e²it, stejn¥ jako ho zanedbávají ve h°e Warcraft 3 (viz 2.2.2).
16
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
Kapitola 4
Realizace 4.1
Pouºité technologie
Pro realizaci vyuºijeme jazyka C/C++, který se jako zástupce kompilovaných jazyk· hodí na tvorbu výpo£etního modulu více neº jazyky interpretované. Umoº¬uje nám lep²í správu pam¥ti a kompilátor optimalizuje kód pro cílový procesor[4] Pro leh£í a rychlej²í vývoj a zaji²t¥ní multiplatformnosti pouºijeme framework Qt, který zjednodu²í práci s vlákny a zp°ehlední p°edávání dat mezi objekty.[12]
4.2
Základní rozd¥lení
Celý vyhledávací modul m·ºeme rozd¥lit na n¥kolik díl£ích celk· podle základních t°íd, jak je vid¥t na diagramu 4.1. Pro p°ehlednost je diagram zjednodu²en a také neobsahuje t°ídu realizující datový typ sou°adnice.
4.2.1 MainWindow T°ída
MainWindow
je hlavní t°ídou projektu. Zaji²´uje spu²t¥ní aplikace, nahrání
mapy a komunika£ního modulu. Má na starosti zpracování p°íchozích poºadavk· na nalezení nové cesty. Zárove¬ se také stará o periodické obnovování pozice jednotek, °e²í jejich p°ípadné kolize a periodicky informuje komunika£ní modul o aktualizaci pozicí. Toto je realizováno uloºením poºadavku do statického pole poºadavk· ve t°íd¥ Threads a opakovaným emitováním signálu.
4.2.2 Map Map reprezentuje celou herní mapu a jednotky na map¥. Obsahuje dv¥ podt°ídy Tile a Unit, které reprezentují jedno herní pole a jednu jednotku. Herní mapa je ve t°íd¥ Map realizována jako dvourozm¥rné pole objekt· Tile. JedT°ída
notky jsou realizovány spojovým seznamem a navíc, pro urychlení vyhledávání jednotky podle polohy v map¥, je ke kaºdému hernímu poli p°idán ukazatel na aktuální jednotku na tomto poli stojící. 17
18
KAPITOLA 4.
REALIZACE
Obrázek 4.1: Rozvrºení t°íd
4.2.3 Tile Tile
je jednoduchá struktura udrºující základní informace o herním poli. Mezi tyto
informace pat°í cena pole, nebo téº náro£nost terénu, sou°adnice v map¥ a ukazatelé na sousední pole. Jak jiº bylo °e£eno d°íve, je zde také ukazatel na jednotku, která na tomto poli práv¥ stojí. Tento p°ístup je moºné pouºít díky p°edpokladu, ºe na jednom poli nesmí ve stejné chvíli stát více jak jedna jednotka. Tato optimalizace zna£n¥ urychluje vyhledávání jednotek dle sou°adnic. Místo vyhledávání jednotky ve vektoru s lineární sloºitostí m·ºeme jednotku vyhledat v konstantním £ase.
4.2.4 Unit T°ída
Unit, jak jiº název napovídá, shromaº¤uje informace o jednotce. Pro vyhledávací
modul jsou relevantní jen n¥která data, pro plnohodnotný herní server bychom tuto t°ídu museli zna£n¥ roz²í°it. Prozatím uchováváme jen identi ka£ní £íslo jednotky, její sou°adnici v map¥ a aktuální cestu, pokud jednotka n¥kam sm¥°uje. Tato t°ída také poskytuje metodu, pomocí které m·ºeme nastavit novou aktuální cestu. V této metod¥ se musí zajistit thread-safe chování, jelikoº ke kaºdé jednotce m·ºe p°istupovat více vláken. Je tedy zapot°ebí metodu synchronizovat pouºít mutex[11]. Druhou d·leºitou metodou v této t°íd¥ je metoda, která provede pohyb jednotky. Tato metoda se na pokyn hlavního okna periodicky vykonává.
4.2.
19
ZÁKLADNÍ ROZD
LENÍ
4.2.5 PathThread Tato t°ída obsahuje výpo£etn¥ nejnáro£n¥j²í algoritmy z celého serveru. Kaºdý objekt této t°ídy je samostatným vláknem a umoº¬uje ostatním objekt·m vypo£ítat cestu z bodu A do bodu B. Vlákna vybírají poºadavky z t°ídní fronty poºadavk· a postupn¥ je zpracovávají. Op¥t je zde pot°eba pouºít synchroniza£ního prvku mutexu.[11] O dokon£ení výpo£tu informuje objekt t°ídy
MainWindow.
PathThread
za pomoci signálu[12] nad°azený objekt t°ídy
4.2.6 Pomocné t°ídy Pro implementaci modulu je pot°eba n¥kolika dopl¬kových t°íd.
Coord T°ída realizuje datový typ sou°adnice v map¥. Zjednodu²uje práci s pozicí v map¥ díky n¥kolika p°etíºeným operátor·m.
Container T°ída
Container
p°edstavuje datové úloºi²t¥ uzav°ených uzl·. Je implementována za
pomocí mapy z frameworku Qt[12] a umoº¬uje p°idávání (push), vybírání (pop) a vyhledávání ( nd) prvk·. V²echny operace mají logaritmickou sloºitost
PriorityQueue Prioritní fronta otev°ených uzl·, která je implementována vektorem z frameworku Qt[12]. Umoº¬uje vybírat uzel s nejmen²í cenou. To implementujeme pomocí vyhledávání minima p°ed výb¥rem. Takto implementovaná fronta má konstantní sloºitost nej£ast¥ji provád¥né operace vkládání a lineární sloºitost operace výb¥ru nejmen²í poloºky.
4.2.7 Communication Tato t°ída jiº £áste£n¥ pat°í do sí´ového modulu, který se stará o p°edávání poºadavk· od klienta k výpo£etnímu modulu, který zajistí jejich zpracování. Druhým úkolem modulu je zpracovávání aktualizací a jejich posílání zp¥t klient·m, coº uº ov²em není obsahem této práce.
4.2.8 Viewer Tato t°ída je pouze do£asná a pro ú£ely testování. Stará se o zobrazení aktuálního stavu mapy a jednotek a umoº¬uje tak sledovat, co se v modulu d¥je.
20
4.3
KAPITOLA 4.
REALIZACE
D·leºité metody
4.3.1 Nová ºádost Nové ºádosti obstarává metoda
ndPath
ve t°íd¥
PathThread.
Obsluha spo£ívá ve
vytvo°ení dvojice jednotka a cílové sou°adnice a její uloºení do fronty poºadavk·. Následn¥ se zkontroluje, zda jiº bylo spu²t¥no výpo£etní vlákno, pokud ne, spustí se, jinak se pouze uv¥domí o novém poºadavku a v p°ípad¥ pot°eby se probudí.
void PathThread::findPath(Map::Unit* u, Coord dest) { req_pair rp; rp.unit = u; rp.destination = dest; mutex.lock(); request.enqueue(rp); mutex.unlock(); if (!isRunning()) { start(); } else { condition.wakeOne(); } }
4.3.2 Spu²t¥ní vlákna Po spu²t¥ní nebo probuzení vlákna dojde ke kontrole fronty poºadavk·. Pokud se zde nachází nezpracovaný poºadavek, vybere se z fronty a provede se spu²t¥ní výpo£tu, dle poºadavku. Pokud je fronta prázdná, vlákno se uspí.
void PathThread::run(void) { while(!abort) { while(!abort) { mutex.lock(); if (request.isEmpty()) { mutex.unlock(); break; } req_pair rp = request.dequeue(); mutex.unlock(); Coord* path = NULL; int path_lenght = 0; search(rp.unit->getCoord(), rp.destination, &path, path_lenght, true); if (abort) return; rp.unit->navigate(path, path_lenght); emit pathComputed(); }
4.3.
}
DLEITÉ METODY
}
21
emit queueEmpty(); mutex.lock(); condition.wait(&mutex); mutex.unlock();
4.3.3 A* algoritmus hledání Jedná se o nejd·leºit¥j²í metodu celého modulu a je také tou nejsloºit¥j²í. Pro lep²í pochopení ji rozebereme po £ástech. Na po£átku se provedou nutné inicializace a nastaví se hodnoty po£áte£nímu a cílovému uzlu a po£áte£ní se vloºí do fronty.
bool PathThread::search(const Coord start, const Coord goal, Coord** path, int& lenght, bool ignoreUnits) { Node *start_node, *goal_node; try { start_node = new Node(map[start]); goal_node = new Node(map[goal]); } catch(std::bad_alloc&) { std::cerr << "Out of memory" << std::endl; throw ERR_MEMORY; } if (goal_node->cost == -1 || (!ignoreUnits && goal_node->occupied)) { delete start_node; delete goal_node; return false; } open.clear(); closed.clear(); start_node->g_cost = 0; start_node->h_cost = heuristic(start_node, goal_node); start_node->f_cost = start_node->g_cost + start_node->h_cost; start_node->parent = NULL; start_node->state = NODE_OPEN; goal_node->state = NODE_CLOSED; goal_node->g_cost = INT_MAX; goal_node->parent = NULL; closed.push(goal_node); open.push(start_node); Následn¥, dokud je ve front¥ n¥jaký uzel opakujeme hlavní cyklus, ve kterém na£teme sousedy uzlu.
while (!open.empty()) {
22
KAPITOLA 4.
REALIZACE
Node* node = open.pop(); Coord* neighbors; int count; neighbors = map.loadNeighbors(node->coord, count); Pro kaºdého souseda na£teme z mapy informace o odpovídajícím poli, zjistíme, zda jsme uzly jiº nenav²tívili, náleºit¥ je ohodnotíme a nakonec vloºíme do správných front.
for (int i = 0; i < count; i++) { //informace z mapy Node* n; try { n = new Node(map[neighbors[i]]); } catch (std::bad_alloc&) { std::cerr << "Out of memory" << std::endl; throw ERR_MEMORY; } if (n->cost == -1 || (!ignoreUnits && n->occupied)) { delete n; continue; } int g_cost = node->g_cost + COST_MULTIPLIER * n->cost; //zjisteni zda jiz byl navstiven Node* tmp = NULL; if ((tmp = closed.find(n->coord)) || (tmp = open.find(n->coord))) { if (tmp->g_cost <= g_cost) { delete n; continue; } else { delete n; n = tmp; } }
}
//nastav hodnoty n->parent = node; n->g_cost = g_cost; n->h_cost = heuristic(n, goal_node); n->f_cost = n->g_cost + n->h_cost; if (n->state == NODE_CLOSED) closed.remove(n->coord); if (n->state != NODE_OPEN) open.push(n); n->state = NODE_OPEN;
A nakonec uzav°eme uzel, jehoº sousedy jsme zpracovávali.
4.4.
23
SHRNUTÍ FUNKCE MODULU
delete[] neighbors; node->state = NODE_CLOSED; closed.push(node);
}
Pokud je fronta prázdná, cesta neexistuje
open.clear(); closed.clear(); return false;
}
Uº jen zbývá p°idat podmínku pro p°ed£asný konec vyhledávání. Vyhledávání cesty kon£í ve chvíli, kdy z prioritní fronty vybereme cílový uzel. Tuto podmínku umístíme ihned za vybrání uzlu z fronty. Pak jen sta£í zp¥tn¥ projít uzly a podle ukazatele na p°edch·dce sestavit výslednou cestu.
if (node == goal_node) { lenght = 0; Node* tmp = goal_node; while (tmp != start_node) { lenght++; tmp = tmp->parent; } try { *path = new Coord[lenght]; } catch(std::bad_alloc&) { std::cerr << "Out of memory" << std::endl; throw ERR_MEMORY; } tmp = goal_node; for (int i = lenght-1; i >= 0; i--) { (*path)[i] = tmp->coord; tmp = tmp->parent; } open.clear(); closed.clear(); return true; } 4.4
Shrnutí funkce modulu
Hlavní t°ídou modulu je
MainWidget.
Jako potomek t°ídy Widget z Qt[1] se tato
t°ída zobrazuje jako klasické aplika£ní okno, ve kterém se vypisují aktuální události. Po spu²t¥ní aplikace se vytvo°í objekt z této t°ídy, který ve svém konstruktoru vytvo°í objekt
24
KAPITOLA 4.
t°ídy
REALIZACE
Map pro reprezentaci herní mapy, dále p°ipraví objekty t°ídy PathThread, které Communication starající se o komunikaci
se starají o výpo£ty a vytvo°í objekt t°ídy
s okolním sv¥tem. Po vytvo°ení v²ech objekt· se propojí odpovídající signály a sloty zaji²´ující asynchronní meziobjektovou komunikaci.[12] T°ída
MainWidget reaguje na dv¥ hlavní události vlastní £asova£ a vn¥j²í ºádost
o novou cestu. Interní £asova£ umoº¬uje serveru sledovat plynutí £asu, v p°esn¥ daných intervalech probíhá p°epo£et polohy jednotek a také informování komunika£ního modulu o p°ípadné aktualizaci dat pro klienty. Slot zachytávající ºádosti o novou cestu získává informaci, která jednotka se pot°ebuje dostat na jaké sou°adnice. Tyto informace jsou p°edány výpo£etním vlákn·m pomocí sdílené fronty poºadavk·. T°ída
PathThread je potomkem Qt t°ídy Thread, která umoº¬uje vyuºití vláken. PathThread je kontrolovat frontu poºadavk· a pokud se zde n¥-
Úkolem objektu t°ídy
jaký poºadavek nachází, obslouºit ho. To se provede spu²t¥ním vyhledávacího algoritmu. Na konci vyhledávání je emitován signál informující t°ídu
MainWidget
o dokon£ení
poºadavku a nalezená cesta je p°edána jednotce, která o nalezení zaºádala. T°ída
PathThread také obsahuje statickou metodu pro spu²t¥ní vyhledávání v reºii
jiného vlákna, toho je vyuºito pro vyhledávání úhybných manévr·.
PathThread jsou pot°eba dv¥ r·zné fronty dat. Ty jsou realizovány t°ídami Container a PriorityQueue. První z nich poskytuje rychlé vyhledávání uzl· Pro funkci t°ídy
podle mapové sou°adnice, to je vhodné pro reprezentaci fronty uzav°ených uzl·. Druhá t°ída je naopak vhodná pro uzly otev°ené umoº¬uje výb¥r uzlu s minimální hodnotou. T°ída
Map
reprezentuje pomocí dvourozm¥rného pole herní mapu. V poli jsou
uloºené jednotlivé dílky mapy. Kaºdý je reprezentován strukturou s n¥kolika datovými poloºkami. Tato t°ída také udrºuje seznam jednotek a zprost°edkovává pro ostatní objekty p°ístup k informacím o map¥ i jednotkách. V²echny t°ídy vyuºívají pomocný datový typ
Coord,
který má význam mapové
sou°adnice.
4.5
Uºivatelské rozhraní
A£koliv gra cké uºivatelské rozhraní (GUI) nebylo sou£ástí zadání, je v implementaci obsaºena t°ída
Communication
a
View.
T°ída Communication ukazuje jakým zp·-
sobem se lze dostat k aktuální herní map¥ a informacím v ní obsaºeným a t°ída View je schopna tyto informace zobrazit. Zobrazení je pouze orienta£ní a umoº¬uje ov¥°it funkci sm¥rování.
4.5.
UIVATELSKÉ ROZHRANÍ
Obrázek 4.2: Ukázka z GUI
25
26
KAPITOLA 4.
REALIZACE
Kapitola 5
Testování 5.1
M¥°ení rychlosti
5.1.1 Princip testu rychlosti Na serveru m·ºeme provést celou sérii r·zných test·. Jedním z hlavních výkonových test· je spu²t¥ní serveru s následujícími parametry
•
Velikost mapy: 1000 x 1000 polí
•
Po£et jednotek: 1000
•
Po£et ºádostí na novou cestu: 1000
Jako ur£ující výsledek testu budeme povaºovat pr·m¥rnou dobu na zpracování jednoho poºadavku.
5.1.2 Testovací sestavy Tento test byl proveden na n¥kolika r·zných po£íta£ových sestavách.
•
NB 1 Notebook HP Compaq 6715b Procesor AMD Turion TL-60 Opera£ní systém Windows XP Professional SP3
•
NB 2 Notebook Compaq Presario C700 Procesor Intel Pentium Dual T2410 Opera£ní systém Windows Vista Home Basic
•
PC 1 Stolní PC Procesor AMD Athlon XP 1700+ Opera£ní systém Windows XP Professional SP2 27
28
KAPITOLA 5.
•
TESTOVÁNÍ
PC 2 Stolní PC Procesor AMD Sempron 2600+ Opera£ní systém Windows XP Home
•
PC 3 Stolní PC v u£ebn¥ K310 Procesor Intel Pentium Dual T2300 Opera£ní systém Gentoo Linux
5.1.3 Výsledky testování rychlosti Z test· vyplynulo, ºe námi implementovaný modul zvládá obsluhovat poºadavky velice rychle a graf s milionem uzl· mu ned¥lá problémy. Jist¥ by se na moderním a správn¥ upraveném stroji mohl tento modul provozovat na mnohem v¥t²í map¥ a s °ádov¥ v¥t²ím mnoºstvím jednotek.
Po£et jader Frekvence Velikost pam¥ti RAM as na jeden poºadavek
NB 1 NB 2
PC 1
PC 2
PC 3
2
2
1
1
2
2 GHz
2 GHz
1.5 GHz
1.6 GHz
1.6 GHz
2 GB
2 GB
1.5 GB
0.5 GB
1.5 GB
54 ms
32 ms
76 ms
86 ms
10ms
Tabulka 5.1: Výsledky testování rychlosti
5.2
Vliv velikosti mapy
Na první testovací sestav¥ (NB 1) prob¥hlo m¥°ení pr·m¥rné doby na výpo£et jednoho poºadavku v závislosti na velikosti mapy. Z grafu 5.1 je patrné, ºe doba výpo£tu roste p°ibliºn¥ kvadraticky. Jinými slovy, zv¥t²íme-li hranu mapy dvojnásobn¥, zv¥t²í se po£et uzl· v map¥ £ty°ikrát a stejn¥ tak se výpo£et stane £ty°ikrát pomalej²í. Na m¥°ící sestav¥ je maximální vhodná velikost mapy 1250 x 1250 polí. P°i této velikosti trvá výpo£et jednoho poºadavku p°ibliºn¥ 100 milisekund. Tento £as se dá pro realtimovou strategickou hru ozna£it za p°ijatelný.
5.3
Srovnání
Bohuºel se námi implementovaný zp·sob sm¥rování nedá porovnat s prvním vzorem pro modul, se strategií FreeCiv (2.2.1), jelikoº v jejich p°ípad¥ se jedná o tahovou strategii, kde mají dostatek £asu k propo£ítání minimálních cest. Na²e sm¥rování p°ipomíná hru Warcraft 3 (2.2.2), je schopno se vyrovnávat s p°ekáºkami na cest¥, ale trpí podobnými neduhami jako je ne moc inteligentní vzhled výsledné cesty p°i zablokování úzkého pr·chodu. Námi implementovaný algoritmus je vlastn¥ odleh£enou verzí algoritmu pouºitého ve h°e Red Alert 3 (2.2.3). V práci na tomto modulu je moºné nadále pokra£ovat a algoritmus vyhledávání vylep²it do stejné podoby.
29
SROVNÁNÍ
250
Průměrná doba na jeden požadavek [ms]
5.3.
200
150
100
50
0 0
200
400
600
800 1000 1200 Velikost mapy [pole]
1400
1600
1800
Obrázek 5.1: Graf závislosti pot°ebného £asu na velikosti mapy
2000
30
KAPITOLA 5.
TESTOVÁNÍ
Kapitola 6
Záv¥r Poda°ilo se nám docílit implementace serverového modulu, který p°ijímá poºadavky na nalezení cesty a dokáºe je obsluhovat. Modul p°i sm¥rování bere ohled na okolní terén a snaºí se vyhledat nejoptimáln¥j²í cestu. Implementace je pouºitelná jako výpo£etní £ást pro jakýkoliv server 2D strategické hry, kde je pot°eba v reálném £ase sm¥rovat jednotky. Pomocí A* algoritmu jsme ve sm¥rování jednotek docílili kompromisu mezi minimálností nalezené cesty a rychlostí nalezení cesty. Celý modul se chová obdobn¥ jako komer£ní produkty. Bohuºel mi nebyli zp°ístupn¥ny k nahlédnutí zdrojové kódy t¥chto komer£ních °e²ení a nem·ºeme s nimi tak na²e °e²ení podrobn¥ji porovnávat. A£koliv nebylo GUI v zadání práce, je v implementaci obsaºeno jednoduché rozhraní umoº¬ující vizualizovat £innost modulu a sledovat tak celé sm¥rování v reálném £ase. Koe cient heuristické funkce by se dal v dal²ích úpravách provázat s po£tem poºadavk· a ud¥lat tak celý systém více dynami£t¥j²í. V p°ípad¥ velkého po£tu poºadavk· by se modul mohl zam¥°it více na rychlost vyhledávání na úkor minimálnosti nalezených cest a zajistit tím stejný £as vyhledávání pro v²echny poºadavky nezávisle na jejich po£tu. Implementovaný modul neobsahuje sí´ovou £ást a klientskou aplikaci. Rád bych se v budoucnu podílel na jejich vytvá°ení a za£lenil tak tento modul do v¥t²í aplikace.
31
32
KAPITOLA 6.
ZÁV
R
Literatura [1] J. Blanchette and M. Summer eld.
C++ GUI programming with Qt 4.
Prentice
Hall, 2006. [2] D. M. Bourg and G. Seemann. [3] C. Browne.
Hex strategy.
[4] B. Eckel and C. Allison.
AI for game developers.
O'Reilly, 2004.
A K Peters, Ltd., 2000.
Thinking in C++.
Prentice Hall, 2nd edition, 2000.
[5] D. Harabor and A. Botea. Hierarchical path planning for multi-size agents in heterogeneous environments.
IEEE Symposium on Computational Intelligence and Games,
2008. [6] J. S. Harbour. [7] J. Kolá°.
Teoretická informatika.
[8] I. Millington. [9] S. Rabin.
Game programming all in one.
eská informatická spole£nost, 2004.
Arti cial intelligence for games.
AI Game Programming Wisdom.
[10] A. Rollings and E. Adams.
Thomson Course Technology, 2004.
Morgan Kaufmann, 2006.
Cengage Learning, 2002.
Andrew Rollings and Ernest Adams on Game Design.
New Riders, 2003. [11] A. S. Tanenbaum. [12] J. Thelin.
Modern Operating Systems.
Foundations of Qt development.
Prentice Hall, 2001.
Apress, 2007.
[13] FreeCiv hlavní stránka.
http://freeciv.wikia.com. [14] Qt A cross-platform application and UI framework.
http://www.qtsoftware.com/. [15] Qt reference documentation.
http://doc.qtsoftware.com/4.4/index.html. [16] Red Alert Universe > Home.
http://www.commandandconquer.com/portal/site/redalert/. [17] Tower defense Wikipedia, the free encyclopedia.
http://en.wikipedia.org/wiki/Tower_defense. 33
34
LITERATURA
[18] Blizzard Entertainment WarCraft III.
http://www.blizzard.com/war3/. [19] Map Wikipedia, the free encyclopedia.
http://en.wikipedia.org/wiki/Map.
P°íloha A
Seznam pouºitých zkratek 2D
Two-dimensional Dvourozm¥rný
GUI
Graphic User Interface Gra cké uºivatelské rozhraní
NB
Notebook P°enosný po£íta£
PC
Personal Computer Osobní po£íta£
RTS
Real-Time Strategy Strategie v reálném £ase
TBS
Turn-Based Strategy Tahová strategie
TD
Tower Defense Obrana v¥ºemi
35
36
PÍLOHA A.
SEZNAM POUITÝCH ZKRATEK
P°íloha B
Instala£ní a uºivatelská p°íru£ka B.1
Kompilace
Modul je implementován za pomoci Qt[14]. Pro úsp¥²nou kompilaci a spu²t¥ní serveru je pot°eba mít na PC Qt minimáln¥ ve verzi 4 (modul vyvíjen pod verzí 4.4). Pro provozování v opera£ním systému Windows je pot°eba Qt nainstalovat dle návodu v dokumentaci Qt[15]. V unixových opera£ních systémech bývá jiº Qt nainstalováno, je sou£ástí prost°edí KDE. Pokud tomu tak není, op¥t je pot°eba provést instalaci dle návodu[15]. Pokud je Qt správn¥ nainstalované je na PC k dispozici p°íkaz
qmake.
Jeho
spu²t¥ním se docílí vytvo°ení make le pro daný stroj a opera£ní systém. Následn¥ se p°íkazem
make
provede samotná kompilace dle make lu vytvo°eného
p°edchozím p°íkazem. Po vytvo°ení binárního souboru je ho jiº moºné normálním zp·sobem, zcela bez parametr·, spustit.
Shrnutí 1. Nainstalovat a zkompilovat Qt, dle dokumentace[15], není-li jiº na cílovém PC k dispozici 2. Zkopírovat zdrojové kódy na cílový po£íta£ 3. P°íkazem
qmake vytvo°it make le
4. P°íkazem
make zkompilovat zdrojové kódy do binárního souboru
5. Spustit zkompilovaný modul
B.2
Parametry
Pro testovací ú£ely lze modul spustit s n¥kolika parametry, které výrazn¥ ovliv¬ují chování a výkon vyhledávacího modulu. Tato funkce je pouze experimentální a m·ºe vést k ne£ekaným událostem v£etn¥ pádu samotného modulu. Moºnosti volby parametr· jsou do£asná náhrada za neexistujícího klienta. 37
38
PÍLOHA B.
INSTALANÍ A UIVATELSKÁ PÍRUKA
Moºné parametry -f xx
Jméno vstupního souboru (bitmapy)
-s xx
Velikost mapy
-h xx
Hodnota koe cientu heuristické funkce
-t xx
Po£et r·zných ohodnocení terénu
-u xx
Po£et jednotek v map¥
-n
Zakáºe vykreslování aktuálního stavu
B.3
Ovládání
Samotný modul nelze nijak ovládat, je zde jen moºnost ho ukon£it. Testovací verze obsahuje navíc widget, který zobrazuje aktuální herní situaci a obsahuje tla£ítko, kterým je moºné poslat modulu testovací ºádosti o nalezení nových cest pro v²echny jednotky na náhodné sou°adnice.
P°íloha C
Obsah p°iloºeného CD Na p°iloºeném CD se nachází i spustitelná verze modulu pro opera£ní systém Windows, která v²ak pro sv·j b¥h vyºaduje n¥které dynamické knihovny z frameworku Qt. Doporu£uji proto nainstalovat Qt a zkompilovat si sv·j vlastní binární soubor viz P°íloha B. CD obsahuje následující adresá°ovou strukturu.
/bin /text /src /figures /src
spustitelný soubor text bakalá°ské práce v digitální podob¥ zdrojová podoba textu obrázky k textu zdrojové soubory modulu
39
