BAKALÁŘSKÁ PRÁCE
SÍŤOVÁ IMPLEMENTACE HRY TUNNELER Jiří Procházka 2010
Fakulta informatiky
Masarykova univerzita
Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.
Poděkování: Děkuji vedoucímu své práce, Mgr. Jiřímu Filipovičovi, za jeho cenné rady. Dále bych chtěl poděkovat Martinu Procházkovi, Tereze Váňové a Kateřině Váňové za podporu a korekci chyb.
Shrnutí Obsahem této bakalářské práce je vytvoření síťové multi-player hry. To zahrnuje především výběr implementačních technologií, vytvoření objektového návrhu, implementaci hry a formulaci algoritmů pro udržení konzistence herního světa.
Klíčová slova C++, OGRE, RakNet, návrhové vzory, multi-player hry, konzistence herního světa
Obsah 1 Úvod 1.1 Původní hra Tunneler . . . . . . . 1.2 Předmět bakalářské práce . . . . . 1.3 Analýza požadavků na technologie 1.3.1 Síť . . . . . . . . . . . . . . 1.3.2 Grafika . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
3 3 4 4 4 6
2 Výběr technologií 2.1 Vývojové prostředí . . 2.2 Síťový subsystém . . . 2.3 Prezentační subsystém 2.4 Vstupní rozhraní . . . 2.5 Platforma . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
7 7 7 8 8 8
3 Návrh 3.1 Síťový model a komunikace 3.1.1 Komunikace . . . . . 3.2 Návrh architektury . . . . . 3.3 Systém kolizí . . . . . . . . 3.4 Konzistence světa . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
9 9 10 10 13 13
4 Implementace 4.1 Komunikace . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Připojení, inicializace a správa spojení . . . 4.1.2 Spolehlivost a priorita . . . . . . . . . . . . 4.2 Rozdělení herních objektů . . . . . . . . . . . . . . 4.3 Herní plocha . . . . . . . . . . . . . . . . . . . . . 4.4 Konzistence světa . . . . . . . . . . . . . . . . . . . 4.4.1 Kolize střely se základnou . . . . . . . . . . 4.4.2 Kolize lokální střely s herní plochou . . . . 4.4.3 Kolize vzdálené střely s herní plochou . . . 4.4.4 Kolize vzdálené střely se vzdáleným tankem 4.4.5 Kolize vzdálené střely s lokálním tankem . 4.4.6 Kolize tanku s herní plochou . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
15 15 15 16 16 17 17 17 17 17 17 18 18
. . . . .
. . . . .
1
5 Nasazení 19 5.1 Požadavky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.2 Ovládání hry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Experimenty 21 6.1 Měření síťové komunikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2 Vliv latence na hratelnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 7 Závěr
24
A Režijní data RakNetu
26
B Obrazová příloha
27
2
Kapitola 1
Úvod 1.1
Původní hra Tunneler
Historický vývoj počítačových her je těsně svázán se stupněm rozvoje informačních technologií a dalo by se říci, že je částečně jejich katalyzátorem. Obrovský herní trh žene stále kupředu vývoj grafických karet, jejich GPU už v mnoha ohledech předčí klasický procesor. Díky tomu existují projekty distribuovaných výpočtů, které jsou schopny využít potenciál grafických karet. Jedním z nich je například známý Seti@home1 . Nezřídka jsou hry testovacím prostředím pro nové algoritmy a přístupy: šachy pro umělou inteligenci, masové konference v Second Life, simulátor pro armádu VBS1 (původem hra Operation Flashpoint), atd.
Obrázek 1.1: Snímek ze hry Tunneler. Počítačová hra Tunneler, vydaná v roce 1991, je originální procedurálně generovaným podzemním světem, ve kterém se k sobě musí dva hráči ovládající tanky prokopat. Ani jeden z hráčů netuší, kde se nalézá ten druhý, kopáním tunelů vytváří systém chodeb, 1
Více na: http://setiathome.berkeley.edu/
3
které se nakonec propojí. Proces hledání je zkomplikován herním prvkem energie tanku. Ta se musí pravidelně doplňovat na startovní pozici (základně), pro hráče je tak životně důležité zorientovat se v systému chodeb a odhadnout dostačující čas pro návrat. Současná hra dvou hráčů na jednom počítači je realizována takzvaným split-screen módem, kdy je obrazovka vertikálně rozdělena na dvě poloviny. Hra je zajímavá i z hlediska použitých technologií. Využívá speciální nedokumentovaný grafický mód s nízkým rozlišením 160 x 100 pixelů. Výseč zobrazované hrací plochy každého hráče činí 80 x 80 pixelů, což je přesně jedno procento z celého světa. 6 MHz procesor je udáván jako minimální konfigurace počítače. Autor uvádí, že při této konfiguraci může generování světa trvat až desítky sekund.
1.2
Předmět bakalářské práce
Předmětem mé bakalářské práce je implementovat hru založenou na podobném herním konceptu hry Tunneler využívající modernější technologie. To zahrnuje především implementaci pro některý moderní operační systém a implementaci síťové hry namísto hry více hráčů sdílejících jeden počítač. Mým úkolem je nastudovat technologie potřebné k vykreslování grafiky a k síťové komunikaci, navrhnout objektově orientovanou architekturu hry a formulovat algoritmy pro udržení konzistence herního světa z pohledu jednotlivých hráčů propojených sítí. V původní hře dva hráči sdíleli dohromady jeden svět, v naší implementaci počítáme s větším počtem hráčů. Hra je přenesena na více počítačů, kde každý vlastní svou kopii světa, musíme tedy zajistit, aby se tyto kopie podstatně nelišily. Drobným rozdílům nelze z technických důvodů zabránit, ale aplikace musí být vůči nim tolerantní a musí minimalizovat jejich dopady na hratelnost a spravedlivost hry. Koncept hry si žádá ponechání herní logiky ve 2D, což ovšem nevylučuje použití trojrozměrných herních objektů. Jejich prostorovost může vyniknout například dynamickým osvětlením (střely by byly zdrojem světla). Budeme potřebovat nějaký systém testovaní kolizí. V původní hře se tank skládal z dvaceti šesti pixelů, předpokládám tedy, že se kolize zjišťovaly pixel po pixelu. My budeme používat mnohem větší rozlišení, podobný způsob testování kolizí mezi objekty by nebyl optimální. Avšak jelikož jsme se rozhodli implementovat dvojrozměrnou herní logiku, testování bod po bodu se pravděpodobně nevyhneme u kolize objektu s herní plochou.
1.3
Analýza požadavků na technologie
V této kapitole rozebereme klíčové požadavky na jednotlivé subsystémy aplikace.
1.3.1
Síť
Síť umožňuje, aby hráči na více počítačích sdíleli jedno prostředí a aby akce jednoho byla přenášena k ostatním účastníkům. Síťová komunikace ale přináší řadu komplikací v po4
době kvalitativních nedostatků parametrů sítě: šířka pásma, zpoždění, rozptyl zpoždění a ztrátovost paketů. Existují síťové multi-player hry, které nemají na kvalitu sítě téměř žádné požadavky. Jedná se především o webové strategické hry jako Travian2 , jejichž komunikace se serverem je založena na metodě požadavek-odpověď, kde na zpoždění odpovědi příliš nezáleží. Tyto hry s horší kvalitou spojení počítají, server obsluhuje stovky až tisíce lidí, požadovat kvalitní spojení by nebylo z technického hlediska reálné. Akční hry typu First-person Shooter (FPS) a Third-person Shooter (TPS) 3 jsou naopak velmi náročné na všechny zmíněné parametry sítí. Herní servery jsou schopny pojmout řádově desítky hráčů a jsou poměrně netolerantní na kvalitu spojení. Hráče se špatným spojením odpojí, protože má ve hře výhodu v tom, že se ostatním zobrazuje trhaně a se zpožděním. Pohybuje-li se rychle, není možné ho zasáhnout. V našem případě se jedná spíše o akční hru. Vezmu-li v úvahu dnešní běžně dostupné sítě, myslím, že šířka pásma nebude při rozumné implementaci omezující faktor. Největší potíže předpokládám u zpoždění a ztrátovosti paketů. Výběr transportního protokolu TCP je velmi robustní spojově orientovaný protokol. Z mnoha jeho vlastností nás zajímá především: • spolehlivý přenos, • zachování pořadí paketů, • kontrola toku a mechanizmy předcházení a regulace zahlcení sítě. Nevýhodou protokolu TCP je blokující příjem paketů. Pokud se nějaký paket ztratí, nejsou přijímána žádná data, dokud není doručena jeho znovuposlaná kopie. Tím se TCP stává nevhodným pro mnoho real-time aplikací, jako je streaming multimedií, VoIP a některé hry. Tento protokol je s převahou užíván v hrách typu MMORPG4 a jim podobných, kde jsou data velmi důležitá a nemůžeme si dovolit jejich ztrátu. UDP je jednoduchý protokol založený na pouhém posílání nezávislých zpráv, který má na první pohled oproti TCP řadu nevýhod. • Negarantuje doručení paketů. Mohou dojít data celá, jen část, nebo žádná. • Negarantuje pořadí paketů, což může být u programování her velký problém. Například dostaneme zprávu, že střela explodovala, předtím než dostaneme zprávu, že byla vytvořena. 2
Hru je možné hrát na: http://www.travian.cz/ Hry, kde hráč vidí svět vlastníma očima, nebo zprostředkovaně skrze kameru blízko hlavní postavy, plynule v reálném čase. 4 Massive(ly)-Multiplayer Online Role-Playing Game je typ online počítačové hry na hrdiny, kde jsou tisíce hráčů přítomny v jednom virtuálním světě. 3
5
• Neposkytuje žádnou kontrolu toku ani mechanizmy předcházení a regulace zahlcení sítě, data mohou být posílána neefektivně. Výhodou UDP je malá režie a neblokující příjem zpráv. Tento protokol se používá u akčních počítačových her, kde jsme schopni tolerovat, že data občas nedorazí, nejdůležitější je, aby se nezpožďovala. Už bylo zmíněno, že Tunneler má nejblíže k akčním počítačovým hrám, proto jsem se rozhodl vystavět síťovou komunikaci na transportním protokolu UDP. Spolehlivost doručení řídících dat si můžeme zajistit sami na aplikační úrovni.
1.3.2
Grafika
Pro nenáročná 2D řešení interaktivních aplikací (včetně her) se nezřídka užívá software jako Adobe Flash nebo Shockwave. Tato vývojářská prostředí považuji však za příliš omezující jak z grafického hlediska, tak i z hlediska programování. Jejich doménou jsou spíše webové aplikace a hry velmi malého rozsahu, proto o jejich použití nebudeme uvažovat. Nároky na prezentační subsystém nejsou vysoké z hlediska funkcionality ani schopnosti optimálně zobrazovat množství objektů. Prototyp bude prezentovat pouze dvourozměrný herní svět, kde pozadí tvoří v reálném čase modifikovaná textura. Zároveň není potřeba maximalizovat efektivitu tohoto subsystému vlastní implementací nad nízkoúrovňovým rozhraním, jako je například OpenGL. S výhodou lze integrovat hotový 3D renderovací engine, který obsahuje i správu datových zdrojů.
6
Kapitola 2
Výběr technologií Stanovili jsme požadavky kladené na jednotlivé subsystémy, nyní na jejich základě zvolíme vhodné implementační technologie.
2.1
Vývojové prostředí
Jako primární programovací jazyk bylo zvoleno C++. Jeho nevýhodou je absence automatické správy paměti, proto je nutné přistupovat k odstraňování dynamicky vytvořených objektů zodpovědně. Výhodou je efektivnost zkompilovaného kódu a volnost ve výběru dalších technologií.
2.2
Síťový subsystém
Rozhodli jsme se používat transportní protokol UDP, přesto budeme potřebovat zajistit spolehlivé doručení některých zpráv. Potřebujeme implementovat mechanizmus znovuposílání a řazení. Mnoho již hotových a úspěšně nasazených produktů adresuje implementací řešení tohoto problému. Jedním z nejpoužívanějších je RakNet – C++ knihovna postavená nad UDP zajišťující vybrané prvky relační a prezentační vrstvy OSI modelu přesně pro potřeby multi-player her na lokální sítě a Internet. RakNet je nadplatformní, má otevřený kód a jeho užití je v případě nekomerčních účelů bezplatné. Jak již bylo zmíněno, RakNet je postavený na protokolu UDP, ale řeší jeho nedostatky oproti TCP. Kromě garance doručení nabízí i uspořádání datagramů, které přišly mimo pořadí (viz tabulka 2.1). RakNet poskytuje rychlé a jednoduché spojení, které blokuje neautorizovaný přenos dat, a dokonce poskytuje i mechanizmy na kontrolu toku a agregace. RakNet si při startu vytváří dvě vlákna. Jedno vlákno čeká na příchozí datagramy a druhé slouží ke správě spojení. V příloze jsou pro zajímavost uvedena režijní data, která RakNet připojuje k jednotlivým datagramům a zprávám. Umožňují lépe pochopit jeho funkcionalitu.
7
Spolehlivost UNRELIABLE
UNRELIABLE SEQUENCED RELIABLE RELIABLE ORDERED RELIABLE SEQUENCED
Popis Nespolehlivé, nezaručuje správné pořadí. Tento způsob je určen pro data, která nejsou důležitá, nebo jsou posílána velmi často a nevadí nám některá ztratit. Nespolehlivé, zaručuje správné pořadí. Přijde-li starší zpráva (mimo pořadí), je zahozena, přijímány jsou jen nejnovější. Spolehlivé, nezaručuje pořadí. Spolehlivé, zaručuje pořadí. Spolehlivé, zaručuje přibližné pořadí. Při řazení se nečeká na zprávy, které jsou příliš zpožděné.
Tabulka 2.1: Typy spolehlivostí zpráv RakNetu.
2.3
Prezentační subsystém
Object-Oriented Graphics Rendering Engine (OGRE) byl použit pro vědecké vizualizace, v mnoha komerčních a nespočtu nezávislých herních projektů. Scéna je abstraktní reprezentací zobrazení virtuálního světa. Scény se mohou skládat ze statické geometrie, jako je například terén, z modelů, jako je například tank, zdrojů světla, které scénu ozařují, a kamer, které ji zabírají. Předností OGRE je hierarchický model uzlů scény, ke kterým lze připojit jakýkoliv objekt implementující rozhraní MovableObject, což nám umožňuje libovolně pospojovat různé entity do funkčních celků. OGRE poskytuje automatickou správu zdrojů a podporuje také jejich načítání z archivů (ZIP). Dále podporuje mnoho formátů textur a import objektů z řady modelovacích nástrojů, jako jsou například 3D Studio Max, Maya a Blender. Mezi jeho další výhody patří stabilita, otevřenost kódu, dobrá dokumentace, aktivní vývojářská komunita a nezávislost na platformně a renderovacím API. OGRE je napsán v C++.
2.4
Vstupní rozhraní
Pro získávání vstupu z periferií byl zvolen Object-Oriented Input System. Jeho výhodou je jednoduchost, otevřenost kódu a nezávislost na platformě. Podporovaná vstupní zařízení jsou klávesnice, myš, joystick, a dokonce i Nintendo Wii ovladač.
2.5
Platforma
Cílovou platformou byl zvolen operační systém Microsoft Windows, jehož doménou jsou právě hry. Avšak platformě nezávislý výběr technologií nám umožní portování na jiný operační systém.
8
Kapitola 3
Návrh V této kapitole se zaměříme na obecný návrh aplikace a řešení problémů, které vyvstávají.
3.1
Síťový model a komunikace
Model peer-to-peer 1 v síťových hrách je rarita. Teoreticky poskytuje velmi lákavé možnosti ve využití počítačové sítě, neboť u tohoto modelu se s rostoucím počtem hráčů přenosová kapacita zvyšuje, avšak implementace je velmi obtížná. V minulosti byl použit u her typu play-by-mail 2 , jednou z nejznámějších je Quantum Space, které bylo spuštěno v roce 1982 na AOL3 . Pokud vím, žádná moderní hra čistý model peer-to-peer nevyužívá. V síťových multi-player hrách se s převahou používá model klient-server. Komunikace je asynchronní a pouze mezi klientem a serverem. Server je komunikační uzel, který má na starost vytvoření hry a její řízení. Může být dvojího typu: • dedikovaný, • nededikovaný. Nededikovaný server je obvykle implementován v síťových hrách určených k hraní po LAN. Z pohledu hráče se od klienta nijak neliší, je rovnocenným účastníkem hry. U online her je téměř výhradně implementován dedikovaný server. Jedná se o specializovanou službu (daemon), která je vyhrazena pouze k plnění úlohy serveru. Některé dedikované servery zvládají až tisíce hráčů4 . V naší hře předpokládáme malý počet hráčů, proto budeme implementovat síťový model klient-server s variantou nededikovaného serveru. 1
Model síťového spojení rovný s rovným. Typ her založený na komunikaci přes e-mail. Více na: http://en.wikipedia.org/wiki/Play-by-mail game 3 AOL je americká společnost poskytující internetové služby. 4 Server Molten hry World Of Warcraft se pyšní deseti tisíci hráči. Více na: https://www.moltenwow.com/ 2
9
3.1.1
Komunikace
Komunikace může probíhat dvěma způsoby: voláním vzdálených procedur (RPC), nebo zasíláním zpráv. U RPC si zaregistrujeme nativní C++ funkci, ke které chceme přistupovat vzdáleně. Pomocí RakNetu pak můžeme vzdáleně volat zaregistrované funkce na jiných systémech. Dle mého názoru má RPC pár nedostatků. Předně, nemusí být vláknově bezpečné: RakNet běží v jiném vlákně, kdyby volal naše metody, musely by být nějak zabezpečené. RPC také neumožňuje použití strategií (například fronty či filtrování), které nabízí zasílání zpráv. Narozdíl od RPC jsou přijaté zprávy uloženy do vláknově bezpečné fronty, odkud si je sami vybereme ve chvíli, kdy je chceme zpracovat. Zasílané zprávy tak mají jasný vstupní bod, lze je zahodit při zahlcení, nebo když je nechceme zpracovávat. Zprávy lze navíc snadno předávat i uvnitř systému. Z těchto důvodů je komunikace řešena zasíláním předdefinovaných zpráv.
3.2
Návrh architektury
Po evaluaci byly zvoleny technologie, které poskytují abstrakci jak od hardware, tak i od operačního systému. Interaktivní aplikace na nejvyšší úrovni sledují návrhový vzor model-view-controller [3, 4], což je softwarová architektura, která rozděluje datový model aplikace, uživatelské rozhraní a řídicí logiku do tří nezávislých komponent tak, že modifikace některé z nich má minimální vliv na ostatní. Tento vzor se velice hodí pro návrh počítačových her, protože se v nich odehrávájí nějaké simulace (model), ty jsou ovládané například joystickem (controller) a nakonec složitě zobrazované (view). V případě našeho systému OGRE zajišťuje funkcionalitu vzoru view a RakNet je spodní vrstvou pro controller. Hlavní práce bude vytvořit model a specifickou část controlleru (viz obrázek 3.1). Některé třídy používají návrhový vzor singleton [3, 4], který zabezpečuje existenci jediné instance dané třídy a poskytuje k ní globální přístupový bod. Problém nastává u vícevláknových aplikací, kde se může stát, že ve chvíli, kdy jedno vlákno požádá o vytvoření singletonu, dojde k přepnutí kontextu do druhého vlákna, kde není singleton ještě vytvořen, a je spuštěn proces vytváření. Po přepnutí kontextu zpět je v prvním vlákně dokončena přerušená tvorba singletonu, ale v systému pak existují instance dvě. Problém se obvykle řeší synchronizací tovární metody. Naše aplikace je sice vícevláknová, ale problém synchronizace není třeba řešit, protože další vlákna používá síťový engine, který singletony nevytváří a naši část aplikace ani nevolá. Další použitý návrhový vzor je observer [3, 4], který umožňuje šířit událost, která nastala v jednom objektu, ke všem entitám, které si o ni zaregistrují zájem. Návrhový vzor abstract factory method [3, 4] poskytuje způsob, jak zapouzdřit skupinu individuálních továren (návrhový vzor Factory), které jsou navzájem podobné, což umožňuje 10
Obrázek 3.1: Rozdělení tříd podle návrhu model-view-controller. vytvořit v běhu programu na základě rozhodnutí instanci třídy, která vytváří další závislé objekty. Na obrázku 3.2 je zobrazena zjednodušená struktura aplikace. Nyní ve stručnosti popíšeme zodpovědnosti většiny uvedených tříd. Třída NetMgr má na starost síťovou komunikaci, na základě parametrů se inicializuje jako server, nebo klient a ustanovuje spojení. Třída používá návrhový vzor singleton a vzor observer, který v tomto případě umožňuje předat přijatou zprávu objektům, které konkrétní typ zprávy zajímá. Třída OgreMgr má na starost vytvoření okna aplikace a jeho vykreslování. Poskytuje přístup k objektům grafického enginu. Třída používá návrhový vzor singleton. Třída Input poskytuje rozhraní pro čtení periferií. Třída používá návrhový vzor singleton. Třída GUI slouží k zobrazování HUDu 5 , krátkých textových zpráv a dalších grafických prvků, které se vykreslují nad grafickou vrstvou hry. Třída používá návrhový vzor singleton. Třída Timer poskytuje čas delta time, který zajišťuje, že herní čas ubíhá na všech počíta5
Head-up display je způsob zobrazení dat, kde se uživatel není nucen při čtení podívat mimo své zorné pole. Termín se používá v armádě, automobilovém průmyslu, ale i ve hrách.
11
Obrázek 3.2: Zjednodušená struktura aplikace. čích stejně rychle, nezávisle na jejich výkonu. Dále třída poskytuje službu časovač, pomocí které mohou být objekty upozorněny na libovolné časové události. Třída používá návrhový vzor singleton a observer. Třída Game má na starost řízení hry od inicializace, přes střídání kol, až po její ukončení. Třída SessionMgr zajišťuje životní cyklus herních objektů v rámci jednoho herního sezení. Třída Map spravuje hrací plochu. Poskytuje metody k její editaci a testování kolizí. Dále poskytuje metodu na generovaní náhodných bodů, kterých je zapotřebí při rozmísťování startovních pozic. Třída Object je třídou herního objektu, ten je jednoznačně určen svým id, které se skládá z id vlastníka a unikátního čísla. Dalšími vlastnostmi jsou pozice, směr a množina kolizních boxů, která může být prázdná. Množina kolizních boxů umožňuje pohodlně definovat herní objekt v prostoru pro interakci s ostatními entitami. Podobné či stejné typy herních objektů by měly být uskupeny ve svých manažerech, k tomu účelu slouží abstraktní třída ObjectMgr definující základní vlastnosti a chování, které konkrétní manažer musí implementovat. Tato třída ve spojení s třídou Object tvoří základ vzoru abstract factory method. Třída CollisionMgr poskytuje službu testování kolizí herních objektů. ObjectMgr si může vyžádat testy kolizí s libovolným typem herního objektu. V případě kolize je mu předáno id obou objektů a odkaz na druhý ObjectMgr. Testování se provádí na základě kolizních boxů.
12
3.3
Systém kolizí
Samotný OGRE nabízí skromné nástroje na detekci kolizí. Umožňuje obalit mesh 6 kolizním boxem nebo koulí, kolize je pak testována mezi těmito primitivními tělesy. Složitější geometrii lze testovat takzvaným paprskem, což si můžeme představit jako nalezení průsečíku přímky a plochy. Spolu s OGRE se doporučuje používat malou knihovnu Minimal Ogre Collision, která se pyšní snadnou použitelností. Ale jelikož má být hra – přesněji herní logika, protože samotné modely mohou být prostorové – ve 2D, rozhodl jsem se vytvořit vlastní systém testování kolizí, který by byl jednoduchý a kompatibilní s vytvářením tunelů do herní plochy.
Obrázek 3.3: Systém kolizních boxů. Při řešení problému jsem využil stromové struktury uzlů scény. Kolizní box se skládá ze čtyř vrcholů, které tvoří uzly, ty jsou potomky uzlu herního objektu. Změna pozice a orientace objektu je tak automaticky promítnuta do kolizních boxů. Herní objekt se může skládat z libovolného počtu kolizních boxů, ty jsou uskupeny v kontejneru (viz obrázek 3.3), který ví, jaký radius pokrývají jeho boxy (viz obrázek 3.4). Při testování kolize dvou herních objektů se nejdříve porovná jejich vzájemná vzdálenost s radiusy, a teprve v případě, kdy opravdu hrozí kolize, se testují jednotlivé boxy. Zde je kvůli malému počtu objektů takto primitivní optimalizace postačující, jinak lze problém vyřešit pomocí hierarchického uspořádání prostoru (například quadtree7 ).
3.4
Konzistence světa
V síťové hře vlastní každý hráč svou kopii světa. Konzistence světa znamená, že herní objekty jsou v rámci těchto kopií na stejných pozicích a události (například výstřel) nastávají ve stejnou chvíli. Avšak především kvůli síťovému zpoždění tohoto stavu nelze dosáhnout. Ve hře Tunneler se mění i prostředí, navíc je s ním hráč v tak těsném kontaktu, že ovlivňuje další události. Proto považuji za důležité zajistit, aby se konkrétní zásahy do herní plochy rozhodovaly vždy jen u jednoho hráče – například vlastníka herního objektu, který je v kolizi s herní plochou – ten by je pak sdílel s ostatními pomocí zpráv. Hráč bude při 6 7
Geometrie objektu Více o hierachickém uspořádání prostoru na: http://en.wikipedia.org/wiki/Quadtree
13
Obrázek 3.4: Základna se zakreslenými kolizními boxy (červeně) a kružnicí znázorňující radius (zeleně). kopání často v kolizi s herní plochou každý frame, proto se musí vykopané části plochy ukládat do fronty a posílat ve větším počtu, jinak by mohlo snadno dojít k zahlcení sítě. Vlastnosti herních objektů, jako pozice, směr a rychlost, musí být sdíleny s ostatními v jednorázových klíčových momentech hráčem, který je vyvolal. Klíčovým momentem rozumíme například vytvoření objektu nebo změnu směru pohybu. U herních objektů, jejichž chování je složitější, například u tanku, jehož vektor rychlosti není konstantní, musí být údaje sdíleny i v pravidelných časových intervalech. Mezi aktualizacemi musí být kvůli plynulosti pohyb herních objektů extrapolován od momentu poslední aktualizace. Komplikací sdílení událostí po síti je, že čas příjmu události není totožný s časem jejího vygenerování. Přijmeme-li zprávu o vypálení střely z určité pozice, střela zatím mohla urazit nezanedbatelnou vzdálenost. Umístíme-li ji na uvedenou pozici, bude se střela v každé instanci hry pohybovat jinak, čímž porušíme konzistenci světa. Může též vzniknout potřeba porovnat dvě události a určit, která nastala dříve. Jelikož má každý systém obvykle různý systémový čas, potřebujeme nějak zajistit jednotné časové měřítko. V tom nám pomůže RakNet, který nabízí výpočet rozdílů systémových časů mezi připojenými systémy. Do zprávy je pak vloženo časové razítko, které je ihned po přijetí přepočítáno na čas lokálního systému. To nám umožní přesněji odhadnout současnou pozici objektu i porovnat časy událostí.
14
Kapitola 4
Implementace Nyní se podrobněji podíváme na konkrétní řešení některých implementačních detailů.
4.1
Komunikace
Vyhledávání vzdálených systémů je realizováno broadcastem na daném portu. Komunikace probíhá asynchronně mezi klientem a serverem. Server slouží jako komunikační uzel a přeposílá zprávy klientům. Každá zpráva je obvykle doručena všem účastníkům komunikace. Ta sestává především ze systémových zpráv a aktualizací pozic a hrací plochy, což jsou informace, které zajímají všechny hráče.
4.1.1
Připojení, inicializace a správa spojení
Následující výčet systémových zpráv seřazených v časové posloupnosti slouží k objasnění inicializačního procesu a správy spojení. AssignIdMsg Server přiřazuje unikátní id klientovi. Tato zpráva je poslána jen konkrétnímu klientovi. StartSessionMsg Server oznamuje, že jsou připojeni všichni klienti a mají přiřazená svá id. Ve zprávě je uveden počet hráčů, po jejím přijetí je inicializován SessionMgr. SessionStartedMsg Klient oznamuje, že jeho třída SessionMgr byla inicializována. InitializeMsg Server dává znamení, že jsou všichni připraveni a může se pokračovat v inicializaci. PlayerInfoMsg Server nebo klient posílá údaje o sobě. Zpráva obsahuje pouze id a jméno hráče. GetPositionMsg Klient žádá o přiřazení startovní pozice. Součástí zprávy je id klienta. 15
AssignPositionMsg Server oznamuje startovní pozici hráče daného id. Na přijetí této zprávy reagují všichni vytvořením tanků a základen v příslušných manažerech herních objektů. StartGameMsg Server oznamuje start hry. NewRoundMsg Server oznamuje začátek nového kola. Zpráva je odeslána ve chvíli, kdy je naživu nejvýše jeden hráč. EndGameMsg Server oznamuje konec hry. ConnectionLostMsg Server oznamuje, že bylo přerušeno spojení s hráčem daného id. Hráč je do konce hry považován za mrtvého. AllConnectionsLostMsg Zpráva je vygenerována, když je přerušeno veškeré spojení. Reakce na zprávu je stejná jako na EndGameMsg.
4.1.2
Spolehlivost a priorita
V tabulce 4.1 jsou shrnuty typy předdefinovaných zpráv do čtyř kategorií podle parametrů, s kterými jsou posílány. Typ zprávy Systémové zprávy Herní události Aktualizace objektů Aktualizace herní plochy
Spolehlivost RELIABLE ORDERED RELIABLE ORDERED UNRELIABLE SEQUENCED RELIABLE
Priorita HIGH PRIORITY HIGH PRIORITY MEDIUM PRIORITY MEDIUM PRIORITY
Tabulka 4.1: Spolehlivost a priorita předdefinovaných zpráv.
4.2
Rozdělení herních objektů
Herní objekty jsou rozlišeny na lokální a vzdálené – podle toho, kdo je jejich vlastníkem. Stejné herní objekty lišící se umístěním mají odlišné chování, proto jsou separovány do zvláštních manažerů. Největší rozdíly jsou ve vytváření objektů, jejich odstranění a především v interakci s ostatními entitami.
16
4.3
Herní plocha
Herní plocha je reprezentovaná dvojrozměrným polem typu bool uloženým v paměti. Hodnota označuje, zda je v daném místě vykopaná. Testování kolizí s mapou je realizováno kolizními boxy. Je-li při testu do hrací plochy vyhloubena díra, kolizní box je uložen do fronty, která se v pravidelných časových intervalech posílá ostatním hráčům. Hráč vytvářející tunel je v kolizi s herní plochou každý frame. Každý frame by se tedy ukládaly kolizní boxy tanku s drobnou obměnou pozice ke sdílení. Proto jsem implementoval jednoduchou optimalizaci, která (pokud to je možné) slučuje kolizní boxy zvětšením rozměrů jednoho z nich. Jede-li tank při vytváření tunelu rovně, je v časových intervalech sdílení poslána aktualizace obsahující jen jeden delší kolizní box. Vykreslování herní plochy je realizováno vytvořením dynamické textury z výseku mapy, který se má zobrazit.
4.4
Konzistence světa
Už máme zajištěno, že se sdílí vlastnosti herních objektů, nyní se zaměříme na interakce mezi nimi, neboli kolize.
4.4.1
Kolize střely se základnou
Základna je statický herní objekt a pohyb střely je díky času delta time a časovému razítku v každé instanci hry stejný, proto není třeba událost sdílet. Střela je zničena v každé instanci hry bez posílání zprávy.
4.4.2
Kolize lokální střely s herní plochou
Kolize má za následek vyhloubení díry do hrací plochy a zničení objektu střely. Aktualizace hrací plochy se posílá rovnou se zprávou o explozi střely (ShellExplosionMsg), aby byly oba děje časově synchronizované.
4.4.3
Kolize vzdálené střely s herní plochou
Vzdálená střela se pouze přestane zobrazovat, ale nadále existuje. Střela je definitivně odstraněna s příchodem zprávy ShellExplosionMsg. Není vhodné rozhodovat o osudu střely, protože situace by mohla být vyhodnocena u každého hráče jinak. Herní plocha může být v tomto místě už vykopaná, ale ještě nebyla doručena aktualizace, střela mohla mít také kolizi s herním objektem, kterou jsme nezaznamenali. Kdyby byla střela odstraněna neprávem, už bychom se nedozvěděli, co se s ní ve skutečnosti stalo (například mohla narazit do našeho tanku).
4.4.4
Kolize vzdálené střely se vzdáleným tankem
Naše představa o pozici cizího tanku je jen přibližná, tank se mohl na poslední chvíli střele vyhnout. Vzdálená střela je opět pouze skryta jako u kolize s herní plochou.
17
4.4.5
Kolize vzdálené střely s lokálním tankem
Už bylo několikrát zmíněno, že pohyb střely je na všech počítačích stejný. Není možné, aby byla kolize vyhodnocena mylně, avšak střela na jiných systémech už nemusí existovat. Nastávají celkem tři možnosti. • Střela je maskovaná (nezobrazuje se), proto se dá předpokládat, že je na cestě zpráva o předchozí explozi střely. Zaznamená se čas vygenerování události a id střely. Pokud do krátkého časového intervalu nedorazí zpráva o explozi této střely s dřívějším časem, tank kolizi uzná. • Střela není maskovaná, přesto však mohlo dojít ke kolizi, kterou jsme nezaznamenali (přichází v úvahu jen kolize s jiným tankem). Pokud se v blízkosti lokálního tanku na trase střely nachází cizí tank (vyjma majitele střely), postupuje se stejně jako v případě maskované střely. Test přítomnosti cizího tanku je realizován vytvořením pomocného kolizního boxu. • Střela není maskovaná a v blízkosti není žádný tank, lokální tank kolizi uzná ihned. Kolize má za následek zničení střely a poškození štítů tanku.
4.4.6
Kolize tanku s herní plochou
Kolize má za následek vykopání díry do herní plochy. Zpomalení a spotřeba energie tanku při kolizi je přímo závislá na obsahu vykopané oblasti. Za poslání aktualizace herní plochy má zodpovědnost třída Map.
18
Kapitola 5
Nasazení 5.1
Požadavky
Aplikace byla bez potíží testována na operačních systémech Microsoft Windows XP, Windows Vista a Windows 7. Pro grafický výstup doporučuji renderovací subsystém DirectX 9c. Alternativou je OpenGL 1.2. Grafické rozlišení aplikace je 800 x 600. Nastavení aplikace je řešeno dvěma konfiguračními soubory: ogre.cfg a resources.cfg. Ty slouží především k nastavení grafického výstupu a cest k datům. Data (fonty, textury a skripty) jsou uložena v adresáři media.
5.2
Ovládání hry
Ovládání je velmi jednoduché a intuitivní, typické pro většinu her podobného žánru. Po spuštění aplikace je hráč vyzván k zadání jména, to se smí skládat pouze z alfanumerických znaků bez diakritiky. Vstup je potvrzen klávesou <<Enter>>. Hráči je poté nabídnuta možnost vytvoření nové hry <
>, nebo připojení ke hře vytvořené <<J>>. U možnosti vytvoření nové hry je nutno uvést počet hráčů, vstup je omezen na celé číslo z intervalu h2, 9i. Hra je odstartována po připojení všech hráčů. Hra je viděna shora, tank se nachazí v základně uprostřed obrazovky. V horní části je umístěno GUI, které zobrazuje štíty a energii tanku a pro testovací účely i pozici. Nalevo od GUI se vypisují herní události. Hra se ovládá pouze šipkami a klávesou <>, kterou se střílí. Tank se může pohybovat v osmi směrech, pohybem v hrací ploše vytváří tunely. Tank je kopáním zpomalován, pro urychlení lze využít současného pohybu a střelby. Důležitým prvkem hry je energie tanku, ta je spotřebovávána jeho činností. Klesne-li hodnota energie na nulu, tank exploduje. Energii lze doplnit jak ve své základně, tak i v základnách protihráčů. Stav tanku je také vyjádřen štíty, ty mohou být poškozeny zásahem střely protihráče. Klesne-li hodnota štítů na nulu, tank exploduje. Štíty lze opravit pouze ve své vlastní základně. Cílem hry je přežít a zničit tanky protihráčů. Hra probíhá ve třech kolech. Konec kola nastává, je-li naživu nejvýše jeden tank. Startovní
19
Obrázek 5.1: Provizorní vzhled hry. pozice tanků je každé kolo stejná, hrací plocha zůstává vykopaná. Na konci každého kola je vypsáno skóre jednotlivých hráčů, vítězem se stává hráč s nejvyšším skóre po posledním kole. Průměrná herní doba činí tři až pět minut.
20
Kapitola 6
Experimenty Aplikace byla během vývoje s úspěchem testována na sítích LAN a WLAN, v této kapitole se chci pokusit zjistit více o nárocích hry na síťové spojení.
6.1
Měření síťové komunikace
Cílem testu je nalézt kvantitativní zhodnocení komunikace v různých fázích hry. Byla zaznamenána síťová komunikace běheme dvou her dvou hráčů na síti LAN. První hra trvala 133 sekund a byla vypnuta optimalizace zpráv aktualizací herní plochy. Druhá hra, s aktivní optimalizací zpráv, trvala 151 sekund. K měření provozu byla využita aplikace Wireshark1 . Interference jiného síťového provozu v měření byla odfiltrována specifikací portu. Naměřené hodnoty byly pro přehlednost zaneseny do grafů a tabulek. A
B
C
D
Obrázek 6.1: I/O graf znázorňující počet přenesených paketů v čase během hry bez optimalizace. Na grafech 6.1 a 6.2 je vidět navázání spojení a počáteční inicializace (oblast A). Oblasti B, C a D jsou střetnutím hráčů, které bylo pokaždé zakončeno zničením jednoho z nich. Tyto oblasti nejsou z grafu čitelné, jsou doplněny z vizuálního záznamu hry. Vzhledem k tomu, že každá hra je jedinečná, nelze naměřená data přímo porovnat. Přesto uvedené grafy (obrázky 6.2 a 6.3) dostatečně ilustrují přínos optimalizace. Úspora množství 1
Aplikaci je možno získat na: http://www.wireshark.org/
21
A
B
C
D
Obrázek 6.2: I/O graf znázorňující počet přenesených bytů v čase během hry bez optimalizace.
Obrázek 6.3: I/O graf znázorňující počet přenesených bytů v čase během hry s optimalizací. sdílených dat je též patrná z tabulky 6.1. Doplňující statistická data ze hry s optimalizací jsou uvedena v tabulce 6.2. Z měření vyplývá, že je aplikace nenáročná na šířku pásma a že vytíženost sítě je poměrně nezávislá na činnosti hráčů, což považuji za dobrou vlastnost.
6.2
Vliv latence na hratelnost
S nároky akčních multi-player her na síť bývá nejčastěji spojována latence. V následujícím experimentu se pokusím zjistit vliv latence na hratelnost naší hry. Test probíhal ve dvou hráčích na síti LAN se zpožděním menším jak 1 ms. Pro simulaci různých zpoždění byl použit program QoS Emulator2 . Výsledky jsou uvedeny v tabulce 6.3, doplněné o subjektivní hodnocení hratelnosti a pozorované jevy způsobené zpožděním paketů. Vzhledem k originalitě hry (prvku dynamické hrací plochy) jsem nenalezl vhodného kandidáta ze síťových počítačových her pro účely srovnání. Většinou se však udává mez pro hratelnost akčních multi-player her okolo 100 ms zpoždění [6]. Tento odhad je samozřejmě velmi hrubý a slouží jen pro představu. Naše hra se vyrovná se zpožděním i nepatrně vyšším (viz tabulka 6.3).
2
Aplikaci je možno získat na: http://www.jenkinssoftware.com/forum/index.php?topic=1671.0
22
Velikost paketů v B 40 – 79 80 – 159 160 – 319 320 – 639
Četnost v % 52,33 31,61 8,94 7,12
Četnost v % po optimalizaci 52,33 43,15 4,52 0
Tabulka 6.1: Intervaly velikostí paketů před a po optimalizaci zpráv aktualizací mapy.
KB Pakety b/s
Server → klient 178,358 1943 9472,59
Server ← klient 174,467 1922 9265,94
Celkem 352,825 3865
Tabulka 6.2: Statistiky přenesených dat ve hře s optimalizací.
Ping/2 v ms 20
Hratelnost Výborná
50
Velmi dobrá
100
Dobrá
200
Špatná
Popis Žádné známky zhoršení hratelnosti. Žádné známky zhoršení hratelnosti. Cizí tank se občas pohybuje trhaně, mapa se vykopává s malým zpožděním. Cizí tank často přeskakuje, je těžké ho zasáhnout střelou, mapa se vykopává se značným zpožděním.
Tabulka 6.3: Vliv latence sítě na hratelnost.
23
Kapitola 7
Závěr Dle mého názoru jsem splnil požadavky zadání bakalářské práce. Aplikace je hotová v rozsahu, jaký zadání vyžaduje. Hlavním těžištěm práce bylo nastudování problematiky a výběr vhodných technologií, vytvoření snadno rozšiřitelného objektového návrhu využívajícího návrhové vzory, napsání dobře udržovatelného kódu a zajištění konzistence herního světa z pohledu jednotlivých hráčů. Obecný návrh herních objektů a manažerů, služba automatického testování kolizí a systém kolizních boxů umožňuje jednoduchou implementaci nového herního objektu. Spravedlivost hry a konzistence světa byly zajištěny systémem jednoduchých pravidel, která jsou velmi nenáročná na šířku pásma síťového spojení a využívají ho v různých fázích hry stejně. Míra závislosti hratelnosti hry na nízké latenci je oproti obdobnému typu her zcela v normě. Je možné dále pokračovat ve vývoji, navrhuji v první řadě nahrazení jednoduché grafiky GUI a HUDu, nahrazení 2D herních objektů 3D animovanými modely a vytvoření grafických efektů. Podle mého mínění by aplikace mohla být s úspěchem nasaditelná jako freeware, popřípadě jako malá reklamní hra.
24
Literatura [1] Ogre Manual v1.7 [online]. 2009-12-30 [cit. 2010-01-02]. OGRE Manual v1.7 (’Cthugha’). Dostupné z WWW: http://www.ogre3d.org/docs/manual/ [2] RakNet Manual [online]. 2009-08-02 [cit. 2009-11-19]. RakNet. Dostupné z WWW: http://www.jenkinssoftware.com/raknet/manual/index.html [3] GAMMA, Erich, et al. Design Patterns : Elements of Reusable Object-Oriented Software. [s.l.] : Addison-Wesley Professional, 1994. 416 s. ISBN 0-201-63361-2. [4] Objekty [online]. 2003 [cit. 2009-11-10]. Návrhové vzory (design paterns). Dostupné z WWW: http://objekty.vse.cz/Objekty/Vzory [5] PRATA, Stephen. Mistrovství v C++. [s.l.] : Computer Press, 2007. 1120 s. ISBN 978-80-251-1749-1. [6] KLAŠKA, Luboš. Základní kvalitativní parametry sítě (1) : latency (zpoždění). Svět sítí [online]. 6. prosince 2006, 326, [cit. 2010-05-20]. Dostupný z WWW: http://www.svetsiti.cz/view.asp?rubrika=Tutorialy&clanekID=326
25
Příloha A
Režijní data RakNetu Na datagram: 1 byte pro bitová označení, 4 byty pro časové razítko sloužící k vypočtení RTT 1 pro kontrolu zahlcení, 3 byty pro sekvenční číslo. Na zprávu: 1 byte pro bitová označení, 2 byty označující délku zprávy, IF (RELIABLE, RELIABLE SEQUENCED, RELIABLE ORDERED) A. 3 byty pro sekvenční číslo, abychom nepřijali duplikovanou zprávu vícekrát, IF (UNRELIABLE SEQUENCED, RELIABLE SEQUENCED, RELIABLE ORDERED) A. 3 byty pro sekvenční číslo sloužící k řazení zpráv na stejném kanálu, B. 1 byte označující řadící kanál, IF (MTU 2 ) A. 4 byty označující počet dílů B. 2 byty pro identifikaci dílu, C. 4 byty pro ukazatel do počtu dílů.
1 2
Round-trip time je čas, za který se signál dopraví od zdroje do cíle a zpět. Maximální velikost paketu, kterou je možno přenést z jednoho síťového zařízení na druhé.
26
Příloha B
Obrazová příloha
27
Obrázek B.1: Snímek ze hry.
Obrázek B.2: Snímek ze hry.
28
