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:
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:
Struktura volání modulů AI.
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):
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:

  1. Vypočítej hodnoty f,g a h pro uzel v S.
  2. Přidej tento uzel do OPEN (v této chvíli je jediným uzlem v OPEN).
  3. 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čí.
  4. 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.
  5. 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:
Struktura haldy v A* algoritmu
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:
Identifikátor transparencePopis transparence
PFT_UnitsNotTransparentS touto transparencí nemůže cesta procházet přes jakoukoliv jednotku.
PFT_IgnoreMyUnitsS touto transparencí může cesta procházet přes jednotky hráče, kterému patří jednotka, se kterou cestu vyhledávám.
PFT_IgnoreTargetUnitS touto transparencí ignoruje vyhledávání cesty jakoukoliv jednotku na jejím cílovém hexu.
PFT_IgnoreMyUnitsAndTargetUnitS 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_IgnoreAllUnitsS touto transparencí ignoruje vyhledávání cesty jakékoliv jednotky.
PFT_BridgeAnalysisS 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:
Dědičnost tříd PathFindingu
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.
Jméno metodyPopis metody
astarSimpleMetoda pro nalezení cesty ve verzi A* algoritmu se spojovými seznamy.
astarHeapsMetoda pro nalezení cesty ve verzi A* algoritmu s haldami.
astarFloodSimpleMetoda pro algoritmus záplavy (A* Flood) ve verzi A* algoritmu se spojovými seznamy.
astarFloodHeapsMetoda 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:
Hodnota diplomatického vztahuPopis hodnoty diplomatického vztahu
AlianceTento 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.
NeutralitaPř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álkaTento 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):
Jméno metodyPopis metody
hexDistanceMetoda vrátí prostou vzdálenost mezi dvěma hexy.
findCityByPositionMetoda vrátí informace na určeném hexu.
getRandomInvisibleHexMetoda vrátí nejvhodnější neprozkoumanou pozici pro daného AI hráče - určuje, kam má poslat své jednotky k průzkumu.
getActionRadiusVrací akční rádius (tj. kruhové okolí určitého poloměru) od určitého hexu jako seznam hexů.
isUnitPossibleToTrainInBuildingOnHexVrací příznak, zdali je možno vytrénovat jednotku určitého typu v zadané budově.
findUnitPositionNalezne 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á:
  1. načtení AI dat specifických pro daného hráče
  2. validace a aktualizace hodnot AI dat v porovnání s reálnými daty na mapě
  3. rozdělení peněz pro různé oblasti činností AI hráče (obrana, útok a expanze)
  4. vylidnění budov (z důvodu, že produkovat jednotky je možné pouze v prázdných budovách)
  5. zpracování všech probíhajících procesů útoků, popřípadě plánování nových
  6. zpracování všech probíhajících procesů staveb a oprav budov, popřípadě plánování nových
  7. sestavení strategického grafu a vygenerování obranného plánu
  8. 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í)
  9. uložení modifikovaných AI dat specifických pro daného hráče
  10. 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:
Jméno komponentyNázev reprezentativní třídyPopis činnosti komponenty
ObranaCStrGraphTato 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íCStrategyAttackEngineTato 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.
ExpanzeCStrategyExpansionEngineTato 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 dataCStrategySerializationTato 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:
Dědičnost tříd vrcholů strategického grafu
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:
Ž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:
Životní cyklus procesu stavby
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.