OpenTTD AI

Následující část textu se zabývá vytvořením vlastní umělé inteligence (AI) pro hru OpenTTD, se kterou se můžete seznámit v předchozí kapitole. Vytvoření vlastního AI je jeden ze semestrálních úkolů pro předmět Umělá Inteligence II. Jedním z požadavků je, že toto AI musí primárně využívat železnici. V této části se dozvíte jednak jak AI vytvořit, a dále potom některé základní funkce, které se týkají zejména stavby železnice a A* algoritmu. Většinu zde uvedených informací najdete také na oficiální wiki pro OpenTTD AI. Oproti wiki je tento text postaven jako průvodce k experimentování s A* algoritmem a inteligentními agenty.

Vytvoření AI

AI pro OpenTTD se programuje v interpretovaném jazyce Squirell. Jazyk Squirell má poněkud bizarní syntaxi, která je mixem C, C++, Pythonu, PHP, Pascalu, C#, Javy, Lua, SQL, JavaScriptu a deliria autora. Interpret jazyka Squirell obsahuje také nějaké základní API funkce z nichž řada není v OpenTTD implementována. Z hlediska vlastního AI jsou podstatně důležitější API funkce OpenTTD a doplňující AI knihovny.

Nejprve si zvolte název svého AI NazevAi, měl by být unikátní, proto doporučuji použít například váš login. Pro založení AI je nutné vytvořit novou složku NazevAi uvnitř složky OpenTTD/content_download/ai, kterou najdete ve složce Dokumenty. Ve vytvořené složce NazevAi je dále nutné vytvořit dva soubory: info.nut a main.nut. Soubor info.nut je řídící soubor AI, který obsahuje informace o názvu, autorovi a verzi AI. Obsah souboru info.nut:

class NazevAi extends AIInfo
{
	  function GetAuthor()   	{ return "Autor"; }
	  function GetName()      	{ return "NazevAi";}
	  function GetDescription()	{ return "Popis"; }
	  function GetVersion()		{ return 1; }
	  function GetDate() 		{ return "2011-11-30"; }
	  function CreateInstance()	{ return "NazevAi"; }
	  function GetShortName() 	{ return "XXXX"; }
	  function GetAPIVersion() 	{ return "1.1"; }
	  function GetSettings() 	{}
}
RegisterAI(NazevAi());

Poznámka 1: Místo XXXX doplňte krátký název AI, musí být zadané přesně 4 znaky!
Poznámka 2: Názvy tříd a název AI (na některých místech) jsou case-sensitive.

Obsahem souboru main.nut je vaše třída NazevAi, která implementuje AI. Pokud budete využívat další třídy, je vhodné je umístit do dalších souborů. Všechny ostatní soubory je nutné do hlavního souboru includovat – podobně jako například v PHP. Pro includování se používá funkce require(). Parametrem je název souboru – cesta je relativní k souboru, ve kterém je funkce require() volána. Tj. například: require("include.nut"); Vloží soubor include.nut v stejném adresáři jako je main.nut. Jako minimální obsah souboru main.nut lze použít následující kód:

class NazevAi extends AIController {
	function Start();
}
function NazevAi::Start()
{
	while (true) {
		AILog.Info("Ahoj vsichni! Provedl jsem " +
			"instrukci: " + this.GetTick());
		this.Sleep(500);
	}
}

Ladění AI

Nyní je možné AI otestovat, spusťte aplikaci a začněte novou hru. U nové hry je vždy ochranná lhůta, která dává lidskému hráči náskok (nastavuje se v „AI configuration“ po kliknutí na konkrétního hráče). Při ladění si můžete své AI zapnout hned. To je možné udělat pomocí příkazů konzoly, kterou spustíte kliknutím na položku Toggle Console; v menu nápověda Ikona funkce. Příkazem list_cmds vypíšete všechny dostupné příkazy konzoly. Příkazem start_ai NazevAi (možno psát také jako startai) spustíte své AI. Potom si otevřete okno AI Debug, které najdete opět v menu nápověda Ikona funkce. Z konzoly je možné AI také zastavit a restartovat. Pokud se vám v ladícím okně AI vypisuje text „Ahoj vsichni! Provedl jsem instrukci 1“, tak je vaše AI funkční. Pokud se zobrazí chyba „Failed to load the specified AI“, máte chybu v souboru info.nut, nebo není tento soubor na správném místě. Pokud se zobrazí chyba „One of running AIs crashed…“, máte chybu v souboru main.nut. Další tipy pro vytvoření AI najdete také na wiki.

Spuštění AI, ladící konzola
Screenshot ze hry

Poznámka: Pokud změníte soubor info.nut, musíte buď restartovat celou aplikaci, nebo v konzoli použít příkaz rescanai.

Z konzoly je možné AI restartovat příkazem reloadai (například reloadai 2 obnoví první nahrané AI). Restartování AI je užitečné, při vývoji – soubor main.nut se načte znovu z disku a AI se znovu spustí. Při změnách v AI tedy není nutné znovu spouštět celou aplikaci. Také je možné znovu spustit celou hru na stejné mapě příkazem restart. Restartovat AI je také možné pomocí ladícího okna AI Debug. V ladícím okně se také zobrazují všechny chyby (syntaktické i běhové), ke kterým dojde v průběhu hry. Chyby je také možné zobrazit do textové konzoly (herní konzola je hůř čitelná) spuštěním aplikace s parametrem -d. Tj. po spuštění aplikace příkazem openttd.exe -d, se otevře textové okno, do kterého budou chyby vypisovány. V případě runtime chyby se zobrazuje číslo řádku, na kterém byla chyba detekována. V případě syntaktické chyby se zobrazuje číslo řádku a pozice znaku, na kterém byla chyba detekována. První číslo je číslo řádku, druhé číslo je číslo znaku. Následující chyba je tedy na řádku 7 na devátém znaku: Error \OpenTTD\content_download\ai\Katureel\main.nut:7/9: expected 'IDENTIFIER'. Další pomocí při ladění AI mohou být breakpointy v logu. Pro jejich povolení je nutné do konzoly zadat příkaz set gui.ai_developer_tools 1. Potom je možné v okně AI Debug zadat text, který se bude hledat ve výpisu AI. Pokud bude nalezen, bude hra pozastavena.

Struktura AI

AI modul má několik povinných částí. První povinnou částí je informační třída odvozená z AIInfo, která je umístěna v souboru info.nut. Pokud neplánujete své AI dále distribuovat, tak už se o tuto část nemusíte zajímat. Druhou povinnou částí je soubor main.nut, respektive vlastní třída AI, která je odvozena z AIController. Třída AIController má dvě užitečné metody Sleep() a GetTick(). Metoda Sleep() pozastaví vykonávání na zadaný počet „tiknutí“. Metoda GetTick() vrátí aktuální počet tiknutí. Vlastní třída AI musí mít metodu Start(), která se zavolá při spuštění AI. Uvnitř této metody je vždy nekonečný cyklus, ve kterém AI pracuje. Pokud dojde k ukončení metody Start(), dojde i k ukončení celého AI!

Tiknutí AI (AI tick) je časový úsek, během kterého AI může vykonat zadaný počet instrukcí ( standardně 10 000) Squirellu. Po vykonání zadaného počtu instrukcí, nebo po spuštění nějakého příkazu ve hře (např. stavění tratě, koupení vozidla, … – akce, které ovlivňují hru) dojde k ukončení ticku interním plánovačem aplikace. AI je uspáno a hraje člověk nebo ostatní AI. Skutečnou délku ticku v milisekundách nelze zjistit, záleží na tom, co AI skript během něj dělá. Kolik ticků dostane AI přiděleno záleží na nastavení obtížnosti hry. Pro zajímavost: jeden den ve hře má 74 ticků, při nejvyšší rychlosti AI dostane AI přidělený čas procesoru ve všech 74 tiknutích (celkem tedy může během jednoho herního dne provést až 740 000 instrukcí Squirellu, nebo 74 příkazů, které mění stav hry). Při nejpomalejší rychlosti dostane AI čas pouze v 4 tiknutích. Zdroj

Jazyk Squirell nerozlišuje statické a dynamické metody (ani soukromé a veřejné metody). Znamená to, že výše uvedenou metodu Sleep() je možné volat jak dynamicky, tak staticky. Uvnitř třídy AI je tedy možné metodu volat jako this.Sleep(), nebo Sleep(), nebo AIController.Sleep() nebo NazevAi.Sleep(). Názvy metod i tříd jsou case sensitive!.

V AI můžete používat veřejně dostupné knihovny. Knihovny lze nainstalovat přímo uvnitř aplikace. Na úvodní obrazovce klikněte na „Check Online Content“. Potom můžete vybrat knihovny pro AI, které se mají nainstalovat, kromě toho lze takto nainstalovat již hotové AI moduly, a řadu dalších rozšíření. Rozšíření stačí označit a kliknutím na „Download“ stáhnout. AI knihovny se ukládají do adresáře OpenTTD/content_download/ai ve složce Dokumenty. Jsou to obyčejné TAR archivy, takže je můžete rozbalit a prozkoumat (jsou napsané ve Squirellu). Soubory je také možné stáhnout ručně ze služby BaNaNaS, kde jsou také odkazy na fórum pro jednotlivé knihovny.

Stažení AI knihoven
Screenshot ze hry

Do AI modulu se knihovny importují funkcí import. Přestože se oficiálně jedná o metodu třídy AIController, tak se tak nepoužívá. Funkce import se musí volat mimo jakoukoliv třídu (ideálně jako jedna z prvních věcí, které jsou v main.nut). Například volání import("graph.aystar", "AyStar", 6); importuje knihovnu A* algoritmu verze 6. Importovaná třída bude pojmenována AyStar. Další užitečnou knihovnou je knihovna SuperLib s celou řadou pomocných funkcí – import("util.superlib", "SuperLib", 17);, nebo knihovna RailPathFinder pro hledání cesty.

Pokud máte zažité dobré návyky objektově orientovaného programování, bude se vám pravděpodobně zdát NoAI API poněkud podivné. Všechny objekty ve hře jsou identifikované indexem, což je obyčejný integer. Pokud například chceme zjistit, co je na konkrétním políčku na mapě, použijeme třídu AITile. Nevytváří se však instance této třídy, ale volají se statické metody, kterým se předává index pole (TileIndex). Tento index musíme předtím někde zjistit – například pomocí třídy AIMap. Příklad:

// zjistíme index pole na souřadnici [x, y] = [10, 1]
local tile = AIMap.GetTileIndex(10, 1);
if (AITile.IsWaterTile(tile)) {
	AILog.Info("Na souradnici [10, 1] je voda.");
} else {
	AILog.Info("Na souradnici [10, 1] je něco jineho.");
}

Tento způsob práce s objekty ve hře se používá univerzálně v celém API (kvůli tomu, že Squirell nerozlišuje mezi statickými a dynamickými metodami). V API dokumentaci se uvádí datový typ parametrů a návratových hodnot různě – např. TileIndex, SignID, VehicleID, IndustryType, CompanyID, EngineID, BridgeID, … Jedná se vždy o integer (výjimečně výčet), který identifikuje konkrétní herní objekt (např. BridgeID identifikuje typ mostu (nikoliv most)). Rozlišení na různé datové typy je podstatné pro to, aby nedocházelo k záměně (TileIndex == 1 je něco jiného než CompanyID == 1).

Stavba železnice

Nyní byste měli mít vytvořenou kostru AI modulu. Do této kostry nyní doplníme základní algoritmus hledání cesty mezi dvěma body. AI, které máte vytvořit v rámci předmětu UI2, musí primárně využívat železnici. Stavba lodí a letadel nevyžaduje vytvoření žádné cesty. Stavba vozidel je mnohokrát vyřešená v jiných AI a jedná se o jednodušší úlohu. To je dáno zejména tím, že u silničních vozidel není vliv cesty na rychlost přepravy tak znatelný jako u vlaků. Jedná se v podstatě „pouze“ o optimalizace závislostí uvedených v popisu ekonomického modelu hry. Pro začátek doporučuji začít s jednoduchou cestou na jednoduché mapě. Můžete použít například testovací scénář, nebo si vytvořte vlastní scénář. Hru potom zahájíte přes play scenario.

Situace na testovacím scénáři
Screenshot ze hry

Orientace na mapě

Před stavbou cesty je nutné zorientovat se v herní mapě. Používá se několik označení směrů. Při stavbě železnice se používá označení směru pomocí světových stran (N – sever, E – východ, S – jih, W – západ) a jejich kombinace (NE, SE, SW, NW). V OpenTTD se za základní směry považují právě tyto kombinace světových stran, protože jsou kolmé na mapovou mřížku (ano, kolmé směry jsou ty, které jsou na obrazovce zobrazeny diagonálně). Většinu staveb lze stavět pouze v kolmých směrech (silnice, nádraží, …). Dále se, zejména na wiki a na fóru, používá označení: vlevo, vpravo, nahoře, dole. Levý horní roh mapy je směrem na západ (W). Pravý horní roh mapy je směrem na sever (N). Třetím způsobem označování je číselný index políčka (TileIndex), který se při programování AI používá zdaleka nejčastěji. Políčka jsou indexovaná po řádcích tak, že 0 je v pravém horním rohu mapy a postupuje do levého horního rohu mapy. Další řádek začíná opět na pravé straně. Kolem mapy je nahoře a dole neviditelné ochranné pásmo, první viditelné políčko mapy má tedy index 257. Čtvrtým způsobem označování polí v mapě jsou souřadnice x, y, které se někdy používají při plánování cesty. Počátek tohoto souřadného systému je opět v pravém horním rohu mapy na souřadnici [1, 1] (souřadnice [0, 0] neexistuje ze stejného důvodu, jako neexistuje TileIndex 0).

Srovnání určení směru pomocí světových stran a relativního TileIndexu. Zdroj
Screenshot ze hry

Jak bylo uvedeno výše, většinu staveb lze stavět pouze v kolmých směrech (horizontálních, vertikálních – míněno vzhledem k mapě, nikoliv vzhledem k obrazovce!). Železnici je navíc možné stavět i v diagonálních směrech. Určení směru železniční tratě je tedy komplexnější, protože z každé strany políčka mohou vycházet tři železniční tratě. Celkem může být na jednom políčku až 6 směrů kolejí. Tyto směry mají označení definované výčtovým typem AIRail::RailTrack:

  • RAILTRACK_NE_SW – kolej ve směru osy x (severovýchod na jihozápad),
  • RAILTRACK_NW_SE – kolej ve směru osy y (severozápad na jihovýchod),
  • RAILTRACK_NW_NE – kolej v horním rohu políčka (severozápad na severovýchod),
  • RAILTRACK_SW_SE – kolej v dolním rohu políčka (jihozápad na jihovýchod),
  • RAILTRACK_NW_SW – kolej v levém rohu políčka (severozápad na jihozápad),
  • RAILTRACK_NE_SE – kolej v pravém rohu políčka (severovýchod na jihovýchod).
Různé směry kolejí a některých jejich kombinací (všechny kombinace jsou možné).
Screenshot ze hry

Ve hře je možné pomocí nástroje Land area information (v menu nápověda Ikona funkce) získat informace o poloze políčka. Poloha je uvedena jako souřadnice x,y,z (z je nadmořská výška, která se pro změnu počítá od 0 – úroveň moře). V závorce je uveden TileIndex políčka jako hexadecimální číslo.

Informace o políčku uvnitř hry.
Screenshot ze hry

Hledání cesty

Nyní se vraťme k testovacímu scénáři, pohledem do mapy můžeme určit polohu elektrárny například jako 0xA810 a polohu dolu jako 0xF212. Přesná hodnota není v tuto chvíli důležitá. Důležité je, aby se jednalo o volné pole, na kterém lze stavět a aby bylo někde v dosahu dolu respektive elektrárny.

Inicializace A* algoritmu

Pro nalezení cesty můžeme použít knihovnu A* algoritmu. Knihovnu do AI modulu importujeme příkazem: import("graph.aystar", "AyStar", 6);. Budou importovány třídy AyStar a AyStar.Path. Třída AyStar v dokumentaci předpokládá, že se používá k hledání cesty na mapě, je však možné ji použít i jinak, protože implementace je obecná. Prozatím ji však budeme potřebovat pouze pro hledání cesty v mapě. Pro použití třídy je nutné vytvořit její instanci, konstruktor má následující parametry:

  1. pfInstance – parametr předaný následujícím funkcím jako callback parametr. Dobrou volbou je použít instanci AI modulu, budeme tedy dále předpokládat, že parametr se jmenuje self a je instancí třídy NazevAi
  2. costCallbackcallback funkce, která se zavolá pokud bude A* algoritmus potřebovat zjistit cenu z počátečního stavu do aktuálního stavu (hodnotu g() funkce). Návratová hodnota funkce je celé nebo desetinné číslo, které je hodnotou g() funkce. Cost callback funkce má následující parametry:
    • NazevAI self – parametr pfInstance předaný konstruktoru Aystar.
    • Aystar.Path oldPathcesta z počátečního stavu do aktuálního stavu.
    • TileIndex newTile – aktuální políčko na mapě (viz funkce neighboursCallback()). Cost funkce se volá těsně před přidáním nového políčka k cestě. Cena cesty má tedy zahrnovat i aktuální stav (pole newTile).
    • integer newDirection – aktuální směr kolejí (viz funkce neighboursCallback().
  3. estimateCallback – callback funkce, která se zavolá při zjišťování hodnoty odhadu (heuristiky) z aktuálního stavu do cílového stavu (hodnota h() funkce). Návratová hodnota funkce je celé nebo desetinné číslo, které je hodnotou h() funkce. Funkce by měla vracet minimum odhadů pro jednotlivé cílové stavy (pokud je jich zadáno víc). Dále musí splňovat požadavky na heuristiku A* algoritmu, především tedy požadavek, že nesmí být vyšší, než skutečná cena cesty do cílového stavu (tedy to, co by vrátila cost funkce v cílovém stavu, kdyby prošla právě zvažovanou cestou). Estimate callback má následující parametry:
    • NazevAI self – parametr pfInstance předaný konstruktoru Aystar.
    • TileIndex tile – aktuální políčko (stav) cesty (AyStar.Path.GetTile()).
    • integer direction – aktuální směr cesty (viz funkce neighboursCallback()).
    • array[TileIndex, direction] goalNodes – pole cílových stavů. Pole obsahuje vždy index políčka a směr cesty.
  4. neighboursCallback – callback funkce, která se zavolá při zjišťování sousedních stavů pro aktuální stav. Tato funkce implementuje generátor přechodů mezi stavy. Neighbours callback má následující parametry:
    • NazevAI self – parametr pfInstance předaný konstruktoru Aystar.
    • Aystar.Path currentPathcesta z počátečního stavu do aktuálního stavu.
    • TileIndex node – Aktuální stav (currentPath.GetTile()). Funkce vrací pole polí array[array[TileIndex, direction]]. Pro každého potomka aktuálního stavu se tedy do pole uloží TileIndex políčka a směr stavby. Proměnná direction se v AyStar třídě nijak nezpracovává, pouze se předává cost a estimate callbackům. Může se tedy jednat o libovolný způsob identifikace směru.
  5. checkDirectionCallback – callback funkce, která se používá pro kontrolu, zda může být na daném políčku více směrný provoz. Funkce se uplatní v případě, že se při hledání cesty algoritmus dostane na pole, kterým už prošel (ale s jiným směrem). Praktické využití této funkce bohužel neznám, ve všech implementovaných AI algoritmech vrací vždy false, a zatím mne nenapadlo, k čemu by bylo dobré, kdyby tato funkce vracela true. Funkce vrací true pokud je přípustné, aby cesta prošla stejným políčkem znovu, ale jiným směrem. Funkce má následující parametry:
    • NazevAI self – parametr pfInstance předaný konstruktoru Aystar.
    • TileIndex tile – Aktuální políčko.
    • integer existingDirection – Stávající směr trasy na políčku.
    • integer newDirection – Nový (přidaný) směr trasy na políčku.

Cesta (na mapě nebo obecněji cesta z počátečního do koncového stavu) je reprezentována třídou AyStar.Path(). Cesta je reprezentována jako jednosměrný spojový seznam, tedy každá položka se odkazuje na nadřazenou položku. Poslední prvek cesty (TileIndex vrácený metodou GetTile()) je nejblíže cíli. Směr trati na tomto políčku se zjistí metodou GetDirection(). Aktuální cena (hodnota cost funkce, pro cestu do daného políčka se zjistí metodou GetCost(). Předcházející políčko vrátí metoda GetParent(), tato metoda vrací opět instanci třídy AyStar.Path. Pro první políčko na cestě vrací (počátek cesty na mapě, počáteční stav ve stavovém prostoru) vrací GetParent() hodnotu null. Délku cesty je možné zjistit metodou GetLength(). Žádné další metody už třída nemá.

Vytvořenou instanci třídy AyStar je nutné ještě před každým hledáním cesty inicializovat metodou AyStar.InitializePath(). Metoda má parametry:

  1. array[array[TileIndex, integer]] sources – pole počátečních stavů, kde každý stav je pole obsahující index políčka (TileIndex) a směr trasy. Počáteční stav je možné zadat také jako instanci třídy AyStar.Path.
  2. array[TileIndex] goals – pole cílových stavů, může jich být více, pokud to podporuje estimate callback funkce. Vždy však musí být uvedeny alespoň dvě sousední políčka, tak se kontroluje, jestli cesta přišla z požadovaného směru (zadává se tedy cílový stav a jeden stav před ním).
  3. array[TileIndex] ignoredTiles – pole políček na mapě, kterými cesta nesmí procházet.

Po inicializaci instance AyStar je možné spustit vlastní hledání cesty. Třída umožňuje hledání cesty přerušovat (tak, aby AI „nezamrzlo“ a mohlo reagovat na změny ve hře). Hledání cesty (metoda FindPath()) se proto spouští v cyklu. Metoda FindPath() vrací:

  • instanci třídy AyStar.Path, pokud byla cesta nalezena,
  • false, pokud nebylo hledání cesty ukončeno (při novém spuštění funkce FindPath() bude hledání pokračovat),
  • null, pokud bylo hledání cesty neúspěšné (cesta neexistuje).

Parametrem funkce FindPath() je počet iterací, po kterých má dojít k přerušení. Hodnota -1 znamená nekonečno – hledání nebude nikdy přerušeno.

Minimální kód

Následující kód je minimum pro spuštění A* prohledávání. Vzhledem k tomu, že v něm není implementována ani cost funkce, ani estimate funkce, ani neighbours funkce, tak pochopitelně nic nenajde. Můžete si také stáhnout soubor main.nut.

// načtení knihovny, musí byt mimo třídu
import("graph.aystar", "AyStar", 6);

class Katureel extends AIController
{
	aystar = null;

	// constructor AI Modulu (zapisuje se dovnitř třídy)
	constructor()
	{
		// vytvoreni instance A*
		this.aystar = AyStar(this,
				this._cost,
				this._estimate,
				this._neighbours,
				this._directions
		);
	}

}

// Metody AI modulu (zapisuji se mimo třídu!)

// g() funkce A* algoritmu
function Katureel::_cost(/* Katureel */ self,
		/* Aystar.Path */ oldPath,
		/* TileIndex */ newTile,
		/* integer */ newDirection)
{
	return 1;
}

// h() funkce A* algoritmu
function Katureel::_estimate(/* Katureel */ self,
		/* tileindex */ tile,
		/* integer */ direction,
		/* array[tileindex, direction] */ goalNodes)
{
	// políčko, kterým algoritmus prosel označíme cedulkou
	AISign.BuildSign(tile, "test");
	return 1;
}

// funkce pro generování stavu
function Katureel::_neighbours(/* Katureel */ self,
		/* Aystar.Path */ currentPath,
		/* tileindex */ node)
{
	return [[node - 1, 1]];
}

function Katureel::_directions(self,
		tile,
		existingDirection,
		newDirection)
{
	return false;
}

// Hlavni funkce AI
function Katureel::Start()
{
	local sources = [];
	local goals = [];

	sources.push([0xA810, 1]);
	goals.push([0xF212, 0xF211]);
	this.aystar.InitializePath(sources, goals, []);
	local path = false;
	AILog.Info("Hledam cestu");
	while (path == false) {
		path = this.aystar.FindPath(100);
		AILog.Info("Porad jeste hledam cestu");
	}
	if (path != null) {
		AILog.Info("Cesta nalezena");
	}

	while (true) {
	}
}

Přechodová funkce algoritmu

Prvním krokem ke zprovoznění A* je implementace funkce, která generuje sousední stavy. Zbývající dvě funkce pracují s daty, která generuje tato funkce. Nejjednodušší možné řešení je hledat trasu pouze na úrovni prázdných celých políček (bez svahu). V tom případě není nutné zabývat se směrem kolejí. Ten bude nutné určit až při stavění kolejí, což není problém, protože budeme mít „vyhrazené“ vždy celé pole (půjde postavit cokoliv). Můžete si také stáhnout soubor main.nut.

function Katureel::_neighbours(/* Katureel */ self,
		/* Aystar.Path */ currentPath,
		/* tileindex */ node)
{
	// posuny ve směru X, Y
	local offsets = [1, // posun na ose X doleva
		-1, // posun na ose X doprava
		AIMap.GetMapSizeX(), // posun na ose Y dolů
		-AIMap.GetMapSizeX() // posun na ose Y nahoru
		];
	local newTile;
	local result = [];

	// každý posun přičteme k aktuálnímu TileIndexu
	// a dostaneme tak sousedy
	foreach (offset in offsets) {
		newTile = node + offset;
		// políčko není na svahu a je na něm možné stavět
		if ((AITile.GetSlope(newTile) == AITile.SLOPE_FLAT)
				&& AITile.IsBuildable(newTile)) {
			result.push([newTile, 1]);
		}
	}
	return result;
}

Následující video ukazuje postup prohledávání. Pro aktuální stav se vygenerují sousední stavy (políčka se označí cedulkou). Pokud algoritmus narazí na „překážku“, vydá se jiným směrem. Kterým směrem se algoritmus vydá, záleží na pořadí posunovacích indexů (pole offsets) ve výše uvedené funkci.

A* bez hodnotící funkce

Heuristická funkce

Nejjednodušší možnou heuristikou pro odhad ceny cesty do cíle je „vzdušná“ vzdálenost. Výše uvedená funkce pro generování sousedních stavů nepracuje nijak se směrem trati a pouze generuje sousední políčka. Díky tomu můžeme použít funkci pro výpočet manhattanské (pravoúhlé) vzdálenosti.

// h() funkce A* algoritmu
function Katureel::_estimate(/* Katureel */ self,
		/* tileindex */ tile,
		/* integer */ direction,
		/* array[tileindex, direction] */ goalNodes)
{
	// políčko, kterým algoritmus prošel označíme cedulkou
	local result = AIMap.DistanceManhattan(tile, goalNodes[0][0]);
	AISign.BuildSign(tile, result);
	return result;
}

Vzhledem k tomu, že algoritmus nyní již nějakou cestu najde, doplníme také funkci Start() o zobrazení této cesty. Následující kód bude spuštěn, pokud A* nalezne nějakou cestu. Můžete si také stáhnout soubor main.nut. Následující video ukazuje postup algoritmu. Všimněte si rozložení hodnot manhattanské vzdálenosti (hodnoty jsou uvedeny na cedulkách).

// odstraníme cedulky umístěné při prohledávání A*
foreach (idx, dSign in AISignList()) {
	AISign.RemoveSign(idx);
}

// projdeme spojový seznam cesty - procházení začíná od konce cesty
local current = path;
while (current != null) {
	AISign.BuildSign(current.GetTile(), "K");
	current = current.GetParent();
}
A* s estimate funkcí

Ve výše uvedeném příkladu není nalezená cesta nejkratší (délka cesty je 158 polí). Proč?

Cenová funkce algoritmu

Odpověď na předchozí otázku je: „protože algoritmu chybí cenová funkce g().“ Jinými slovy, pro algoritmus jsou všechny stavy stejně vzdálené od počátečního stavu. Velmi jednoduchou cenovou funkcí je například délka nalezené cesty. Následující kód uvádí možnou implementaci cenové funkce. Můžete si také stáhnout soubor main.nut.

function Katureel::_cost(/* Katureel */ self,
		/* Aystar.Path */ oldPath,
		/* TileIndex */ newTile,
		/* integer */ newDirection)
{
	if (oldPath != null) {
		return oldPath.GetLength() + 1;
	} else {
		return 1;
	}
}
A* s estimate i cost funkcí

Délka nalezené cesty je nyní 134 polí. Cesta však zjevně není optimální a její nalezení také ne, prohledávají se nesmyslné oblasti severně od elektrárny. Že není cesta optimální je způsobené především použitím manhattanské vzdálenosti, která je pro všechny pravoúhlé cesty mezi dvěma stejně vzdálenými body stejná. Je tedy jedno, jestli jdeme „poctivě přes rožek“, anebo to „střihneme přes trávník“. Také tím vznikají v nalezené cestě zbytečné zatáčky, protože jsou manhattanskou vzdáleností nerozlišitelné. Prohledávání není optimální proto, že v hodnotících funkcích srovnáváme hrušky a jablka. Délka cesty měřena počtem polí neodpovídá manhattanské vzdálenosti. A* algoritmus pracuje se součtem g() funkce a h() funkce. Další expandovaný stav je ten, ve kterém je nejmenší hodnota tohoto součtu, tedy funkce f().

Zkuste použít místo manhattanské vzdálenosti vzdálenost přímočarou (euklidovskou), která je implementována ve funkci AIMap.DistanceSquare(). V čem je řešení lepší, v čem je řešení horší? Zkuste různě modifikovat mapu (můžete použít CTRL + ALT + C pro přidání peněz, není nutné vytvářet nový scénář).

Stavba železnice

Aby AI mělo šanci vydělávat nějaké peníze, je potřeba ještě dokončit ještě nějaké drobnosti. Musíme postavit zastávky, koleje, depo a vlak. Následující kód ukazuje minimalistické řešení. V ukázkovém kódu je řada proměnných napevno nastavená a řada věcí nedokončená:

  • napevno se vozí uhlí (zboží s ID = 1), které vůbec nemusí ve hře existovat,
  • souřadnice dolu a elektrárny jsou nastaveny napevno,
  • zastávky jsou postaveny vždy vodorovně,
  • neřeší se, jestli se zastávky, koleje a depo podařilo postavit (nezapomínejte, že hra je real-time, hrací plocha se tedy neustále mění) – je nutné kontrolovat úspěšnost stavby,
  • připojení zastávek a depa je napevno nastavené (nebude fungovat, pokud povede cesta jinudy),
  • vlak má nastaveno 5 vagonů,
  • staví se „náhodná“ lokomotiva a vagony (lokomotiva a vagon s ID = 1),
  • vlak má pevný počet vagonů,
  • nekontroluje se, jestli na stavbu jsou peníze,
  • po postavení tratě už AI vůbec nic neudělá,
  • neřeší se, jestli postavený spoj bude vydělávat,
  • neřeší se údržba vlaku, obnovování, stavba další spojů,
  • nelze stavět mosty, tunely a na svahu,

Výše uvedené jsou některé tipy na doplnění AI – což je semestrální úkol do předmětu umělá inteligence. V každém případě by odevzdané AI mělo minimálně implementovat dynamické výběry (tj. nemělo by se vozit zboží s ID = 1, ale třeba uhlí, dřevo, atd., neměla by se stavět lokomotiva s ID = 1, ale nějaká vhodná lokomotiva, souřadnice dolu se musí zjišťovat dynamicky, …). V každém případě musí jít AI spustit i na jiných mapách (klidně i na jednoduchých scénářích). Vzhledem k tomu, že je hra real-time, je nutné využívat systém událostí (event system). Například pokud pošlete vlak do depa, musíte počkat na událost oznamující, že vlak přijel do depa. Níže uvedené AI umí něco dělat pouze na konkrétním testovacím scénáři. Mezi ukázkami programů najdete rozšířenou verzi AI, která vyhledává pozici pro depo, má spirálový vyhledávač pro pozici zastávky, kontroly různých operací a některá další vylepšení. Ve zdrojovém kódu jsou také docela podrobné komentáře (včetně toho principu Valuate()). Dále uvedený minimální kód si můžete také stáhnout v souboru main.nut.

// Hlavní funkce AI
function NazevAI::Start()
{
local sources = [];
local goals = [];

// vložení prvku do pole
sources.push([0xA810, 1]);
goals.push([0xF212, 0xF211]);

// výběr typu kolejí - bez tohoto kroku nelze stavět!
AIRail.SetCurrentRailType(AIRailTypeList().Begin());

// postavíme zastávky - orientace vodorovně, délka 4, výška 1,
// parametry jsou: pozice, orientace, svislý rozměr, vodorovný rozměr, nová stanice
AIRail.BuildRailStation(sources[0][0] - 4,
	AIRail.RAILTRACK_NE_SW, 1, 4, AIStation.STATION_NEW);
AIRail.BuildRailStation(goals[0][0] - 5,
	AIRail.RAILTRACK_NE_SW, 1, 4, AIStation.STATION_NEW);

this.aystar.InitializePath(sources, goals, []);
local path = false;
AILog.Info("Hledam cestu");
while (path == false) {
	path = this.aystar.FindPath(100);
	AILog.Info("Porad jeste hledam cestu");
}
if (path != null) {
	AILog.Info("Cesta nalezena, delka: " + path.GetLength());

	// odstraníme cedulky umístěné při prohledávání A*
	foreach (idx, dSign in AISignList()) {
		AISign.RemoveSign(idx);
	}

	// projdeme spojový seznam cesty
	// procházení začíná od konce cesty
	local current = path.GetParent().GetParent();
	local prev = path.GetParent().GetTile();
	local prevprev = path.GetTile();

	// napojeni zastávky v cíli
	AIRail.BuildRail(goals[0][0],
		goals[0][0] - 1, goals[0][0] - 2);
	AIRail.BuildRail(prev, goals[0][0], goals[0][0] - 1);

	while (current != null) {
		// BuildRail ma parametr From, Tile, To
		// staví se na políčku Tile, políčka From a To
		určují směr koleji na políčku Tile
		local ret = AIRail.BuildRail(prevprev,
			prev, current.GetTile());
		prevprev = prev;
		prev = current.GetTile();
		// posun o jeden prvek cesty
		current = current.GetParent();
	}

	// napojení zastávky na začátku
	AIRail.BuildRail(prevprev, prev, sources[0][0] - 1);

	// postavení depa
	AIRail.BuildRailDepot(goals[0][0] - AIMap.GetMapSizeX(),
		goals[0][0]);

	// koleje k depu
	AIRail.BuildRailTrack(goals[0][0], AIRail.RAILTRACK_NE_SW);
	AIRail.BuildRailTrack(goals[0][0], AIRail.RAILTRACK_NW_NE);
	AIRail.BuildRailTrack(goals[0][0], AIRail.RAILTRACK_NW_SW);
	local depot = goals[0][0] - AIMap.GetMapSizeX();

	// seznam všech kolejových vozidel
	local engList = AIEngineList(AIVehicle.VT_RAIL);

	// vybereme vozidla, která umí převážet uhli (ma ID = 1)
	engList.Valuate(AIEngine.CanRefitCargo, 1);
	engList.KeepValue(1);

	// vybereme vozidla, která jsou vagóny
	engList.Valuate(AIEngine.IsWagon);
	engList.KeepValue(1);
	local wagonType = engList.Begin();

	// seznam všech kolejových vozidel
	engList = AIEngineList(AIVehicle.VT_RAIL);

	// vybereme všechno, co není vagón
	engList.Valuate(AIEngine.IsWagon);
	engList.KeepValue(0);

	local engineType = engList.Begin();
	// postavíme 5 vagónů
	for (local i = 0; i < 5; i++) {
		AIVehicle.BuildVehicle(depot, wagonType);
	}

	// postavíme lokomotivu
	local train = AIVehicle.BuildVehicle(depot, engineType);

	// jízdní řád
	AIOrder.AppendOrder(train, goals[0][0] - 2,
		AIOrder.AIOF_FULL_LOAD_ANY);
	AIOrder.AppendOrder(train, sources[0][0] - 1,
		AIOrder.AIOF_NONE);

	// spuštění vlaku
	AIVehicle.StartStopVehicle(train);
}

while (true) {
	// AI necháme dále běžet, ale nebude už nic dělat
}
}

Shrnutí

V této kapitole jsou popsány základní technické principy pro vytvoření vlastního AI modulu pro hru OpenTTD. Velká část kapitoly se zabývá spoustou technických detailů, které jsou bohužel nutné pro rozchození. Nicméně i tyto technické detaily vnímejte, protože dobře vypovídají o komplexnosti celého problému vytvoření solidního AI pro hru. Všimněte si, že nalezením cesty mezi dvěma body problémy zdaleka nekončí, spíš teprve začínají. Zkuste experimentovat s různými variantami cenové a heuristické funkce A* algoritmu. Některé varianty jsou zde uvedené na videích, ale možných variant je podstatně více. Vždy sledujte, jak se algoritmus chová – jednou z možností je například stavění cedulek (ve hře dostupné pod ikonou landscape Ikona funkce). Také se podívejte na rozšířenou verzi AI, kterou najdete mezi ukázkami programů. Další zajímavé čtení může být také diplomová práce na toto téma.

Touto kapitolou také končí část, která se věnuje hře OpenTTD a v podstatě část, která se věnuje prohledávání stavového prostoru. Následující část textu se zběžně věnuje učícím se algoritmům, které stavový prostor sice využívají také, ale už pouze jako velmi interní nástroj nebo princip, o který není nutné se příliš starat.

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace