Jak na tvorbu her typu Travian?

TondaG

Jak na tvorbu her typu Travian?
« kdy: 19. 10. 2014, 05:38:39 »
Ahoj, chtěl bych se zeptat, jak nejlépe jít principiálně na tvorbu her typu Travian. Pro ty, kteří neznají:

Webová hra, ve které hráči staví různé budovy, těží suroviny, posílají na sebe útoky, obchodují spolu apod. Podstatné je, že běží na serveru a jednu hry hraje paralelně mnoho hráčů (desítky tisíc). Hra má mapu (čtvercová síť) a kontinuální herní čas. Hráči plánují započetí různých akcí (např. pošlou útok svými jednotkami, který dorazí do cíle v určitý čas dle rychlosti jednotek a vzdálenosti, jakmile dorazí útočné jednotky na cílové místo, vykoná se vlastní útok - podle poměru sil se zredukují útočné a obranné jednotky - a zbytek se vrátí třeba i s nějakým ukradenými surovinami zpět, což zase nějakou dobu trvá).

V takovém případě mi dává smysl něco jako "prioritní fronta", do které se budou dávat naplánované události s časem, kdy u události dojde. A ní se budou postupně vybírat ty aktuální, které mají nastat "v tento čas". V tom problém zatím nevidím.

Pak je ale otázka, jak ty události efektivně zpracovávat. Jedna možnost je dělat to sériově. Ke zpracování jedné události je ale třeba získat celou řadu údajů, vyhodnotit a zapsat změny zpět. Pokud údaje budou někde v DB, tak vyhodnocení jedné události bude trvat příliš dlouhý čas na to, aby to zvládalo ve špičce zpracovat dostatečný počet událostí za sekundu. Hrubou silou by bylo vše držet v paměti, aby se doba vyhodnocení události zkrátila na minimum. Na druhou stranu i tak sériové zpracování není škálovatelné, je třeba data ukládat na disky pro případ výpadku apod.

Chytřejší řešení by mohlo spočívat v tom, že by se vyhodnocovaly některé události souběžně. Ovšem musely by to být zřejmě události, které spolu nijak nesouvisí, neovlivňují se navzájem. Např. zmenšování a zvětšování počtu jednotek ve vesnici (=políčko mapy) je velmi podobné klasickému příkladu převodu částky z účtu na účet, na kterém se ukazuje potřeba transakcí. Jenže jak rychle a efektivně zjistit, které události se neovlivňují?

Další možnost by zřejmě byla používat klasické transakce nad relační DB, ale otázka, zda by to bylo vhodné řešení.

Hra už existuje asi 10 let, byla údajně vytvořena v PHP+MySQL. Tedy výkon počítačů byl značně nižší než nyní. V té době např. MySQL ještě transakce ani neuměla (verze 5 přišla až o rok později).

Co si o tom myslíte? Jak to dělali/mohli dělat před 10 lety a jak na to jít v současné době tak, aby to mohlo zpracovat co největší množství událostí za jednotku času a tedy to stíhalo co nejvíce paralelních hráčů? A nakonec i z pohledu spolehlivosti (odolnosti proti výpadku serveru). Nejde mi o konkrétní technologie, ale o princip, ideu.
« Poslední změna: 20. 10. 2014, 10:47:49 od Petr Krčmář »


Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #1 kdy: 19. 10. 2014, 10:04:25 »
Dopředu analýzou zjistit, co jde dělat paralelně a to dělat paralelně. Mít populaci na serveru jen takovou, aby to server stíhal (pak máš to s1., s2., ...).

Bla

Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #2 kdy: 19. 10. 2014, 10:17:43 »
V Travianu to funguje následovně:
Uživatelské rozhraní funguje jako generátor dat, která se ukládají do DB.
Pak jsou tam "procesory", které události zpracují.

Jedná se o následující procesory:
- stavby a obchod
- bitvy

Vyšleš vojáky do vesnice X, ve chvíli vyslání se do budoucnosti naplánuje událost útok.
Spolu s tebou vyšle do vesnice X vojáky pět tvých kamarádů tak, aby dorazili ve stejnou vteřinu jako ty.
Někdo jiný vyšle do vesnice X posily, ve chvíli vyslání se do budoucnosti naplánuje událost přišla posila.
 
Máš tedy naplánované události:
- útok: 0:51 vteřin
- útok: 0:51 vteřin
- útok: 0:51 vteřin
- posila: 0:51 vteřin
- posila: 0:51 vteřin
- posila: 0:51 vteřin

Plánovač, tedy procesor, prochází DB a počítá si děj.
Nastala 0:51
- vezme všechny posily, narve je do města
- vezme všechny útoky, spojí je dohromady a pak nějak vygenerují výsledek
- výsledek se zapíše do DB, s uživatelským UI se vůbec nespojuje, tam se zobrazí až při příštím refreshi

Původně, někdy v roce 2002?, kdy jsem hrál travian poprvé, to všechno bylo velmi jednoduché.
Dokonce docházelo ke stavům, že procesor útoků nestíhal a pak jsem viděl červeně, že nastal útok třeba minutu, než přišel výsledek.
Ze začátku taky nešlo tuším kumulovat útoky, to přišlo až později.

Ale o co jde, ve stejnou vteřinu nastává jen minimum údálostí.
Pokud prioritně vyřešíš boje mezi hráči, tak ostatní eventy mohou počkat.
Hlavně musíš korektně vyřešit plánovač.
Plánování délky chůze nesmíš generovat na klientovi, jinak budou lidi cheatovat s instatnním útokem napříč mapou.

Travian je megajednoduchá hra, kterou by měl zvládnout naprogramovat šikovnější středoškolák.

Velkou výhodou je, že například produkci farem může počítat klient a nemusíš jí počítat ty.
Tedy, ty tu produkci počítáš taky, ale počitadlo jeho počitadlo zobrazuje neustále aktuální stav.
Ovšem ve chvíli, kdy začne něco stavět, vezmeš to ze stavu, který počítáš ty, aby nešvindloval.

Navíc Travian je ohromná řada malých funkcí, které nejsou vzájemně provázané, takže můžeš postupně udělat stavění vesnice, pak přidat produkci farem, pak přidat útočení, jednotlivé věci nejsou přímo propojené, přesněji řečeno můžeš stavě baráky a přitom se nemusíš zabývat tím, jestli tam někdy nějací vojáci budou.

Prakticky nemušíš analyzovat nic, co jde paralelně.
Představ si, že bys stavěl třeba nějakou zeď, kteár ti má zlepšit obranu vesnice.
Co se stane, pokud ty jí v útoku nezohledníš, protože ještě neproběhl event upravující obranu vesnice?
Nic, hráč ti nic nedokáže!
Stejně tak ti nedokáže nic, pokud ti bude blbě počítat vyhodnocení bojů, bude nasranej, přemejšlet, proč to tak dopadlo, ale pokud zrovna jeho tisíc vojáků neporazí jeden panáček, tak nad tím nasraně mávne rukou.

Je to o tom, že při vyslání vojáků stanovíš target.
Plánovač si periodicky zjišťuje, kam ty útoky jdou.
Select * from utoky where target=vesniceX
Na základě nalezení události vytvoří plán provedení tak, aby nejprve proběhly události v čas 0.50, pak 0.51 a nakonec 0.52
Je to o tom, abys nemusel každou vteřinu vyhodnocovat, jestli na každou vesnici nejde útok.

A to, jak si data při útoku srovnáš, jestli jednotky sečteč nebo ne, to je vedlejší.

Bla

Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #3 kdy: 19. 10. 2014, 10:21:44 »
Jo a klidně můžeš udělat širší časové okno.
Proč by útok nemohl probíhat celou minutu?
Války taky netrvají vteřinu.
Město může být klidně minutu zahalené do ohně, pokud bude útok dostatečně silný.
Ty si v danou minutu postupně seřadíš, co tam jde a můžeš to vypočítávat nějak místně a zajímavěji, než vteřinový útok v travianu.
Za minutu s moderním počítačem vypočítáš let na měsíc a zároveň sečteš příjem všech Američanů z formulářů sčítání lidí.

vojta

Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #4 kdy: 19. 10. 2014, 11:00:00 »
Takovahle uloha je zrovna pomerne dost dobre paralelizovatelna. Slusna cast akci je celkem hodne izolovanych (jako treba stavba budovy) nebo pomerne snadno roztriditelnych na nezavisle (hraci, co se navzajem nemohou v danou chvili ovlivnovat) a navic vypocetne dost jednoducha. Postaveni budovy ci vytvoreni jednotky je otazka zapisu hodnoty nekam do databaze. Vyhodnocovani boje trvajiciho nejakou dobu bude v urcitych casovych intervalech a opet vypocetne celkem jednoduche.

Nejvic zamysleni tedy vidim spise v tom, udelat architekturu dostatecne lehkou a pruznou, aby mela velkou propustnost a byla dobre skalovatelna. Ale to je spis asi o hrani si s clusterem serveru, coz s vykonem dnesnich stroju ma vyznam resit az v pripade, ze bude hrat tak pul planety :). V ramci jednoho serveru bude jen nekolikero zpracovavajicich procesu/vlaken + webserver obsluhujici lidi.
Ohledne drzeni a zpracovavani udalosti bych pro zacatek zkusil pouzit nejake okno udalosti, co se bude drzet v pameti. Tahat kazdou jednu z databaze by v pripade velkeho mnozstvi hracu bylo narcne, ale jednou za cas natahnout "davku" ke zpracovani neni problem (celkem bezny pristup).

Cele je to rozhodne dalece mene narocne na zdroje nez "opravdove" online hry (napr. MMORPG jak World of Warcraft). Mozna i proto jsem vzdycky mel hry typu Travian za absolutni odpad nabizejici temer nulovou zabavu (vecne cekani) a pokud clovek nechce cekat, tak nehorazne platby vpodstate za nic (zkraceni cekani).


Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #5 kdy: 19. 10. 2014, 12:30:30 »
No, mas daemony, kteri pocitaj akce, ktery maji zpozdeni (kazdej pro jednu cast mapy), php je na webserverech, info si taha z daemonu (pokud je to akce pres oblasti vice daemonu, tak je treba trocha synchornizace, ktera je tosku narocnejsi, ale techdle requestu bude minimum). webservery by mely komunikovat db prave skrze daemony. pred webservery pak posadis load balancer (za predpokladu, ze budes mit fakt hafo hracu, bezne by ti mel stacit jeden daemon a jeden webserver a mely by se vejit i s db na jeden stroj). Vetsina veci, co daemon bude delat budou akce typu udelej X za Y minut. Samozrejmosti by mely bejt veci typu odlozena inicializace, prepocet hracskych surovin, az kdyz je potreba vedet, kolik toho ma a pri zmene produkce, odlozeny zapisy do db. jinak toho daemona bych delal treba v jave, tam se jednoduse pracuje s vlaknama a paralelismem (a JVM udela radu optimalizaci, aby to bezelo rychle)

Bla

Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #6 kdy: 19. 10. 2014, 23:30:22 »
Jak vypadá takový démon, který vyhodnotí boje?

Útočník: 10 (pěchota typ 1),20 (pěchota typ 2),30 (koně typ 1)

Obránce: 0,0,60
+ Obranný bonus 10
Obránce: 10,10,70

Pak:
Útočník: 10,20,30
Obránce: 10,10,70
Výsledek prvního kola:
Útočník: 0,10,0
Obránce: 0,0,40
Výsledek druhého kola:
Útočník: 0,0,0
Obránce: 0,0,35

Je to naprosto primitivní matematika a troufám si tvrdit, že zvládneš počítat stovky bojů za vteřinu jediným vláknem.

A teď otázka, kolik asi takových bojů v jedné jediné vteřině bude co?

I kdyby ti každý server hrálo deset tisíc hráčů, kdy dojde ve stavu, že v jednu stejnou vteřinu budou probíhat boje řekněme na víc než ve dvou městech naráz?

Prostě tohle, když se to udělá jednoduše, je velmi výpočetně nenáročné a je zbytečné přemýšlet nad složitým škálováním.

Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #7 kdy: 19. 10. 2014, 23:58:52 »
autor se ptal, jak udelat hru skalovatelnou, tj je mozny, ze planuje neco vypocetne slozitejsiho, jinak u delani veshi v php je treba ohlidat vykonavani boju asynchronne (tj az kdyz nekdo vyvola stranku, neco se spocita a aby se to nespocitalo dvakrat [dva lidi po dlouhy dobe naraz nactou stranku])

TondaG

Re:Jak principálně na tvorbu her typu Travian?
« Odpověď #8 kdy: 20. 10. 2014, 00:22:53 »
Děkuji za odpovědi. Cílem je udělat to tak, aby mohl být ohromný herní svět s velkým množstvím hráčů. Nejde tedy o klon Travianu, ale principem je to velmi podobné. Např. Travian je dnes provozován celosvětově na stovkách nezávislých herních světů. Ve výpočetní složitosti nevidím takový problém. Nejpomalejší bude podle mě získání potřebných údajů a zápis změn. Samozřemě, pokud vše bude provozováno na jednom počítači v RAM, tak to bude zvládat vše velmi rychle, ale budou s tím zase jiné problémy (např. odolnost proti výpadku serveru). Zadalší průměrný počet událostí za sekundu bude asi poměrně malý, ale je třeba zvládat i špičky (pokud člověk nechce rezignovat a říct si, že to stejně nikdo nedokáže apod.). A špičky mohou být i poměrně velké, protože snaha koordinovat akce na jeden okamžik apod. tu přirozeně jsou, navíc hraje roli denní doba, různé globální události apod.

ehm

Re:Jak na tvorbu her typu Travian?
« Odpověď #9 kdy: 20. 10. 2014, 12:46:03 »
kazde mmo porusuje transakcni integritu uz v navrhu. napis si kriteria, ktere by si rad a postupne z nich ubirej az do faze, ktera bude unosna pro provozni zatez, implementaci, hrace. urcite se situace opet zopakuje a opet dojde na navrh bez transakcni integrity. a je jen velmi malo kusu, kde se investovalo i do navrhu vyporadani integritnich kolizi zpusobem, kdy se server snazi vyhovet obema stranam soucasne.