4 AI - Umělá inteligence
4.1 Úvod
Umělá inteligence (AI), neboli počítačem řízený protihráč je jedním ze
stěžejních prvků hry 8 Kingdoms. Zajišťuje zajímavost a zábavnost hry i bez
lidských protihráčů. Při jejím vývoji nebylo využito funkčnosti žádných
externích knihoven či frameworků. Jedinou výjimkou je využití skriptovacího
jazyka TCL pro počítání rozličných vzorců potřebných k fungování AI (o tom více
v odstavci 4.3). Veškeré výpočty provádí AI na Serveru a komunikuje pouze s
modulem World. S ostatními moduly hry 8 Kingdoms (GUI, RM, NET) vůbec
nekomunikuje.
Soubory zdrojového kódu k modulům AI se nacházejí v adresáři ai hlavního
adresáře projektu. Samotný adresář obsahuje zdrojový kód pro obecné fungování
AI jako celku a podporu skriptování a také 4 adresáře obsahující zdrojové kódy
4 oddělených modulů tvořících jádro AI ve hře 8 Kingdoms:
-
Vyhledávání cesty (modul Pathfind - adresář ai/PathFind)
-
Diplomacie (modul Diplomacy - adresář ai/Diplomacy)
-
Analyzátor mapy (modul Map Analyzer - adresář ai/MapAnalyzer)
-
Strategický plánovač (modul Strategizer - adresář ai/Strategizer)
4.2 Moduly AI a jejich vzájemné fungování
Každý z výše uvedených modulů je reprezentován třídou, jenž dědí z tzv. třídy
transceiveru. Třída transceiveru obsahuje rozhraní pro volání metod odvozené
třídy obsahující samotnou logiku modulu pomocí Message systému ve hře (více viz
odstavec 1.3). Je v nich implementována registrace do fronty transceiverů
a předávání parametrů modulům. Sama o sobě nemá žádný smysl, je tedy abstraktní
a obsahuje čistě virtuální metody, jenž jsou pak volány v odvozené třídě.
Všechny čtyři moduly (respektive instance tříd, jenž je reprezentují) jsou
vytvořeny a spravovány v rámci třídy CAIEngine
(viz ai/ai.h), která je na začátku korektně vytvoří, dovolí jim zaregistrovat
se ve frontě transceiverů a na konci je dealokuje. Tato třída je uzavřena v prostoru
jmen ai_ns, ve kterém je uzavřena též veškerá
implementace AI modulů, ty však jsou vnořeny ještě do dalších prostorů jmen.
Existuje jediná externí instance třídy CAIEngine
(její název je ai_ns::AIEngine), jenž je vytvořena
voláním funkce ai_ns::AIInit a zrušena voláním funkce
ai_ns::AIDestroy. Tyto funkce jsou volány ve funkci
main (tedy v hlavní funkci celého programu).
Samotné moduly se díky systému zpráv (viz odstavec 1.3) mohou volat vzájemně v podstatě
libovolně, navíc mohou taktéž pomocí zpráv volat jiné existující moduly, jenž
jsou zaregistrovány ve frontě transceiverů. Existuje však určitá hierarchie,
podle které se moduly vzájemně volají. Tu znázorňuje následující diagram:

Diagram 4.1: Základní struktura volání modulů AI
4.2.1 Vyhledávání cesty
Modul Pathfind je primárně určen pro vyhledávání optimální (tj. nejkratší možné) cesty
pro danou jednotku na mapě. Je volán nejen interně moduly AI, ale i "zvnějšku" modulem
World. Sám však komunikuje i s modulem World, a to konkrétně v jednom případě - při
zjišťování ceny dostupnosti sousedního hexu pro danou jednotku. Modul navíc obsahuje
i algoritmus záplavy (A* Flood) jenž je hojně využíván ostatními moduly AI. Oba algoritmy
budou podrobně popsány níže.
4.2.1.1 A* algoritmus
Samotný algoritmus A* je velmi univerzální, dá se využít nejen pro hledání cesty na nějakém
dvourozměrném plánu jako v našem případě, ale v obecném stavovém prostoru, kde je jasně
definována určitá pozice a její dostupní sousedé. Algoritmus využívá dvě obecné datové
struktury (v literatuře nejčastěji označeny OPEN a CLOSED), jenž uchovávají tzv. uzly, což
je datová struktura, reprezentující cestu od počátku do určité pozice na mapě. Každý uzel musí
kromě určení, které pozici náleží, obsahovat následující hodnoty (stejnými písmeny jsou většinou
označovány i v literatuře):
-
g - tato hodnota určuje celkovou cenu, kterou musíme zaplatit po cestě od startovní pozice
do daného uzlu
-
h - tato hodnota určuje odhadovanou cenu za jakou se dostaneme z tohoto uzlu do cílové
pozice. Tato hodnota je pouze odhad (tzv. heuristika), protože nevíme jakou cenu má zbývající cesta
doopravdy. Je nutné podotknout, že aby byla výstupem A* algoritmu opravdu optimální cesta, nesmí
být odhad cesty do cíle nikdy heuristikou přeceněn (tzv. monotónní heuristika). V případě naší hry
byla použita prostá hexová vzdálenost (viz metoda hexDistance třídy
CPathFindEngine v ai/PathFind/pathfind.cpp).
-
f - tato hodnota je součtem hodnot h a g a reprezentuje náš nejlepší odhad
pro cenu cesty přes tento uzel (čím nižší hodnota to je, tím lepší se nám cesta jeví).
Každý uzel musí navíc obsahovat odkaz na svého předchůdce, tj. na uzel, ze kterého sem došel.
Tento odkaz slouží pak k zpětnému určování nalezené cesty směrem od cílového hexu k počátečnímu.
Definici datové struktury uzlu lze nalézt v ai/PathFind/pathenv.h - jedná se o
TNode nebo o THeapNodeValues
pro verzi A* s haldami (více viz odstavec 4.2.1.2).
Samotný algoritmus A* pak pro dva vstupní parametry souřadnic pozic startu (
S) a cíle (
C) funguje takto:
-
Vypočítej hodnoty f,g a h pro uzel v S.
-
Přidej tento uzel do OPEN (v této chvíli je jediným uzlem v OPEN).
-
Nechť X je nejlepší uzel z OPEN (má nejnižší hodnotu f). Pokud pozice uzlu X odpovídá pozici C, pak
optimální cesta byla právě nalezena a algoritmus zpětně pomocí příznaků předchůdců na postupně uzlech zjistí optimální cestu
a poté skončí. Pokud je OPEN prázdný, žádná cesta z S do C neexistuje a algoritmus také končí.
-
Nechť Y reprezentuje uzel na pozici sousedící s X a nejsou v CLOSED (může již existovat v OPEN,
nebo být nově vytvořen). Pro již existující uzel Y zjisti cenu přechodu z X do Y (zde označíme
n) a pokud je g(X)+n < g(Y), pak aktualizuj hodnotu g(Y) a odkaz na předchůdce na
X. Pro nově vytvořený uzel Y nastav hodnotu g(Y)=g(X)+n. Poté dopočítej hodnoty
h a f a pro nově vytvořený uzel Y ho přidej do OPEN. Tento krok proveď pro všechny uzly
sousedící s pozicí na uzlu X, jenž ještě nejsou v CLOSED.
-
Přesuň uzel X z OPEN do CLOSED a přejdi na krok 3.
Protože algoritmy pro vyhledávání cesty jsou používány velmi často, měly by být co nejrychlejší. V kroku 4
výše uvedeného algoritmu potřebuji zjistit, zdali již uzel není v CLOSED. V implementaci je toto
řešeno mapou příznaků (viz TPFMarkMap v ai/PathFind/pathenv.h).
Mapa příznaků je pouze struktura velikosti rozměrů samotné mapy, jenž nám říká, zdali je nutné na danou
pozici expandovat (tedy zdali již není uzel tuto pozici reprezentující v CLOSED či se na pozici
nemá expandovat vůbec). V kroku 4 se tedy pro každou sousední pozici (sousední hex) algoritmus ve hře
podívá do mapy příznaků, zdali tam má expandovat.
4.2.1.2 Optimalizace A* pomocí hald
Rychlost A* algoritmu závisí krom dobře navržené heuristické funkce (odhad délky cesty do cíle) též na
konkrétních datových strukturách OPEN a CLOSED. Modul PathFind byl nejprve naimplementován
s OPEN a CLOSED datovými strukturami jako spojovými seznamy, nicméně poté byl v nové verzi
optimalizován s datovými strukturami hald, jenž přinesly znatelné zlepšení hlavně na rozsáhlých mapách.
Při bližším prozkoumání, jaké operace základní verze A* algoritmu provádí na datových strukturách OPEN
a CLOSED lze snadno zjistit, že je potřeba uzly mít setříděné dle hodnoty f (či být schopen
efektivně vyhledat uzel s nejnižší hodnotou f) snadno je přidávat a odebírat. Pro tyto požadavky
na datové struktury se perfektně hodí právě haldy. Asymptotická časová složitost přidání či odebrání v haldách
je rovna O(LogN) a nalezení minima je možné dokonce v konstantním O(1) čase, protože nejmenší prvek je přímo
v kořeni haldy. Třídění uzlů v haldě je tedy prováděno podle hodnoty f.
Obě struktury OPEN i CLOSED jsou v optimalizované verzi haldami (viz THeap
v ai/PathFind/pathenv.h). Implementace hald má oproti například spojovým seznamům nevýhodu v tom, že
při odebrání nebo přidání prvku je potřeba haldu konsolidovat - přesunout určité prvky, aby byla opět splněna
vlastnost haldy (synové jakéhokoliv vrcholu mají větší klíčovou hodnotu, nežli prvek sám). Proto je nutné oddělit
v prvku haldy samotné hodnoty uzlu (viz THeapNodeValues v ai/PathFind/pathenv.h)
a informace o tom, kde se v haldě prvek nachází (viz THeapNode v ai/PathFind/pathenv.h).
Každý prvek haldy obsahuje pouze ukazatel na hodnoty uzlu - hodnoty uzlu jsou tedy nezávislé na prvku haldy a není pak problém
s její konsolidací. Je potřeba také mít pole ukazatelů velikosti mapy, kde jeho položky budou ukazovat na uzel pro danou pozici, pokud
existuje (proměnná HeapNodesMap třídy CPathFindSkelet).
To je z důvodu hledání, zdali při expanzi uzlu a prověřování sousedních pozic uzel již existuje nebo má být vytvořen nový.
Samotné prvky haldy tvoří klasickou strukturu binárního stromu - musí mít ukazatele na své syny a i na svého rodiče.
Navíc kvůli operacím, kde přidávám nebo umírám prvek haldy, potřebují ukazatele na předchozí a následující prvek v posloupnosti
dle procházení do šířky. Celou strukturu fungování haldy znázorňuje následující obrázek:

Diagram 4.2: Struktura haldy v A* algoritmu
4.2.1.3 A* Flood algortimus
Kromě klasického vyhledávání cesty nabízí modu PathFind ještě jeden užitečný algoritmus. Jedná se o algoritmus
záplavy (pracovně pojmenovaný a i v dalším textu označovaný jako A* Flood), jenž zjistí pro každý hex určité
oblasti cenu pohybu jednotkou od zadaného startovního hexu. Jedná se v podstatě o neřízený A* algoritmus, jenž
nehledá žádný cíl a má heuristiku vždy rovnou nule. Končí vždy úplným vyprázdněním OPEN struktury
a navrací pouze masku s hodnotami cen pohybu na daný hex. Existuje jak ve verzi se spojovými seznamy, tak ve
verzi s haldami. Jako vstup má A* Flood ještě navíc masku velikosti mapy, jenž má počáteční hodnotu natavenou na
hodnoty FLOOD_MASK_VALUE_NOT_ACCESSIBLE. Tam kde hráč vůbec nevidí (tím se
nemyslí prozkoumaný hex s fog of war (viz odstavec 3.7.2), ale úplně neprozkoumaný hex) se nastaví hodnoty
FLOOD_MASK_VALUE_CANT_SEE - A* Flood tam pak ani neexpanduje.
A* Flood tuto masku ve výsledku modifikuje tak, že tam kde jednotka může dojít, je kladná číselná hodnota. Tam
kam se jednotka dostat nemůže, zůstane hodnota FLOOD_MASK_VALUE_NOT_ACCESSIBLE.
A* Flood algoritmus je hojně využíván při taktických manévrech umělé inteligence jako je například útok na jednotku.
AI si v tom případě od Worldu nechá zjistit, z jakých hexů je možné útočit určitou jednotkou na jinou, pak zavolá
A* Flood algoritmus a zjistí, který z nich je jednotce nejblíže. Na ten pak jednotku pošle a zavelí k útoku.
Jiným příkladem využití A* Flood algoritmu je stavba mostů (více viz odstavec 4.2.4.4). Nejprve je spuštěn algoritmus
klasický, poté s módem transparence ignorování vody (více o transparencích viz odstavec 4.2.1.4). Pak jsou porovnávány
hodnoty výstupních masek a podle toho se určí zdali a případně i kde se bude stavět most.
4.2.1.4 Módy transparence při vyhledávání cesty
Modul Strategického plánování hlavně pro expanze a útoky (více viz odstavce 4.2.4.3 a 4.2.4.4) potřebuje často
synchronizovat skupiny jednotek. Například pro útok se vytvoří útočná skupina, sejde se na určitém místě a poté
zaútočí na cíl. Problémem je, že pokud všem jednotkám dám za úkol jít na hex, kde se mají shromáždit, v okamžiku,
kdy je hex obsazen (dojde tam například první jednotka), výsledek vyhledávání cesty bude vždy neúspěšný. Cesta nebude
existovat, protože cílový hex je obsazen a na hexu může být v jednu chvíli pouze jedna jednotka - ostatní jednotky
se tedy nikam nepohnou. Jiným příkladem může být, když například jedna jednotka blokuje jiné jednotce průchod přes most.
Lepší, než stát a nic nedělat je v tom případě alespoň jít směrem k mostu a čekat, až se uvolní. Výše zmíněné problémy
řeší právě různé módy transparence.
Jedním ze vstupů pro vyhledávání cesty je i parametr typu TPathFindTransparency
(viz ai/PathFind/pathenv.h). Určuje, zdali a co se má při hledání cesty ignorovat, či úplně upravuje
vlastnosti daného hledání. Následující tabulka stručně vyjmenovává všechny typy transparence pro vyhledávání cesty:
PFT_UnitsNotTransparent | S touto transparencí nemůže cesta procházet přes jakoukoliv jednotku. |
PFT_IgnoreMyUnits | S touto transparencí může cesta procházet přes jednotky hráče, kterému patří jednotka, se kterou cestu vyhledávám. |
PFT_IgnoreTargetUnit | S touto transparencí ignoruje vyhledávání cesty jakoukoliv jednotku na jejím cílovém hexu. |
PFT_IgnoreMyUnitsAndTargetUnit | S touto transparencí ignoruje vyhledávání cesty jakoukoliv jednotku na jejím cílovém hexu a může také procházet přes jednotky hráče, kterému patří jednotka, se kterou cestu vyhledávám. |
PFT_IgnoreAllUnits | S touto transparencí ignoruje vyhledávání cesty jakékoliv jednotky. |
PFT_BridgeAnalysis | S touto transparencí ignoruje vyhledávání cesty všechny hexy s terénem řeky a moře a nahrazuje je plání. Taktéž ignoruje veškeré jednotky a jednotka, jenž cestu vyhledává má pohybové vlastnosti jako lehká pěchota. |
Tabulka 4.1: Přehled PathFind transparencí
Pathfind potřebuje komunikovat s Worldem při zjišťování ceny pohybu dané jednotky z jednoho hexu na sousední hex.
To je zajištěno v metodě getCost třídy CPathFindEngine.
Modul World má vlastní sadu transparencí (mají pracovní název GetCost transparence, viz
TGetCostTransparency v ai/PathFind/pathenv.h) a je nutné transparence
pro PathFind překládat na GetCost transparence, kterým rozumí modul World. Pro většinu PathFind transparencí
existuje přímý ekvivalent GetCost transparence, pouze u transparencí, jenž nějakým způsobem pracují s cílovým hexem
(PFT_IgnoreTargetUnit a PFT_IgnoreMyUnitsAndTargetUnit)
je nutné zkontrolovat, jestli se neexpanduje zrovna na onen cílový hex a GetCost transparenci zvolit podle toho, protože
modul World, ve kterém se požadavek na cenu pohybu na sousední hex vyhodnocuje, nemá žádnou informaci o tom, zdali se
jedná o hex cílový. Transparence fungují úplně stejně jak pro klasické vyhledávání cesty, tak i pro A* Flood algoritmus.
4.2.1.5 Struktura a klíčová volání PathFind modulu
Celý modul PathFind je rozdělen na tři třídy, které tvoří dědičnou hierarchii. Následující obrázek ukazuje,
jak jsou třídy v dědičné hierarchii uspořádány:

Diagram 4.3: Dědičnost tříd PathFindingu
Třída CPathFindSkelet obsahuje obecnou kostru A* algoritmu, jenž pak
využívá vyhledávání cesty nebo A* Flood. Protože se jedná o obecnou kostru nezávislou na konkrétním
typu mapy a jejích vlastnostech, je čistě virtuální. Vyžaduje konkrétní implementaci inicializačních
metod a metod pracujících přímo s informacemi pro danou mapu.
Třída CPathFindTransciever je třídou transceiveru pro modul PathFind
a obsahuje pouze implementaci pro komunikaci s ostatními moduly (více viz odstavec 4.2).
Třída CPathFindEngine obsahuje implementaci metod, jenž pracují již
s konkrétní mapou a taktéž komunikuje s modulem World. Pokud by bylo potřeba nějak změnit prostředí,
ve kterém se vyhledávání cesty realizuje (například místo hexové mapy by byla čtvercová mapa), stačí
pouze přepsat příslušné metody této třídy a vyhledávání cesty bude fungovat stejně. Kromě metod této
třídy je nutno ještě přepsat určitá makra v ai/PathFind/pathenv.h.
Metody třídy CPathFindSkelet v následující tabulce mohou být volány
zprávou z vnějšku modulu PathFind a reprezentují vyhledání cesty A* Flood pro verze algoritmu se
spojovými seznamy i s haldami. V kódu (jedná se o makra PATHFIND_ASTAR_VERSION
a FLOODING_ASTAR_VERSION v ai/PathFind/pathenv.h) lze pouhým
přepsáním makra určit, z jakou vnitřní reprezentací OPEN a CLOSED struktur bude
vyhledávání cesty či A* Flood realizováno.
astarSimple | Metoda pro nalezení cesty ve verzi A* algoritmu se spojovými seznamy. |
astarHeaps | Metoda pro nalezení cesty ve verzi A* algoritmu s haldami. |
astarFloodSimple | Metoda pro algoritmus záplavy (A* Flood) ve verzi A* algoritmu se spojovými seznamy. |
astarFloodHeaps | Metoda pro algoritmus záplavy (A* Flood) ve verzi A* algoritmu s haldami. |
Tabulka 4.2: Přehled klíčových metod modulu PathFind
Je nutné poznamenat, že pro jakékoliv vyhledávání cesty nebo volání A* Flood algoritmu je potřeba i určit,
pro jakou konkrétní jednotku bude prováděno. Každá jednotka má rozdílné možnosti a rychlosti pohybu
přes různé typy terénů. Může tomu tak být, i pokud jsou jednotky stejných typů, protože mohou mít
nakoupeny bonusy, jenž zvyšují body pohybu jednotky.
4.2.2 Diplomacie
Modul Diplomacie slouží k reprezentaci diplomatických vztahů mezi hráči. Hra nabízí systém vyhlašování
či uzavírání nových diplomatických vztahů, při jejichž platnosti jsou hráči vázáni určitými pravidly a
v případě jejich porušení jsou za ně též pokutováni. Velký význam má modul Diplomacie též v tom, že pro
počítačového hráče je schopen rozumně určovat spřátelené a znepřátelené hráče dle jejich akcí a sám
navrhovat a uzavírat nové diplomatické vztahy. Je to naprosto samostatný modul, který po počátečním
nastavení pouze přijímá aktualizační informace z Worldu, ale žádné již nevyžaduje.
Diplomatický vztah mezi dvěma hráči je reprezentován typem TDipRelation (viz ai/Diplomacy/diptypes.h).
Ten obsahuje postupně oficiální diplomatický vztah, navržený vztah, důvěru, odhadovanou důvěru a příznak,
zdali protihráč navržený vztah již viděl. Tyto vztahy má modul Diplomacie interně uloženy v matici vztahů (rozměr 8×8),
kde hodnoty v jednom řádku znamenají vztah hráče k všem ostatním. Hodnoty na diagonálách (diplomatický vztah hráče
k sobě samému) tedy nemají smysl. Diplomatický vztah je jednosměrná relace, matice vztahů tedy není symetrická
podle diagonály. Oficiální vztah (tj. ten, na kterém jsou obě strany dohodnuty a obě jsou o tom srozuměny) musí být
symetrický podle diagonály. Navržený vztah však rozhodně nemusí být symetrický.
Oficiální a navržený vztah může nabývat čtyř hodnot (seřazeno od nejpřátelštějšího k nejvíce nevraživému) - Aliance,
Příměří, Neutralita a Válka. Každý z těchto vztahů se řídí určitými pravidly, při jejichž porušení je dána hráči pokuta.
Tyto pravidla shrnuje následující tabulka:
Aliance | Tento vztah znamená absolutní přátelství mezi hráči. Je zakázáno útočit na jakékoliv jednotky druhého hráče, toto porušení je trestáno pokutou. |
Příměří | Při příměří mohou hráči beztrestně útočit na jednotky druhého hráče. Pokutou se trestá jakýkoliv útok či obsazení budovy nebo města. |
Neutralita | Při neutralitě mohou hráči beztrestně útočit na jednotky druhého hráče. Taktéž mohou beztrestně útočit a obsazovat jeho budovy. Pokutou se trestá jakýkoliv útok či obsazení města. |
Válka | Tento vztah znamená absolutní nepřátelství mezi hráči. Je dovoleno vše - pokuty se nedávají za nic. |
Tabulka 4.3: Přehled a popis hodnot diplomatických vztahů
Hodnoty pokut je možno nalézt jako konstanty v TCL skriptu se Strategickými koeficienty (soubor
res/xml/scripts/ai/strategy_coefs.xml). Při jakémkoliv útoku na jednotku je oficiální diplomatický vztah
okamžitě zhoršen alespoň na vztah Příměří. Při jakémkoliv útoku či obsazení budovy je oficiální diplomatický vztah
okamžitě zhoršen alespoň na vztah Neutralita a při jakémkoliv útoku či obsazení města je oficiální diplomatický vztah
okamžitě zhoršen na vztah Válka. Hráči sami se mohou snažit oficiální vztahy měnit (ať již k lepšímu či horšímu).
To mohou učinit navržením diplomatického vztahu druhému hráči. Pokud se jedná o navržení k lepšímu (navržený vztah
je přátelštější nežli stávající oficiální), ke změně oficiálního vztahu je potřeba, aby druhý hráč navrhl stejný nebo
ještě lepší vztah. Pokud tak učiní, po ukončení tahu druhého hráče vstoupí tyto navržené vztahy v platnost jako oficiální.
Pokud hráč navrhuje zhoršení vztahu (navržený vztah je nepřátelštější než stávající oficiální), nepotřebuje potvrzení navržení
od druhého hráče - oficiální vztah po konci kola druhého hráče nabývá hodnoty navrženého zhoršeného vztahu. Tento
mechanismus je implementován v metodě changeOfficialRelations třídy
CDiplomacyEngine.
Událost obsazení budovy má jedinou výjimku - a to pro most. Protože jakákoliv jednotka, jenž most přejde,
ho zároveň i obsadí, je obsazení/útok na most modulem Diplomacie ignorováno.
Modul Diplomacie ve svých záznamech o hráčích rozeznává i to, zdali se jedná o hráče lidského nebo AI.
Ten potřebuje nějak určovat, s kým by měl udržovat mírové vztahy a s kým by měl válčit. To obstarávají
hodnoty důvěr v diplomatickém vztahu. Jsou to číselné hodnoty na určité škále (ze zdola neomezené,
s maximální hodnotou makra MAXIMAL_BELIEF v ai/Diplomacy/dipcoefs.h).
Modulu Diplomacie jsou během hry posílány informace o každém útoku nebo obsazení budovy či města. Ten je převede
(voláním vzorce některého z TCL skriptů) na jednu hodnotu, jenž udává změnu důvěry pro daného hráče na základě
provedené akce. Nutno poznamenat, že jakákoliv z takových akcí, které ovlivňují hodnoty důvěry, nemusí ovlivňovat
důvěru hráčů, kterých se akce přímo týkala (například u útoku obránce a útočníka), ale důvěru všech ostatních
hráčů (například spojenců či nepřátel obránce nebo útočníka). Tento mechanismus je složitě propočítáván v metodě
calculateEvent třídy CDiplomacyEngine.
Pro lidského hráče propočítávání důvěry nemá moc smysl. Přesto se však dělá z toho důvodu, že například při
nenadálém odpojení lidského hráče v síťové hře je tento hráč nahrazen AI (modul diplomacie pak dostane zprávu
MSG_DIPLOMACY_CHANGE_DIPLOMAT_TYPE, jenž způsobí změnu typu hráče v záznamech
o diplomatech). Pro umělou inteligenci jsou vždy na konci kola brány hodnoty důvěr k ostatním hráčům a z nich
jsou určeny navrhované vztahy k ostatním hráčům (jak je určena navrhovaný vztah z jedné hodnoty důvěry viz metoda
getBeliefRelationship třídy CDiplomacyEngine.
Modul World při hře vypisuje pro každého hráče na začátku kola změny od posledního kola v Diplomatických vztazích.
To vyžaduje, aby byly Worldu takové posílány pro každého hráče zvlášť. Proto modul Diplomacie obsahuje
pro každý záznam hráče kopii matice diplomatických vztahů, ve které jsou uloženy hodnoty vztahů na konci posledního
kola pro daného hráče. Na začátku každého kola je jsou nejdříve modulu World zaslány informace o změnách oproti
aktuálnímu stavu diplomatických vztahů a poté je tato matice pro hráče aktualizována. Změny vztahů v matici
diplomatických vztahů mezi dvěma hráči jsou reprezentovány třídou TPacket_DIPLOMACY_CHANGE.
Tato třída obsahuje seznam změn, kde každá je reprezentována datovou strukturou TDipChange
(viz ai/Diplomacy/diptypes.h).
Samotný modul Diplomacie je reprezentován jednou velkou třídou CDiplomacyEngine
(viz ai/Diplomacy/diplomacy.h). Ta dědí ze své třídy transceiveru CDiplomacyTransciever
(viz ai/Diplomacy/diplomacytransciever.h), jenž obstarává komunikaci s Worldem a jinými moduly AI.
Identifikátory všech zpráv jenž definují komunikaci s modulem Diplomacie začínají prefixem MSG_DIPLOMACY_
a jejich kompletní výčet lze nalézt v implementaci třídy transceiveru tohoto modulu.
4.2.3 Analyzátor mapy
4.2.3.1 Inicializace a princip fungování Analyzátoru mapy
Účelem modulu Analyzátor mapy je provádět rozsáhlé výpočty potřebných výpočtů pro algoritmy Strategického
plánovače (o něm více v odstavci 4.2.4). Je to v podstatě pouze takový podmodul Strategického plánovače
a je využíván pouze jím. Modul Strategického plánovače při své inicializaci zároveň inicializuje modul
Analyzátoru mapy - předá mu sadu pointerů na struktury Worldu, které pak Analyzátor mapy využívá
pro čtení informací na mapě, stejně jako Strategický plánovač. Pro volání funkcí analyzátoru mapy jsou
opět použity posílány zprávy v rámci systému zpráv (viz odstavec 1.3). Samotný modul tvoří pouze jedna třída
CMapAnalyzerEngine (viz ai/MapAnalyzer/mapanalyzer.h), jenž dědí
ze třídy CMapAnalyzerTransciever (viz ai/MapAnalyzer/mapanalyzertransciever.h),
což je pouze třída transceiveru pro modul Analyzátoru mapy podobně jako v ostatních modulech AI. Další
odstavce již popisují problémy, které Analyzátor map řeší.
4.2.3.2 Výběr nejvhodnější budovy pro výcvik jednotky daného typu
Strategický plánovač potřebuje buď pro útoky nebo obranu verbovat nové jednotky ve svých budovách.
Analyzátoru mapy je předán požadavek na vytrénování určitého typu jednotky a ID hexu, kde je jednotka
zapotřebí. Úkolem Analyzátoru mapy je nalézt takovou budovu, kde může být jednotka vytrénována (budova
musí být prázdná a jednotku v ní musí být vůbec možno vyrobit) a ze seznamu takovýchto budov vybrat tu
nejbližší danému hexu. Analyzátor budov ze seznamu budov pro daného hráče vybere ty budovy, ve kterých
lze jednotka vyrobit aktuálně (budova je prázdná a dostavená a jednotka tam lze standardně vyrobit nebo
je brán v potaz i výskyt ras) a pak použije prostou hexovou vzdálenost k výběru té nejbližší. Celý tento
postup je implementován v metodě getNearestFreeProductionBuildingForUnitTrain třídy
CMapAnalyzerEngine.
4.2.3.3 Výběr nejvhodnějšího místa pro stavbu produkční budovy
Při expanzi potřebuje počítačový hráč stavět budovy pro produkci nových jednotek. Zásadním problémem
tohoto procesu je inteligentní výběr místa, kde bude nová budova postavena. Tento problém řeší právě
Analyzátor mapy, a to konkrétně v metodě getBestProductionBuildingPlace
třídy CMapAnalyzerEngine. Metodě jsou předány pozice, kde aktuálně AI
hráč plánuje nebo staví produkční budovy. Analyzátor mapy pak vyhledá všechny své budovy a města a taktéž
všechny cizí budovy a města na které vidí. Poté prochází každý hex mapy, který byl již objeven a je na něm
možno budovu vůbec stavět a počítá pro něj vzdálenosti (prosté hexové) od všech výše zmíněných budov.
Vytváří si tak jistou masku koeficientů. Pro každý relevantní hex nejprve sečte vzdálenosti od cizích
statických entit a od nich odečte součty vzdáleností od svých statických entit a plánovaných budov.
Nakonec pro každý hex přidá i určitý bonus, pokud je na něm výskyt nějakých ras (viz makro
UNIT_OCCURENCE_BONUS). To zaručuje, že se bude AI hráč snažit přednostně
stavět produkční budovy na těchto hexech. Když se takto spočítá celá maska, vezme se největší hodnota.
Podle toho jakému hexu tato hodnota náleží se určí výsledné souřadnice hexu, na kterém se bude stavět
nová budova. Tento proces navíc nabízí i speciální mód pro určitého stavitele. To je z důvodu, kdyby
například nějaký hráč po rozhodnutí stavět na určitém hexu tento hex obsadil svou jednotkou - pak by již
nebylo možné na hexu stavět a celý proces by se zasekl, což je nepřípustné. Speciální mód pro určitého
stavitele poté najde nejbližší dostupný hex pro stavbu produkční budovy vzhledem k pozici daného stavitele.
4.2.3.4 Nalezení pomyslného středu hráčova území
Strategický plánovač potřebuje pro určité operace (jako například verbování jednotek pro obranu nebo
verbování nových stavitelů) znát pomyslný střed hráčova území. Přestože taková pozice není jasně definována
ve všech případech, je potřeba určit alespoň nějaký rozumný kompromis. Tato úloha je řešena konkrétně metodou
findPlayerEmpireCenter třídy CMapAnalyzerEngine.
Pokud AI hráč vlastní nějaké statické entity (města a budovy) je pozice středu hráčova území spočítána dle
prosté hexové vzdálenosti jako jejich těžiště (jedná se o minimalizaci součtu vzdáleností). Pokud AI hráč
žádné statické entity nemá, jsou brány vzdálenosti od všech jeho jednotek.
4.2.3.5 Analýza stavby mostu
Zvláštním problémem, jenž musí AI hráč také řešit je stavba mostů. Jedná se o problém zdali (a pokud ano,
tak navíc na jakém místě) most postavit. Analyzátor mapy řeší tento problém v metodě
bridgeBuildingAnalysis třídy CMapAnalyzerEngine.
Ta vrací ukazatel na TPacket_MapAnalyzer_BridgeBuildingResponse, jenž obsahuje
informace o tom, kde a jak postavit aktuálně nejvíce potřebný most, pokud se vůbec vyplatí nějaký stavět.
Algoritmus pracuje tím způsobem, že prochází všechny AI hráčem objevené hexy, na kterých je vůbec možno stavět
most (jsou to obecně řeky a moře, navíc musí mít okolní hexy stejné převýšení). Pro ně pak generuje zvlášť možnosti
stavby mostu přes všechny povolené orientace mostu (vstupní a výstupní hex musí mít terén pláň - to bylo určeno
z důvodu, že je to jediný terén, po kterém se mohou pohybovat všechny jednotky). Nyní všechny validní
možnosti stavby algoritmus ohodnotí pomocí dvou volání A* Flood algoritmu (více viz odstavec 4.2.1.3). Jednou
je volán s transparencí, jenž pouze ignoruje jednotky a podruhé se speciálním módem transparence určeným právě
pro analýzu stavby mostů (příznak PFT_BridgeAnalysis). Pro každou možnou pozici
stavby mostu analyzuji hodnoty obou volání A* Flood algoritmu na vstupních a výstupních hexech mostu. Pokud je
vstupní dostupný na obou maskách a druhý jen ve výsledné masce druhého volání A* Floodu, jedná se o pozici stavby
mostu, jenž by AI hráči případným postavením umožnil dostat se do oblastí mapy, kam momentálně nemůže, což je primární
cíl stavby mostů. Pak je vybrána ta nejbližší pozice od startovní pozice A* Floodu (což je střed hráčova území). AI
hráč se vždy bude snažit přednostně stavět mosty na místa, kam se nemůže dostat. Jsou však případy, kdy se AI hráč může
dostat všude, ale most by se mu stejně hodilo postavit kvůli ušetření délky cesty. Zde záleží pouze na
vhodném určení kritéria, kdy je vhodné stavět most v závislosti na tom, kolik tahů chůze mi ušetří. To se dá poznat
z rozdílu hodnot výsledkových masek A* Floodu na výstupních hexech mostu. Pokud je větší než určitá mez, znamená
to, že stavba mostu by ušetřila jednotkám dlouhou cestu "okolo". Tato mez je určena makrem
BRIDGE_BUILDING_CRITERIUM v ai/ai_makra.h, které určuje počet kol chůze
jednotky jenž musí být ušetřeny, aby se vyplatilo most stavět. Ze všech takovýchto pozic vyberu tu, která jednotkám
ušetří nejvíce.
4.2.3.6 Ostatní problémy řešené Analyzátorem mapy
Modul Analyzátoru mapy neřeší pouze výše zmíněné problémy, ale i mnoho dalších, jenž jsou však většinou mnohem
jednodušší a není třeba je nijak explicitně popisovat. Zde je alespoň jejich stručný přehled (všechny jsou řešeny
v rámci nějaké metody třídy CMapAnalyzerEngine):
hexDistance | Metoda vrátí prostou vzdálenost mezi dvěma hexy. |
findCityByPosition | Metoda vrátí informace na určeném hexu. |
getRandomInvisibleHex | Metoda vrátí nejvhodnější neprozkoumanou pozici pro daného AI hráče - určuje, kam má poslat své jednotky k průzkumu. |
getActionRadius | Vrací akční rádius (tj. kruhové okolí určitého poloměru) od určitého hexu jako seznam hexů. |
isUnitPossibleToTrainInBuildingOnHex | Vrací příznak, zdali je možno vytrénovat jednotku určitého typu v zadané budově. |
findUnitPosition | Nalezne přesnou pozici jednotky na mapě dle jejího World ID. |
Tabulka 4.4: Přehled dalších metod modulu Analyzátor mapy
4.2.4 Strategický plánovač
Modul strategického plánovače je nejsložitější částí celé implementace umělé inteligence. Má za úkol provádět
konkrétní tahy jednotek, produkovat nové, organizovaně s nimi útočit, opravovat budovy a stavět nové, starat se
o průzkum nových území, atd. Je volán modulem World zasláním zprávy MSG_AI_ON_TURN,
jenž oznamuje, že AI hráč je na tahu a má pro něj být vygenerována posloupnost akcí, které v daném tahu provede.
Ta způsobí zavolání metody AITurnForPlayer třídy
CStrategizerEngine, jenž obsahuje hrubou kostru všech činností, které AI ve
svém tahu vykonává:
-
načtení AI dat specifických pro daného hráče
-
validace a aktualizace hodnot AI dat v porovnání s reálnými daty na mapě
-
rozdělení peněz pro různé oblasti činností AI hráče (obrana, útok a expanze)
-
vylidnění budov (z důvodu, že produkovat jednotky je možné pouze v prázdných budovách)
-
zpracování všech probíhajících procesů útoků, popřípadě plánování nových
-
zpracování všech probíhajících procesů staveb a oprav budov, popřípadě plánování nových
-
sestavení strategického grafu a vygenerování obranného plánu
-
průběh doplňkových akcí pro plně nevyužité jednotky (léčení, doplňování mužů do jednotek, možné útoky na nepřítele, průzkum neobjevených oblastí)
-
uložení modifikovaných AI dat specifických pro daného hráče
-
ukončení tahu a předání řízení opět modulu World
Modul Strategický plánovač má rozděleny své činnosti do určitých komponent. Jejich úkoly a reprezentativní
třídy udává následující tabulka:
Obrana | CStrGraph | Tato komponenta má na starost obranu statických entit (budov a měst) AI hráče. Buduje strategický graf mezi entitami na mapě, provádí na něm výpočet a generuje výsledný plán bránění. Více viz odstavec 4.2.4.3. |
Útočení | CStrategyAttackEngine | Tato komponenta má na starosti organizaci útoků na nepřítele. Určuje cíl útoku, složení útočné skupiny a zajišťuje jeho synchronizaci. Více viz odstavec 4.2.4.4. |
Expanze | CStrategyExpansionEngine | Tato komponenta má na starosti rozdělování peněz AI hráče na různé úkony, stavbu a opravu budov, verbování stavitelů, doplňování mužů do jednotek a jejich léčení. Více viz odstavec 4.2.4.5. |
AI data | CStrategySerialization | Tato komponenta má na starosti ukládání a načítání dat, jenž si musí AI pamatovat i po skončení kola. Více viz odstavec 4.2.4.2. |
Tabulka 4.5: Přehled komponent modulu Strategický plánovač
Kvůli asynchronní povaze modulů Worldu je potřeba, aby i výpočet tahu AI hráče
běžel ve vlákně. K tomu je potřeba i výpočet synchronizovat, na což jsou použity
mutexy a semafory z implementace SDL knihovny. Samotná funkce vlákna
(runAIPlanning v ai/Strategizer/strategytransciever.cpp)
volá metodu AITurnForPlayer třídy
CStrategizerEngine která průběžně kontroluje (pomocí makra
CHECK_AI_THREAD_STATE), zdali nedošlo k přerušení výpočtu
AI ve vlákně z vnějšku. Veškeré informace, které AI potřebuje ke svým výpočtům předá
při její inicializaci World pomocí zprávy MSG_AI_LETS_GO.
Tyto informace je sada pointerů na struktury Worldu, ze kterých AI pouze čte - jedná se
o struktury mapy, budov, jednotek a v podstatě všech relevantních věcí, které World
zpracovává. AI tedy má k dispozici veškeré informace které potřebuje. Protože třídy Worldu
mají poměrně složitou strukturu, pro zjednodušení přístupu k nejvíce využívaným informacím
je použita sada maker v souboru world/useful.h.
4.2.4.1 Zpracování plánu
Výstupem celého strategického plánovače je sada zpráv posílaných do modulu World, jenž reprezentují akce
jednotek nebo budov. Strategický plánovač má pro tyto zprávy naimplementované obalové třídy a navíc tzv.
třídu plánu CPlan. Třída plánu umožňuje tvořit posloupnosti akcí pro modul
World a hromadně je provádět. Umí též poznat ty akce, jenž World neprovedl, protože je označil jako invalidní
a pokusit se tyto akce provést znovu. Klíčovou metodou třídy plánu je processPlan,
jenž pošle všechny akce v posloupnosti k exekuci modulu World. Ve své implementaci obsahuje i možné napojení
na zásobník historie (viz odstavec 3.4.1), nicméně AI nakonec toto možnost nevyužívá a všechny informace čte
rovnou přímo ze struktur Worldu. Po exekuci akcí lze ty úspěšně provedené odstranit z posloupnosti voláním
metody deleteAllDoneActions. Veškeré výše zmíněné třídy lze nalézt
v ai/Strategizer/planning.h.
4.2.4.2 Načítání a ukládání dat AI hráče
Každý AI hráč potřebuje pro rozumné plánování vytvářet a mít přístup k datům, jenž budou perzistentní
(tedy budou mít schopnost přetrvat i po skončení tahu daného hráče). V těchto datech jsou uloženy záznamy
o jednotkách (jejich primární určení činnosti), záznamy o přidělených penězích jednotlivým činnostem, záznamy
o průběhu procesů útoků, procesů staveb a procesů oprav budov. O načítání a ukládání AI dat se stará třída
CStrategySerialization (viz ai/Strategizer/strategyserialization.h).
Veškerá AI data jsou ukládána pouze do jednoho řetězce (char*). Tato třída jej
umí rozebrat a naplnit získanými hodnotami vnitřní struktury a naopak uložit obsah vnitřních struktur do
jednoho řetězce. Tento řetězec je přístupný ve strukturách Worldu, jenž jsou předávány modulu Strategický
plánovač při jeho inicializaci. Jedná se také o jediná data tohoto typu, u kterých může AI něco přímo zapisovat
do struktur Worldu (všechny ostatní Worldem poskytované struktury má AI k dispozici pouze pro čtení).
AI data se při uložení hry ukládají přímo do XML souboru mapy - díky tomu je třeba ošetřovat situace, kdy v AI
datech jsou hodnoty (protože uživateli nic nebrání tyto hodnoty změnit) - v tomto případě AI inicializuje
vnitřní struktury na validní hodnoty dle určitých pravidel a plánuje nové procesy pro ně. AI data se navíc po
načtení musí každé kolo aktualizovat dle aktuálního obsahu na mapě - viz metoda
updateSerializationStructures třídy
CStrategizerEngine.
4.2.4.3 Obrana
Obranná fáze hry má za úkol těm jednotkám, jenž mají u svého záznamu v AI datech (reprezentován typem
TAIUnitInfo) nastavenu položku global_desire
na hodnotu Defence (tedy určení jejich činnosti je obrana), naplánovat
systematické bránění svých budov a měst (v textu dále označovány jako statické entity) před nepřátelskými
jednotkami. Kromě těchto příznaků nepotřebuje plánování obranné fáze ukládat jakákoliv další perzistentní
AI data. Obranná fáze není pouze obrana v pravém slova smyslu, může to být i vyražení na zteč vůči útočníkovi,
jenž ohrožuje mé statické entity.
Stěžejní částí algoritmu, jenž řeší obrannou fázi je vybudování tzv. strategického grafu, jenž je reprezentován
třídou CStrGraph. Tento graf má ve svých vrcholech informace o všech jednotkách
AI hráče určených na obranu, o všech nepřátelských jednotkách na území, jenž má AI hráč prozkoumané a také
informace o všech svých statických entitách. Základní třídou vrcholu grafu je
CStrVertex, od něhož jsou odvozeny další třídy pro konkrétní entity. Pro jejich
zpětné rozpoznávání v grafu je využito mechanismů RTTI a operátoru dynamic_cast.
Jejich hierarchii zobrazuje následující diagram:

Diagram 4.4: Dědičnost tříd vrcholů strategického grafu
Tyto třídy obsahují nutné informace pro plánování jako například pozici entity, její příslušnost a poté
specifické informace pro konkrétní třídy (například pro města jeho velikost, pro jednotky příznak, zdali
bojují nablízko nebo umějí střílet, atd.). Pro kompletní výčet těchto informací viz Doxygen dokumentaci
výše uvedených tříd.
Po shromáždění všech vrcholů a jejich inicializaci je třeba mezi nimi vytvořit hrany dle určitých pravidel.
Základní třídou hrany ve strategickém grafu je CStrEdge, jenž obsahuje
reference na vrcholy, které spojuje a tzv. časovou disponibilitu, což je počet kol, za které může entita
(zde pouze jednotka) prvního vrcholu dojít či zaútočit na entitu druhého vrcholu. Časovou disponibilitu
spočtu pomocí volání vyhledávání cesty modulu PathFind. Je třeba rozlišit, zdali se jedná o hranu, jenž
reprezentuje pouze relaci dostupnosti nebo relaci útoku na entitu. V druhém případě je hrana reprezentována odvozenou
třídou CAttackEdge (pro zpětné určení typu třídy hrany je stejně jako
u vrcholů využito mechanismů RTTI). Tato třída obsahuje oproti CStrEdge navíc
i souřadnice bodu (tzv. action point), ze kterého může entita prvního vrcholu hrany útočit na entitu druhého vrcholu
hrany. Souřadnice tohoto bodu se zjišťuje pomocí volání zprávy MSG_GET_INVERSE_ATTACK_RANGE
a následného volání A* Flood algoritmu na navrácené hexy, z nichž je poté vybrán ten nejbližší. Action point je
tedy souřadnice nejdostupnějšího hexu pro entitu prvního vrcholu hrany, ze které může zaútočit na entitu druhého
vrcholu hrany. Je důležité uvést, že hrany ve strategickém grafu jsou orientované, mezi dvěma vrcholy tedy mohou
být i dvě hrany opačných orientací. Navíc hrany se nevytváří mezi každými dvěma vrcholy. Jediným případem, kdy
vytvářím hranu reprezentovanou třídou CAttackEdge (tedy hranu pro útočení) je
mezi jednotkou AI hráče a cizí jednotkou. Hrany reprezentované třídou se vytváří pak CStrEdge
mezi libovolnou jednotkou (náležející AI hráči nebo cizí) a jakoukoliv statickou entitou AI hráče. Celý výše uvedený
postup vytváření strategického grafu je obsahem metody buildStrategyGraph třídy
CStrategizerEngine.
Po vystavění strategického grafu nastává čas na plánování tahů jednotek určených pro bránění. To zajišťuje
metoda generateDefencePlan třídy CStrGraph.
Prvně ze strategického grafu vygeneruji struktury tzv. hrozeb (reprezentovány typem TThreat),
což je jiná reprezentace každé hrany od cizí jednotky k statické entitě AI hráče. Poté se podobně vygenerují
struktury tzv. zdrojů reprezentující bránící jednotky AI hráče schopné pokrývat hrozby. Nakonec se vygenerují
struktury tzv. potřeb reprezentující statické entity AI hráče, jenž mají být bráněny. Tyto potřeby se ohodnotí
a seřadí dle své důležitosti. Poté přes ně iteruji a kontroluji, zdali některá hrozba (primárně beru hrozby
od nejnižší časové disponibility, tedy ty nejvíce akutní) neohrožuje právě danou potřebu a pokud ano, přiřazuji
jí (dle časové disponibility) vhodný zdroj. Přiřazení jednoho zdroje jedné hrozbě pro danou potřebu a generování
konkrétních akcí je obsahem metody performDefensive třídy
CStrGraph. Nakonec se ještě provádí doplňkové činnosti obranné fáze, jako
například útočení na neútočící cizí jednotky (například cizí stavitel na území AI hráče) - viz metoda
performRestDefensive.
Obranná fáze, výstavba strategického grafu a generování plánu na něm je pravděpodobně programově nejsložitější částí
celého modulu AI. Umělá inteligence ve hře nabízí zvolení různé obtížnosti - to se projeví pouze v obrané fázi
při přidělování zdrojů a hrozbám. Při nízké úrovni umělé inteligence se berou v potaz hrozby s časovou disponibilitou
menší, nežli při vyšší úrovni umělé inteligence. Vyšší úroveň umělé inteligence tedy řeší více hrozeb a v důsledku
toho i úpěnlivěji brání své území.
4.2.4.4 Útočení
Útočná fáze AI hráče má na starosti organizovaný útok na nepřátelské budovy a města. Navíc za určitých
okolností může cíleně útočit i na nepřátelskou jednotku, jenž nebrání žádnou nepřátelskou statickou entitu.
Všechny činnosti ohledně útoku jsou implementovány v rámci třídy CStrategyAttackEngine.
Narozdíl od obranné fáze, je zde potřeba ukládat specifická AI data obsahující informace o útočném procesu.
Ten je reprezentován typem TAIAttackInfo a obsahuje informace o cíli útoku,
stavu útoku a jednotkách, jenž jsou pro útok určeny, popřípadě přímo obsazeny. Nové útočné procesy jsou
plánovány v metodě findBestAttackTarget, jenž vrátí souřadnice nejideálnějšího
cíle útoku pro daného AI hráče. Poté je dle síly cíle útoku určeno složení útočné skupiny a útočný proces je
přidán do globální struktury spravující všechny útočné procesy. Tam jsou tyto útočné procesy zpracovávány voláním
metody updateAttacks, přičemž pro zpracování jednoho konkrétního útočného procesu
je volána metoda processAttack. Ta dle stavu útočného procesu určí akce přiřazených
jednotek (nebo vytvoří v nějaké budově jednotku novou, jenž pak útočnému procesu přiřadí) a změní stav (tento stav
je reprezentován typem TAttackState, viz ai/Strategizer/strategytypes.h),
pokud jsou splněny určitá kritéria. Ty jsou zřejmé z následujícího obrázku, kde je zachycen životní cyklus
útočného procesu:

Diagram 4.5: Životní cyklus útočného procesu
Třída CStrategyAttackEngine též zajišťuje (až po zpracování veškerých
útoků, staveb a oprav a obranné fázi) útočení nevyužitými jednotkami. Ty jednotky, jenž mají ve svém dosahu
nepřítele a jsou schopny na něj v tomto kole zaútočit, tak učiní. Tuto funkčnost implementuje metoda
processAttackingWithUnusedUnits.
Další doplňkovou činností, jenž třída CStrategyAttackEngine provádí
je průzkum neobjevených částí mapy jednotkami, jenž nejsou přiřazeny k žádnému procesu útoku. Je
pro ně určen náhodný neprozkoumaný hex, k němuž jsou poté vyslány - viz metoda
processExploringWithUnassignedAttackers.
4.2.4.5 Expanze
Fáze expanze má za úkol hlavně rozdělování peněz na jednotlivé činnosti (útok, obrana a expanze), stavbu
nových budov, opravu existujících poškozených budov a navíc ještě péči o jednotky jako léčení a doplňování
mužů. Všechny výše zmíněné činnosti jsou implementovány v rámci třídy
CStrategyExpansionEngine.
Jedním z problémů, jenž komponenta pro expanzi řeší je stavba nových produkčních budov. Co se týče umístění,
to nechává počítat modul Analyzátor mapy (viz odstavec 4.2.3.3). Musí však určit kdy má postavit jakou budovu.
V TCL skriptu se Strategickými koeficienty (soubor res/xml/scripts/ai/strategy_coefs.xml) je ve výstupní
proměnné BUILD_ORDER určeno pořadí (dle ID typů budov v RM), ve kterém se mají
budovy stavět. Ve stejném skriptu jsou navíc uloženy relativní četnosti počtu budov pro celou posloupnost.
AI hráč nejprve spočítá voláním metody countBuildingStatistics počty všech
svých budov a plánovaných budov. Poté vydělením relativními četnostmi na jednu posloupnost dostane poměr
pro každou budovu a bude stavět právě tu, jenž má tento poměr nejmenší. Nové stavby produkčních budov nejsou
plánovány donekonečna, ale jsou omezeny počtem království, jenž AI hráč vlastní (viz metoda
shouldBuildNewBuildings). Co se týče stavby mostů, komponenta pro
expanzi může mít v jednu chvíli naplánován pouze jeden proces stavby mostu. To je z toho důvodu, že modul
Analyzátor mapy, jenž umístění nejvhodnějšího mostu počítá (viz odstavec 4.2.3.5) by volal A* Flood algoritmus
při výpočtu dvou masek určujících možné pozice mostů bez existence nového mostu, což by dávalo hloupé výsledky
(například dva mosty těsně vedle sebe).
Dále komponenta pro expanzi spravuje verbování stavitelů a jejich využívání na stavbu nově naplánovaných budov
či opravu existujících poškozených budov. Co se týká verbování nových stavitelů, probíhá stejně jako verbování
jakýchkoliv jiných jednotek - naleznu volnou budovu jenž umí stavitele vyprodukovat (to má opět v režii modul
Analyzátor mapy, viz odstavec 4.2.3.2). Klíčové je kritérium, kdy je třeba stavitele verbovat. To je závislé na
aktuálním počtu budov AI hráče a řeší to metoda needToRecruitBuilder. Stavitelé
jsou dále přiřazováni jednotlivým plánovaným procesům staveb nebo oprav budov (obě tyto činnosti mají stejnou
prioritu). Proces stavby budovy je reprezentován typem TAIBuildDesireInfo a je
zpracováván metodou processBuild. Jeho životní cyklus zobrazuje následující
obrázek:

Diagram 4.6: Životní cyklus procesu stavby
Životní cyklus opravy budovy (proces opravy budovy je reprezentován typem TAIRepairDesireInfo
a zpracováván metodou processRepair) je velmi podobný. Liší se v podstatě pouze
kontrolou cílového hexu procesu. U procesu stavby je nutné kontrolovat, zdali je cílový hex volný, než k němu
stavitel dojde. U procesu opravy budovy se musí kontrolovat, zdali budova stále existuje a zdali stále patří
danému AI hráči, nežli k ní stavitel dojde.
Další činnosti, které umí komponenta pro expanzi řešit jsou léčení jednotek (viz metoda processHealingWithUnits),
doplňování mužů do jednotky (viz metoda processRecruitingWithUnits), a taktéž
proces opuštění všech svých budov (viz metoda getUnitsOutOfBuildings).
To je důležité kvůli pravidlu hry, že není možno verbovat novou jednotku v obsazené budově. Zvláštní kapitolou
je způsob rozdělování peněz jednotlivým činnostem. Nové peníze (tedy pouze ty, co přibyly od posledního kola)
jsou rozděleny (podle koeficientů v TCL skriptu se Strategickými koeficienty - viz soubor
res/xml/scripts/ai/strategy_coefs.xml) do tří oblastí - útok, obrana a expanze. Částky peněz, jenž má AI
hráč k dispozici pro jednotlivé činnosti musí být perzistentní - ukládají se a načítají z AI dat. Peníze pro
útok slouží k verbování jednotek určených pro útok, peníze pro obranu slouží k verbování jednotek určených pro
obranu a peníze pro expanzi slouží k placení doplňování mužů ve všech jednotkách, na verbování stavitelů, na stavby
nových budov a opravu budov existujících.
4.3 Využití skriptů TCL
Jazyk TCL (Tool Command Language) je silným a užitečným nástrojem pro
skriptování. Je to jediná externí knihovna přímo využívaná v implementaci AI.
Ta využívá TCL pouze a výhradně k počítání různých vzorců pro její vyvážené
fungování. Tyto vzorce by sice mohly být implementovány přímo v C++ kódu AI,
to by však vyžadovalo opětovnou kompilaci celého programu. Vzorce jsou zapsány
jako TCL skripty (viz odstavec 6.4.6) a po jejich modifikaci není nutné program opět
kompilovat. Takto je navíc možné i jednoduše měnit chování AI pro budoucí
modifikace.
Pro snadný způsob volání TCL skriptů se vzorci pro AI byla implementována třída
CAIScriptCaller jenž pro daný účel poskytuje pohodlné
a jednoduché rozhraní. Pro spočítání libovolného vzorce stačí vytvořit její instanci,
předat ji vstupy vzorce, zavolat výpočet a požádat o výsledky. Následující kus kódu
jasně demonstruje práci se třídou CAIScriptCaller
na výpočtu příkladového skriptu pro součet dvou čísel.
// vytvořím instanci Script Calleru pro volání AI skriptů
ai_ns::CAIScriptCaller* sc=new ai_ns::CAIScriptCaller();
// vytvořím strukturu pro vstupní proměnné
ai_ns::CTCLAIVar* varsin=new ai_ns::CTCLAIVar();
// přidám vstupní proměnnou
varsin->addInt("PRVNI_SCITANEC",2);
// přidám vstupní proměnnou
varsin->addInt("DRUHY_SCITANEC",3);
// provedu výpočet na vstupních proměnných
ai_ns::CTCLAIVar* varsout=sc->countScript(AI_SCRIPT_ID,varsin);
// vypíši požadovanou proměnnou z vytvořené výstupní struktury
printf("%d\n",varsout->getInt("SOUCET"));
// dealokuji strukturu se vstupními proměnnými
delete varsin;
// dealokuji strukturu se výstupními proměnnými
delete varsout;
// dealokuji samotný Script Caller
delete sc;
Výše uvedený kus kódu by pravděpodobně vytiskl "5" (pokud samozřejmě má TCL
skript správně pojmenované vstupy, odpovídají jejich typy a i tělo skriptu
opravdu počítá součet). Třída CAIScriptCaller
pouze pracuje s objekty pro vstupní a výstupní proměnné a volá na nich výpočet.
Jaký skript by se měl spustit záleží na prvním parametru metody
countScript, jenž obsahuje ID skriptu, který se
má volat. Tyto ID odpovídají IDčkům tagů xml v souboru res/xml/others.xml.
Jsou to pouze symbolické názvy čísel (viz soubor ai/aiscriptids.h). Druhým
parametrem je objekt se vstupními proměnnými třídy CTCLAIVar.
Tato třída pouze pojmenovává a spravuje proměnné, se kterými skript pracuje (ať už se
jedná o vstupní nebo výstupní proměnné). Pro tyto účely poskytuje následující metody:
// vymaže všechny přidané proměnné z vnitřní struktury
void clearAll();
// přidá proměnnou typu int do vnitřní struktury
void addInt(char* varName,int value);
// přidá proměnnou typu float do vnitřní struktury
void addReal(char* varName,float value);
// přidá proměnnou typu char* do vnitřní struktury
void addString(char* varName,char* value);
// vrátí proměnnou typu int obsaženou ve vnitřní struktuře
int getInt(char* varName);
// vrátí proměnnou typu float obsaženou ve vnitřní struktuře
float getReal(char* varName);
// vrátí proměnnou typu char* obsaženou ve vnitřní struktuře
char* getString(char* varName);
Samotná třída CAIScriptCaller neobsahuje přímo
ve své implementaci věci jako načítání zdroje skriptu z RM, parsování XML souboru
ve kterém je skript zapsán či přímo počítání v TCL. Tyto věci pouze využívá skrz
modul World a upravuje a zjednodušuje jejich používání pro účely AI.