Sem vložte zadání Vaší práce

Sem vložte zadání Vaší práce.

České vysoké učení technické v Praze Fakulta informačních technologií Katedra softwarového inženýrství

Bakalářská práce

Herní server strategické tahové hry Sepulcher Václav Starý

Vedoucí práce: Ing. Jiří Daněček

16. května 2012

Poděkování Na tomto místě bych rád poděkoval Ing. Jiřímu Daněčkovi za vedení mé bakalářské práce, jeho čas, ochotu a cenné rady.

Prohlášení Prohlašuji, že jsem předloženou práci vypracoval samostatně a že jsem uvedl veškeré použité informační zdroje v souladu s Metodickým pokynem o etické přípravě vysokoškolských závěrečných prací. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona, ve znění pozdějších předpisů, zejména skutečnost, že České vysoké učení technické v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle § 60 odst. 1 autorského zákona.

V Praze dne 16. května 2012

..................... 7

České vysoké učení technické v Praze Fakulta informačních technologií c 2012 Václav Starý. Všechna práva vyhrazena.

Tato práce vznikla jako školní dílo na Českém vysokém učení technickém v Praze, Fakultě informačních technologií. Práce je chráněna právními předpisy a mezinárodními úmluvami o právu autorském a právech souvisejících s právem autorským. K jejímu užití, s výjimkou bezúplatných zákonných licencí, je nezbytný souhlas autora.

Odkaz na tuto práci Václav Starý. Herní server strategické tahové hry Sepulcher: Bakalářská práce. Praha: ČVUT v Praze, Fakulta informačních technologií, 2012.

Abstract This thesis focuses on creating a multiplayer server application, used in the turn-based strategy game Sepulcher. Its major part deals with artificial intelligence algorithms for pathfinding in graphs. In order to maintain a smooth flow of the game, the thesis elaborates on the client-server communication. A design of the game logic, which allows to customize and extend the game easily, is also discussed. Keywords Sepulcher, Artificial intelligence, Server application, Pathfinding, C#

Abstrakt Práce je zaměřena na tvorbu serverové aplikace umožňující hru více hráčů, pro tahovou strategickou hru Sepulcher. Její velká část je věnována algoritmům umělé inteligence zabývajících se hledáním cest v grafech. Z důvodu plynulosti hry řeší způsob komunikace mezi klientem a serverem. Není opomenut návrh herní logiky, který umožňuje hru jednoduše upravovat a rozšiřovat. Klíčová slova Sepulcher, Umělá inteligence, Serverová aplikace, Hledání cest, C# 9

Obsah Úvod

17

1 Teoretická část 1.1 NP problém . . . . . . . . . . . 1.2 Terminologie AI . . . . . . . . . 1.3 Základní strategie hledání cest 1.4 A* a heuristická funkce . . . . 1.5 Využití A* v PC hrách . . . . . 1.6 Genetický algoritmus . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

19 19 20 21 23 24 26

2 Analytická část 2.1 Požadavky na serverovou aplikaci . . . . 2.2 Technologie C#, .NET Framework 4 . . 2.3 Analýza herního prostředí . . . . . . . . 2.4 Analýza A* . . . . . . . . . . . . . . . . 2.5 Heuristiky - odhad vzdálenosti . . . . . 2.6 Jump Point Search . . . . . . . . . . . . 2.7 Lightning-Fast A* . . . . . . . . . . . . 2.8 Výběr algoritmu pro hledání cest . . . . 2.9 Vzhled cesty . . . . . . . . . . . . . . . . 2.10 Komunikační protokol – návrh a analýza 2.11 Návrh komunikace . . . . . . . . . . . . 2.12 Domain model - herní logika . . . . . . 2.13 Domain model - serverová aplikace . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

31 31 32 33 34 36 37 38 39 42 43 46 47 48

3 Implementační část 3.1 Konvence úpravy kódu . . . 3.2 Implementace protokolu . . 3.3 Synchroní komunikace . . . 3.4 Problém zvýraznění dlaždic

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

51 51 52 52 53

. . . . 11

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . .

3.5 3.6 3.7 3.8

Testování . . . . . . . . Základní testování . . . Testy vstupních hodnot Zátěžový test . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

54 55 56 57

Závěr

59

Literatura

61

A Seznam použitých zkratek

63

B Obsah přiloženého CD

65

12

Seznam obrázků 1.1 1.2 1.3 1.4 1.5 1.6

Schéma agent(7). . . . . . . . . . . . . . . . . Procházení grafu - základní strategie. . . . . . Prohledávání iterative deeping search . . . . . Procházení grafu - A* algoritmus. . . . . . . Prohledaný prostor v závislosti na algoritmu. Hledání cesty v hrách. . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

20 22 23 24 25 26

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Ukázka převodu mapy do grafové repreazentace. . . . . . . Křivka rotoucí náročnosti při expanzi jednoho uzlu. . . . . Prohledaný prostor v závislosti na algoritmu. . . . . . . . . Roustoucí časová náročnost grafu v závisloti na počtu uzlů. Vzhled optimální cesty. . . . . . . . . . . . . . . . . . . . . Kanály mezi klientem a serverem. . . . . . . . . . . . . . . Asynchronní kanál a fronta. . . . . . . . . . . . . . . . . . . Domain model herní logiky. . . . . . . . . . . . . . . . . . . Domain model serverové logiky. . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

34 36 38 41 44 47 47 48 49

13

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Seznam tabulek 2.1 2.2 2.3

Složitosti datových struktur. . . . . . . . . . . . . . . . . . . . . . Algoritmy pro hledání cest a jejich optimálnost. . . . . . . . . . . . Naměřená rychlost testovaných algoritmů. . . . . . . . . . . . . . .

34 40 41

3.1 3.2

Velikost nejjednoduššího příkazu. . . . . . . . . . . . . . . . . . . . Porovnání velikost objektů v závislosti na formátu. . . . . . . . . .

53 53

15

Úvod Práce byla vytvořena v návaznosti na předmět Počítačové hry a animace. V tomto předmětu nebyl dostatečný prostor pro téma umělé inteligence. Je to rozsáhlá vědecká disciplína, proto bude většina mé práce zaměřena na hledání cest v grafech, To je základní prvek umělé inteligence počítačových her. Práce se bude opírat o design dokument hry Sepulcher, který byl vytvořen i s hrou na předmětu Počítačové hry a animace. Návrh Sepulcher hry počítá s hrou pro více hráčů, která byla v původní verzi umožněna pouze v módu horkého křesla. Tedy v módu, kde se více hráčů střídá u jednoho počítače. Možnost hry více hráčů z různých míst na světě by měla zajistit právě serverová aplikace vytvořená v této práci. Původní hra Sepulcher, pro kterou jsem implementoval herní logiku a umělou inteligenci byla pro hraní na osobním počítači přijatelná. Serverová aplikace bude však vyhodnocovat více příchozích požadavků ve stejném okamžiku. Proto bude muset být většina kódů přepsána, jak z důvodu špatného odstínění herní logiky od prezentační vrstvy, tak špatně napsanými algoritmy pro hledání cest. Práce je rozdělena na tři hlavní úseky. V prvním části je úvod do problematiky související s umělou inteligencí a hledáním cest v grafech. Na konci této části je také uveden „vše řešící“ genetický algoritmus, jako univerzální způsob řešení problémů za pomoci umělé inteligence. Analytická část není klasickou analýzou softwarového inženýrství. Z velké části je zaměřena na prohledávací algoritmy uvedené v části první. Je zde rozebíráno jejich uplatnění při implementaci, měří se jejich kvality a diskutuje se nad možnostmi zlepšení. V poslední části se zabývám několika zajímavými problémy, které bylo nutno řešit při implementaci a nebylo též opomenuto testování. Cílem mé práce je vytvořit serverovou aplikaci, které bude umožňovat hru více hráčů. Rád bych ukázal, jakým způsobem se přistupuje k hledání cest v grafech a hrách. Jaké algoritmy zvolit a jak je optimalizovat v prostředí, ve kterém se hra odehrává.

17

Kapitola

Teoretická část 1.1

NP problém

NP problémy jsou takové problémy, u kterých není doposud znám algoritmus řešení s polynomiální složitostí. Problematika NP úplných problémů je celkem novou záležitostí, přicházející s moderním věkem výpočetní techniky. Poprvé byl NP úplný problém zmíněn v práci Stephna Cooka roku 1971, kterou následně ukázal na splnitelnosti logických formulích. Jedním z problémů tisíciletí (problém, za jehož vyřešení je vypsána odměna 1 mil. dolarů), je problém P=NP, tedy zda jde NP problém vyřešit na deterministickém turingově stroji v polynomiálním čase. Pokud by se tato rovnost prokázala, znamenalo by to převratné změny především v moderní kryptografii, která své šifrování staví tak, aby nalezení klíče k šifře bylo NP úplným problémem. V dnešní době můžeme pro řešení NP úplných problémů použít heuristiky. Heuristiky neprocházejí celý stavový prostor (neprocházejí všechny možnosti), ale pouze jeho části. To značně urychluje hledání přípustného řešení. Výsledkem heuristiky je pak často řešení sub-optimální. Optimální řešení je takové řešení, které dosahuje nejlepších možných výsledků. Nemusí existovat pouze jedno. Sub-optimální řešení je řešení s hodnotami, které se velice blíží řešení optimálnímu. Občas je dobré přijmou tuto variantu v případech (mimo jiné) kdy: • Nalezení optimálního řešení je časově velice náročné. • Je obtížné nalézt nějaké řešení (například u tvorby rozdělovníků). • Nelze rozhodnou, zda řešení je optimální. 19

1

1. Teoretická část

1.2

Terminologie AI

1.2.1

Intelligent Agent

Intelligent Agent je v umělé inteligenci nazývaná autonomní entita se schopností pozorovat a manipulovat s prostředím(1).

Obrázek 1.1: Schéma agent(7). S pomocí vstupních senzorů monitoruje stav prostředí a díky aktuátoru pak tento stav může ovlivňovat. Hlavní otázkou, kterou řeší umělá inteligence, je zpracování vstupů a výstupů tak, aby agent dosáhl určitého cíle.

1.2.2

Agentí prostředí

Prostředí, které agent prozkoumává, může mít různé vlastnosti, podle kterých se dělí. • Plně nebo částečně prozkoumatelné prostředí – Plně prozkoumatelné prostředí ukazuje všechny stavy. V tomto prostředím se hrají například šachy, kde vidíme celou hrací plochu a všechny figurky. – Částečně prozkoumatelné prostředí poskytuje pouze informace o některých stavech. Příkladem mohou být karetní hry, kde hráč zná pouze své karty a karty vyložené na stole. O hracích kartách jiných hráčů nemá informace. • Deterministické nebo nedeterministické prostředí – Deterministické prostředí má jasně daná pravidla pro přechod mezi stavy. Figurky na šachovnici mají jasně daná pravidla pohybů, kterými se můžou pohybovat. – Nedeterministické prostředí obsahuje prvky náhody. Nelze tedy jednoznačně rozhodnout, do jakého stavu prostředí se přejde. Jsou to například hry s kostkami. 20

1.3. Základní strategie hledání cest • Diskrétní nebo spojité prostředí – Diskrétní prostředí se může nacházet pouze v konečném množství stavů. – Spojité prostředí se může nacházet v nekonečném množství stavů. • Neutrální nebo cílené prostředí – Neutrální prostředí změnou svého stavu nesleduje žádný konkrétní cíl. – Cílené prostředí změnou stavu nějaký cíl sleduje. Toto prostředí obsahuje většina her. • Statické nebo dynamické prostředí – Statické prostředí mění svůj stav pouze v závislosti na akci agenta. – Dynamické prostředí může změnit svůj stav bez agentova zásahu.

1.3 1.3.1

Základní strategie hledání cest Definice problému hledání cest

Problém hledání nejkratší cesty v grafu je jeden ze základních problémů teorie grafů. S problémem hledání (nejkratší) cesty v grafu se setkáváme v mnoha různých oborech. Nemalé úsilí je mu věnováno i v počítačových hrách. Umělá inteligence, která tento problém řeší, se pohybuje v agentním prostředí, které je plně prozkoumatelné, diskrétní, deterministické a statické. Všechny dále uvedené algoritmy, které zohledňují ohodnocení hran požadují, aby cena všech hran byla větší nebo rovna 0. Problém se záporným ohodnocením hran řeší například Johnsonův algoritmus, jehož popis je v knize (2). Algoritmy rozdělují uzly prohledávaného grafu do třech tří množin. Fresh uzly, o kterých algoritmus ještě neví. Open uzly, které má algoritmus právě k dispozici. Close uzly, které algoritmus již zpracoval. Tato množina uzlů je zde proto, aby algoritmus nenavštěvoval uzly víc než jedenkrát a tak nedocházelo k redundanci cest. Pokud algoritmus expanduje uzel, pak uzel přesouvá z Open do Close množiny a do Open množiny umisťuje všechny následovníky expandovaného uzlu. 21

1. Teoretická část

Obrázek 1.2: Procházení grafu - základní strategie. Čísla v uzlech udávají pořadí, v jakém jsou uzly expandovány pro: A prohledávání do hloubky B prohledávání do šířky C uniform-cost search

1.3.2

Prohledávání do šířky

Základní jednoduchý přístup k nalezení cesty spočívá v procházení grafu po jednotlivých úrovních. Algoritmus se dá jednoduše implementovat pomocí FIFO fronty, která reprezentuje množinu Open uzlů. Prohledáváním grafu do šířky se nalezne optimální cesta, pokud hrany nemají ohodnocení, nebo ohodnocení hran je rostoucí funkce závislá na hloubce uzlu(1). Má však vysokou výpočetní a paměťovou náročnost. Proto je tento algoritmus použitelný pouze na problémy s malým počtem uzlů.

1.3.3

Uniform-cost search (Cheapest first)

Uniform-cost search nalezne optimální řešení vždy. Bez ohledu na ohodnocení hran (které je 0 nebo kladné). Pokud je ohodnocení na všech hranách stejné nebo žádné, pak se algoritmus chová stejně jako prohledávání do šířky. Uniform-cost při hledání cesty vždy expanduje uzel s nejnižším ohodnocení cesty, která k němu vede z počátečního uzlu. Variantou Uniform-cost je Dijskrův algoritmus(17).

1.3.4

Prohledávání do hloubky

Prohledávání do hloubky vždy expanduje nejhlubší uzel. Jednoduchá implementace je pomocí LIFO fronty reprezentující Open množinu. Algoritmus má menší paměťovou náročnost než prohledávání do šířky. V rozsáhlém, téměř nekonečném prostoru, je pro tento algoritmus velice obtížné najít cestu z důvodu stálého sestupování do hloubky. Také toto prohledávání grafu nezaručuje nalezení optimální cesty. Malá paměťová náročnost je 22

1.4. A* a heuristická funkce

Obrázek 1.3: Prohledávání iterative deeping search

velice atraktivní a proto prohledávání grafu do hloubky je často použito jako stavební kámen složitějších algoritmů.

1.3.5

Iterative deeping search

U tohoto algoritmu je postup stejný jako u prohledávání grafu do hloubky s tím, že je nastaven limit na maximální hloubku, do které lze sestoupit. Pokud nebude nalezeno řešení, limit hloubky se navýší a graf je znovu prohledán. Algoritmus má malou paměťovou náročnost stejně jako prohledávání do hloubky a cesta, kterou nalezne, je optimální.

1.4 1.4.1

A* a heuristická funkce Heuristika

Heuristika se využívá v situacích, kdy je stavový prostor pro úplné procházení příliš velký nebo pro daný problém není znám algoritmus řešení. Heuristika nemusí nalézt nejlepší řešení. Často nalezené řešení je pouze přibližné, ale lze je nalézt v rozumném čase. Proto jsou heuristiky zpravidla používané při řešení NP-úplných problémů.

1.4.2

A* algoritmus

Spojením Uniform-cost search s vhodnou heuristikou, která do algoritmu vnáší hlubší znalost problému, vzniká velice silný nástroj A*. A* vybírá pro expanzi takový uzel, který má nejmenší hodnotu f (x) = g(x) + h(x), kde g(x) je ohodnocení hrany, h(x) předpokládaná vzdálenost z uzlu k cíli. Funkce f (x) je tedy předpokládaná cena řešení. Na heuristiku h(x) jsou kladeny dva požadavky - přípustnost a konzistenčnost. 23

1. Teoretická část

Obrázek 1.4: Procházení grafu - A* algoritmus. Černé číslice udávají cenu hrany. dé číslice udávají hodnotu heuristiky. Při procházení grafu by se po dosažení cíle šedivé uzly neexpandovaly.

Heruristika h(x) je přípustná, pokud předpokládaná cena řešení je menší nebo rovna reálné ceně. Tehdy se jedná o optimistickou heuristiku. Konzistence vyžaduje, aby pro každý uzel platilo, že h(x) ≤ d(x, y) + h(y), kde d(x, y) je ohodnocení hrany mezi uzly x a y. Platí, že pokud je heuristika konzistentní, je i přípustná(1). Cesta nalezena A* je optimální, pokud jsou tyto dvě podmínky splněny. Při prohledávání stromového grafu je pro nalezení optimální cesty postačující podmínka přípustnosti.

1.4.3

Weighted A*

Úpravou funkce f (x) na tvar f (x) = g(x) + εh(x), kde ε > 1 získáváme weighted A* algoritmus. Parametr ε udává jak velkou váhu má heuristika při výběru, jaký uzel bude expandován. Při této úpravě již heuristická funkce není optimistická a nalezená cesta tudíž nemusí být optimální. Za tuto cenu weighted A* nabízí v mnoha případech větší rychlost a menší paměťovou náročnost než klasický A* algoritmus.

1.5

Využití A* v PC hrách

Hledání cest je základní a velice důležitý problém v PC hrách. atná realizace hledání cest je velice snadno odhalitelná. Buď nesmyslnou cestou, kterou se pohybující objekt vidá, nebo snížením výkonu z důvodu špatně zvolené strategie hledání, popřípadě špatné implementace. Velice často pro problém hledání cest je využíván A* algoritmus a jeho různé mutace. Hry kladou na hledání cest vysoké nároky na rychlost nalezení cesty a kvalitu cesty, která v některých případech může být i sub-optimální. Prohledávaný prostor je konečný, jeho velikost může být značně velká. Tomu je úměrná i časová náročnost na nalezení cesty. Hledaní cesty tedy musí 24

1.5. Využití A* v PC hrách

Obrázek 1.5: Prohledaný prostor v závislosti na algoritmu. A prohledávání do šířky, které nalezne nejkratší cestu B A* algoritmus nalezne nejkratší cestu, prohledá při tom méně prostoru C weighted A*, nalezne sub-optimální cestu s nejmenším nárokem na prostor

být rozděleno tak, aby proces nadměrně nezatěžoval výpočetní prostředky procesoru (tím nebrzdil průběh hry) a cesta působila přirozeným dojmem tak, že byla nalezena v jednom okamžiku. Problém můžeme rozdělit na hledání tří cest: rychlé cesty, úplné cesty a spojovací cesty. Rychlá cesta V okamžiku, kdy je po objektu vyžadováno aby se přemístil, není čas na hledání úplné cesty k cíli. Proto se nalezne pouze neúplná krátká cesta tak, aby se objekt vydal přibližným směrem k požadovanému bodu. Rychlá cesta je zde tedy proto, aby nám dala čas k nalezení cesty úplné. Úplná cesta Úplná cesta je cesta, která vede k cíli objektu. Hledání začíná tam, kde končí cesta rychlá. Její hledání je rozděleno do více průchodů herní smyčkou. Rozpracované cesty jsou ukládány do fronty, která může mít různé strategie rozdělování výpočetních prostředků. Ty se mohou rozdělovat rovnoměrně mezi všechna rozpracovaná hledání nebo podle priorit. Priorita je pak často určena dobou strávenou ve frontě. Spojovací cesta Poslední hledanou cestou je cesta spojovací. S jejím hledáním se začíná v okamžiku nalezení úplné cesty. Její počátek je aktuální pozice objektu a cílovým bodem je bod na cestě úplné. Není jasně dáno o který bod se jedná, protože nalezení spojovací cesty musí být co nejrychlejší a zároveň tato cesta musí vypadat co nejpřirozeněji.

25

1. Teoretická část

Obrázek 1.6: Hledání cesty v hrách.

1.5.1

Optimalizace

Pro rychlejší nalezení cesty je třeba zmenšit prohledávaný prostor. V A* algoritmu využijeme vlastnost iterative deep search. Tedy omezíme hloubku do které se A* může vnořit. Pokud nebude cesta nalezena, omezení zmírníme posunem hranice maximální hloubky a prohledávání opakujeme. Omezení hloubky může být závislé na délce cesty, ceně nebo na využité paměti. Volba správných datových struktur pro open a close množiny výrazně ovlivňuje A* algoritmus. Je důležité zaměřit se na složitost vkládání a odebírání prvků ze seznamů. Pokaždé, když se expanduje uzel, dochází k jeho odebrání prvku z open listu a je přesunut do close listu. Následovníci expandovaného uzlu jsou vloženi do open listu, proto je vhodné mít datovou strukturu se složitostí vkládání O(1). Problém je komplikován faktem, že A* expanduje uzel s nejnižší hodnotou f (n), proto by se mělo jednat o upořádanou strukturu. Řešení toho problému nabízí v knize (6), kdy před open listem je list o velikosti patnácti prvků s řazením vkládáním a obsahuje uzly s nejnižší hodnotou f (n).

1.6

Genetický algoritmus

Genetický algoritmus je inspirován Darwinovou teorií evoluce. Byl vymyšlen Johnem Hollandem a kolektivem. Publikován byl roku 1975 v knize „Adaption in Natural and Artificial Systems“. Algoritmus je velice jednoduchý. Začíná s počáteční množinou řešení, která může být jak náhodně vybraná, tak nalezena pomocí jiných heuristik. Tato množina řešení se nazývá počáteční populace. Pro snažší aplikaci genetických operátorů se jedinci kódují. Takto zakódovaný jedinec se nazývá chromozom. Algoritmus musí být schopen jednotlivá řešení ohodnotit. K tomu účelu definujeme fitness funkci, která pro lepší řešení vrací vyšší hodnoty. Následuje selekce řešení pro křížení s pravidlem: Čím větší fitness hodnota, tím větší pravděpodobnost výběru. 26

1.6. Genetický algoritmus Nad vybranými jedinci začíná proces křížení, tedy proces, který z vybraných jedinců vytváří nová řešení. Následuje mutace, která s malou pravděpodobností pozmění nepatrně chromozom. Mutace brání příliš rychlému zjednotvárnění vlastností v populaci, ztrátě potencionálně užitečného genetického materiálu a předčasné konvergenci populace(4). Poslední krok algoritmu je vytvoření nové počáteční populace. V nové populaci buď budou pouze potomci populace stávající nebo se všechny chromozomy seřadí a do nové populace se zařadí prvních N s nejvyšší hodnotou fitness funkce. V tomto okamžiku se algoritmus vrací na začátek a postup opakuje. Algoritmus je ukončen pokud najde řešení s odpovídající fitness funkcí nebo bylo vytvořeno požadované množství generací. Algoritmus 1 Genetický algoritmus Vytvoř počáteční populaci. Ohodnoť jedince populace. while ukončující podmínka do Vytvoř novou populaci tak, že: { while Populace není kompletní do Vyber 2 jedince z Populace. Zkřiž tyto jedince - zisk minimálně jednoho potomka. Nad potomkem proveď mutaci. Ulož potomka do nové populace. end while } Nahraď starou populaci populací novou. end while

1.6.1

Příklad

Najděte maximum funkce f (x) = x2 , x ∈ h0, 255i. Náhodně vybraná počáteční populace: 5, 23, 71, 96. Zakódování do binárního kódu. N 5 23 71 96

Binární zakódování 0000 0101 0001 0111 0100 0111 0110 000

Fitness hodnota 25 429 4 624 9 216

Prav. křížení [%] 0,4 3,6 32 64

Fintess se stanoví stejným předpisem jako funkce pro níž hledáme maximum, tedy x2 . Tento předpis má vypovídající hodnotu o kvalitě jedince. V případě hledání minima by byla nevyhovující a zvolila by se například 27

1. Teoretická část f (x) = 105 − x2 . Algoritmus nyní vypočítá pravděpodobnost křížení pomocí kola štěstí. Provede se křížení mezi hodnotou 96 a 71. Bod křížení je náhodně zvolen za čtvrtým bitem. Předek 0100 | 0111 0110 | 0000

Potomek 0100 0000 0110 0111

N 64 103

Fitness hodnota 4 096 10 609

Druhé křížení bude mezi hodnotou 96 a 23, bod křížení za třetím bitem. Předek 011 | 00000 000 | 10111

Potomek 0111 0111 0000 0000

N 64 0

Fitness hodnota 4 096 0

Předposledním krokem algoritmu je mutace. Tedy s velice malou pravděpodobností si jedinec sám sobě neguje jeden bit. Zde je velice dobře vidět její nutnost. Pouhé křížení nám samo o sobě nikdy nevytvoří jedince, který by měl jedničku na prvním nebo čtvrtém bitu. V posledním kroku se vytvoří z potomků nová počáteční populace a algoritmus se opakuje. Uvedený příklad je pouze ilustrativní a mnohem lépe by se na řešení tohoto problému hodil například horolezecký algoritmus popsaný v (1). Ten by na rozdíl od genetického algoritmu s jistotou našel nejlepší řešení a to s výrazně menším nárokem na výpočetní prostředky. Pro účel seznámení s postupy používané v genetických algoritmech je však velice užitečný.

1.6.2

Kódování

Prvním zásadním rozhodnutím při používání genetického algoritmu je volba kódování. Při špatné volbě kódování můžou vznikat redundance, které zvětšují mohutnost prohledávaného prostoru a tím snižují efektivitu algoritmu (4). Tradičně je používáno binární kódování, na které se snadno aplikují klasické genetické operátory. Pro binární reprezentaci čísel je preferován Grayův kód, v kterém se sousedící čísla liší pouze v jednom bitu. Tato vlastnost je pozitivní při mutaci, kdy malá změna chromozomu znamená malou změnu řešení. Mezi další často používané typy kódování patří permutační kódování, maticové kódování, stromové kódování nebo kódování nad abecedou znaků. Kódování je silně závislé na problému. Proto nelze jednoznačně říci, které je nejlepší nebo uvést univerzální kódování.

1.6.3

Fitness funkce

Fitness funkce přiřazuje chromozomům takovou hodnotu, která reprezentuje jeho sílu v populaci. V mnoha případech se jako fitness funkce dá použít užitková funkce. Je dobré si uvědomit, že při ohodnocení populace může platit A > B > C > A (například při volbě vhodné herní strategie). Takovou situaci 28

1.6. Genetický algoritmus řeší mimo jiné turnajová fitness funkce, kde ohodnocení chromozomu je počet vyhraných turnajů (porovnání).

1.6.4

Selekce

Pro selekci platí podobná pravidla jako pro volbu fitness funkce. Při špatné volbě selekce může docházet k pomalé konvergenci populace a k úpadku do lokálního extrému. Často se používá pro selekci kolo štěstí. nce na výběr pak odpovídá procentnímu zastoupení fitness hodnoty v populaci. Pokud se ale v populaci nachází pár silných jedinců (ti mohou být v lokálním extrému), ostatní jedinci nemají příliš možností pro křížení a algoritmus nalezne pouze lokální extrém. Takové situace lze řešit například ranked selection(4). Ta šanci na křížení přiděluje podle pořadí. Mnoho pravidel platících pro selekci se dá aplikovat na fitness funkci a obráceně.

1.6.5

Křížení

Díky křížení se genetický algoritmus posouvá v prohledávání stavového prostoru kupředu. Jeho efektivnost velice záleží na správně zvolené fitness funkci a selekci. Části informací z dvou chromozomů vybraných selekcí jsou spojené a vytvářejí nového jedince. Časté je použití jednobodového křížení (obecně n-bodové křížení). Na křížení je kladen požadavek, aby jedinec takto vzniklý byl přípustným řešením. To v mnoha úlohách není samo o sobě splněno (úlohy plánování, obchodní cestující) a proto se na nepřípustné jedince musí aplikovat opravné algoritmy. Druhou možností je použití codeků (zobrazení), které převádějí chromozomy na přípustného jedince.

1.6.6

Mutace

Mutace slouží k udržování genetické variace v populaci a tím brání, aby proces hledání sklouznul do oblasti nějakého lokálního optima. Také přináší do populace nové prvky, které by nemusely být pomocí genetického operátoru křížení v populaci přítomné (viz příklad). Podle (4) by mutace jedince měla nastat s pravděpodobností 0,001 až 0,05. Stejně jako u křížení je u některých problémů potřeba oprava zmutovaného jedince na přípustné řešení.

1.6.7

Elitismus

Při vygenerování všech potomků stávající populace umírá a potomci vzniklí křížením vytvoří novou počáteční populaci. Pokud se do této populace dostanou i nejsilnější jedinci z rodičovské populace, je do genetického algoritmu zahrnut elitismus. Ten zaručuje, že doposud nejlepší řešení nebude ztraceno, zároveň však zvyšuje pravděpodobnost uváznutí v lokálním extrému.

29

Kapitola

Analytická část 2.1

Požadavky na serverovou aplikaci

Požadavky na serverovou aplikaci Sepulcher vycházejí z design documentu (v příloze) a nároky na klientskou aplikaci. Klientská aplikace Na klientskou aplikaci jsou kladeny minimální požadavky. Nepředpokládá se, že by poskytovala jinou než prezentační funkcionalitu. To na server klade větší zatížení jak na přenos dat, tak na výpočetní prostředky. Příkladem toho může být zvýraznění dlaždic zasažené efektem. Přestože klientská aplikace by tuto operaci mohla sama vypočítat, není to po ní vyžadováno a server tuto funkcionalitu musí poskytnout. Tento fakt však brání tomu, aby různí klienti viděli různé, často nesmyslné věci (out-of-syn). Klientská aplikace bude implementována v technologii C# a frameworkem XNA a neklade žádné požadavky na komunikační protokol. Ten se tedy musí v rámci této práce navrhnout s ohledem na technologie používané klientem. Generování map Jedním ze selling-pointů uvedeným v design documentu je náhodná generace map. Mapa musí být generována tak, aby (bez modelů) byla každá místnost a dlaždice dostupná. Některé mapy nemusí být od začátku hry hned zobrazeny a jsou odhaleny až během hry. Mapa je generována pomocí semínka, které, pokud není určeno, je vygenerováno náhodně. Toto náhodné semínko je hráčům nabídnuto, aby v budoucnu mohli vygenerovat stejnou mapu. Softwarové požadavky Pro běh aplikace nejsou definovány žádné softwarové požadavky. Lze je tedy specifikovat v závislosti na použité technologii. 31

2

2. Analytická část Hardwarové požadavky Stejně jako u softwarových požadavků nejsou definovány. Minimální hardwarové požadavky budou stanoveny na sestavu, na které bude aplikace testována. Jednoduché spuštění hry Hráč by měl mít možnost spustit hru „jedním“ kliknutím. Není vyžadována po hráči žádná registrace, ani logování do systému. Free-To-Play Hra má splňovat model Free-To-Play. Hraní bude zcela zdarma. Také bude mít otevřený zdrojový kód, nebude tedy možné využít žádné placené technologie. Bezpečnost Aplikace nemusí obsahovat žádné bezpečnostní prvky, protože neobsahuje žádná citlivá data o uživatelích. Zatížení Server by měl zvládnout alespoň 100 uživatelů v jednom okamžiku.

2.2

Technologie C#, .NET Framework 4

Volba programovacího jazyka je důležitou součástí analýzy. atná volba může vést k prodloužení práce nebo dokonce úplnou nemožností implementace některých částí programu. Pro tuto serverovou aplikaci byl zvolen jazyk C# veze 4.0, s .NET Framework 4.0. Tento jazyk byl zvolen, protože původní Sepulcher hra je v tomto jazyce napsána a bude tedy možno využít při implementaci některé již hotové části kódu. To by ale pro volbu technologie nestačilo. Serverová aplikace bude potřebovat především dobře umět pracovat s vlákny a s komunikačními kanály. C# tyto požadavky velice dobře zvládá, navíc je okolo C# velká komunita a kvalitně zpracovaná dokumentace na Microsoft Developer Network. Pro čtenáře, který se se C# ještě nesetkal, je zde výčet základních vlastností tohoto programovacího jazyka. • C# je objektově orientovaný jazyk, ve kterém je vše objektem (potomkem třídy object) a to včetně primitivních datových typů. • Jazyk je inspirován jazykem Java a přebírá (stejně jako Java) syntaxi jazyka C. • Automatická správa paměti v podobě garbage collector. • Detekce hranic polí a neinicializovaných proměnných. 32

2.3. Analýza herního prostředí • Neexistuje zde vícenásobné dědění, které používá jazyk C++. Náhradou jsou zde interface, který předepisuje rozhraní třídy. • Jednou ze zásad softwarového inženýrství je zapouzdření. Zde C# nabízí property, které se chovají jako klasický datový atribut, vně se jedná o funkce get a set. • C#, stejně jako C++, má ukazatele na funkce. Jistou nevýhodou je závislost .NET Frameworku 4 na platformě systému Windows. Podporované verze Windows jsou Windows XP a novější. Protože však z požadavků na aplikaci nevyplývá požadavek na platformní nezávislost nebo na konkrétné operační systém, není použití této technologie problém. Z této volby plyne požadavek na softwarové vybavení počítače, na kterém serverová aplikace poběží.

2.3

Analýza herního prostředí

Pro správnou implementaci a volbu algoritmů je nutné nejprve analyzovat prostor, ve kterém se hra odehrává. Podkladem této analýzy je design document. Herní plocha se skládá ze čtvercových místností. Těch může být v jedné hře maximálně 49 × 49 = 2 401. Herní plocha je takto záměrně omezena, aby byla umožněna jednoduchá reprezentace dvourozměrným polem s fixní velikostí. Počet místností je tak dostatečně velký a nebude proto omezovat hráče. Tento závěr je odvozen ze stolní hry Castle Ravenfoft (touto hrou je Sepulcher inspirován), která má stejné herní prostředí. Zde se většina her odehrává na prostoru menším než 25 místností. Na každou místnost je dále kladen požadavek, aby měla alespoň jeden vstup. Také nesmí být rozdělena tak, aby se vytvořilo více místností. Je tedy jednoznačně dané z jakého směru se do místnosti dá vstoupit a také odejít. Každou místnost tvoří 4 × 4 = 16 čtvercových dlaždic. Každá dlaždice se může nacházet ve třech stavech. Prvním je dlaždice prázdná - tedy taková, která neobsahuje žádný model a na kterou lze vstoupit a zůstat na ní stát. Druhý typ je dlaždice s modelem. Je neprůchozí, nelze na ni vstoupit, ani umístit další jiný model. Model na této dlaždici má ale možnost z dlaždice odejít. Poslední typ je dlaždice obsahující zeď - na takovou dlaždici nelze umístit model ani dlaždicí projít. Po dlaždicích se mohou modely pohybovat do 8 směrů a to za cenu jednoho kroku. Za tuto √ cenu je tedy možný i pohyb po úhlopříčce, který je v reálném světě delší ( 2). Pohyb po úhlopříčce je stanoven pravidlem: Pohyb po úhlopříčce o jednu dlaždici je umožněn, pouze pokud této dlaždice lze dosáhnout dvěma kroky bez cesty po úhlopříčce. 33

2. Analytická část

Obrázek 2.1: Ukázka převodu mapy do grafové repreazentace. Operace Insert Remove IsElement FindMinimum

Hash tabulka Θ(1) Θ(1) Θ(1) O(n)

Strom O(log2 n) O(log2 n) O(log2 n) O(log2 n)

Priority queue O(log2 n) O(log2 n) O(log2 n) O(1)

φ volání1 3,5 1 3,5 1

Tabulka 2.1: Složitosti datových struktur.

Z uvedeného vyplývá, že herní mapa je graf, kde z nebo do každého uzlu vede maximálně 8 hran. Do uzlu reprezentující zeď nevede žádná hrana.

2.4

Analýza A*

Jak už bylo popsáno v teoretické části je A* jedením ze základních algoritmů pro hledání cest v počítačových hrách. V pseudokódu jsou používány dvě datové struktury pro fresh uzly (open list) a pro již prohledané uzly (close list). Výběr struktur je velice důležitý, protože má dopad jak na rychlost hledání, tak na využité paměti. Pro tyto dvě struktury připadají v úvahu tyto možnosti uvedené v tabulce 2.1. První hledanou strukturou bude struktura pro open list. Hash tabulka má pro Inser, Remove a IsElement konstantní časovou složitost (záleží ale také na vnitřní implementaci tabulky), pro nalezení minima má však složitost O(n). Protože pro strom a priority queue budou platit stejná pravidla, budeme nadále uvažovat pouze priority queue, která má konstantní náročnost 1

34

Aritmetický průměr počtu volání při expanzi jednoho uzlu.

2.4. Analýza A* Algoritmus 2 A* algoritmus P = počáteční uzel. Výpočet ceny heuristiky a F pro P. Přidání P do open listu. while Open list není prázdný do B = uzel s nejmenší hodnotou F z open listu. if B == cíl then return B end if Přesunutí uzlu B z open listu do close listu. for all C z potomků B do Výpočet F = G + H pro uzel C. if C je v close listu then continue end if if C je v open listu s hodnotou F je větší než právě vypočítanou then Aktualizuj rodiče a cenu F. else Přidej C do open listu. end if end for end while return Cesta neexistuje.

na nalezení minima. Porovnáme tedy pro jaké N je výhodnější použít hash tabulku, před prioritní frontou. Při expanzi jednoho uzlu se provede v průměrném množství uvedeném v tabulce 2.1. Tedy při expanzi hash tabulka provede 8 + n operací, zatímco priority queue 8 log2 n + 1. Na grafu 2.4 jsou tyto funkce znázorněny. Ani jedna ze složitostí není větší než složitost lineární, což je přijatelné. Prioritní fronta dokonce dosahuje logaritmické složitosti, to z ní dělá velice silného kandidáta pro využití. Pokud se však na aplikaci prioritní fronty podíváme důkladněji zjistíme, že složitost u operace IsElement v tomto případně nebude log n ale bude lineární, tedy n. To je způsobeno faktem, že fronta je řazena pomocí hodnoty funkce F. Pokud je hledán konkrétní prvek, musíme množinu procházet až do okamžiku nalezení. Též nastává problém v okamžiku, kdy upravujeme cenu uzlu, který je již v open listu zařazen. Nejen že tento prvek musí být nalezen a upraven, ale také musí být přesunut na správné pořadí ve frontě. Snížením ceny klesne hodnota F a tím stoupne priorita tohoto uzlu. Z těchto důvodů bude pro open list vybrána hash tabulka. U close listu je situace výrazně jednodušší. Používají se zde pouze funkce IsElement a Insert. Proto i zde bude použita hash tabulka, nabízející konstantní složitost pro tyto operace. 35

2. Analytická část

Obrázek 2.2: Křivka rotoucí náročnosti při expanzi jednoho uzlu.

2.5

Heuristiky - odhad vzdálenosti

Dalším důležitým faktorem u A* je použitá heuristika. Ta musí být konzistentní a optimistická. Nejčastěji se v odborné literatuře lze setkat s heuristikou Manhattan distance, která je definována H = |Xuzel − Xcíl | + |Yuzel − Ycíl |. Ten ale v případě Sepulcheru nelze použít pro nalezení optimální cesty, protože se nejedná o optimistickou heuristiku. Na rozdíl od reálného světa v prostředí Sepulcher má pohyb po úhlopříčce stejnou hodnotu jako pohyb po hraně (přes√ tože úhlopříčka má délku 2). Další p používanou heuristikou je eklidovská metrika definována vzorcem H = (Xuzel − Xcíl )2 + (Yuzel − Ycíl )2 . I přestože se v reálném světě jedná o heuristiku optimistickou, v našem prostředí pro ni platí stejný závěr jako u Manhattan distance. Navíc heuristika nevrací celá čísla, což by se mohlo jevit jako další nedostatek. Optimistickou a konzistentní heuristikou v prostředí Sepulcher je diagonal distance, H = max(|Xuzel − Xcíl |, |Yuzel − Ycíl |). Zde platí stejné pravidlo a to takové, že pohyb po diagonále je stejně drahý jako pohyb do ostatních směrů. Protože je vyžadováno, aby bylo vždy nalezeno optimální řešení, bude A* používat právě tuto techniku. Díky faktu, že heuristika je optimistická, je možné některá prohledávání omezená hloubkou rovnou prohlásit za neřešitelná. Tato kontrola bude použita v okamžiku, kdy od hráče přijde požadavek na pohyb, který je omezen počtem zbývajících kroků (tedy je omezen hloubkou). V případě, že heuristika bude 36

2.6. Jump Point Search mít větší hodnotu než je počet kroků, požadavek bude zamítnut a nebude se zbytečně plýtvat prostředky serveru.

2.5.1

Více informovaná heuristika

Vytvořit a navrhnout vlastní více informovanou heuristiku není triviální úkol. Heuristika, jak už několikrát bylo zmíněno, musí být optimistická a konzistentní. Navíc její výpočet musí být rychlý, aby nezatěžoval výpočetní prostředky. V úvaze nad více informovanou heuristikou byla využita skutečnost prostředí Sepulcher, že jednotlivé dlaždice jsou součástí místností (viz analýza prostředí). Místnosti tedy tvoří graf o maximální velikosti 49 × 49 = 2 401 uzlů (dlaždic v tomto grafu je 16 × 492 = 38 416). Tento graf by se na začátku algoritmu prohledal do šířky a posléze by hodnota heuristiky odpovídala vzdálenosti dané místnosti od místnosti s cílovou dlaždicí. Při testovací implementaci se ukázalo, že heuristika je optimistická i konzistentní, ale hodnoty, které vrací, jsou příliš malé a A* expanduje více uzlů než s použitím diagonal distance. Výsledkem analýzy A* a heuristik je rozhodnutí, že pro datové kontejnery budou použity hashovací tabulky a zvolenou heuristikou bude diagonal distance.

2.6

Jump Point Search

V prostředí, ve kterém se Sepulcher odehrává a které je popsáno v předešlé části, je prostředí známé a často ve hrách používané. Jedinou jeho odchylkou je nižší cena při pohybu po úhlopříčce. Je známo, že v mnoha hrách se používá prostředí známé jako mřížka a vyhledávací algoritmus A*. Optimalizací tohoto vyhledávajícího algoritmu v prostředí mřížky se zabývá Daniel Harabor. V práci (19) využívá vlastnosti Manhattanské metriky, tedy, že cesta mezi dvěma body v mřížce je vždy stejně dlouhá, ať se vybere jakákoliv posloupnost hran mířících k bodu B. Mapa je poté rozdělena na čtverce (v případě Sepulcheru by šlo využít místnosti) a hledání vně čtverců se v problému nezabýváme. Tento způsob však lze použít pouze pokud je pohyb omezen na čtyři základní směry a proto je toto řešení pro Sepulcher nevhodné. Druhou variantou a pro Sepulcher mnohem zajímavější, je práce (20) zabývající se prořezáváním sousedních uzlů a nazvaná Jump Point Search, který upravuje A*. Prvním krokem v algoritmu Jump Point Search (JPS) je ořezávání. Z uzlu vyloučíme všechny následovníky, do kterých se lze dostat z rodiče za stejnou nebo levnější cenu. U diagonálního pohybu se jedná pouze o levnější cestu. Sousedi, kteří po tomto kroku zbudou, však ještě nejsou finální. Následuje krok nazvaný Jump (odtud jump point), při kterém ve směru potomka přeskočíme všechny uzly, které by po ořezání měly maximálně jednoho souseda. 37

2. Analytická část

Obrázek 2.3: Prohledaný prostor v závislosti na algoritmu. Délka optimální cesty je 16 kroků. A JPS, expanduje 7 uzlů, což je méně než délka optimální cesty. B A*, expanduje 73 uzlů.

První uzel, který nelze přeskočit, je zařazen do finální množiny potomků právě zkoumaného uzlu. V práci (20) jsou dobře popsané používané algoritmy a podmínky pro JSP a je zde uveden důkaz, že cesta nalezená JPS při optimistické heuristice, bude optimální. Na začátku práce o JPS je dán požadavek na prostředí. Vyžaduje prostředí mřížky s pohybem do 8 směrů s cenou jednoho kroku do základních směrů a √ 2 kroku při posunu po úhlopříčce. Fakt, že délka úhlopříčky v Sepulcheru je menší, JPS v nalezení optimální cesty neovlivní. Pouze bude expandováno více uzlů (s délkou úhlopříčky 1 lze prořezat více sousedů). Při implementaci však bude použit nezměněný algoritmus. Nalezená cesta vypadá mnohem přirozeněji a to díky tomuto lehkému znevýhodnění pohybu po úhlopříčce.

2.7

Lightning-Fast A*

Jedním z algoritmů, který bude zvažován pro použití v aplikaci, bude kombinace doposud nabytých znalostí. Pro implementaci A* a použitých struktur budou využity rady z knihy (6) uvedené také v teoretické části. Bude zvolena optimistická heuristika a práce se sousedy bude podle pravidel Jump Point Search uvedené v předchozí kapitole. Tento algoritmus bude označen 38

2.8. Výběr algoritmu pro hledání cest jako Lightning-fast A* (LFA). Implementace algoritmu nebude používat předdefinované .NET kolekce. Tím se odstraní případná nadbytečná režie a budou implementovány funkce přesně odpovídající požadavkům. Výjimkou bude hash tabulka, jejíž implementace je složitější a také by vyžadovala větší množství času na testování. Další změna se týká zatížení memory managera. To se sníží na minimum pomocí návrhového vzoru pool – tedy potřebné instance se vytvoří předem a za běhu algoritmu jsou recyklované. V případě, že v poolu nebude dostatečný počet instancí, vytvoří se pro něj nová. Horní limit počtu instancí v poolu nebude definován. Open list bude rozdělen na dva listy. První list, s optimální kapacitou 15 prvků, je obousměrně zřetězený seznam se zarážkami tříděným algoritmem insert-sort. Druhý list pak bude jednosměrně zřetězený seznam. Při vkládání uzlu do open listu se zkontroluje, zda není možno uzel vložit do tříděného seznamu, který obsahuje nejmenší prvky v open listu. Kontrola, zda je do seznamu prvek vhodný, se provede porovnáním s posledním prvkem (tříděný seznam se zarážkou má složitost na tuto operaci O(1)). Pokud se uzel do tříděného seznamu nehodí, je uložen do jednosměrně zřetězeného listu. Při hledání nejlepšího uzlu v open listu se pak bere první prvek ze tříděného seznamu. Pokud bude seznam prázdný, naplní se do optimální kapacity z netříděného seznamu. Sousední uzly budou prohledávány a prořezávány podle pravidel Jump Point Search. A* bude využívat optimistickou heuristiku diagonal distance. Kombinací znalostí, které mají co nejvíce zefektivnit problém hledání cest, by se mělo dosáhnout nejlepšího výsledku. Předpoklad autora (na základě předběžného měření Jump-Point) je minimální úspora oproti Jump-Point. Navíc použití vlastních kolekcí znamená zvýšenou časovou náročnost na implementaci a především na testování.

2.8

Výběr algoritmu pro hledání cest

Tato část je věnovaná volbě algoritmu pro hledání cest, použitých při implementaci serverové aplikace. Uvažovanými kandidáty budou všechny možné přístupy doposud popsané v této práci a vypsány v tabulce 2.2. Mezi požadavky na aplikaci je deterministické chování umělé inteligence, proto je nutné, aby nalezené cesty byly optimální. Také pro hráče je důležitá optimálnost, protože při pohybu na vedlejší dlaždici nechce oběhnout celou hrací plochu. To se může stát například s prohledáváním do hloubky. V prvním kroku výběru algoritmů tedy vyloučíme všechny ty, které negarantují nalezení optimální cesty. Dále můžeme vyloučit uniform cost search, který se v prostředí, ve kterém se Sepulcher odehrává (mřížka s cenou pohybu vždy za jeden bod), chová stejně jako prohledávání do šířky. 39

2. Analytická část Algoritmus Prohledávání do šířky Uniform-coast search Prohledávání do hloubky A* Weighted A* Jump point search Lighting-fast A* Iterative deeping search

Optimálnost Ano Ano Ne Ano Ne Ano Ano Ano

Tabulka 2.2: Algoritmy pro hledání cest a jejich optimálnost.

Iterative deeping search nemůže být časově lepší než prohledávání do šířky. Protože testujeme rychlost hledání, ne požadovanou paměť, nemusíme nadále iterative deeping search brát na zřetel. U algoritmů používajících heuristiku pro odhad vzdálenosti uzlu od cíle, je jediná přípustná heuristika taková, která je konzistentní a optimistická. Tedy její použití neovlivní nalezení optimálního řešení. Použitou heuristikou bude diagonál distance. Výběr ze zbylých algoritmů bude proveden na základě měření výpočetní náročnosti na sérii testů. Měření bude probíhat nad množinou náhodně vygenerovaných grafů s náhodným výběrem dvou uzlů — počáteční a cílový. Takovýto problém potom bude předán k řešení jednotlivým algoritmům. Jednotlivé ceny nalezených cest se budou mezi sebou porovnávat, čímž se bude kontrolovat správná implementace algoritmů. Testy budou rozděleny do třech skupin podle maximálního počtu uzlů, které grafy mohou obsahovat. Malé grafy Grafy, které obsahují maximálně 400 uzlů, což je 25 místností na herní ploše. To je velikost, která se nejvíce blíží klasické herní situaci stolní společenské hry Castle Ravenloft, kterou je Sepulcher inspirován. Předpokládá se, že tato situace bude nastávat v kratších hrách. Střední grafy Střední grafy obsahují maximálně 15 376 uzlů, tedy 961 místností. Takto velká hrací plocha je hranice únosnosti a většina her by se k této hranici neměla přiblížit. Velké grafy Tato nejnáročnější skupina obsahuje až 38 416 uzlů v 2 401 místnostech. Toto je maximální počet uzlů, které hra bude podporovat. Takto velké mapy jsou abnormální a nepředpokládá se, že by nějaká herní plocha 40

2.8. Výběr algoritmu pro hledání cest Algoritmus Prohledávání do šířky A* Jump point search Lightning-fast search

Malé grafy 16 1 2 2

Střední grafy 1 265 420 183 185

Velké grafy 4 522 1 385 479 495

Tabulka 2.3: Naměřená rychlost testovaných algoritmů.

Obrázek 2.4: Roustoucí časová náročnost grafu v závisloti na počtu uzlů.

dosáhla této velikosti. Tak velká mapa by byla velice nepřehledná a přejít z jednoho konce na druhý bez překážek by trvalo přibližně 40 tahů. V tomto případě se nejlépe ukážou schopnosti jednotlivých testovaných algoritmů.

2.8.1

Výsledek měření

V tabulce 2.3 jsou uvedeny výsledky měření časové náročnosti pro jednotlivé problémy. Na grafu 2.4 je pak zobrazen trend růstu časové náročnosti v závislosti na počtu uzlů grafu. Pro lepší přehlednost je z grafu vypuštěn lightning-fast algoritmus, který má křivku totožnou s jum point search.

41

2. Analytická část Jump point search JPS a LFA dopadly nejlépe s velkým náskokem před ostatními algoritmy. Tento výsledek ukazuje, že na prohledávání grafu je nejvíce náročná práce s open listem, tu JPS výrazně omezuje za cenu vyšší režie při expanzi uzlu. Při porovnání práce vykonané s open listem je výrazně méně časově náročná. Paměťová náročnost, vzhledem k počtu uzlů v listech, je také velice malá v porovnání s jinými přístupy. JPS bude využit při hledání cest pro pohyb hráčem ovládaným hrdinou, protože velice rychle zjistí, zda dlaždice, na kterou se chce hráč přemístit, je v dosahu. Také ji budou používat protivníci, kteří útočí na konkrétního hrdinu. Bude efektivnější pětkrát spustit JPS (pro každého hrdinu jeden) než jednou prohledávat do šířky. Prohledávání do šířky Očekávaně nejhůře dopadlo prohledávání do šířky. Přesto tento přístup bude při implementaci aplikace také použit. Bude určen pro případy, kdy by bylo použití JPS velice nevýhodné. Takovým příkladem je AI analýza blízkého herního prostředí. Ta nastává mimo jiné v okamžiku příchodu dotazu na dostupnost dlaždic k pohybu. Také umělá inteligence prohledává svůj blízký prostor, aby zjistila, jaké má možnosti. Lightning-fast A* LFA dosahuje předpokládaných hodnot, tedy nezlepšuje rychlost jump pointu search - naměřené hodnoty jsou téměř totožné. Důvodem toho je zřejmě dobrá implementace C# struktur a memory managera. Také jump point search výrazně snižuje potřebu manipulace s open listem a tím zastiňuje použití speciální implementace open listu. V implementaci serverové aplikace nebude tento přístup použit z důvodu větší časové náročnosti na testování a žádného zlepšení v časové náročnosti prohledávání grafu. A* Klasický A* algoritmus dosahuje dobrých výsledků, je však pomalejší než jeho vylepšená verze jump point search a proto zde není žádný důvod, proč ho v implementaci použít.

2.9

Vzhled cesty

Mimo požadavku na nalezení optimální cesty budeme na prohledávací algoritmy klást také požadavek na vzhled nalezené cesty. Pokud cesta z počátečního uzlu do cílového uzlu existuje, je pravděpodobné, že optimálních cest bude více. Algoritmus by tedy měl vybrat takovou cestu, která je pro lidského pozorovatele co nejpřirozenější. 42

2.10. Komunikační protokol – návrh a analýza Nejprve se musí definovat pojem „nejpřirozenější cesta“. V našem světě jsme zvyklí na fakt, že úhlopříčka čtverce je delší než jeho strana. Zároveň ale vnímáme, že je výhodnější jít po úhlopříčce, než čtverec obcházet po hranách. Jinak řečeno, hledáme takovou cestu, která je optimální co do počtu prošlých dlaždic (prošlých uzlů) a takovou, která je nebo se co nejvíce blíží k optimálnosti fyzické délky. Příkladem různých optimálních cest je vidět na obrázku 2.5. Všechny tři cesty jsou optimální a mají délku 7 dlaždic. Pro prohledávací algoritmy jsou všechny tři stejně dobré a výsledkem bude první nalezená. Cesta A a C však vypadají velice nepřirozeně. Kdyby se po této trase vydal model, působilo by to√nerealisticky a komicky. Je to tím, že fyzická vzdálenost na cestě A a C je 6 2 + 1 = 9, 4 (při předpokladu že strana dlaždice měří jednu jednotku). Jakým způsobem budou algoritmy volit cestu tak, aby byla co nejkratší? Rovnou vyloučíme možnost hledat všechny optimální cesty v zadaném problému a z nich vybrat tu fyzicky nejkratší. Tento algoritmus „řešení hrubou silou“ by velice zatížil výpočetní prostředky (a potřebný čas) potřebné k nalezení cesty. Jak bylo uvedeno v předešlé kapitole, v implementaci serverové aplikace budou pro hledání cest využity JPS a prohledávání do hloubky. Nebude se řešit problém pro oba algoritmy najednou, ale budeme hledat řešení individuálně. U JPS je problém triviální a již vyřešen faktem, že nebyl upraven pro prostředí, ve kterém je délka úhlopříčky stejně dlouhá jako délka strany čtverce. Tím, že je pohyb po úhlopříčce lehce diskriminován (bez ztráty optimálnosti), je nalezená cesta sub-optimální, co se fyzické délky týče. U prohledávání do šířky se také pokusíme diskriminovat úhlopříčku jako u JPS. Toho dosáhneme správným pořadím vkládání potomků do open listu. Nejprve vložíme potomky, kteří leží na základních čtyřech směrech, teprve poté vložíme potomky na diagonále. Na obrázku 2.5 je vidět, jak se vzhled cesty mění s tím, v jakém pořadí vkládáme potomky do fronty.

2.10

Komunikační protokol – návrh a analýza

Při návrhu komunikačního protokolu je nutno brát v potaz následující skutečnosti: Technologie klienta: C#, XNA Framework, .NET Framework 4 Důležité především proto, že lze posílat živé serializované objekty mezi klientem a serverem, pokud jsou oba implementovány na stejné technologii. Technologie serveru: C#, .NET Framework 4 Rychlost komunikace: pomalejší rychlost je akceptovatelná Protože se jedná o tahovou strategickou hru, není nutné mít okamžitou 43

2. Analytická část

Obrázek 2.5: Vzhled optimální cesty. Změna tvaru optimální cesty v závislosti na pořadí vkládání potomků do open listu. Cesta nalezena pomocí prohledávání do hloubky. A Potomci vkládáni podle směru hodinových ručiček. B Potomci vkládáni podle směru - preferován směr kurzorových kláves. C Potomci vkládáni podle směru - preferován diagonální směr. dé linky znázorňují strom vzniklý procházením grafu.

odezvu jako u akčních her, ve kterých záleží na každém okamžiku. Komunikace však musí být dostatečně rychlá, aby nezpomalovala klienta. Úroveň chybovosti komunikace: bezchybná komunikace Aby všichni hráči vždy viděli stejný obraz a nedocházelo tedy k out-of-syn, je vyžadována bezchybná komunikace. Také odeslaná data musí dorazit ve stejném pořadí, jak byla odeslána.

2.10.1 2.10.1.1

Komunikační protokol UDP (User diagram protokol)

Jedná se o komunikační protokol z rodinu TCP/IP protokolů. Protokol UDP je vhodný pro nasazení pro aplikace pracující systémem otázka-odpověď (9), což by se při komunikaci s klientem velice hodilo. Příkladem takové komunikace může být dotaz na server, kdo je právě na řadě. Oproti protokolu TCP má UDP hlavička méně dat a tím i menší režii. Tento protokol však negarantuje doručení odeslaných diagramů. Také doručení diagramů může být v jiném pořadí, než jak byly odeslány. NET Framework 4 poskytuje pro UDP komunikaci třídu UdpClient(10). 44

2.10. Komunikační protokol – návrh a analýza 2.10.1.2

TCP (Transmission Control Protocol)

Druhou možnou uvažovanou variantou protokolu je TCP, který je také z rodiny protokolů TCP/IP. Na rozdíl od UDP tato varianta garantuje bezchybné doručení odeslaných dat a to i ve stejném pořadí jak byla odeslána. Jeho režijní náklady jsou však větší kvůli většímu množství informací v hlavičce. I pro tento typ komunikace nabízí .NET Framework 4 třídu s názvem TcpClient (11). TCP protokol přesně odpovídá předem uvedeným požadavkům. Bezchybnost a dodržené pořadí odeslaných a přijatých dat, což je kompenzováno menší rychlostí, která nevadí. Proto bude upřednostněn před komunikačním protokolem UDP a použit při implementace serverové aplikace.

2.10.2

Formát odesílaných dat

Další volbou je formát odesílaných dat. 2.10.2.1

Binární data

Odesílání řetězce bajtů, jehož interpretace přesně a minimalisticky odpovídá komunikační zprávě, je první uvažovanou možností. Výhodou je malá velikost odesílaných dat, kdy se odesílá informace zakódovaná do binárního řetězce. Nevýhodou tohoto přístupu je vyšší časové náročnost na návrh a specifikaci kódování. Také, protože jde o vlastní novou implementaci, je potřeba věnovat úsilí testování. Tato forma dat nevyžaduje, aby klient používal stejnou technologii jako server. 2.10.2.2

Serializované objekty

Při procesu serializace se živý objekt převede do své sériové podoby. To poskytuje snadnou a rychlou možnost, jak komunikovat s klientem bez nutnosti další implementace. Zároveň, aby klient rozuměl příchozí zprávě, je nutné, aby klient i server sdíleli knihovnu objektů a byli tedy napsáni stejnou technologií. Přenesených dat oproti prvnímu uvažovanému způsobu bude také více, protože je zde přídavná režie na metadata. 2.10.2.3

Textový protokol

Poslední uvažovanou možností je forma textová. Máme již více předem definovaných možností, jaký textový formát využít. Protože .NET Framework 4 nabízí jednoduchou možnost práce se SOAP (Simple Object Access Protocol), který vnikl za podpory Microsoftu v roce 1998(12), bude uvažován právě tento formát jako zástupce textových formátů. 45

2. Analytická část Textové protokoly mají výhodu své univerzálnosti. Nevyžadují žádnou společnou technologii a jsou většinou velice dobře čitelné i pro člověka. Protokol SOAP je založený na XML, což je nesporná výhoda, protože většina moderních programovacích jazyků nabízí dobře zpracovanou funkcionalitu pro práci se XML soubory. Protože jsou všechny údaje uvedeny mezi xml tagy, velikost dat narůstá. Nepředpokládá se, že by v budoucnu vznikl klient na jiné technologii než .NET Framework, proto bude jako forma odesílaných dat použita druhá varianta, tedy serializované objekty. V rychlosti přenosu je to zlatá střední cesta a díky tomu, že není požadavek na vysokou rychlost, můžeme při implementaci ušetřit čas, který by byl třeba k vypracování návrhu binárního protokolu.

2.11

Návrh komunikace

Návrh komunikace bude vycházet z původní hry Sepulcher. Základní myšlenkou je: Logika hry je vykonána mnohem rychleji, než je hráči přehrána. Proto se mezi logiku hry a prezentační vrstvu vloží fronta. Do této fronty se ukládají příkazy reprezentující provedenou akci z logiky. Prezentační vrstva si pak z této fronty příkazy postupně vybírá a zobrazuje je hráči. V případě komunikace klienta se serverem se tohoto modelu dá využít. Pokud předpokládáme, že prezentace daného příkazu bude v celém systému nejnáročnější na čas (přesun postavy na serveru je záležitost do milisekundy, zatímco přehrání animace může trvat i několik vteřin), klient bude vždy čekat pouze na první příkaz od serveru a než ho vykoná, bude již ve frontě další. Pro posílání těchto příkazů bude použit návrhový vzor Command pattern. Ten je velice dobře popsán buď na stránkách (14) nebo v knize (5). Command pattern si pro náš účel upravíme, což není nic proti logice návrhových vzorů. Úprava se bude týkat faktu, že command pattern má do objektu zabalit funkci, která se posléze vykoná. Protože není známá vnitřní implementace klienta, není jak napsat funkcionalitu této balené funkce. Místo funkce se tedy zabalí pouze popis, co má příkaz vykonat a jeho seznam parametrů. Zavolání příslušné funkce se ponechá klientovi. Klient však může mít dotazy na server, na které bude potřebovat okamžitou odpověď. Například kdo je na řadě. Proto mezi serverem a klientem budou otevřené dva komunikační kanály. První asynchronní kanál bude sloužit pro odesílání příkazů na klienta, které si bude ukládat do fronty. Server nebude na tomto kanálu přijímat data, bude pouze v případě potřeby do tohoto kanálu data ukládat. Druhé spojením je synchronní kanál, bude fungovat jako volání funkce, tedy otázka-odpověď. Klient do kanálu zapíše dotaz, server ho vyhodnotí a odešle na tomto kanálu odpověď, na kterou klient čeká. 46

2.12. Domain model - herní logika

Obrázek 2.6: Kanály mezi klientem a serverem.

Obrázek 2.7: Asynchronní kanál a fronta.

2.12

Domain model - herní logika

Při návrhu herní logiky byl kladen velký důraz na vysokou úroveň abstrakce. Téměř veškeré třídy jsou abstraktní a k tomu je zde použito mnoho rozhraní, aby byla co nejvíce usnadněna případná rozšiřitelnost hry o nové prvky. Názvy tříd byly voleny tak, aby co nejvíce vypovídaly o reprezentaci a poskytované funkcionalitě. Proto budou níže zmíněny jen ty nejzajímavější třídy. Game je centrální třídou herní logiky. Zajišťuje funkcionalitu konce kola a začátku nového a vyhodnocuje souboje. Také tato třída funguje jako komunikátor s rozhraním IGameHolder, které zajišťuje odesílání dat klientovi. Třídy Map, Room a Tile je reprezentace herní plochy, která se dá chápat jako graf. Tyto třídy jsou používané algoritmy pro hledání cest. Adventure určuje, jaké dobrodružství se hraje. Generuje mapu a kontroluje, zda byly splněny podmínky vítězství nebo prohry. Interface IArtificialIntelligence implementují třídy, za které hraje server. Interface ITileOccupation implementují všechny modely, které mohou stát na dlaždici, aby však takový model mohl být zaměřen dovedností (jak plošnou tak cílenou), musí implementovat interface ITargetable. 47

2. Analytická část

Obrázek 2.8: Domain model herní logiky.

2.13

Domain model - serverová aplikace

Při návrhu serverové logiky byla snaha o co největší odstínění od herní logiky. Jediným bodem mezi herní a serverovou logikou je relace mezi IGameHolder a Game. Každý připojený klient dostane své vlákno. To většinu času bude spát a čekat na příchod požadavku. Pokud požadavek obdrží, vlákno ho zpracuje. To znamená, že při obdržení požadavku na konec kola vlákno vyhodnotí všechny události s tím spojené, jako je ovládání umělé inteligence. Následuje popis jednotlivých tříd, jejichž funkcionalita nemusí být na první pohled jasná. ClientHandler Kdykoliv je se serverem navázáno spojení, je vytvořen ClientHandler, kterému se předá komunikační kanál. Tato třída se může nacházet ve dvou stavech. V prvním, na začátku komunikace s klientem, řeší inicializační zprávy obsahující informace o hře a hrdinech. Na konci této fáze mu server posílá jeho identifikační číslo. 48

2.13. Domain model - serverová aplikace

Obrázek 2.9: Domain model serverové logiky. V druhém stavu, v nekonečné smyčce, čte z proudu požadavky od klienta a předává je IGameHolder. Tato třída umí z kanálu číst i zapisovat a je to jediný bod, přes který lze s konkrétním klientem komunikovat. IFormatter IFormatter je rozhraní z .NET Frameworku a zajišťuje serializaci objektů. Mezi předvytvořené implementace IFormatter patří BinnaryFormatter nebo SoapFormatter. O vlastní implementaci ServerFormatter se lze dočíst v kapitole 3.2. IServerEngine – MainServerEngine Tato třída udržuje všechny aktivní hry. Její úkolem je dále vytvářet nové herní instance a mazat dohrané a ty bez hráčů (pokud se všichni odhlásí). IGameHolder – GameHolder Je článkem mezi hráčem a hrou. Přijímá přes ClientHandler od hráče po49

2. Analytická část žadavky, které předává třídě Game. A naopak, pokud se při řešení herní logiky stane událost, o které by měl být hráč informován, třída Game použije právě toto rozhraní, aby informace poslala klientské aplikaci. PlayerHolder Je pouze přepravka obsahující informace o hráči, využívané při práci IGameHolder.

50

Kapitola

Implementační část 3.1

Konvence úpravy kódu

Na začátku implementace je dobré si ujasnit, jakým způsobem bude kód formátován. To je velice důležité, především při práci v teamu, kdy každý z programátorů má vlastní styl úpravy a celek pak působí chaoticky. Přesto i při práci jedince na aplikaci je dobré dodržovat předem daný standard formátování. Konvence úpravy kódu se týká jak způsobu pojmenování proměnných, tak vzhledu samotného kódu. Níže popsaný způsob pojmenování proměnných vychází ze stylu pojmenování v knihovnách poskytující Microsoft v .NET Framorku. • Konstanty a hodnoty výčtových typů budou psány pouze velkými písmeny a slova v názvech budou oddělena podtržítky. • Jména tříd, výčtových typů a rozhraní jsou psána velbloudí notací2 s prvním písmenem velkým. • Názvy funkcí a proměnných s přístupovým právem private nebo protected jsou psány velbloudí notací s prvním písmenem malým. • Property, proměnné a funkce s přístupovým právem public jsou psány velbloudí notací s prvním písmenem velkým. Díky tomuto stylu pojmenování je podle názvu hned znát, jakou má funkce nebo proměnná viditelnost. Při implementaci budou psány závorky otevírající blok kódu na stejném řádku, jako konstrukce jej používající. Koncové závorky jsou vždy samostatně na vlastním řádku. Jsou dovoleny jednořádkové řídící konstrukce. 2

Velbloudí notace píše jméno proměnné složené z více slov stylem, že každé další slovo začíná velkým písmenem. Všechna ostatní písmena jsou malá. Používají se pouze písmena, speciální znaky a číslice by se neměly používat.

51

3

3. Implementační část

3.2

Implementace protokolu

3.3

Synchroní komunikace

Klient a server mezi sebou komunikují pomocí posílání objektů, které spolu sdílejí přes SepulcherCommon. V počáteční fázi implementace navržený protokol dosahoval očekávané rychlosti a spolehlivosti komunikace. Posléze se ukázalo, že původní návrh je chybný a to v bodě synchronního komunikačního kanálu. Pro klientskou aplikaci bylo v některých situacích velice náročné čekat na vyhodnocení zaslaného požadavku. I přes pokus co nejvíce urychlit práci vykonanou serverem a zasláním odpovědi téměř okamžitě nazpět, bylo na klientské aplikaci viditelné zpoždění. Proto byl synchronní kanál nakonec úplně odstraněn. Stále zůstala potřeba na některé dotazy klientovi odpovídat. Zaslané objekty byly rozděleny na dva typy – systémový a normální. Ve skupině systémových příkazů jsou všechny příkazy, které se přímo netýkají prezentace, tedy i odpovědi na některé požadavky, které to vyžadují. Protože se komunikuje na asynchronním kanále, nemá klient jistotu, že příští přečtený objekt bude odpovědí na dotaz. Server ale garantuje, že první systémový příkaz bude požadovanou odpovědí. Proto, pokud klient posílá více dotazů, ukládá si tyto příkazy do fronty. Tak jak z kanálu přicházejí, páruje je s vrchními dotazy fronty. Odpověď tedy nedostane okamžitě, ale vzniklá prodleva není patrná.

3.3.1

Porovnání velikosti odesílaných dat

V analytické kapitole byly navrženy tři způsoby, v jakém formátu lze data odesílat. Po vyřešení problému se synchronní komunikací a následném testování rychlosti, které probíhalo na lokální síti, bylo stále při některých obtížnějších operacích nepatrné zpoždění. Přestože několik nezávislých pozorovatelů si při hraní tohoto zpoždění nevšimlo, problém je nutné řešit z obavy, že se na Wide Area Network (WAN) zpoždění prohloubí. Prvním změnou je zrušení objektů obsahující kolekce a nahradí je posloupnost menších objektů. Například pokyn k pohybu obsahoval jméno modelu a seznam dlaždic, které model musí projít. Místo toho bude pro každou dlaždici v seznamu klientovi odeslán příkaz obsahující jméno modelu a pozici, na kterou se má hnout. Tato změna byla provedena, aby ke klientovi dorazil první příkaz co nejdříve a ten ho mohl začít vykonávat. Než ho vykoná, bude mít ve frontě další příkaz a tím se tedy sníží celkově viditelná prodleva. Dalším krokem bude měření velikosti odeslaných dat. Měřit budeme formáty zmíněné v kapitole 2.10. BinaryFormatter jako zástupce klasické serializace objektů, SoapFormatter bude zastupovat textové formáty a pro čistá data bude navržen jednoduchý bitový formát. Několik ukázkových příkazů bude uloženo do souboru a porovnána jejich velikost. 52

3.4. Problém zvýraznění dlaždic Příkaz Konec kola

SoapFormatter 922 bajtů

BinaryFormatter 343 bajtů

Bajtový formát 1 bajt

Tabulka 3.1: Velikost nejjednoduššího příkazu. Objekt MoveCommand HightlightCommand State Ping

SoapFormatter 1 270 bajtů 1 287 bajtů 998 bajtů 895 bajtů

BinaryFormatter 505 bajtů 594 bajtů 488 bajtů 339 bajtů

Bajtový formát 6 bajtů 6 bajtů 2 bajty 1 bajt

Tabulka 3.2: Porovnání velikost objektů v závislosti na formátu.

Měření nejprve provedeme na nejjednodušším možném příkazu a to na požadavku ukončení kola. To v čistě binárním formátu zabere jediný bajt, tedy příznak příkazu. Velikost pro různé formáty je vidět v tabulce 3.1. Na základě tohoto měření, které mělo proběhnout již v analytické části, bylo rozhodnuto, že se nebudou posílat pomocí serializace živé objekty, ale vytvoří se vlastní bitový formát. Práci nám ulehčí C# s rozhraním IFormatter, díky kterému se nebudou muset dělat žádné výrazné úpravy kódu. Do abstraktní třídy SepulcherCommand, od které dědí všechny objekty používané ke komunikaci, bude přidána abstraktní funkce ToBajtArray(). Objekt převede do bajtové podoby. Také každý příkaz bude mít konstruktor, který bude vyžadovat komunikační kanál. Z něj si pak sám načte potřebné bajty, které bude správně reprezentovat, čímž si inicializuje všechny vnitřní proměnné. V tabulce 3.2 je pak vidět několik základních, často používaných objektů a jejich velikost při odesílání. Z naměřených hodnot, které jsou uvedené v tabulce 3.2, je vidět obrovská úspora přenesených dat s využitím binárního formátu. Po implementaci a nasazení SepulcherFormater, klientská aplikace neměla sebemenší viditelné zpoždění. Toto měření mělo proběhnout již v analytické části. Hodnoty se od sebe tak výrazně liší, že by bylo již před implementací jasné využít binární formát. Je třeba dodat, že s novou implementací protokolu se již neklade žádný požadavek na technologii klienta. Společná knihovna SepulcherCommons bude používána i nadále, ale není již pro běh a komunikaci potřebná.

3.4

Problém zvýraznění dlaždic

Každý hratelný hrdina má sadu pěti dovedností, které se od sebe liší efektem a oblastí zásahu. Když hráč zvolí dovednost, musí se mu zobrazit oblast, kterou 53

3. Implementační část je možno zasáhnout. Tato oblast se odvíjí od pozice hrdiny (ta je při výběru cíle statická) a dlaždicí, nad kterou je kurzor myši. Protože je oblast vždy překreslena, pohne-li se ukazatel na jinou dlaždici, dochází v přístupu, kdy vše vypočítává server, k velké časové prodlevě. Ta je způsobená přenosem požadavku na server a jeho odpovědí. Způsob kdy vše vypočítává server, je použit u zvýraznění dlaždic, na které se může hrdina přesunout. Je to zapříčiněno tím, že pozice hrdiny je statická a oblast se posílá klientovi pouze jednou po každém přesunu. Data klient obdrží dříve, než se přehraje animace pohybu a vše působí plynule. Nejlepším řešením by bylo, kdyby klientská aplikace sama vypočítávala zvýraznění. To však není možné. Z důvodu požadavku nulové funkcionality na klientskou aplikaci i faktem, že klient nemá dostatečné množství informací pro správné zvýraznění. Pro řešení toho problému bylo nakonec nutné vytvořit sekvenci příkazů. Při příchodu požadavku na zvýraznění dosahu dovednosti server nejprve odešle příkaz obsahující základní informace pro obarvení, kterými jsou: Vzhled a barva zasažené oblasti, počet dlaždic, které lze zacílit. Po odeslání tohoto příkazu okamžitě začne odesílat informace o jaké dlaždice se jedná. Tím předá klientské aplikaci dostatečné množství informací pro správné obarvení oblasti v závislosti na pozici kurzoru. Pro usnadnění implementace klientské aplikace je do sdílené knihovny SepulcherCommons přidána třída, která umí tato data reprezentovat. Této třídě se předají informace ze serveru a pozice kurzoru. Výsledkem je tabulka se záznamy: souřadnice dlaždice — barva. Tento způsob je pro požadavky uvedené v design dokumentu vyhovující. Také se odesílá relativně malé množství dat, přesto zůstává požadavek na zvýraznění dovednosti jeden z nejnáročnějších. U toho způsobu je nevýhodou, že tvar oblasti musí být statický a nelze ho dynamicky měnit například v závislosti na vzdálenosti od hrdiny. To klade omezení na návrh dovedností v případném rozšíření.

3.5

Testování

Testování je důležitá součást vývoje softwaru. Nedostatečně otestovaný software má velkou pravděpodobnost na výskyt chyb, což povede k nespokojenosti zákazníka, reklamacím a dalším výdajům na vývoj. U počítačových her je to obzvláště důležitá část, protože výskyt chyb ve hře hráče odrazuje. Na modelu Free-To-Play je u hraní drží pouze zábava (žádný pocit z promarněné investice). Když bude zážitek z hraní ovlivněn chybami, tak s největší pravděpodobností od hry odejdou. To v případě multiplayerové hry by byl problém. Proto ani při implementaci této aplikace nebylo zapomenuto na testování.

54

3.6. Základní testování Jaké jsou další důvody testování? • Měření kvality. • Odhalení chyb před nasazením ulehčuje následnou údržbu programu a snižuje její cenu. • Lze odhalit rizikové partie programu nebo nedostatečnou specifikaci. • Nalezení funkcí, které vyžadují optimalizaci. O testování a dalších jeho výhodách by se toho dalo napsat velice mnoho. To ale není cíl této práce, proto těm, kteří mají zájem o tuto problematiku, lze doporučit publikací (13).

3.6

Základní testování

Jedním ze základních způsobů testování, použitých při vývoji aplikace, jsou jednotkové testy. Jednotkové testy (unit testing) jsou základním nástrojem testování při implementaci. Jsou využívány pro testování jednotlivých objektů nebo ještě lépe a detailněji, jednotlivých funkcí daných objektů. Microsoft ve svém produktu Visual Studio 2010 nabízí možnost vytvoření testovacího projektu, který je zaměřen na jednotkové testy. Jinou variantou je open source knihovna NUnit. O jednotkovém testování s využitím knihovny NUnit (i s příklady v C#) pojednává kniha (3). Protože jednotkové testy mohou být v jiném projektu než definice tříd a také se mohou testovat pouze některé funkcionality objektu, je dobré vyhýbat se statickým funkcím a singltonům. Zde je tedy snaha využívat dependency injection. Není to však omezení pro celou aplikaci. Návrhový vzor singlton využívající právě statické funkce, je velice silným nástrojem pro některé problémy. V takovém případě je však na zvážení, zda využít jednotkové testy. Jednotkové testy byly často při implementaci využívané, především pak u vyhledávacích algoritmů. Ty byly testovány nejvíce z celé aplikace, což je i díky experimentům provedených v analytické části. Tyto algoritmy byly vždy spouštěny nad grafy reprezentující prostředí Sepulcher a nebyly využity žádné známé benchmarky3 . Délky nalezených cest se porovnávaly a musely být pro všechny algoritmy stejné. Tento způsob testování se ukázal jako velice užitečný, především při testování heuristik. Heuristika s velmi malou odchylkou odhadu totiž vrací sub-optimální řešení pouze s velmi malou pravděpodobností(1). 3

Benchmarky jsou problémy pro testování, na které je Pro hledání cest na mapách ze známých počítačových her, z http://www.movingai.com/benchmarks/

známo řešení. jsou dostupné

55

3. Implementační část Jednotkové testy odhalily velkou spoustu drobných chyb, které byly opraveny. Některé problémy jsou však příliš specifické a nedokážou odhalit komplexnější problémy. Právě pro komplexnější pohled byli vytvořeni dva testovací klienti. První klient má textovou podobu. Je velice nenáročný a lze ho na jednom počítači spustit vícekrát. Testuje především komunikační protokol. Díky tomuto klientovi byly odhaleny některé chyby v synchronizaci vláken a se zápisem do komunikačního kanálu. Tohoto klienta lze použít v zátěžovém testu. Druhým klientem je klient grafický. Ten byl vytvořen z původní hry Sepulcher. Byla odstraněna veškerá stará logika hry a zůstala pouze prezentační vrstva. Přestože tvorba tohoto testovacího klienta byla poměrně časově náročná, jeho přínos byl výrazný. Díky grafickému klientovi bylo možno testovat rychlost protokolu nejenom pomocí poměřování číselných hodnot, ale také subjektivním pocitem. Právě to odhalilo nutnost přepsat protokol. Tohoto klienta nebude již v budoucnu třeba, protože jeho práci zastane reálná klientská aplikace.

3.7

Testy vstupních hodnot

Aplikace je autonomní jednotkou, která nevyžaduje a ani neumožňuje zásah uživatele. Jediný vstup od uživatele je zadání parametrů při spouštění aplikace. Těmi jsou IP adresa a port, na které bude server naslouchat. Testování těchto hodnot je triviální záležitost, navíc v jazyku C# existují konstrukce, které se o to samy postarají. Uživatel za běhu serveru nemá žádnou možnost, jak může jeho běh ovlivnit. Proto není v tomto směru co testovat. Aplikace též přijímá ještě vstupní hodnoty od klienta přes komunikační kanál. Klient nemusí vždy poslat korektní data (pokus o útok nebo chyba na straně klienta). Server musí umět bezchybně zpracovat všechny nesmyslné příkazy, nebo příkazy ve špatném pořadí. Pokud klient pošle serveru špatná data, bude okamžitě od něho odpojen. Byly vytvořeny tři testy vstupních hodnot: Náhodné příkazy se správným pořadím. Při tomto testu bude klient na server posílat náhodné existující příkazy, dodrží však jejich správné pořadí. Server nesmí komunikaci s klientem ukončit. Pokud klient pošle příkaz, na který nebude mít oprávnění (požadavek na ukončení kola v kole jiného hráče), server klientovi odešle zprávu, že danou akci nemůže provést. Příkazy ve špatném pořadí. Klient na server bude posílat existující příkaz ve špatném pořadí. To povede k jeho okamžitému odpojení. Server v takovém případě pouze vypíše informaci, že je klient odhlášen a spojení ukončí. 56

3.8. Zátěžový test Náhodné bajty V posledním testu bude klient na server posílat náhodné bajty, čímž bude tvořit neexistující příkazy. Očekává se stejné chování serveru jako v předchozím bodě. Testy odhalily drobný nedostatek v bloku try-catch, kdy byly odchytávány pouze některé chyby. Po opravě se už žádná jiná chyba nevyskytla. Server je implementován dostatečně robustně a nevede při špatném vstupu od klienta k chybám. Je to zcela jistě i tím, že server jakoukoliv chybu od klienta řeší odpojením. Je zde tedy jistý prostor pro optimalizaci, ve které by se server snažil danou situaci řešit méně radikálním způsobem.

3.8

Zátěžový test

Jedním z důležitých testů pro serverovou aplikaci obsluhující více klientů zároveň je zátěžový test a test hraničních hodnot. Při zátěžovém testu posíláme na server požadavky simulující práci většího množství uživatelů. Obvykle se provádí s 1,5(16) násobkem Safe Working Load, tato hodnota uvádí bezpečný počet zároveň pracujících uživatelů. Z požadavků na server vyplývá, že tato hodnota by měla mít hodnotu 100 uživatelů. Pomocí určených monitorů sledujeme chování aplikace, které porovnáváme s předem volenými cíli. Test hraničních hodnot testuje, jak se systém chová při velké zátěži. Požadavky, které jsou na server posílány, nemusí odpovídat požadavkům generující uživatel. Cílem testu hraničních hodnot je zjistit, jak se aplikace chová při velké zátěži a zda se neprojeví nějaké chyby. Oba dva testy nám poskytují informaci o maximální kapacitě zároveň pracujících uživatelů a také, na které části aplikace se zaměřit při optimalizaci. Při měření budeme sledovat dva ukazatele: Rychlost odpovědi na požadavek obarvení dlaždic. Je to nejsložitější požadavek, který server může obdržet. Musí analyzovat prostředí v okolí hrdiny, najít v něm spojence, nepřítele, překážky a všechny ostatní dlaždice, které mohou být cílem. Všechna tato data poté musí odeslat klientovi. Měřit se bude rychlost od okamžiku odeslání až po přijetí poslední souřadnice zvýrazněné dlaždice. Tento ukazatel nám poskytne číselné hodnoty, které lze snadno porovnávat. Hratelnost Je subjektivní pozorování odezvy při hraní. Takto se již odhalil problém s návrhem protokolu, a proto bude nasazen i zde. Nejprve se provede měření bez zátěže, aby se zjistily výchozí hodnoty. Při spuštění serveru a konzolového testovacího klienta na stejném počítači je 57

3. Implementační část naměřena průměrná odezva 9 ms a na LAN síti je 181 ms. Hratelnost byla v obou případech plynulá a nerušená. Při postupném zvyšování počtu klientů komunikujících přes LAN síť na počet 40 a 100 klientů, byly stále naměřené hodnoty v okolí 200 ms s plynulou hratelností. Tento výsledek je poněkud překvapující, protože na server bylo kladeno velké množství požadavků, které ale odbavoval stále se stejnou rychlostí. Je pravděpodobné, že je to způsobeno nedostatečným hardwarem, na kterém byli spuštěni klienti. Tento test byl velice přínosný, protože odhalil zásadní chyby při synchronizaci vláken, ty byly opraveny. K největší chybě docházelo při odpojení velkého množství klientů v jednom okamžiku, kdy se více vláken snažilo přistoupit k jedné asynchronní hash tabulce. Také podle chování serveru by bylo dobré se při optimalizaci zaměřit na tvorbu nové hry. Server hry vytváří sériově, což není zcela potřeba. Zde je prostor pro lepší synchronizaci vláken.

58

Závěr Hlavní úkoly, kterými bylo implementovat serverovou aplikaci s herní logikou a dobře fungujícím protokolem pro komunikaci, byly úspěšně splněny. Faktem je, že počítačová hra není nikdy dokončená a stále je do ní co přidávat. V případě Sepulcheru to může být hra více hráčů hrajících proti sobě. Přestože design dokument tuto možnost neuvádí, je v současné době tento způsob hraní velice populární a proto na něj bylo při implementaci myšleno. Nebude problém toto rozšíření dodělat. Jsou zde i úseky, zmíněné v části s testováním, vhodné k optimalizaci. Rozdělení aplikace na dvě vrstvy (serverová a herní) umožňuje jednoduchou úpravu komunikačního protokolu. Třídy jsou navíc odstíněné rozhraním, proto není problém přejít například na UDP protokol, kdyby to skutečnosti v budoucnu vyžadovaly. Návrh herní logiky je dostatečně abstraktní a s funkcionalitou, kterou nabízí, je velice jednoduché do hry přidávat nové prvky nebo upravovat stávající. Implementace nových dovedností nebo nepřátel je jednoduchá záležitost. To je dobré z důvodu balancování herních mechanik a přidáváním nových rozšíření. Doufám, že především první dvě části mé práce budou nejenom pro studenty předmětu Počítačové hry a animace přínosné. Kapitoly zabývající se Jump Point Search, který jak věřím, se v budoucnu stane standardem pro umělou inteligenci v počítačových hrách.

59

Literatura (1) Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.),Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2 (2) Roy Osherove, The Art of Unit Testing with Examples in .NET, Manning Publications Co., ISBN 1933988274 (3) Kolář Josef, Teoretická informatika, Česká informatická společnost, ISBN 80-900853-8-5 (4) Hynek Josef, Genetické algoritmy a genetické programování, Grada: Praha 2008, ISBN 978-80-247-2695-3 (5) Rudolf Pecinovský, Návrhové vzory, Computer Press, a.s. ISBN 978-80251-1582-4 (6) Steve Rabin AI Game Programming Wisdom, 2002 (7) Intelligent agent. Wikipedie : otevřená encyklopedie [online]. St. Petersburg (Florida) : Wikimedia Foundation, 2001-, strana naposledy edit. 2012-04-24 [cit. 2012-04-29]. Anglická verze. Dostupný z WWW: (8) Racionální agent. Wikipedie : otevřená encyklopedie [online]. St. Petersburg (Florida) : Wikimedia Foundation, 2001-, strana naposledy edit. 2012-03-25. Česká verze. Dostupný z WWW: (9) UDP. Wikipedie : otevřená encyklopedie [online]. St. Petersburg (Florida) : Wikimedia Foundation, 2001-, strana naposledy edit. 2012-01-02 [cit. 2012-04-29]. Česká verze. Dostupný z WWW: 61

Literatura (10) UdpClient. Microsoft Developer Network [online]. c2012. Microsoft. [cit. 2012-04-29]. Dostupný z WWW: (11) TcpClient. Microsoft Developer Network [online]. c2012. Microsoft. [cit. 2012-04-29]. Dostupný z WWW: (12) Soap. O’Reilly Media, Inc. [online]. c2010. [cit. 2012-04-29]. Dostupný z WWW: (13) Little Book of Testing - Volume I. Computers & Concepts Associates [online]. c1998. Dostupný z WWW: (14) Command pattern. diplomová práce M. Dvořáka [online]. Dostupný z WWW: (15) Umění unit testování. Webtrh Blog [online]. Dostupný z WWW: (16) Zátěžové testování SW aplikací. Miroslav Růžovský Softec CZ, spol. s.r.u. [online]. [cit. 2012-05-1] Dostupný z WWW: (17) Základní grafové algoritmy. Jakub Černý [online]. Dostupný z WWW: (18) Introduction to Genetic Algorithms. Marek Obitko [online]. Dostupný z WWW: (19) Breaking Path Symmetries on 4-connected Grid Maps Daniel Harabor and Adi Botea [online]. Dostupný z WWW: (20) Graph Pruning and Symmetry Breaking On Grid Maps Daniel Harabor [online]. Dostupný z WWW:

62

Příloha

Seznam použitých zkratek FIFO First In, First Out LIFO Last In, First Out PC Personal Computers OS Operační Systém JPS Jump Point Search LFA Lightning-Fast A* AI Artificial intelligence WAN Wide Area Network LAN Local Area Network UDP User Datagram Protocol TCP Transmission Control Protocol IP Internet Protocol

63

A

Příloha

Obsah přiloženého CD

readme.txt...................................stručný popis obsahu CD exe sepulcherServer ................. spustitelná forma SepulcherServer consoleClient................spustitelná forma konzolového klienta graphicalClient................spustitelná forma grafického klienta src sepulcherServer.......zdrojové kódy implementace SepulcherServer consoleClient......zdrojové kódy implementace konzolového klienta graphicalClient ..... zdrojové kódy implementace grafického klienta sepulcherCommon .... zdrojové kódy implementace SepulcherCommon thesis ...................... zdrojová forma práce ve formátu LATEX required .............................potřebné programy pro spuštění text.....................................text práce a design document thesis.pdf ............................. text práce ve formátu PDF thesis.ps ................................ text práce ve formátu PS design.pdf ................................. text design dokumentu documentation sepulcherServer ................. dokumentace pro SepulcherServer sepulcherCommons..............dokumentace pro SepulcherCommon 65

B