Pohyb v projektu ENTI

Univerzita Karlova v Praze Matematicko-fyzikáln´ı fakulta

´ RSK ˇ ´ PRACE ´ BAKALA A

Lukáˇs Bajer Pohyb v projektu ENTI Katedra software a v´ yuky informatiky

Vedouc´ı bakaláˇrské práce: Mgr. Cyril Brom Studijn´ı program: Informatika, Programován´ı

2007

Velk´ y d´ık za veden´ı práce, podnˇetné pˇripom´ınky i trpˇelivost patˇr´ı Mgr. Cyrilu Bromovi. Za pomoc pˇri ˇreˇsen´ı poˇcáteˇcn´ıch problém˚ u v orientaci ve vnitˇrnostech projektu ENTI bych rád podˇekoval i RNDr. Ondˇreji Bojarovi a Mgr. Milanu Hlad´ıkovi. Tˇret´ı podˇekován´ı pak smˇeˇruje knihovnickému personálu Mˇestské knihovny v Novém Boru, d´ıky jehoˇz ochotˇe vznikla nemalá ˇcást této práce i v ˇcervenci 2007.

Prohlaˇsuji, ˇze jsem svou bakaláˇrskou práci napsal samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. Souhlas´ım se zap˚ ujˇcován´ım práce a jej´ım zveˇrejˇ nován´ım. V Praze dne 10. srpna 2007

Lukáˇs Bajer

2

Obsah ´ 1 Uvod

6

1.1

C´ıl práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2

Struktura dokumentu . . . . . . . . . . . . . . . . . . . . . . . . .

7

2 Algoritmy pro pathfinding

9

2.1

Algoritmus A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2

Hierarchical Pathfinding A* . . . . . . . . . . . . . . . . . . . . .

11

2.3

Partial-Refinement A* . . . . . . . . . . . . . . . . . . . . . . . .

13

2.4

Dalˇs´ı metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3 Projekt ENTI

17

3.1

Struktura projektu ENTI . . . . . . . . . . . . . . . . . . . . . . .

17

3.2

Svˇet ent˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.3

Programován´ı ent˚ u . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.4

Pohybové skripty . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

4 Pouˇ zit´ e postupy a algoritmy

22

4.1

Hierarchické hledán´ı cest . . . . . . . . . . . . . . . . . . . . . . .

22

4.2

Bagrován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

4.3

Pronásledován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

4.4

Vyh´ ybán´ı se ostatn´ım ent˚ um . . . . . . . . . . . . . . . . . . . . .

30

4.5

On-line hledán´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3

5 Implementace a modelov´ e situace

32

5.1

Hierarchické hledán´ı cest . . . . . . . . . . . . . . . . . . . . . . .

32

5.2

Bagrován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

5.3

Pronásledován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

5.4

Vyh´ ybán´ı se ostatn´ım ent˚ um . . . . . . . . . . . . . . . . . . . . .

39

5.5

On-line hledán´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

6 Z´ avˇ er

41

6.1

Budouc´ı práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

6.2

Dalˇs´ı aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

6.3

Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

Literatura

45

Pˇ r´ıloha: Obsah CD

47

4

Název práce: Pohyb v projektu ENTI Autor: Lukáˇs Bajer Katedra (´ ustav): Katedra software a v´ yuky informatiky Vedouc´ı bakaláˇrské práce: Mgr. Cyril Brom e-mail vedouc´ıho: [email protected] Abstrakt: Projekt ENTI je simulátor prostˇred´ı, které je podobné lidskému svˇetu. ˇ ı v nˇem autonomn´ı agenti naz´ Zij´ yvan´ı enti, kteˇr´ı se o svˇet staraj´ı. K naplˇ nován´ı sv´ ych u ´kol˚ u a ˇzivotn´ıch potˇreb potˇrebuj´ı ˇcasto hledat po svém svˇetˇe cestu. Tato práce je zamˇeˇrena na skripty, které toto hledán´ı a následné procházen´ı cest ˇr´ıd´ı. Pohyb ent˚ u mezi m´ıstnostmi vylepˇsuje hierarchickou verz´ı algoritmu A*, ˇc´ımˇz sniˇzuje nároky na procesor pˇri hledán´ı delˇs´ıch cest. Dále pak rozˇsiˇruje skripty pro pohyb po m´ıstnosti, sledován´ı a vyh´ ybán´ı se ciz´ım ent˚ um a hledán´ı pˇredmˇet˚ u. Kl´ıˇcová slova: umˇelá inteligence, hledán´ı cest, grafové algoritmy, hierarchick´ y A*

Title: Movement in The Ents Project Author: Lukáˇs Bajer Department: Department of Software and Computer Science Education Supervisor: Mgr. Cyril Brom Supervisor’s e-mail address: [email protected] Abstract: The ENTS project is a simulator of an environment which is similar to our common world. In this environment, there live autonomous agents called ents. They take care of their world. To fulfil their goals and satisfy their daily needs, they often have to look for a path around the world. This work is focused on scripts which are responsible for this pathfinding. The ents’ movements are improved by hierarchical version of the A* algorithm. Thanks to this, demands on CPU during looking for longer paths are considerably decreased. In addition, ents’ scripts are enhanced by better movement around a room, other ents following and avoiding, and “lazy” picking up objects. Keywords: artificial intelligence, pathfinding, graph algorithms, hierarchical A*

5

Kapitola 1 ´ Uvod Snahy napodobit nebo modelovat lidské myˇslen´ı existuj´ı jiˇz pomˇernˇe dlouho. Praktické realizace vznikaly nejprve jen pomoc´ı podvod˚ u (napˇr´ıklad znám´ y ˇsachov´ y automat Wolfganga Kempelena [13]) nebo v d´ılech literárn´ıch autor˚ u (viz napˇr. [3]), ale ve druhé p˚ uli dvacátého stolet´ı jiˇz technické podm´ınky umoˇznily tento obor rozvinout i ve skuteˇcnosti. Postupnˇe se rod´ı poˇc´ıtaˇcové programy, které jsou schopny se na základˇe sloˇzitˇejˇs´ıch vstupn´ıch informac´ı samy rozhodovat. S rostouc´ı v´ ypoˇcetn´ı silou poˇc´ıtaˇc˚ u lze konstruovat sloˇzitˇejˇs´ı a propracovanˇejˇs´ı rozhodovac´ı systémy a autonomn´ı agenti, jak se tyto programy naz´ yvaj´ı, nacházej´ı uplatnˇen´ı nejen ve vˇedeck´ ych laboratoˇr´ıch, ale i v pr˚ umyslu nebo zábavˇe. Projekt ENTI je pˇr´ıkladem platformy pro práci s autonomn´ımi agenty. I kdyˇz nás projekt po spuˇstˇen´ı pˇriv´ıtá pˇekn´ ym uˇzivatelsk´ ym rozhran´ım, patˇr´ı sp´ıˇse k projekt˚ um vˇedeck´ ym. Je to diskrétn´ı kolová simulace, která si klade za c´ıl zjistit, do jaké m´ıry a za jakou cenu lze simulovat prostˇred´ı podobné lidskému svˇetu (v´ıce viz [1]). Ve zjednoduˇseném modelu rodinného domku ˇzij´ı postavy, které se naz´ yvaj´ı enti. Jsou ˇr´ızeni poˇc´ıtaˇcov´ ymi programy napsan´ ymi pˇreváˇznˇe ve speciáln´ım jazyce E. Elementárn´ımi u ´koly, tzv atomick´ ymi instrukcemi1 , jsou schopni ovlivˇ novat svˇet kolem nich, ale umˇej´ı ˇreˇsit i komplexnˇejˇs´ı u ´lohy2 nebo obstarávat své ˇzivotn´ı potˇreby. Uˇzivatel do svˇeta vstupuje v roli jednoho z ent˚ u, kter´ y má stejná práva i omezen´ı jako enti strojov´ı. M˚ uˇze tak stejnˇe jako ostatn´ı enti brát pˇredmˇety, zav´ırat dveˇre nebo chodit na záchod. Tento druh práce nebo zábavy by nás 1 2

napˇr. udˇelej krok, otevˇri dveˇre, seber pˇredmˇet pˇred sebou napˇr. zalej kvˇetiny na zahradˇe

6

ale pravdˇepodobnˇe po ˇcase pˇrestal bavit. Moˇznosti projektu vˇsak t´ımto nekonˇc´ı: zkuˇsenˇejˇs´ı uˇzivatelé mohou vytváˇret své vlastn´ı skripty, podle kter´ ych se pak budou jejich enti chovat.

1.1

C´ıl pr´ ace

Autor˚ um nov´ ych ent˚ u se nab´ız´ı pomˇernˇe ˇsiroká nab´ıdka pˇredpˇripraven´ ych funkc´ı a skript˚ u, které mohou pouˇz´ıt. Tato práce se zab´ yvá skripty, které souvis´ı s jejich pohybem. Vylepˇsuje a opravuje nˇekteré stávaj´ıc´ı a doplˇ nuje nové. Konkrétn´ı c´ıle jsou následuj´ıc´ı: ˇ v projektu ENTI bˇeˇz´ı po kolech, Zrychlen´ı prohled´ avac´ıch algoritm˚ u. Cas která trvaj´ı, dokud vˇsichni enti nepoˇslou atomickou instrukci. Na v´ ypoˇcty tedy maj´ı enti ˇcasu teoreticky neomezenˇe, uˇzivatel ho vˇsak vn´ımá. Prvn´ım c´ılem je zmenˇsen´ı ˇcasové nároˇcnosti prohledáván´ı mezi r˚ uzn´ ymi m´ıstnostmi aplikac´ı hierarchické formy algoritmu A*. Vˇ erohodnˇ ejˇ s´ı chov´ an´ı ent˚ u. Pohyb ent˚ u se v nˇekter´ ych pˇr´ıpadech znaˇcnˇe liˇs´ı od toho, jak by se chovali lidé. Druh´ ym c´ılem je nˇekteré nedostatky odstranit, konkrétnˇe nauˇcit“ enty proj´ıt zatarasenou cestou (tzv. bagrovat“), ” ” lépe pronásledovat a vyh´ ybat se ostatn´ım ent˚ um a hledat pˇredmˇety i pˇri jin´ ych ˇcinnostech.

1.2

Struktura dokumentu

Práce je rozdˇelena do sedmi kapitol. Prvn´ı z nich právˇe ˇctete. Uvád´ı do problému a vytyˇcuje základn´ı c´ıle, kter´ ych práce dosáhla. V kapitole 2 najdete struˇcn´ y a ponˇekud teoretick´ y popis algoritm˚ u pro hledán´ı cest, mezi kter´ ymi jsme pˇred jejich implementac´ı volili. Kapitola 3 hloubˇeji popisuje projekt ENTI, zejména pak vlastnosti a specifika, které bylo nutné vz´ıt v u ´vahu pˇri v´ ybˇeru algoritm˚ u i bˇehem jejich aplikace. Kapitola 4 je vedle softwarového d´ıla vlastn´ım jádrem práce, nebot’ nab´ız´ı popis konkrétnˇe pouˇzit´ ych algoritm˚ u i s d˚ uvody, proˇc bylo nebo nebylo vhodné je pouˇz´ıt. Kapitola 5 je zamˇeˇrena pˇr´ımo na zmˇenˇené nebo nové skripty a nab´ız´ı bliˇzˇs´ı popis vlastn´ı implementace a jej´ıch problém˚ u, stejnˇe jako pˇr´ıklady jejich pouˇzit´ı. Kapitola 6 nab´ız´ı dalˇs´ı pokraˇcován´ı práce, krátce diskutuje v´ yhody a nev´ yhody pouˇzit´ ych ˇreˇsen´ı a shrnuje dosaˇzené v´ ysledky. 7

Ned´ılnou souˇcást´ı práce jsou kromˇe tohoto textu i zdrojové soubory, kter´ ymi je potˇreba pˇred kompilac´ı projektu ENTI nahradit soubory p˚ uvodn´ı. V´ıce viz Instalaˇcn´ı pˇr´ıruˇcka“ um´ıstˇená na pˇriloˇzeném CD. ”

8

Kapitola 2 Algoritmy pro pathfinding Standardem dneˇsn´ıch algoritm˚ u na prohledáván´ı dlaˇzdicového prostoru je jistˇe algoritmus A* [5]. Pro jedno nalezen´ı skuteˇcnˇe nejkratˇs´ı cesty je se správnou heuristikou dokonce nejlepˇs´ı moˇzn´ y. Aby vˇsak ve své klasické podobˇe naˇsel s jistotou cestu mezi startovn´ı a c´ılovou pozic´ı, mus´ı pˇri hledán´ı zpracovat alespoˇ n vˇsechny dlaˇzdice na dané cestˇe, sp´ıˇse vˇsak (vlivem pˇrekáˇzek) jeˇstˇe o poznán´ı v´ıce. To m˚ uˇze vyˇzadovat pˇr´ıliˇs mnoho ˇcasu a pamˇeti. Vznikly sice mnohé zrychlen´ı pouˇzit´ım lepˇs´ıch datov´ ych struktur nebo oˇrezáván´ım prohledávaného stromu (viz napˇr. [7]), v´ yrazného zlepˇsen´ı vˇsak dosáhneme aˇz pouˇzit´ım nˇejakého systematického pˇr´ıstupu. Po krátkém nahlédnut´ı do klasického algoritmu A* se zamˇeˇr´ıme na metody, které v´ ymˇenou za zaruˇcen´ı optimality ˇreˇsen´ı z´ıskaj´ı podstatné zrychlen´ı a zmenˇsen´ı pamˇet’ov´ ych nárok˚ u. Dále nás budou zaj´ımat pouze algoritmy pracuj´ıc´ı nad dlaˇzdicov´ ymi mapami a naopak aˇz na v´ yjimky se nebudeme zab´ yvat technikami steeringov´ ymi (viz napˇr. [12]). V podstatˇe mimo náˇs zájem stoj´ı také pˇr´ıstupy, které zaˇc´ınaj´ı s dopˇredu neznám´ ym terénem a aˇz cestou zjiˇst’uj´ı topologii prostoru – enti znaj´ı design m´ıstnost´ı i pˇredmˇet˚ u v nich po startu dokonale, staˇc´ı pouze reagovat na zmˇeny. Tato kapitola si nebere za c´ıl pˇredvést vyˇcerpávaj´ıc´ı pˇrehled vˇsech algoritm˚ u a technik, které spadaj´ı do vymezeného prostoru. Popisuje pouze ty, které nás nˇejak´ ym zp˚ usobem zaujaly a u kter´ ych se zdálo, ˇze budou v dosti specifickém prostˇred´ı neproceduráln´ıch jazyk˚ u projektu ENTI relativnˇe snadno implementovatelné.

9

2.1

Algoritmus A*

A* patˇr´ı do skupiny algoritm˚ u, které hledaj´ı optimáln´ı cestu v ohodnocen´ ych grafech. Vyznaˇcuje se pouˇzit´ım heuristiky, kterou usmˇerˇ nuje hledán´ı v nejslibnˇejˇs´ım smˇeru. Jeho jednoduchost o nˇem umoˇznila za urˇcit´ ych podm´ınek dokázat vˇsechny podstatné vlastnosti jako správnost, koneˇcnost nebo optimalitu. Algoritmus po kroc´ıch prohledává zadan´ y graf. Zaˇc´ıná startovn´ım vrcholem s, kter´ y oznaˇc´ı jako navˇst´ıvený, tj. um´ıst´ı ho do seznamu open. V kaˇzdém kroku jeden z navˇst´ıven´ ych vybere, prohlás´ı za probraný, tj. um´ıst´ı ho do seznamu closed, a zpracuje jeho sousedy. Algoritmus konˇc´ı v okamˇziku, kdy je do seznamu open um´ıstˇen c´ılov´ y vrchol c (pseudokód viz obrázek 2.1). Aby mohl algoritmus co nejrychleji nalézt nejkratˇs´ı cestu k c´ıli, mus´ı správnˇe vybrat, kter´ y z vrchol˚ u v seznamu open v daném kole zpracovat. Algoritmus A* vyb´ırá vrchol n, kter´ y má nejniˇzˇs´ı hodnotu ohodnocovac´ı funkce f (n). Jej´ı hodnota se spoˇc´ıtá jako souˇcet f (n) = g(n) + h(n), kde • g(n) je nejkratˇs´ı vzdálenost ze startovn´ıho vrcholu s do n pˇres doposud probrané vrcholy a • h(n) oznaˇcuje odhad nejkratˇs´ı moˇzné vzdálenosti z n do c´ılového vrcholu c. Tento odhad nesm´ı b´ yt vˇetˇs´ı neˇz skuteˇcná nejkratˇs´ı vzdálenost z n do c´ıle.

A*(start, c´ıl ) { pˇridej (start, 0) do open while open neprázdn´ y vezmi n nejlepˇs´ı z open if (n == c´ıl ) return u ´spˇech“ ” pˇridej n do closed for (all x ∈ Succ(n) and x ∈ / closed ) if (x ∈ / open) pˇridej (x, f (x)) do open else aktualizuj (x, f (x)) v open, pokud je tˇreba return ne´ uspˇech“ ” }

Obrázek 2.1: Pseudokód jednoduché varianty algoritmu A*

10

Pro kaˇzdého souseda n0 ∈ Succ(n) takto vybraného vrcholu je spoˇctena hodnota f (n0 ) = g(n0 ) + h(n0 ). Pokud n0 jeˇstˇe nen´ı v closed, pˇridá se s hodnotou f (n0 ) do seznamu open 1 . Jestliˇze jiˇz v closed je, pˇreˇrad´ı se do open jenom v pˇr´ıpadˇe, ˇze je jeho nová hodnota f (n0 ) niˇzˇs´ı neˇz p˚ uvodn´ı2 . Po dosaˇzen´ı c´ılového vrcholu c se vlastn´ı cesta z´ıská postupnˇe pomoc´ı zpˇetn´ ych ukazatel˚ u na pˇredka, tj. ukazatel˚ u na ten vrchol, ze kterého byl dan´ y naposledy pˇridán do seznamu open. ´ ech algoritmu je silnˇe závisl´ Uspˇ y na pˇresnosti odhadu vzdálenosti do c´ıle h(n). Podhodnocen´ı vede ke zbyteˇcnému prob´ırán´ı vrchol˚ u nav´ıc, je-li vˇsak odhad vˇetˇs´ı neˇz skuteˇcnost, nalezen´ı nejkratˇs´ı cesty nen´ı zaruˇceno. V porovnán´ı s algoritmy, které heuristiku nepouˇz´ıvaj´ı (napˇr´ıklad s Dijkstrov´ ym algoritmem [4]) sice A* pˇrináˇs´ı znaˇcné zlepˇsen´ı, ale zejména na delˇs´ıch vzdálenostech m˚ uˇze zpracovávat vrchol˚ u stále velmi mnoho.

2.2

Hierarchical Pathfinding A*

Jak jiˇz sám název napov´ıdá, Hierarchical Pathfinding A* (dále HPA*) je typick´ ym zástupcem hierarchick´ ych plánovac´ıch metod. Pomˇernˇe jednoduch´ ym zp˚ usobem rozdˇel´ı prohledávan´ y prostor a postav´ı jednoduˇsˇs´ı graf (ve smyslu poˇctu vrchol˚ u), ve kterém lze hledat podstatnˇe rychleji neˇz v p˚ uvodn´ım plánu. Tato abstraktn´ı ” cesta“ se pak podle potˇreby zjemn´ı“ na konkrétn´ı sled dlaˇzdic. ” Algoritmus si v iniciaˇcn´ı fázi rozdˇel´ı danou mapu na tzv. klastry, coˇz jsou pravidelné ˇctvercové oblasti. Praktické testy ukázaly (viz [2], str. 19), ˇze vhodnou velikost´ı pro standardn´ı mapy je 10 × 10 pol´ıˇcek. Vybraná pol´ıˇcka, která bezprostˇrednˇe soused´ı s voln´ ymi pol´ıˇcky sousedn´ıch klastr˚ u, pak urˇc´ı za tzv. pr˚ uchody. Tyto pr˚ uchody se spoj´ı jednak se sousedn´ımi pr˚ uchody z jin´ ych klastr˚ u, jednak navzájem v rámci jednoho klastru, pokud mezi nimi existuje cesta (viz obrázek 2.2). Délky cest v rámci jednoho klastru se ukládaj´ı. T´ımto zp˚ usobem se vytvoˇr´ı tzv. abstraktn´ı graf. Postup vytváˇren´ı klastr˚ u a abstraktn´ıho grafu lze iterovat a vytváˇret tak zmiˇ novanou hierarchii. Lze tedy poodstoupit“ v´ yˇs a budovat nad klastry do” savadn´ımi klastry vˇetˇs´ı (cca dvojnásobné) velikosti. T´ım se jeˇstˇe zmenˇs´ı velikost abstraktn´ıho grafu a hledán´ı v´ıce urychl´ı. M´ısto pˇrid´ an´ı jiˇz zaˇrazeného vrcholu lze pouze aktualizovat hodnotu f (n0 ) Pˇri pouˇzit´ı tzv. monot´ onn´ı metriky, coˇz je pˇr´ıpad vˇetˇsiny praktick´ ych aplikac´ı, se vrcholy v closed jiˇz nepˇrehodnocuj´ı. 1

2

11

Pˇri hledán´ı urˇcité cesty se s rostouc´ımi klastry stává nároˇcnˇejˇs´ı operace zaˇclenˇen´ı startovn´ıho a c´ılového pol´ıˇcka dané cesty do abstraktn´ıho grafu, zvˇetˇsován´ı klastr˚ u tedy nen´ı vhodné dˇelat do nekoneˇcna (pro mapy velikosti cca 100 × 100 jsou vhodné 2–3 vrstvy hierarchie). Vlastn´ı nalezen´ı cesty v takto doplnˇeném abstraktn´ım grafu je naopak jednoduché a rychlé, pouˇzije se standardn´ıho algoritmu A* na graf, kter´ y má cca setinov´ y poˇcet vrchol˚ u oproti p˚ uvodn´ı mapˇe. Abychom z´ıskali seznam pol´ıˇcek, kudy skuteˇcnˇe povede cesta po mapˇe, je nutné provést tzv. path refinement, neboli zjemnˇen´ı cesty. Tato operace se s v´ yhodou m˚ uˇze provádˇet postupnˇe aˇz kdyˇz je potˇreba konkrétn´ı u ´sek cesty. Pˇri programován´ı umˇel´ ych bytost´ı se totiˇz m˚ uˇze snadno stát, ˇze se ˇr´ızen´ı pˇredá jiné ˇcásti programu, nebo ˇze naplánovaná cesta selˇze, takˇze poˇc´ıtán´ı celé cesty dopˇredu m˚ uˇze b´ yt ˇcasto zbyteˇcné. Posledn´ı, nepovinnou fáz´ı je tzv. vyhlazen´ı cesty. Protoˇze je poˇcet pr˚ uchod˚ u mezi klastry omezen, mezi m´ısty, které by se daly spojit pˇr´ımou ˇcárou, m˚ uˇze vést cesta zbyteˇcnˇe klikatˇe. Vyhlazen´ı tedy postupuje po spoˇctené cestˇe jeˇstˇe jednou a kontroluje, zda-li nelze dlaˇzdice pr˚ uchod˚ u v následuj´ıc´ım klastru spojit pˇr´ımou ˇcárou. V kladném pˇr´ıpadˇe p˚ uvodn´ı cestu nahrad´ı cestou jednoduˇsˇs´ı a kratˇs´ı. Autoˇri v [2] uvádˇej´ı, ˇze praktické testy ukázaly aˇz desetinásobné zrychlen´ı oproti optimalizovanému A*. HPA* spotˇrebovává na sv˚ uj OpenList pˇribliˇznˇe tˇretinu pamˇeti oproti bˇeˇznému A*, poˇcet navˇst´ıven´ ych dlaˇzdic je aˇz desetkrát menˇs´ı. Produkuje o cca 6 % delˇs´ı cestu neˇz A*, kdyˇz se vˇsak zaˇrad´ı postprocessing (smoothing), jeho chyba je kolem 0,5 %. V uvedeném ˇclánku pouˇz´ıvaj´ı autoˇri osmismˇerné dlaˇzdice, ale nenaˇsli jsme d˚ uvod, proˇc by algoritmus nemˇel stejnˇe dobˇre fungovat i s dlaˇzdicemi ˇctyˇrsmˇern´ ymi, které pouˇz´ıvá projekt ENTI. Dopˇredu nebylo jasné, do jaké m´ıry budou moci enti ukládat informace o abstraktn´ım grafu, celkovˇe se ale HPA* ukázal jako dobr´ y kandidát. Za zm´ınku stoj´ı i to, ˇze se na algoritmu dále pracuje, coˇz dokládaj´ı drobná zlepˇsen´ı uvedená v [8].

Obrázek 2.2: Klastry a pr˚ uchody algoritmu HPA*

12

2.3

Partial-Refinement A*

Podobnˇe jako v pˇredchoz´ım pˇr´ıpadˇe, i tento algoritmus pouˇz´ıvá hierarchii abstraktn´ıch graf˚ u, jej´ı struktura i práce s n´ı je ale odliˇsná. Algoritmus se uˇz na základn´ı mapu d´ıvá jako na graf: vrcholy odpov´ıdaj´ı dlaˇzdic´ım a hrana mezi nimi vede v pˇr´ıpadˇe, ˇze spolu odpov´ıdaj´ıc´ı dlaˇzdice soused´ı. Berou se pˇri tom v u ´vahu mimo ˇctyˇr základn´ıch smˇer˚ u i ˇctyˇri smˇery diagonáln´ı. Na rozd´ıl od HPA*, kter´ y pˇrekr´ yvá p˚ uvodn´ı mapu strukturou shora, Partial-Refinement A* (dále PRA*) sluˇcuje vrcholy na základˇe lokáln´ıch vlastnost´ı grafu. Algoritmus hledá ve zpracovávaném grafu kliky, které nahrazuje v budované (vyˇsˇs´ı) vrstvˇe jedin´ ymi stavy. Spojován´ım klik je zaruˇceno, ˇze vˇsechny p˚ uvodn´ı vrcholy náleˇz´ıc´ı k novému stavu jsou od sebe vzdáleny jeden krok. Tedy témˇeˇr: ke klikám se do jednoho stavu pˇridávaj´ı také pˇrilehl´ı sirotci, coˇz jsou vrcholy pˇripojené k dané klice pouze/právˇe jednou hranou (viz obrázek 2.3). Cel´ y algoritmus zpracován´ı grafu je urˇcen k iteraci, dokonce jeˇstˇe v´ıce neˇz u HPA* – abstrakce konˇc´ı v momentˇe, kdyˇz uˇz zbyde jenom jeden vrchol. Celá sada vrstev tvoˇr´ı jak´ ysi strom, kter´ y PRA* vyuˇz´ıvá. PRA* pro poˇcáteˇcn´ı (start) a koncov´ y (goal ) vrchol nejdˇr´ıve zkonstruuje takovou ˇcást stromu, aby start a goal byly v listech a aby mˇely jediného spoleˇcného pˇredka. Poté urˇc´ı hladinu, od které zaˇcne iterovanˇe vylepˇsovat cestu – nesm´ı b´ yt ani moc hluboko (algoritmus by provedl pˇr´ıliˇs mnoho krok˚ u) ani moc mˇelko (v´ ysledná cesta by se mohla od optimáln´ı hodnˇe liˇsit). V kaˇzdé iteraci vezme v aktuáln´ı hladinˇe cestu z vrcholu obsahuj´ıc´ı“ start do vrcholu, kter´ y vznikl abs” trakc´ı vrcholu goal, rozbal´ı jednu u ´roveˇ n n´ıˇz a v tomto pásu“ najde nejkratˇs´ı ” cestu pomoc´ı A* (pseudokód viz obrázek 2.4). Také PRA* umoˇzn ˇuje vylepˇsovat cestu postupnˇe (tj. jaksi cestou), dokonce ho lze pˇr´ımo parametrizovat, kolik dlaˇzdic dopˇredu má poˇc´ıtat – na tuto vlastnost je

Obrázek 2.3: Konstrukce abstraktn´ıho grafu PRA* (zdroj: [14])

13

pˇripraven lépe neˇz HPA*. Autoˇri v [14] nab´ız´ı rychlostn´ı srovnán´ı s m´ırnˇe optimaˇ lizovan´ ym A*. Casov´ au ´spora oproti A* rychle roste s délkou hledané cesty: cestu délky 400 dlaˇzdic PRA* najde aˇz desetkrát rychleji, naopak na mal´ ych mapách (cesty délky cca 50 a ménˇe) m˚ uˇze PRA* dokonce m´ırnˇe ztrácet. Délka nalezené cesty na testovan´ ych mapách se v˚ uˇci cestˇe A* neliˇs´ı o v´ıce neˇz 5 %, v 95 procentech pˇr´ıpad˚ u je pak delˇs´ı o ménˇe neˇz 0,5 %. V ˇclánku [14] autoˇri popisuj´ı algoritmus s osmismˇern´ ymi dlaˇzdicemi, coˇz je dle naˇseho soudu pomˇernˇe kl´ıˇcová podm´ınka: v grafu ze ˇctyˇrsmˇern´ ych dlaˇzdic maj´ı kliky velikost nejv´ yˇse 2. Na druhou stranu t´ım, ˇze PRA* pˇri stavbˇe abstraktn´ıho grafu vycház´ı jen z pˇr´ıstupn´ ych dlaˇzdic, m˚ uˇze b´ yt napˇr´ıklad pro ˇr´ıdké mapy efektivnˇejˇs´ı, nav´ıc striktnˇe nevyˇzaduje celou mapu v jedné ˇctvercové s´ıti, coˇz by se mohlo v prostˇred´ı projektu ENTI ukázat jako v´ yhoda.

PRA*(abstraktn´ıGraf, start, goal ) { PostavHierarchiiAbstrakc´ı(start, goal ) ´ s = VyberStartovn´ıUroveˇ n(start, goal ) vypr´ azdni cestu for kaˇzdou u ´roveˇ n i = s to 1 cesta = ZjemniCestu(cesta, start[i], ocas(cesty)) return cesta } ZjemniCestu(cesta, start, goal ) { return aStar(start, goal ) omezen´ y na vrcholy v cestˇe }

Obrázek 2.4: Pseudokód algoritmu PRA*

14

2.4

Dalˇ s´ı metody

Memory-Efficient Abstractions V ˇclánku [15] je pˇredstaven dalˇs´ı pˇr´ıstup ke generován´ı abstraktn´ıch graf˚ u. Do jisté m´ıry je kombinac´ı dvou pˇredeˇsl´ ych metod. Stejnˇe jako HPA* rozdˇel´ı p˚ uvodn´ı plán na pravidelnou s´ıt’ sektor˚ u. Sektory dále rozdˇel´ı na souvislé oblasti, tzv. regiony, které se stávaj´ı vrcholy budouc´ıho abstraktn´ıho grafu. Ten vzniká spojen´ım tˇech region˚ u, které mezi sebou soused´ı (viz obrázek 2.5). Vlastn´ı algoritmus je pak podobn´ y HPA* – nejdˇr´ıve se najde pomoc´ı A* cesta v abstraktn´ım grafu, která se podle potˇreby zjemn´ı a následnˇe vyhlad´ı. Z algoritmu PRA* si tento pˇr´ıstup pˇrevzal omezen´ı hledán´ı v niˇzˇs´ıch patrech jen na pás“ ” tvoˇren´ y regiony z cesty v abstraktn´ım grafu. ˇ anek se dále detailnˇe zab´ Cl´ yvá postupn´ ym zjemˇ nován´ım, vyhlazován´ım nebo pamˇet’ovou efektivitou, to vˇsak pro naˇse pouˇzit´ı nen´ı podstatné.

Obrázek 2.5: Sektory a regiony Memory-Efficient Abstractions (zdroj: [15])

Incremental heuristic search methods Typick´ ym zástupcem této skupiny algoritm˚ u je D* Lite [9]. Tyto metody pouˇz´ıvaj´ı heuristiku, aby omezily a zac´ılily hledán´ı, a zároveˇ n vyuˇz´ıvaj´ı dˇr´ıve spoˇcten´ ych cest z minul´ ych bˇeh˚ u algoritmu. Opravuj´ı jen to, co se zmˇenilo a která ˇcást jiˇz prohleˇ r´ı tak nemalé mnoˇzstv´ı prohledáván´ı, dané mapy je d´ıky tomu potˇreba opravit. Setˇ nebot’ zmˇeny ˇcasto zasahuj´ı jen malou ˇcást mapy (napˇr. kv˚ uli zamˇcen´ ym dveˇr´ım). D* Lite zaˇc´ıná hledán´ım cesty od c´ılové dlaˇzdice ke startovn´ı. Jeho postup pˇri prvn´ım hledán´ı je v podstatˇe totoˇzn´ y s hledán´ım bˇeˇzného A*, jen kromˇe odhadu vzdálenosti z c´ılové dlaˇzdice, hodnoty g, pouˇz´ıvá odhad jeˇstˇe jeden, hodnotu rhs.

15

Je to jak´ ysi jednokrokov´ y v´ yhled, pˇresnˇeji minimum ze souˇct˚ u hodnot g(s0 ) soused˚ u dané dlaˇzdice a ceny pˇrechodu z tohoto souseda c(s0 , s): (

rhs(s) =

0 pokud s = sstart 0 0 mins0 ∈P red(s) (g(s ) + c(s , s)) jinak.

Tyto hodnoty uchovává u kaˇzdé dlaˇzdice a aktualizuje je v okamˇziku, kdyˇz nalezne zmˇeny v mapˇe. Zmˇenou jedné z hodnot se stane dlaˇzdice nekonzistentn´ı, coˇz m˚ uˇze m´ıt za následek aktualizaci hodnot i dlaˇzdic sousedn´ıch. V´ ysledná cesta se pak najde projit´ım dlaˇzdic s z c´ılové dlaˇzdice sgoal tak, ˇze se vˇzdy vyb´ırá pˇredch˚ udce s0 ∈ P red(s) s minimáln´ı hodnotou g(s0 ) + c(s0 , s). I tato skupina algoritm˚ u je kandidátem na pouˇzit´ı v projektu ENTI, protoˇze zmˇeny v konfiguraci svˇeta vˇetˇsinou neb´ yvaj´ı obrovské. D* Lite mezi nimi vyniká svou jednoduchost´ı a v´ yborn´ ym popisem.

Z´ avˇ er Z uveden´ ych algoritm˚ u byl po zváˇzen´ı v´ yhod a nev´ yhod vybrán HPA*, kter´ y byl upraven tak, aby co nejlépe pracoval v prostˇred´ı projektu ENTI. V´ıce o tom, jaké d˚ uvody k v´ ybˇeru vedly a jak byl HPA* upraven, se doˇctete v kapitole 4.1 na stranˇe 24.

16

Kapitola 3 Projekt ENTI 3.1

Struktura projektu ENTI

Projekt ENTI nen´ı monolitick´ y – lze na nˇeho sp´ıˇse nahl´ıˇzet jako na soubor nˇekolika u ´zce provázan´ ych softwarov´ ych nástroj˚ u1 . Nejd˚ uleˇzitˇejˇs´ımi jsou server prostˇred´ı, 2 prohl´ıˇzeˇc a ent . Server prostˇred´ı je u ´stˇredn´ı sloˇzkou projektu. Jeho u ´kolem je ˇr´ıdit veˇskeré fyzikáln´ı dˇeje v modelovaném svˇetˇe a komunikovat s enty a prohl´ıˇzeˇcem. Server prostˇred´ı od nich pˇrij´ımá informace o jejich ˇcinnosti, opaˇcn´ ym smˇerem pak pos´ılá 3 u ´daje o zmˇenách , které ve svˇetˇe nastaly. Prohl´ıˇzeˇc je uˇzivatelsk´ ym rozhran´ım projektu. Stejnˇe jako ent je to klient, kter´ y se pˇripojuje k serveru prostˇred´ı. Prostˇrednictv´ım prohl´ıˇzeˇce m˚ uˇze uˇzivatel do svˇeta vstupovat jako jeden z ent˚ u a sledovat a ovlivˇ novat tak dˇen´ı ve svˇetˇe. Program ent je komponentou projektu, jeˇz reprezentuje jednoho enta – strojovou bytost ob´ yvaj´ıc´ı modelovan´ y svˇet. Tato bytost je schopna vn´ımat dˇeje ve svém bezprostˇredn´ım okol´ı a tyto vjemy shromaˇzd’ovat ve své pamˇeti4 . Jej´ı chován´ı a rozhodován´ı je ˇr´ızeno skripty, pomoc´ı kter´ ych m˚ uˇze skládat jednoduché u ´kony (tzv. atomické instrukce) do sloˇzitˇejˇs´ıch u ´loh. 1

citace z [1], ˇc´ ast Uˇzivatelsk´ a pˇr´ıruˇcka, str. 15 Stejnˇe jako v [1] oznaˇcuje slovo ent napsané normáln´ım p´ısmem simulovanou bytost. Totéˇz slovo, ale neproporcion´ aln´ım p´ısmem, je název spustitelného programu, kter´ y bytost ˇr´ıd´ı. ENTI v mnoˇzném ˇc´ısle a kapit´ alkami pak obˇcas budeme pouˇz´ıvat m´ısto souslov´ı projekt ENTI“. ” 3 citace z [1], ˇc´ ast Uˇzivatelsk´ a pˇr´ıruˇcka, str. 17 4 citace z [1], ˇc´ ast Uˇzivatelsk´ a pˇr´ıruˇcka, str. 19 2

17

Ke svému bˇehu potˇrebuj´ı ENTI i tzv. bal´ık svˇeta. Je to sada konfiguraˇcn´ıch soubor˚ u, která popisuje simulovan´ y svˇet. Lze s nimi mˇenit vzhled a strukturu svˇeta. Obsahuje téˇz nˇekteré skripty a dalˇs´ı konfigurace pro jednotlivé enty.

3.2

Svˇ et ent˚ u

Jak bylo uvedeno v´ yˇse, jedn´ım z c´ıl˚ u projektu ENTI je simulovat svˇet podobn´ y svˇetu naˇsemu. Autoˇri zvolili nˇekterá zjednoduˇsen´ı, která tuto práci a koneˇcn´ y v´ ybˇer algoritm˚ u podstatn´ ym zp˚ usobem ovlivˇ nuj´ı. Jde zejména o následuj´ıc´ı (viz [1], ˇcást Teoretická dokumentace, str. 10): Diskr´ etn´ı prostor a objekty. Prostor svˇeta ent˚ u je rozdˇelen na malé dlaˇzdice ve ˇctvercové s´ıti. Na dlaˇzdic´ıch mohou b´ yt um´ıstˇeny pˇredmˇety, vˇcetnˇe ent˚ u samotn´ ych. Pˇredmˇety mohou (podle urˇcit´ ych pravidel) zase obsahovat pˇredmˇety. Prostor je dále rozdˇelen do samostatn´ ych u ´sek˚ u, tzv. m´ıstnost´ı. Diskr´ etn´ı bˇ eh ˇ casu. Simulace je provádˇena po kolech, v kaˇzdém kole vˇsichni enti dostanou cel´ y popis m´ıstnosti, kde se nacház´ı, o zmˇenách v jin´ ych m´ıstnostech se naopak nedozv´ı nic. V kaˇzdém kole pos´ılá kaˇzd´ y ent serveru atomickou instrukci a mezi instrukcemi provád´ı v´ ypoˇcty. Omezen´ yˇ cas i prostor. Ent´ı ˇcas je zdola omezen startovn´ım okamˇzikem projektu. Ent´ı prostor je omezen´ y, v simulovaném svˇetˇe je dopˇredu dán poˇcet i velikost m´ıstnost´ı, m´ıstnosti ani dlaˇzdice nemohou pˇrib´ yvat ani ub´ yvat.

Obrázek 3.1: Spuˇstˇen´ y prohl´ıˇzeˇc ENT˚ U

18

Enti se mohou pohybovat ve ˇctyˇrech smˇerech. Neexistuje stav natoˇcen´ı“ ani ” instrukce pro otáˇcen´ı – enti mohou udˇelat v dalˇs´ım kole krok na kteroukoli ze ˇctyˇr sousedn´ıch dlaˇzdic. M´ıstnosti jsou mezi sebou propojeny dveˇrmi. Mezi nˇekter´ ymi m´ıstnostmi mohou vést schody, které svˇet rozdˇel´ı do nˇekolika pater. Ent˚ uv pohled na topologii m´ıstnost´ı je vˇsak jednoduˇsˇs´ı neˇz by se mohlo z uvedeného popisu zdát: ent jen v´ı, které m´ıstnosti jsou propojeny kter´ ymi dveˇrmi. Schody od dveˇr´ı v podstatˇe nerozliˇsuje. Veˇskeré informace o um´ıstˇen´ı pˇredmˇet˚ u a ostatn´ıch ent˚ u jsou vˇzdy relativn´ı k jednotliv´ ym m´ıstnostem, ˇzádné absolutn´ı souˇradnice neexistuj´ı a vlastnˇe je ani ˇzádná ˇcást projektu nepotˇrebuje.

3.3

Programov´ an´ı ent˚ u

Jak jiˇz bylo nˇekolikrát zm´ınˇeno, chován´ı ent˚ u je ˇr´ızeno skripty. Vˇetˇsina z nich je napsaná v jazyce E. Tyto skripty jsou interpretované pˇr´ımo entem, a tak je lze pomˇernˇe snadno mˇenit nebo rozˇsiˇrovat a do znaˇcné m´ıry tak ovlivˇ novat chován´ı kaˇzdého enta zvláˇst’. Nˇekteré v´ ypoˇctové skripty nebo funkce pro práci s databáz´ı jsou vˇsak v jazyc´ıch Mercury [11] nebo C a kompiluj´ı se pˇr´ımo jako souˇcást enta. Jejich zmˇeny pro bˇeˇzné uˇzivatele pˇr´ıliˇs pˇr´ıvˇetivé nejsou (ˇcasto je potˇreba mˇenit nˇekolik soubor˚ u na r˚ uzn´ ych m´ıstech, neexistuje debugger), odmˇenou je vˇsak vyˇsˇs´ı rychlost a do jisté m´ıry i spolehlivost. Pojd’me se na jazyk E pod´ıvat trochu podrobnˇeji. Základn´ı strukturou pro zápis algoritm˚ u je tzv. skript. Je na cestˇe mezi prologovsk´ ym termem a procedurou v C (jakkoli se to zdá nemoˇzné). Zat´ımco v´ ybˇer toho, kter´ y skript se spust´ı, se dˇeje podle ryze specifick´ ych pravidel, vykonáván´ı pˇr´ıkaz˚ u uvnitˇr skriptu prob´ıhá do znaˇcné m´ıry procedurálnˇe. K dispozici jsou i pˇr´ıkazy jako repeat, if—then nebo for-cyklus, na druhou stranu lze pouˇz´ıt verzi s backtrackingem i bez nˇej. K v´ ybˇeru toho, kter´ y skript z nˇekolika variant se má pouˇz´ıt, slouˇz´ı hodnot´ıc´ı funkce. Ta existuje pro kaˇzd´ y skript. Na základˇe stavu enta a jeho okol´ı urˇc´ı, jak moc je pro enta daná verze skriptu zaj´ımavá, a interpret pak vybere nejslibnˇejˇs´ı variantu. Podobn´ y systém pouˇz´ıvaj´ı priority. S jejich pomoc´ı jazyk E dovoluje provádˇet v´ıce u ´loh najednou a jen mezi nimi pˇrep´ınat podle toho, která z nich je nejd˚ uleˇzitˇejˇs´ı (má nejvyˇsˇs´ı prioritu). Tyto priority se nav´ıc mohou mˇenit v ˇcase, takˇze lze elegantnˇe plánovat vykonáván´ı r˚ uzn´ ych u ´kol˚ u, obstaráván´ı ˇzivotn´ıch potˇreb apod. 19

Dalˇs´ım neménˇe zaj´ımav´ ym jevem je tzv. interrupt. Pˇri programován´ı umˇel´ ych bytost´ı je ˇcasto potˇreba zajistit po urˇcitou dobu platnost nˇejak´ ych podm´ınek. Interrupty jsou skripty, které spoustu jinak nutn´ ych test˚ u nahrad´ı elegantn´ım ˇreˇsen´ım: po jejich aktivaci (tzv. navˇeˇsen´ı“) se zaˇcnou provádˇet jakmile zaˇcne ” platit námi zvolená podm´ınka. Pˇr´ıklad: jestliˇze ent potˇrebuje z´ıskat konev, ale o ˇzádné nev´ı, lze navˇesit interrupt seber konev a skonˇci“ na podm´ınku vid´ım ” ” konev“. Staˇc´ı pak procházet svˇet a jakmile ent konev uvid´ı, sebere ji a skript u ´spˇeˇsnˇe skonˇc´ı. Jazyk E má ale i nev´ yhody. Rozliˇsuje jen ˇctyˇri datové typy: handle (v podstatˇe ˇctyˇrbajtové celé ˇc´ıslo slouˇz´ıc´ı k reprezentaci vˇsech ent˚ u, m´ıstnost´ı, objekt˚ u i ˇc´ısel), seznam (bˇeˇzná datová struktura neproceduráln´ıch jazyk˚ u, m˚ uˇze obsahovat objekty typu handle), member (struktura s pevnˇe dan´ ymi poloˇzkami nebo jinak také ˇrádek relaˇcn´ı tabulky, pouˇz´ıvaná ke konkretizaci pˇredmˇet˚ u) a superseznam (seznam member˚ u). Zcela chyb´ı napˇr´ıklad pole, se kter´ ymi by mnohé algoritmy pracovaly podstatnˇe efektivnˇeji. Omezené jsou i moˇznosti ukládán´ı dat mezi bˇehy skript˚ u. Existuj´ı jen dvˇe moˇznosti: globáln´ı promˇenné a entova databáze. Prvn´ı z nich je sice jednoduchá a patrnˇe i rychlá, nelze ale pouˇz´ıt ve funkc´ıch psan´ ych v Mercury nebo C. Pˇridávat nov´ y typ záznamu do entovy databáze tak, aby byl pˇr´ıstupn´ y i z Mercury/Cfunkc´ı, sice lze, vyˇzaduje to vˇsak velké u ´sil´ı v konfiguraci mnoha dalˇs´ıch soubor˚ u, pˇridáván´ı nov´ ych handl˚ u atd. Do entovy databáze nav´ıc nelze ukládat nic jiného neˇz handly, takˇze uchováván´ı vˇetˇs´ıho mnoˇzstv´ı dat, napˇr´ıklad urˇcité informace ke kaˇzdé dlaˇzdici na mapˇe, by databázi velmi zaplnilo a zpomalilo.

3.4

Pohybov´ e skripty

Skripty a funkce, které jsou zamˇeˇreny na ent˚ uv pohyb a navigaci, jsou soustˇredˇeny v knihovnách skript˚ u jazyka E i ve zdrojov´ ych souborech napsan´ ych v Mercury. V prvn´ı skupinˇe najdeme pˇredevˇs´ım ˇr´ıd´ıc´ı v´ ykonné skripty, které obsahuj´ı vyˇsˇs´ı logiku“, atomické instrukce a ˇcasto vyuˇz´ıvaj´ı interrupty, ” napˇr´ıklad jdiNaDlazdici/5, jdiDoMistnosti/3 nebo jdiKEntovi/2. Do druhé skupiny patˇr´ı hlavnˇe v´ ypoˇcetn´ı funkce hledaj´ıc´ı vlastn´ı cestu po dlaˇzdic´ıch nebo mezi m´ıstnostmi, ˇcasto komunikuj´ıc´ı s databáz´ı. Pˇr´ıkladem jsou funkce cSmerKDlazdici/6 nebo cDvereSmeremK/6. Prvn´ı c´ıl této práce (viz kap. 1.1, str. 7), zrychlen´ı prohledávac´ıch algoritm˚ u, se bude naplˇ novat pˇredevˇs´ım ve druhé skupinˇe, tedy v Mercury. Naopak pro skripty, které budou zlepˇsovat vˇerohodnost chován´ı ent˚ u, nab´ız´ı jazyk E pomˇernˇe ˇsirokou 20

paletu nástroj˚ u. Vˇetˇsina zmˇen spadaj´ıc´ıch do této oblasti se tedy bude odehrávat ve zdrojov´ ych souborech ze skupiny prvn´ı. Konkrétn´ı popis toho, co a jak bylo zlepˇseno, najdete v následuj´ıc´ıch dvou kapitolách.

21

Kapitola 4 Pouˇ zit´ e postupy a algoritmy C´ıle této práce byly sice vytyˇceny v kapitole 1.1, nikoliv vˇsak pˇr´ıliˇs konkrétnˇe. Následuj´ıc´ı kapitola pˇredstav´ı problémy, kter´ ymi jsme se zab´ yvali, podrobnˇeji, a to vˇcetnˇe obecného popisu jejich ˇreˇsen´ı. Jde o hierarchické hledán´ı cest pomoc´ı varianty algoritmu A* (4.1), tzv. bagrován´ı (4.2), pronásledován´ı (4.3) a vyh´ ybán´ı ciz´ım ent˚ um (4.4) a sb´ırán´ı pˇredmˇet˚ u pˇri jin´ ych ˇcinnostech, tzv. on-line hledán´ı (4.5). Implementaˇcn´ı detaily a pˇr´ıklady pouˇzit´ı naleznete v kapitole 5.

4.1

Hierarchick´ e hled´ an´ı cest

Pˇrestoˇze virtuáln´ı svˇet ENT˚ U je typicky pouze nˇ ekolik m´ıstnost´ı velik´ y, enti se v nˇem mus´ı rychle a pˇresvˇedˇcivˇe pohybovat. Naj´ıt cestu mus´ı v podstatˇe k jakémukoli u ´kolu – zahradn´ık mus´ı pro zeleninu doj´ıt na zahradu, um´ yt se mus´ı enti u umyvadla nebo ve sprˇse apod. Stejnˇe jako v jin´ ych podobn´ ych aplikac´ıch (nejˇcastˇeji v poˇc´ıtaˇcov´ ych hrách), hledán´ı cest je nejen hojnˇe pouˇz´ıváno, ale nav´ıc jako takové zab´ırá pomˇernˇe mnoho v´ ypoˇcetn´ıho ˇcasu. To zjist´ıme zejména v pˇr´ıpadˇe, kdyˇz projekt ENTI spust´ıme na starˇs´ım poˇc´ıtaˇci (cca 1,3 GHz a ménˇe). C´ıl je tedy zˇrejm´ y: hledán´ı cest zefektivnit pˇri souˇcasném zachován´ı nebo dokonce zlepˇsen´ı vˇerohodnosti pohybu. Jak uˇz jsme uvedli, p˚ uvodn´ı pˇredstava ent˚ u o topologii m´ıstnost´ı byla velmi jednoduchá: enti pouze vˇedˇeli, která m´ıstnost je se kterou spojena dveˇrmi. Je sice pravdou, ˇze na to, aby doˇsli tam, kam potˇrebuj´ı, to staˇc´ı, ale tento pˇr´ıstup neumoˇzn ˇuje k hledán´ı cesty mezi r˚ uzn´ ymi m´ıstnostmi pouˇz´ıt lepˇs´ı algoritmus neˇz Dijkstr˚ uv. Ten se v pˇr´ıpadˇe ENT˚ U, kde jsou vˇ sechny m´ıstnosti podobnˇe velké, moc neodliˇsuje od prohledáván´ı do ˇs´ıˇrky. Enti si nav´ıc spoˇctenou cestu pˇres m´ıstnosti 22

nepamatovali – vyrazili do prvn´ı m´ıstnosti, kudy cesta vedla, a tam celou cestu poˇc´ıtali znova. P˚ uvodn´ı návrh hledán´ı cest mezi dlaˇzdicemi v r˚ uzn´ ych m´ıstnostech byl do jisté m´ıry hierarchick´ y jiˇz od zaˇcátku – nejdˇr´ıve si enti naplánovali, pˇres které m´ıstnosti p˚ ujdou, a v nich pak hledali konkrétn´ı cestu po jednotliv´ ych dlaˇzdic´ıch. Neumoˇzn ˇoval vˇsak ve vyˇsˇs´ıch vrstvách pouˇz´ıt ˇzádnou heuristiku.

Absolutn´ı souˇ radnice dlaˇ zdic Jako prvn´ı krok k efektivnˇejˇs´ım algoritm˚ um jsme proto napsali sadu skript˚ u a Mercury-funkc´ı, které vˇsechny m´ıstnosti zasadily do jakési virtuáln´ı trojdimenzionáln´ı s´ıtˇe, tj. kaˇzdé m´ıstnosti pˇriˇradily souˇradnice (x, y, z) jej´ıho severozápadn´ıho rohu (hodnoty jsou relativn´ı v˚ uˇci startovn´ı pozici enta). Souˇradnice v rámci m´ıstnosti jsou pˇr´ımo uloˇzeny v prvn´ım a druhém bajtu handlu dané dlaˇzdice, pozice konkrétn´ıch dlaˇzdic jsou tedy prost´ ym souˇctem dvou vektor˚ u po sloˇzkách. Postup z´ıskán´ı této sady souˇradnic je pomˇernˇe jednoduch´ y: ent (virtuálnˇe) procház´ı jednotlivé m´ıstnosti do ˇs´ıˇrky. Kaˇzdé dveˇre, na které naraz´ı, jsou jiˇz v proˇslé ˇcásti mapy, a jejich absolutn´ı souˇradnice jsou tedy známy. Pomoc´ı relativn´ı pozice dveˇr´ı v nové m´ıstnosti se pak snadno spoˇc´ıtá pozice jej´ıho severozápadn´ıho rohu. Procházen´ı prob´ıhá po jednotliv´ ych patrech – pokud ent naraz´ı na schody, poˇcká s jejich projit´ım, dokud nen´ı proˇslé celé pˇredchoz´ı patro. Svˇet ent˚ u neˇ rozliˇsuje, zda schody vedou nahoru nebo dol˚ u. C´ısla pater (souˇradnice z) tedy nemus´ı odpov´ıdat zam´ yˇslenému návrhu svˇeta; je to sp´ıˇse poˇrad´ı, v jakém se jednotlivá patra zpracovávala. Aby se vˇsak topologie pater neztratila, ent si vytváˇr´ı paralelnˇe dalˇs´ı strukturu, tzv. graf pater. Tam ukládá, které patro je kde a se kter´ ym spojeno schody. K jeho vyuˇzit´ı se vrát´ıme pozdˇeji. Tento krok umoˇznil u kaˇzdé dlaˇzdice rychle zjistit jej´ı pˇribliˇznou vzdálenost od kterékoli jiné. Protoˇze enti chod´ı jen do ˇctyˇr smˇer˚ u, nejlepˇs´ı metrikou je jistˇe Manhattanská, která vzdálenost rychle spoˇc´ıtá jako souˇcet absolutn´ıch hodnot rozd´ıl˚ u odpov´ıdaj´ıc´ıch souˇradnic d(A, B) = |Ax − Bx | + |Ay − By | + |Az − Bz |. Jak bylo uvedeno v pˇredchoz´ım odstavci, v´ yznam vzdálenosti v ose z je diskutabiln´ı, pro naˇse u ´ˇcely vˇsak staˇc´ı. 23

V´ ybˇ er, u ´ pravy a aplikace HPA* V tomto bodˇe jiˇz bylo tˇreba rozhodnout, kter´ y z algoritm˚ u uveden´ ych v kapitole 2 aplikovat. HPA* se nab´ızel svou jednoduchost´ı, v prostˇred´ı projektu ENTI vˇsak má své slabiny: mapa m˚ uˇze b´ yt pomˇernˇe ˇr´ıdká a nen´ı zaruˇceno, ˇze se m´ıstnosti po zasazen´ı do 3D s´ıtˇe nebudou pˇrekr´ yvat. Dalˇs´ı v poˇrad´ı, PRA*, se zdál na prvn´ı pohled jako dobr´ y kandidát: abstraktn´ı graf vycház´ı pˇr´ımo z dané mapy, nab´ız´ı velkou variabilitu, nav´ıc je algoritmus aktivnˇe pouˇz´ıván a vyv´ıjen. Po bliˇzˇs´ım zkoumán´ı byl ale zavrˇzen: poˇzadavek na osmismˇerné dlaˇzdice je pˇr´ıliˇs siln´ y, nad to by bylo pˇrinejmenˇs´ım nepˇr´ıjemné ukládat do entovy databáze mnoˇzstv´ı abstraktn´ıch graf˚ u. D* Lite a jiné algoritmy ze skupiny incremental heuristic search metods byly zavrˇzeny kv˚ uli omezenosti entovy databáze, nav´ıc nedosahuj´ı takov´ ych zlepˇsen´ı v rychlosti jako hierarchické pˇr´ıstupy. Posledn´ı z uveden´ ych, Memory-Efficient Abstractions, vyuˇz´ıvá zaj´ımavého pˇr´ıstupu v dˇelen´ı mapy na souvislé oblasti, ale nepˇredstavuje pˇr´ıliˇs komplexn´ı ˇreˇsen´ı. Po zváˇzen´ı klad˚ u a zápor˚ u popsan´ ych metod jsme nakonec zvolili sv˚ uj vlastn´ı pˇr´ıstup. Je zaloˇzen na stejné myˇslence jako HPA*, naplno ale vyuˇz´ıvá dodateˇcn´ ych informac´ı a implementaˇcn´ıch detail˚ u naˇs´ı konkrétn´ı aplikace, tedy projektu ENTI. Postup uveden´ y v [2] jsme upravili pˇredevˇs´ım v tˇechto bodech: Klastry nahrazeny m´ıstnostmi. M´ısto klastr˚ u (“clusters” v ˇclánku [2]) velikosti cca 10 × 10 pol´ı jsme vyuˇzili nativn´ıho rozdˇelen´ı svˇeta na m´ıstnosti. Toto ˇreˇsen´ı pˇrináˇs´ı mnohé v´ yhody. Velmi dobˇre, pˇresnˇe a v´ ystiˇznˇe jsou definované pr˚ uchody mezi klastry (“enters” a “transmissions” v [2]) pomoc´ı dveˇr´ı a schod˚ u mezi m´ıstnostmi. Je t´ım zaruˇcena vysoká pˇresnost heuristiky (pˇresnˇeji to vlastnˇe ani nejde – enti nemohou proj´ıt pˇres zed’), nen´ı potˇreba path smoothing (nen´ı kudy cestu zlepˇsit) a nav´ıc je celá implementace o poznán´ı jednoduˇsˇs´ı. Existuj´ı samozˇrejmˇe i záporné stránky. M´ıstnosti jsou obvykle menˇs´ı neˇz 10 × 10 pol´ı a pr˚ uchod˚ u m˚ uˇze b´ yt v´ıce neˇz v origináln´ım ˇreˇsen´ı HPA*, takˇze hledán´ı v abstraktn´ım grafu je nároˇcnˇejˇs´ı. L´ın´ e poˇ c´ıt´ an´ı vzd´ alenost´ı. P˚ uvodn´ı podoba HPA* navrhuje pˇredpoˇc´ıtat vzdálenosti mezi pr˚ uchody (v naˇsem pˇr´ıpadˇe mezi dveˇrmi) v kaˇzdém klastru dopˇredu. Naˇse práce pouˇz´ıvá jin´ y pˇr´ıstup: nejdˇr´ıve se pouˇz´ıvá odhad Manhattanskou metrikou. Pˇresná vzdálenost se spoˇc´ıtá aˇz v okamˇziku, kdy ent skuteˇcnˇe cestu mezi dveˇrmi potˇrebuje naplánovat a proj´ıt. Spoˇctenou vzdálenost si pak uloˇz´ı do databáze a pˇr´ıˇstˇe ji jiˇz pouˇzije m´ısto odhadu. Toto chován´ı nav´ıc odpov´ıdá chován´ı lid´ı – chce-li ˇclovˇek rychle odhadnout 24

nˇejakou vzdálenost, m˚ uˇze se snadno dopustit chyby. Pokud si ale nˇejakou trasu opravdu projde, odhad se podstatn´ ym zp˚ usobem zpˇresn´ı. Druh´ a abstraktn´ı vrstva tvoˇ ren´ a patry. Autoˇri v [2] v˚ ubec neuvaˇzuj´ı, ˇze by mapa mohla vyboˇcit ze dvou rozmˇer˚ u. Bylo proto potˇreba naj´ıt zp˚ usob, jak nejlépe vyˇreˇsit hledán´ı v nˇekolika patrech. Celkem pˇrirozenˇe se nab´ıdlo ˇreˇsen´ı vytvoˇrit mezi nimi druhou abstraktn´ı vrstvu. Právˇe zde se uplatn´ı graf pater generovan´ y pˇri ukládán´ı absolutn´ıch pozic m´ıstnost´ı (viz str. 23). Hled´ an´ı jen v prvn´ı abstraktn´ı vrstvˇ e. Podobnost v entovˇe vn´ımán´ı dveˇr´ı a schod˚ u umoˇznila jednoduˇse implementovat pomˇernˇe pˇrekvapivou vˇec: plánovat cestu mezi m´ıstnostmi v r˚ uzn´ ych patrech lze stejnˇe dobˇre pouˇzit´ım obou abstraktn´ıch vrstev (tzn. nejdˇr´ıve zjistit, pˇres která patra a schody je potˇreba j´ıt, a pak teprve naplánovat nejkratˇs´ı cesty pˇres m´ıstnosti mezi schody v kaˇzdém patˇre) i kdyˇz se bude hledat jen ve vrstvˇe prvn´ı (na schody se bude ent d´ıvat jako na obyˇcejné dveˇre a druhá abstraktn´ı vrstva se nepouˇzije). Prvn´ı pˇr´ıstup je pro delˇs´ı cesty rychlejˇs´ı a zˇrejmˇe i podobnˇejˇs´ı lidskému jednán´ı, druh´ y pak umoˇzn ˇuje naj´ıt cesty o nˇeco kratˇs´ı (pouˇz´ıvá se pˇresnˇejˇs´ı heuristika, patra lze opouˇstˇet a zase se do nich vracet). Vlastn´ı algoritmus nalezen´ı cesty se od p˚ uvodn´ıho algoritmu HPA* v podstatˇe neliˇs´ı (pseudokód viz obrázek 4.1). Pouˇz´ıvá-li se graf pater, najde se nejdˇr´ıve, pˇres které schody je potˇreba proj´ıt. Tato cesta se pak zjemn´ı o sled dveˇr´ı tvoˇr´ıc´ı nejkratˇs´ı cestu mezi schody. Pokud se druhá abstraktn´ı vrstva nepouˇzije, z´ıskáme sled dveˇr´ı a schod˚ u rovnou. Za zm´ınku stoj´ı, ˇze právˇe v tomto bodˇe hraj´ı kl´ıˇcovou roli ´ cinnˇe lze totiˇz pouˇz´ıvat algoritmus absolutn´ı souˇradnice dlaˇzdic, dveˇr´ı a schod˚ u. Uˇ A* i pˇri hledán´ı mezi r˚ uzn´ ymi m´ıstnostmi, coˇz p˚ uvodnˇe nebylo moˇzné. Ent spoˇc´ıtá cestu pˇres aktuáln´ı m´ıstnost k nejbliˇzˇs´ım dveˇr´ım a vyraz´ı k nim. Cestu pˇres dalˇs´ı m´ıstnosti poˇc´ıtá vˇzdy aˇz kdyˇz do nich vstoup´ı. Jednak se t´ımto rozdˇeluje zátˇeˇz procesoru na v´ıc ˇcást´ı, ˇc´ımˇz se bˇeh ENT˚ U st´ avá plynulejˇs´ım, jednak se nepoˇc´ıtá zbyteˇcnˇe dopˇredu v pˇr´ıpadˇe, ˇze je nalezená cesta nepr˚ uchodná nebo je potˇreba pˇreplánovat u ´lohu, a v neposledn´ı ˇradˇe se stává hledán´ı pˇresnˇejˇs´ı, nebot’ ent z´ıská po vstupu do m´ıstnosti aktuáln´ı pˇrehled o vˇsech pˇredmˇetech i entech, kteˇr´ı se v n´ı nacház´ı. Popsaná metoda sniˇzuje ˇcasové nároky na hledán´ı cest, coˇz by se mˇelo v´ yraznˇeji projevit zejména u delˇs´ıch vzdálenost´ı. Kromˇe popsaného hierarchického pˇr´ıstupu au ´spory hledán´ı pouˇzit´ım algoritmu A* se ˇcas uspoˇr´ı i odstranˇen´ım hledán´ı celé cesty v kaˇzdé m´ıstnosti znovu – skripty si cestu pamatuj´ı a k pˇreplánován´ı docház´ı aˇz kdyˇz selˇze nˇekter´ y z podskript˚ u. 25

cNajdiCestuDo(start, c´ıl, pˇresnost, pouˇzijPatra) { if ((StejnéPatro(start, c´ıl ) and pouˇzijPatra == true) or pouˇzijPatra == false) then omezNaJednoPatro = pouˇzijPatra (dlaˇzdicePˇredeDveˇrmi, vzd´ alenost) = aStar(start, c´ıl, pˇresnost, omezNaJednoPatro) else omezNaJednoPatro = true dlaˇzdiceUSchod˚ u = aStarVrat’JenPatra(start, c´ıl, pˇresnost) (dlaˇzdicePˇredeDveˇrmi, vzd´ alenost) = ZjemniPatra(start, c´ıl, dlaˇzdiceUSchod˚ u, omezNaJednoPatro) return (dlaˇzdicePˇredeDveˇrmi, vzd´ alenost) } ZjemniPatra(start, c´ıl, dlaˇzdiceUSchod˚ u) { omezNaJednoPatro = true abstraktn´ıCesta = [start, dlaˇzdiceUSchod˚ u, c´ıl ] dlaˇzdicePˇredeDveˇrmi = [ ] vzd´ alenost = 0 do (s, g) = VezmiPrvn´ıDvojiciZ(abstraktn´ıCesta) (novéDlaˇzdice, nov´ aVzd´ alenost) = aStar(s, g, pˇresnost, omezNaJednoPatro) dlaˇzdicePˇredeDveˇrmi = dlaˇzdicePˇredeDveˇrmi + novéDlaˇzdice vzd´ alenost = vzd´ alenost + nov´ aVzd´ alenost while nepr´ azdn´ a abstraktn´ıCesta return (dlaˇzdicePˇredeDveˇrmi, vzd´ alenost) }

Obrázek 4.1: Pseudokód hledán´ı mezi r˚ uzn´ ymi m´ıstnostmi

26

Pozn´ amka o mˇ eˇ ren´ı vzd´ alenost´ı Algoritmus A* potˇrebuje k odhadu vzdálenosti do c´ıle rychlou a tzv. pˇr´ıpustnou metriku. V pˇr´ıpadˇe ˇctyˇrsmˇern´ ych dlaˇzdic se v naprosté vˇetˇsinˇe pˇr´ıpad˚ u pouˇz´ıvá jiˇz zm´ınˇená metrika Manhattanská a ani v této práci nen´ı pouˇzito jiné. Je to jak´ ysi doln´ı odhad vzdálenosti do c´ıle. Problém se ale objevuje ve vertikáln´ım smˇeru. Jak jiˇz bylo uvedeno v´ yˇse, v´ yznam rozd´ılu v souˇradnic´ıch z pˇr´ıliˇs neodpov´ıdá vzdálenosti pater mezi sebou. Nav´ıc vzdálenost mezi dlaˇzdicemi pˇr´ımo nad sebou bude nejsp´ıˇs ve skuteˇcnosti mnohem delˇs´ı neˇz 1, nebot’ cesta mus´ı vést pˇres nˇejaké schody – heuristika je silnˇe podhodnocená (viz napˇr. obrázek 4.2). Následky nejsou katastrofáln´ı, popsan´ y jev ale m˚ uˇze vést v pˇr´ıpadˇe vynechán´ı druhé abstraktn´ı vrstvy (grafu pater) ke zbyteˇcnému hledán´ı v nec´ılov´ ych patrech do m´ıst, kudy cesta nepovede. Do jin´ ych pater lze totiˇz vstoupit pouze po schodech, hledán´ı jinam tedy nemá smysl. Problém je naopak zcela odstranˇen, kdyˇz se druhá vrstva pouˇzije, nebot’ hledán´ı cesty je pak omezeno vˇzdy jen na jedno patro. Druh´ y typ vzdálenost´ı, se kter´ ymi A* pracuje, je vzdálenost dosud uraˇzená. Ta ’ by mˇela b´ yt co nejpˇresnˇejˇs´ı, nebot pˇri pouˇzit´ı ˇspatného odhadu nemus´ı algoritmus naj´ıt cestu nejkratˇs´ı. Popsané algoritmy sˇc´ıtaj´ı vzdálenosti uraˇzené pˇres jednotlivé m´ıstnosti. Na jejich mˇeˇren´ı lze pouˇz´ıt tˇri stupnˇe pˇresnosti: (1) odhad Manhattanskou metrikou (nejménˇe pˇresn´ y), (2) vzet´ı vzdálenosti z entovy databáze, pokud tam je, jinak pouˇzit´ı pˇredchoz´ıho postupu, (3) pˇresné naplánován´ı cesty

Obrázek 4.2: Vzdálenosti ve vertikáln´ım smˇeru. Heuristika (d = 1) se m˚ uˇze od skuteˇcnosti (d = 22) znaˇcnˇe liˇsit.

27

mezi dveˇrmi a uloˇzen´ı nové vzdálenosti do databáze (to i v pˇr´ıpadˇe, kdyˇz v databázi byla stará hodnota). Je na autorovi, kter´ y skript pouˇz´ıvá, jakou pˇresnost a rychlost zvol´ı.

4.2

Bagrov´ an´ı

Zat´ımco pˇredchoz´ı ˇcást (4.1) se vˇenovala sp´ıˇse teoretickému a algoritmickému zlepˇsen´ı odpov´ıdaj´ıc´ı prvn´ımu c´ıli této práce, následuj´ıc´ı ˇcásti se zamˇeˇr´ı na praktiˇctˇejˇs´ı a viditelnˇejˇs´ı chován´ı ent˚ u. Pˇri hledán´ı cesty po jedné m´ıstnosti se pouˇz´ıval algoritmus A* i v p˚ uvodn´ı verzi ENT˚ U. V nˇ ekter´ ych pˇr´ıpadech vˇsak nefungoval správnˇe. Pˇr´ıkladem je situace, kdy byla cesta na c´ılovou dlaˇzdici zahrazena pˇredmˇety, které lze sebrat. Kdyˇz má ˇclovˇek zablokovanou chodbu vˇecmi, posb´ırá je, pˇrem´ıst´ı a chodbu tak uvoln´ı. Tohoto vˇsak enti nebyli schopni. Náprava byla pomˇernˇe jednoduchá. Zásah vyˇzadoval algoritmus A* tak, aby zaplnˇené dlaˇzdice správnˇe penalizoval, ale aby cestu pˇres nˇe dokázal naj´ıt. Ve skriptu, kter´ y má na starosti vlastn´ı pohyb, pak jiˇz staˇcilo pˇridat schopnost nejdˇr´ıve pˇredmˇety posb´ırat, pokud se ent na naplánovanou dlaˇzdici nevejde. S pohybem po m´ıstnosti souvis´ı i dalˇs´ı podproblém. Pokud se enti chtˇeli dostat na dlaˇzdici ve stejné m´ıstnosti, ve které stáli, hledali cestu pouze po této aktuáln´ı m´ıstnosti. Jestliˇze je vˇsak m´ıstnost zatarasena pˇredmˇety, m˚ uˇze b´ yt v´ yhodnˇejˇs´ı pouˇz´ıt okoln´ı m´ıstnosti a pˇrekáˇzku obej´ıt jinudy. Problém byl postupnˇe vyˇreˇsen dvˇema zp˚ usoby. Prvn´ı testuje cesty okoln´ımi m´ıstnostmi v pˇr´ıpadˇe, ˇze cesta pˇres aktuáln´ı je delˇs´ı neˇz dvojnásobek Manhat-

Obrázek 4.3: Bagruj´ıc´ı ent

28

tanské vzdálenosti. Postupnˇe zkouˇs´ı cesty vˇsemi dveˇrmi, zda-li nem˚ uˇze b´ yt kratˇs´ı. V kladném pˇr´ıpadˇe enta poˇsle touto cestou, nenajde-li ˇzádnou kratˇs´ı cestou, ent se vydá aktuáln´ı m´ıstnost´ı. Druh´ y pˇr´ıstup vyuˇz´ıvá algoritmu z pˇredchoz´ı ˇcásti. Upraven´ım skriptu pro hledán´ı cesty mezi r˚ uzn´ ymi m´ıstnostmi jsme z´ıskali obecnˇejˇs´ı variantu, která umoˇzn ˇuje hledat cestu mezi kter´ ymikoli dlaˇzdicemi, tedy i dlaˇzdicemi jedné m´ıstnosti. Bere pˇri tom v u ´vahu i cesty pˇres m´ıstnosti okoln´ı, na coˇz pouˇz´ıvá uvedenou u ´pravu algoritmu A*.

4.3

Pron´ asledov´ an´ı

´ Ukolem skriptu jdiKEntovi/2 je enta dovést k jinému specifikovanému entovi (dále obˇeti“). V p˚ uvodn´ı verzi se snaˇzil enta nasmˇerovat vˇzdy pˇr´ımo na svoji ” ’ obˇet . Pokud se hnula, skript pˇreplánoval cestu na novou pozici a ent vyrazil nov´ ym smˇerem. Pokud ale budeme zkoumat chován´ı lid´ı, zjist´ıme, ˇze v mnoha pˇr´ıpadech své obˇeti nadbˇehnou a zkrát´ı si tak cestu, zvláˇstˇe pak v pˇr´ıpadˇe, kdy se jim jejich c´ıl nesnaˇz´ı utéci. V ent´ım svˇetˇe ˇctyˇrsmˇern´ ych dlaˇzdic to lze vyjádˇrit pˇresnˇeji. Oznaˇc´ıme-li • zmˇenu souˇradnic, o které se zmˇen´ı pozice naˇs´ı obˇeti za jedno kolo, jako (o∆x , o∆y ), kde o∆x , o∆y ∈ {−1, 0, 1}, |o∆x + o∆y | = 1, • pozici obˇeti jako (ox , oy ), • a pozici naˇseho enta jako (ex , ey ), lze v dané m´ıstnosti alespoˇ n trochu nadbˇehnout pokud sgn(ex − ox ) = sgn(o∆x ) 6= 0 ∨ sgn(ey − oy ) = sgn(o∆y ) 6= 0. Pouˇzijeme techniku pronásledován´ı“ (v orig. “pursuit”) popsanou v [12] ” a upravenou pro prostˇred´ı ˇctyˇrsmˇern´ ych dlaˇzdic. Z pozice obˇeti v aktuáln´ım a pˇredchoz´ım kole lze odhadnout, kudy se naˇse obˇet’ bude pohybovat, pokud se nezastav´ı ani nezmˇen´ı smˇer. Nebo pˇresnˇeji, za kolik kol bude na které dlaˇzdici. Pokud je splnˇena v´ yˇse uvedená podm´ınka, je moˇzné z této informace snadno spoˇc´ıtat pravdˇepodobné m´ısto stˇretu, na které m˚ uˇzeme naˇseho enta poslat (viz obrázek 4.4). 29

Pokud uvedená podm´ınka splnˇena nen´ı, lze jeˇstˇe zkusit jinou moˇznost, a to odhadnout dveˇre, do kter´ ych naˇse obˇet’ m´ıˇr´ı. Jestliˇze ent bude schopn´ y dorazit do vedlejˇs´ı m´ıstnosti dˇr´ıve neˇz obˇet’, zkus´ı j´ı nadbˇehnout sousedn´ımi dveˇrmi. Jestliˇze selˇze i tato moˇznost, nezb´ yvá neˇz se vydat pˇr´ımo za naˇs´ı obˇet´ı s t´ım, ˇze j´ı tˇreba bude moˇzné nadbˇehnout pozdˇeji. intersection

target

ent

Obrázek 4.4: Pronásledován´ı – m´ısto stˇretu

4.4

Vyh´ yb´ an´ı se ostatn´ım ent˚ um

V p˚ uvodn´ı verzi se enti pˇri plánován´ı cesty pˇres m´ıstnost snaˇzili vyhnout pouze dlaˇzdic´ım, na kter´ ych ve chv´ıli hledán´ı nˇekdo stál. To vˇsak bylo zvláˇstˇe na delˇs´ı vzdálenosti témˇeˇr bezpˇredmˇetné – situac´ı, kdy se ciz´ı enti neh´ ybou, je v jejich ˇzivotˇe jen málo. Naˇse metoda na zlepˇsen´ı vycház´ı z postupu uvedeného, stejnˇe jako v pˇredchoz´ım pˇr´ıpadˇe, v [12], konkrétnˇe pˇredcházen´ı koliz´ım“ (v orig. “unaligned ” collision avoidance”). Odhadnou se m´ısta, kde by mohlo doj´ıt ke koliz´ım (pokud se ciz´ı enti budou pohybovat stejnˇe jako v posledn´ım kole), a ent se bude snaˇzit vyhnout tˇemto m´ıst˚ um oˇcekávané sráˇzky. Prvn´ı ˇcást ˇreˇsen´ı je do jisté m´ıry analogická s pˇredchoz´ım pˇr´ıpadem: sledován´ı ostatn´ıch ent˚ u v m´ıstnosti a odhad toho, kter´ ym smˇerem p˚ ujdou. Dobˇre nám pˇri tom poslouˇz´ı jazyk E a jeho interrupty, které dovol´ı sledovat pohyb ostatn´ıch ent˚ u bez enormn´ıho mnoˇzstv´ı test˚ u a podm´ınek. V dalˇs´ım kroku se pak pozice a smˇery, kter´ ym ostatn´ı enti jdou, pˇredaj´ı v´ ypoˇctov´ ym Mercury-funkc´ım, které odhadnou budouc´ı cesty ostatn´ıch ent˚ u a vypoˇctené dlaˇzdice v pˇr´ısluˇsn´ ych kolech pˇri prohledáván´ı algoritmem A* penalizuj´ı. T´ım je dosaˇzeno poˇzadovaného chován´ı – dlaˇzdice, na které m´ıˇr´ı ostatn´ı enti, A* nevybere a ent se jim tedy vyhne. 30

4.5

On-line hled´ an´ı

Pokud chce ent naj´ıt urˇcit´ y pˇredmˇet, nejdˇr´ıve se pod´ıvá do své databáze. Jestliˇze tam odpov´ıdaj´ıc´ı pˇredmˇet najde, jde tam, kde si mysl´ı, ˇze je, a vezme ho. V pˇr´ıpadˇe, ˇze o ˇzádném takovém nev´ı, vyraz´ı na procházku cel´ ym svˇetem a snaˇz´ı se naj´ıt nˇejak´ y splˇ nuj´ıc´ı daná kritéria. Tato práce pˇredstavuje jeˇstˇe jin´ y pˇr´ıstup k hledán´ı vˇec´ı, které (zat´ım) ent nevid´ı. Dal by se nazvat napˇr´ıklad hledán´ı mimodˇek“. Hlavn´ı myˇslenka tkv´ı v tom, ” ˇze ent pˇredmˇety aktivnˇe nehledá, ale sb´ırá aˇz v okamˇziku, kdy je uvid´ı pˇri nˇejaké jiné ˇcinnosti. Ent si udrˇzuje seznam pˇredmˇet˚ u (pˇresnˇeji superseznam member˚ u popisuj´ıc´ıch pˇredmˇety), které by rád naˇsel. Zároveˇ n si nastav´ı globáln´ı interrupt, kter´ y spust´ı sb´ırán´ı pˇredmˇet˚ u aˇz ve chv´ıli, kdy nˇejaké hledané vid´ı. Pro uˇzivatele–programátora jsou k dispozici skripty, které pˇredmˇety pˇridávaj´ı a ub´ıraj´ı ze seznamu hledan´ ych. V podstatˇe v kaˇzdé chv´ıli lze také zjistit, které pˇredmˇety uˇz ent sebral a které jeˇstˇe na sebrán´ı ˇcekaj´ı. Uplatnˇen´ı v praktick´ ych skriptech najde jak verze nová, tak i p˚ uvodn´ı. Nˇekteré vˇeci ent potˇrebuje nutnˇe a dalˇs´ı ˇcinnost se bez nich neobejde (potˇrebuje-li si ent uvaˇrit j´ıdlo, neobejde se bez surovin k jeho v´ yrobˇe). V jin´ ych pˇr´ıpadech je vˇsak moˇzné hledán´ı doˇcasnˇe pˇreruˇsit, zaˇc´ıt dˇelat nˇeco jiného a mezit´ım se pokusit pˇredmˇety naj´ıt. Napˇr´ıklad hudebn´ık˚ uv hlavn´ı u ´kol je chodit po m´ıstnostech a hrát. R˚ uzné hudebn´ı nástroje si m˚ uˇze navˇesit do svého on-line hledaˇce“, v klidu po” kraˇcovat v hran´ı na p˚ uvodn´ı nástroj a nov´ y sebrat aˇz v okamˇziku, kdyˇz se k nˇemu dostane.

Obrázek 4.5: Scéna s vyh´ ybán´ım tˇr´ı ent˚ u

31

Kapitola 5 Implementace a modelov´ e situace 5.1

Hierarchick´ e hled´ an´ı cest

Programovac´ı jazyk Zlepˇsen´ı efektivity hledán´ı cest a v´ ybˇer a implementace nov´ ych prohledávac´ıch algoritm˚ u je kl´ıˇcovou ˇcást´ı této práce. Jak jsme jiˇz naznaˇcili dˇr´ıve, vˇetˇsina zmˇen se odehrála ve zdrojov´ ych souborech jazyka Mercury. Mercury je deklarativn´ı jazyk se silnou kontrolou syntaxe, typ˚ u a druhu determinismu (tzn. jestli a pˇr´ıpadnˇe kolikrát m˚ uˇze predikát uspˇet). To jazyku umoˇzn ˇuje odhalit mnoho chyb jiˇz pˇri pˇrekladu a podstatnˇe zv´ yˇsit rychlost v´ ysledn´ ych program˚ u v porovnán´ı s jin´ ymi deklarativn´ımi jazyky. Jako assembler pouˇz´ıvá jazyk C, ˇc´ımˇz jsou v´ ysledné programy do jisté m´ıry pˇrenositelné. Popsané v´ yhody jako rychlost, silná kontrola a typová ˇcistota jsou zvláˇstˇe v´ yrazné v˚ uˇci jazyku E. Jazyk E má i jiná omezen´ı: do skriptu napˇr´ıklad nelze pˇredat v´ıce neˇz patnáct promˇenn´ ych, coˇz se vzhledem k pˇrekladu kaˇzdého ifvˇetven´ı jako podskriptu ukázalo pro sloˇzitˇejˇs´ı konstrukce jako do znaˇcné m´ıry omezuj´ıc´ı. Vˇse spolu faktem, ˇze nˇekteré prohledávac´ı funkce jiˇz byly v Mercury napsány, bylo kritériem pˇri v´ ybˇeru Mercury. Teoreticky by bylo moˇzné funkce psát i v jin´ ych jazyc´ıch (pˇr´ımo se nab´ızelo C), Mercury vˇsak poskytuje podobnou neproceduráln´ı filozofii jako E – typick´ ym pˇr´ıkladem je bezproblémová práce se seznamy a jejich pˇrevod do/z E. Pˇrestoˇze domovská stránka projektu Mercury [10] p˚ usob´ı dosti amatérsk´ ym a nekomerˇcn´ım dojmem, jeho funkˇcnost a mnoˇzstv´ı kontrol, které skuteˇcnˇe provád´ı, pˇresnˇe odpov´ıdá specifikaci.

32

Jazyk Mercury s sebou pochopitelnˇe pˇrinesl i problémy. Typick´ ym pˇr´ıkladem je absence debuggeru a omezenost na v´ ypisy na standardn´ı v´ ystup. Na domovské stránce je sice uvedeno, ˇze autoˇri ˇzádné lad´ıc´ı prostˇredky nepouˇz´ıvaj´ı, v praxi bychom je ale, mysl´ım, ocenili. Dalˇs´ı problémy vypl´ yvaly z propojen´ı s projektem ENTI. Nejv´ıce ˇcasu zaplnila správná komunikace s entovou databáz´ı. Chybˇel pˇr´ıkaz pro zápis, takˇze bylo potˇreba se ponoˇrit do zdrojov´ ych soubor˚ u nejen Mercury, ale i C++, ve kter´ ym je entova databáze napsána. Jeˇstˇe nároˇcnˇejˇs´ı pak bylo pˇridán´ı nov´ ych tzv. smysl˚ u“, ” které byly nutné pro reprezentaci grafu pater a uloˇzen´ı absolutn´ıch pozic m´ıstnost´ı – zmˇeny vyˇzadovaly i konfiguraˇcn´ı soubory celého projektu ENTI.

ˇ sen´ı Reˇ Vˇsechny popsané problémy se podaˇrilo vyˇreˇsit, a tak jiˇz mohla následovat vlastn´ı implementace upraveného HPA*. Pˇriˇrazen´ı absolutn´ıch souˇradnic m´ıstnostem zaˇr´ıd´ı funkce cNastavPoziceMistnosti/1 s jedn´ım vstupn´ım argumentem udávaj´ıc´ım dlaˇzdici, která bude m´ıt souˇradnice (0, 0, 0) (nejjednoduˇsˇs´ı je pˇredat dlaˇzdici, kde ent právˇe stoj´ı). Tuto funkci je tˇreba zavolat na zaˇcátku entova ˇzivota, zejména pˇred prvn´ım pouˇzit´ım hledac´ıch funkc´ı. Projde vˇsechny dostupné m´ıstnosti a souˇradnice jejich severozápadn´ıch roh˚ u uloˇz´ı do entovy databáze ke smyslu HSmistnost_abspoziceH ve formátu [handle–m´ıstnosti, handle–souˇradnice–X, handle–souˇradnice–Y, handle– souˇradnice–Z ]1 . Za krátkou poznámku stoj´ı, ˇze v ukázkovém svˇetˇe, kter´ y je dodáván spolu s projektem ENTI, nelze vˇsechny m´ıstnosti d´ıky jejich velikostem do krychlové s´ıtˇe správnˇe um´ıstit. Docház´ı tak k jejich pˇrekryv˚ um a/nebo zdem tlustˇs´ım neˇz 1 dlaˇzdice. Nen´ı to vˇsak kl´ıˇcové – souˇradnice se pouˇz´ıvaj´ı vˇzdy jen pro heuristiku tak, ˇze k dlaˇzdici se zjiˇst’uje souˇradnice, nikoliv naopak. Vlastn´ı nové hledán´ı cesty, vyuˇz´ıvaj´ıc´ı variantu algoritmu A*, maj´ı na starosti dvˇe funkce: cNajdiCestuDvermi/8 a cNajdiCestuDo/8. Zásadn´ı rozd´ıl je v tom, ˇze druhá umoˇzn ˇuje hledat cestu nejdˇr´ıve po patrech a teprve následnˇe ji zjemnit na jednotlivé m´ıstnosti, prvn´ı se d´ıvá na schody jako na normáln´ı dveˇre (viz 4.1, str. 25). Souˇcást´ı práce nebylo pouze napsán´ı funkc´ı nov´ ych, ale i nahrazen´ı p˚ uvodn´ıch funkc´ı bez A* nov´ ymi verzemi. Pˇremostˇeny tak byly staré funkce 1

handle–souˇradnice“ znamená handle ˇc´ısla, které se rovná souˇradnici. Napˇr. handle pro ˇc´ıslo ” 0 je totiˇz ve skuteˇcnosti ˇc´ıslo 18120704.

33

cDvereSmeremK/6 a cOdhadVzdalenosti/4 funkc´ı cNajdiCestuDvermi/8 a upraven byl také skript jdiDoMistnosti/1 tak, aby ent nehledal vˇzdy celou cestu znova, jakmile vejde do nové m´ıstnosti, ale aby si ji pamatoval a pouˇz´ıval, dokud to jde.

Testy Testován´ı prob´ıhalo na poˇc´ıtaˇci s procesorem Intel Mobile Celeron 1.8 GHz a 512 MB operaˇcn´ı pamˇeti v prostˇred´ı Linux Fedora Core 5. Vˇzdy byla provedena tˇri nezávislá mˇeˇren´ı téhoˇz nastaven´ı, z kter´ ych se vypoˇc´ıtal aritmetick´ y pr˚ umˇer. Jazyk E by mˇel umoˇzn ˇovat mˇeˇren´ı reálného ˇcasu, kter´ y ubˇehne v daném skriptu, potˇrebné funkce (pushtime, poptime) vˇsak nejsou implementovány. Probˇehlo tedy pouze mˇeˇren´ı v´ ypoˇctov´ ych funkc´ı v Mercury. Aby byly ˇcasy v˚ ubec mˇeˇritelné, jeden predikát probˇehl vˇzdy desetkrát tˇesnˇe za sebou se stejn´ ymi parametry, ˇcasy jednoho bˇehu lze tedy jednoduˇse spoˇc´ıtat vydˇelen´ım deseti. U kaˇzdé trasy jsme mˇeˇrili tˇri r˚ uzné varianty – jako prvn´ı starou funkci cDvereSmeremK/6, jako druhou a tˇret´ı novou cNajdiCestuDo/8, pˇriˇcemˇz ve druhém pˇr´ıpadˇe se pouˇzil graf pater (tedy hierarchická varianta), ve tˇret´ım nikoliv. Nen´ı zcela jasné, do jaké m´ıry byl mˇeˇren skuteˇcnˇe jen ˇcas, kter´ y byl stráven v daném predikátu, jestli mˇeˇren´ı ovlivˇ nuj´ı i ostatn´ı bˇeˇz´ıc´ı procesy a jak se do mˇeˇren´ı prom´ıtla volán´ı ciz´ıch funkc´ı, napˇr´ıklad hledán´ı a zápisy do entovy databáze. Pˇresto hlavn´ım v´ ysledkem jsou hodnoty relativn´ı v˚ uˇci sobˇe. Aˇc jsou leckdy pˇrekvapivé, maj´ı vypov´ıdaj´ıc´ı hodnotu. Neˇz se vˇsak dostaneme k samotnému mˇeˇren´ı, uvˇedomme si, jaké v´ ysledky m˚ uˇzeme oˇcekávat. V ˇcásti 2.2 (str. 11) bylo uvedeno, ˇze HPA* m˚ uˇze b´ yt aˇz desetkrát rychlejˇs´ı neˇz obyˇcejné A* a m˚ uˇze navˇst´ıvit aˇz desetkrát ménˇe vrchol˚ u. Nahlédnut´ım do ˇclánku [2] vˇsak zjist´ıme, ˇze tyto v´ ysledky autoˇri namˇeˇrili u cest délky cca 400. Ukázkov´ y svˇet, na kterém prob´ıhalo testován´ı, takov´ ych rozmˇer˚ u zdaleka nedosahuje. Dalˇs´ı zmˇenou je fakt, ˇze vlastnˇe porovnáváme algoritmus Dijkstr˚ uv s hierarchick´ ym A*. Prvn´ı fakt ukazuje sp´ıˇse na menˇs´ı zrychlen´ı, druh´ y by mˇel naopak rozd´ıl zvˇetˇsovat. Dá se tedy oˇcekávat, ˇze zrychlen´ı bude mˇeˇritelné, a to v´ yraznˇeji s pˇrib´ yvaj´ıc´ı vzdálenost´ı startovn´ı a c´ılové pozice. V ukázkovém svˇetˇe (mapa viz obrázek 5.1 a 5.2) jsme k testován´ı zvolili ˇctyˇri trasy. Vˇsechny vedly z prvn´ıho patra, z toho prvn´ı tˇri z pokoje ˇclovˇeka. Prvn´ı cesta smˇeˇrovala na zahradu, coˇz je pˇribliˇznˇe napˇr´ıˇc cel´ ym svˇetem pˇres vˇsechna tˇri patra, druhá cesta vedla do knihovny, na coˇz staˇcilo pouze vyj´ıt na chodbu 34

komora

pokoj_cloveka

knihovna dilna

Obrázek 5.1: Mapa ukázkového svˇeta: patro a pˇr´ızem´ı

mistnost_s_ _pavucinami

zahrada

Obrázek 5.2: Mapa ukázkového svˇeta: sklep

35

a vej´ıt do c´ılové m´ıstnosti, tˇret´ı do m´ıstnosti s pavuˇcinami, která je, stejnˇe jako zahrada, ve sklepˇe (ent musel tedy proj´ıt pˇres dvoje schody). Posledn´ı cesta vedla z komory do d´ılny v pˇr´ızem´ı. Horizontálnˇe jsou m´ıstnosti na opaˇcn´ ych stranách domu, ale nejkratˇs´ı cesta vede d´ıky tomu, ˇze schody nejsou pˇresnˇe nad sebou, na prvn´ı pohled oklikou. V tabulce 5.1 jsou uvedeny v´ ysledky mˇeˇren´ı. V prvn´ım sloupci je varianta, jakou se hledalo, v dalˇs´ıch dvou délka nalezené cesty v dlaˇzdic´ıch a poˇcet m´ıstnost´ı, kter´ ymi procház´ı. Následuje ˇcas deseti bˇeh˚ u algoritmu v sekundách (pr˚ umˇer ze tˇr´ı mˇeˇren´ı), poˇcet navˇst´ıven´ ych vrchol˚ u (vrchol odpov´ıdá dlaˇzdici pˇrede dveˇrmi) a poˇcet r˚ uzných vrchol˚ u, které algoritmus pˇri svém bˇehu navˇst´ıvil. Prvn´ı hledán´ı, z pokoje ˇclovˇeka na zahradu, dopadlo v zásadˇe podle oˇcekáván´ı. Vzhledem ke stˇredn´ı délce hledané cesty je jiˇz i pˇres nezanedbatelnou reˇzii, se kterou je (hierarchick´ y) A* spojen, rozd´ıl v ˇcase proti Dijkstrovu algoritmu dobˇre patrn´ y. Mezi hierarchickou a nehierarchickou verz´ı v´ yznamn´ y rozd´ıl nen´ı, coˇz jsme vˇsak ˇcekali – hierarchická verze se dle [2] zaˇc´ıná vyplácet aˇz od cest délky cca 50. V poˇctu navˇst´ıven´ ych vrchol˚ u je rozd´ıl v˚ uˇci staré verzi algoritmu velmi markantn´ı: hierarchická verze jich navˇst´ıvila asi sedmdesátkrát ménˇe, nehierarchická pak asi dvaadvacetkrát ménˇe. typ poˇc. dlˇz. poˇc. m´ıst. pr˚ umˇer. ˇcas pokoj cloveka → zahrada cDvere 38 6 0.457 cNajdi/2 36 6 0.280 cNajdi/1 38 6 0.277 pokoj cloveka → knihovna cDvere 16 3 0.030 cNajdi/2 16 3 0.243 cNajdi/1 16 3 0.243 pokoj cloveka → mistnost s pavucinami cDvere 43 6 0.623 cNajdi/2 76 9 0.273 cNajdi/1 43 6 0.403 komora → dilna cDvere 36 6 0.323 cNajdi/2 35 6 0.077 cNajdi/1 36 6 0.067

cel. expnd.

r˚ uz. expnd.

10626 150 480

84 15 41

540 90 110

35 9 11

14260 260 2120

88 21 70

7480 320 310

86 25 31

Tabulka 5.1: V´ ysledky test˚ u

36

Na druhém hledán´ı bylo pomˇernˇe pˇrekvapivé, jak moc m˚ uˇze algoritmus A* na krátk´ ych vzdálenostech ztrácet v ˇcase. D˚ uvodem m˚ uˇze b´ yt, ˇze naˇse implementace v podstatˇe nebyla optimalizovaná, pˇresto je rozd´ıl znaˇcn´ y. Poˇcet navˇst´ıven´ ych vrchol˚ u se ukazuje jako podstatnˇe stabilnˇejˇs´ı ukazatel – A* navˇst´ıvil zhruba pˇetinu; hierarchická a nehierarchická verze se zásadnˇe neliˇs´ı, nebot’ m´ıstnosti byly ve stejném patˇre. Tˇret´ı pˇr´ıklad ukázal typickou vlastnost hierarchického pˇr´ıstupu. Je sice pˇribliˇznˇe dvaap˚ ulkrát rychlejˇs´ı a navˇst´ıvil asi jednu padesátinu vrchol˚ u v˚ uˇci Dijkstrovu algoritmu, d´ıky dˇeravosti“ sklepn´ıho patra (a tud´ıˇz nepˇresné heuris” tice) vˇsak nedokázal naj´ıt nejkratˇs´ı cestu. Nehierarchická verze si za cenu pomˇernˇe velkého poˇctu navˇst´ıven´ ych vrchol˚ u poradit dokázala a d´ıky stˇredn´ı vzdálenosti dokázala Dijkstr˚ uv algoritmus porazit i v ˇcase. Na posledn´ı trase potvrdil Dijkstr˚ uv algoritmus stabilitu sv´ ych v´ ysledk˚ u a ˇcas ani poˇcet navˇst´ıven´ ych vrchol˚ u nevyboˇcuj´ı z vysledovaného chován´ı. Lehce zv´ yˇsen´ y poˇcet navˇst´ıven´ ych vrchol˚ u u algoritm˚ u A* se dá vysvˇetlit nutnost´ı vypoˇrádat se z faktem, ˇze dlaˇzdice, které sousedily s pouˇzit´ ymi dveˇrmi mezi prvn´ım patrem a pˇr´ızem´ım, jsou v horizontáln´ım smˇeru cca 6 dlaˇzdic vzdálené. Vysvˇetlen´ı, proˇc se najednou tak v´ yrazn´ ym zp˚ usobem liˇs´ı ˇcas A* algoritm˚ u, se nám ale nalézt nepodaˇrilo. Celkovˇe lze ˇr´ıci, ˇze ve vˇetˇsinˇe pˇr´ıpad˚ u ke zrychlen´ı skuteˇcnˇe doˇslo. Nové algoritmy ztrác´ı v pˇr´ıpadˇe, ˇze startovn´ı a c´ılové pozice jsou bl´ızko sebe. Vezmeme-li ale v u ´vahu, ˇze nové skripty vrac´ı cestu celou, nejenom prvn´ı m´ıstnost, zrychlen´ı je na delˇs´ıch cestách ve skuteˇcnosti jeˇstˇe v´ yraznˇejˇs´ı a na krátk´ ych se pravdˇepodobnˇe v´ ysledky vyrovnaj´ı, takˇze naˇse práce mˇela smysl.

5.2

Bagrov´ an´ı

Aby enti dokázali nacházet a správnˇe zvaˇzovat nároˇcnost cesty pˇres zaplnˇené dlaˇzdice, bylo potˇreba zmˇenit predikát cSmerKDlazdici/7. P˚ uvodn´ı verze algoritmu A* ignorovala dlaˇzdice, kam se ent neveˇsel. Dalˇs´ı zmˇena pak byla ve skriptu jdiNaDlazdici/5, kter´ y potˇreboval upravit tak, aby dokázal z plné dlaˇzdice nejdˇr´ıve pˇredmˇety posb´ırat. Dalˇs´ı podproblém, schopnost uvaˇzovat i cesty okoln´ımi m´ıstnostmi, jsme nejdˇr´ıve ˇreˇsili pouze ve skriptu jdiNaDlazdici/5. Jak jiˇz bylo naznaˇceno v ˇcásti 4.2 (str. 28), pokud je cesta pˇres aktuáln´ı m´ıstnost velmi dlouhá (delˇs´ı neˇz 37

dvojnásobek teoreticky nejkratˇs´ı vzdálenosti), zkouˇs´ı se postupnˇe cesty pˇres vˇsechny dveˇre i m´ıstnostmi sousedn´ımi. Druhé ˇreˇsen´ı se nab´ıdlo po zlepˇsen´ı prohledáván´ı cest mezi r˚ uzn´ ymi m´ıstnostmi pomoc´ı A*. Pouˇzijeme-li na projit´ı m´ıstnosti skript jdiDoMistnosti/1, prohledávac´ı funkce cNajdiCestuDo/8 bude zkouˇset okoln´ı m´ıstnosti automaticky. Na pˇriloˇzeném CD je video geometrie.avi, které demonstruje dosud popsaná zlepˇsen´ı. Zelen´ y ent je ent ovládan´ y poˇc´ıtaˇcem. Modro-ˇzlut´ y je ovládán uˇzivatelem, jeho pohyb je nutn´ y, aby bylo vidˇet chován´ı strojového enta a nebudeme se ´ j´ım dále zab´ yvat. Ukol zeleného enta je doj´ıt z dlaˇzdice témˇeˇr v nejpravˇejˇs´ım rohu (souˇradnice (2, 5), viz obrázek 5.3) do témˇeˇr nejlevˇejˇs´ıho rohu (8, 2) a poté zase zpˇet. Cestu má zahrazenou kybl´ıky a konvemi, a tak nastane pˇr´ıpad, kdy je spoˇc´ıtaná cesta pˇres aktuáln´ı m´ıstnost velmi dlouhá. Zkus´ı tedy cestu pˇres okoln´ı m´ıstnosti a zjist´ı, ˇze existuje a mohla by b´ yt kratˇs´ı. Na c´ılovou dlaˇzdici tedy dojde pˇres sousedn´ı m´ıstnost. Pˇri plánován´ı cesty v sousedn´ı m´ıstnosti si zapamatuje vzdálenost mezi dveˇrmi, která je d´ıky ˇzidl´ım pomˇernˇe velká, a tak kdyˇz ent plánuje zpáteˇcn´ı cestu (8, 2) → (2, 5), radˇeji sesb´ırá pˇredmˇety v aktuáln´ı m´ıstnosti, protoˇze uˇz v´ı, jak daleko je to d´ıky ˇzidl´ım pˇres m´ıstnost sousedn´ı. Start

Goal

Obrázek 5.3: Topologie m´ıstnost´ı v pˇr´ıkladu z videa na CD

5.3

Pron´ asledov´ an´ı

Základn´ı kostra skriptu jdiKEntovi/2 z˚ ustala stejná, zmˇenila se ale ˇcást, která se stará o dojit´ı aˇz k entovi v aktuáln´ı m´ıstnosti. Skript kombinuje plánovac´ı pˇrednosti jazyka E a na poˇcetn´ı v´ ykony volá funkce napsané v Mercury. Skript navˇes´ı interrupt, kter´ y sleduje pohyb obˇeti. Z jej´ı pozice v pˇredchoz´ım a aktuáln´ım kole zjiˇst’uje smˇer, kter´ ym se obˇet’ za posledn´ı kolo hnula. Zjist´ı-li 38

ent, ˇze obˇet’ zmˇenila smˇer, spust´ı cel´ y skript znovu a pˇreplánuje cestu. Pokud ent v´ı, kam obˇet’ smˇeˇruje, zjist´ı, jestli j´ı m˚ uˇze nadbˇehnout (vzorec viz ˇcást 4.3, str. 29). V kladném pˇr´ıpadˇe spoˇc´ıtá jej´ı cestu a vyraz´ı na nejlepˇs´ı pol´ıˇcko tak, aby j´ı co nejdˇr´ıve potkal. Jestliˇze nadbˇehnout nem˚ uˇze, zkus´ı zjistit, nelze-li doj´ıt kratˇs´ı ’ cestou do m´ıstnosti, kam obˇet m´ıˇr´ı. Najde dveˇre, které jsou nejbl´ıˇz pr˚ useˇc´ıku jej´ı cesty s nejbliˇzˇs´ı stˇenou. Spoˇc´ıtá dvˇe vzdálenosti: vzdálenost d1 obˇeti od tˇechto dveˇr´ı a vzdálenost d2 pr˚ useˇc´ıku jej´ı cesty se stˇenou od dan´ ych dveˇr´ı. Pomoc´ı podm´ınky (5 − 2d1 ) + (5 − 2d2 ) > 0 zkus´ı odhadnout, maj´ı-li dveˇre ˇsanci na to, ˇze do nich obˇet’ skuteˇcnˇe m´ıˇr´ı. Jestliˇze je podm´ınka splnˇena, ent zjist´ı, m˚ uˇze-li doj´ıt do stˇredu m´ıstnosti, kam m´ıˇr´ı tyto dveˇre, kratˇs´ı cestou. Jestliˇze ano, zkus´ı nadbˇehnout takto. Jestliˇze ne, nezb´ yvá, neˇz se vydat pˇr´ımo za obˇet´ı. Dvˇe pˇripravená videa ukazuj´ıc´ı obˇe popsané situace, kdy ent m˚ uˇze obˇeti nadbˇehnout, najdete na CD disku. Zelen´ y ent je strojov´ y a snaˇz´ı se dohnat modroˇzlutého enta ovládaného uˇzivatelem. Prvn´ı video, nadbihani_1.avi, pˇredstavuje pˇr´ıpad, kdy ent m˚ uˇze své obˇeti nadbˇehnout a vyuˇz´ıt tak své poziˇcn´ı v´ yhody i kdyˇz obˇet’ mˇen´ı smˇer. Dobˇre je patrné, ˇze entovy reakce jsou o kolo zpoˇzdˇeny, nebot’ mus´ı nejdˇr´ıve zjistit, kam obˇet’ m´ıˇr´ı. Na druhém videu, nadbihani_2.avi, je ukázka u ´spˇeˇsného odhadu, do kter´ ych dveˇr´ı obˇet’ m´ıˇr´ı, a následné nadbˇehnut´ı kratˇs´ı cestou.

5.4

Vyh´ yb´ an´ı se ostatn´ım ent˚ um

Abychom mohli sledovat pohyb ostatn´ıch ent˚ u v m´ıstnosti, navˇes´ıme ve skriptu jdiNaDlazdici/5 podobn´ y interrupt jako v pˇredchoz´ım pˇr´ıpadˇe. Bude se spouˇstˇet ve chv´ıli, kdy existuj´ı enti, kteˇr´ı jsou bl´ıˇze neˇz zadan´ y polomˇer – na enty, kteˇr´ı jsou dále, se nebere ohled. Z test˚ u vyˇsla pro polomˇer nejlépe hodnota 4, nebot’ je-li to ménˇe, ent nestaˇc´ı uhnout, je-li to v´ıce, zbyteˇcnˇe se zatˇeˇzuje procesor, nav´ıc se pohyb sledovan´ ych ent˚ u m˚ uˇze pˇred stˇretem jeˇstˇe dosti zmˇenit. Pozice a smˇery takto sledovan´ ych ent˚ u se pˇredaj´ı funkci cSmerKDlazdici/7, která spoˇc´ıtá pravdˇepodobné cesty ent˚ u. Dlaˇzdice, po kter´ ych enti zˇrejmˇe p˚ ujdou, v pˇr´ısluˇsn´ ych kolech penalizuje. Pˇri testován´ı jsme zjistili, ˇze penalizovat pouze dlaˇzdici, na které ent bude v pˇr´ısluˇsném kole, nestaˇc´ı. Je to t´ım, ˇze nen´ı dáno poˇrad´ı, v jakém enti vykonaj´ı své atomické instrukce, a nav´ıc ent pˇri svém kroku ˇcasto blokuje p˚ uvodn´ı i c´ılovou dlaˇzdici najednou. Je tedy potˇreba omezit dlaˇzdici pˇred i za tou, kterou odhadnou v´ ypoˇcetn´ı funkce. 39

Pˇriloˇzené CD obsahuje video vyhybani.avi, které popsané zlepˇsen´ı ukazuje názornˇeji. Dva strojov´ı enti jdou proti sobˇe, tˇret´ı, lidsk´ y, kolmo na jejich smˇer. V pˇr´ıpadˇe prvn´ıho vyh´ ybán´ı je moˇzné pozorovat jev, kter´ y známe i z chován´ı lid´ı: enti se snadnˇeji vyh´ ybaj´ı tˇem, kteˇr´ı jdou kolmo. Jdou-li enti pˇr´ımo proti sobˇe, m˚ uˇze se stát, ˇze se zaˇcnou vyh´ ybat na stejnou stranu. Následnˇe ale obˇcas radˇeji kolo poˇckaj´ı, neˇz vyraz´ı na jiˇz navˇst´ıvené dlaˇzdice, takˇze se pomˇernˇe snadno vzájemnˇe obejdou.

5.5

On-line hled´ an´ı

Entovy skripty byly rozˇs´ıˇreny o tˇri nové. Prvn´ı z nich nese název hledejASbirejLazy_Pridej/2. Vytvoˇr´ı nebo rozˇs´ıˇr´ı seznam pˇredmˇet˚ u, které ent bude l´ın´ ym“ zp˚ usobem hledat (popsan´ ym v kapitole 4.5 na str. 31). Jedinou ” moˇznost´ı, jak tento seznam (pˇresnˇeji superseznam) reprezentovat, byly globáln´ı promˇenné. Je potˇreba, aby byl pˇr´ıstupn´ y z v´ıce r˚ uzn´ ych skript˚ u – entova databáze ani fakta pouˇz´ıt nelze, protoˇze do nich lze ukládat pouze typ handle, nikoliv seznam nebo superseznam. Druhá a tˇret´ı funkce hledejASbirejLazy_Uber/1 a hledejASbirejLazy_VsechnoZrus/0 jsou opakem funkce prvn´ı, maj´ı na starosti pˇredmˇety ze seznamu ub´ırat. Pˇr´ıklad pouˇzit´ı m˚ uˇzeme nalézt v ukázce on-line-hled.avi na vloˇzeném CD. Stejnˇe jako v ostatn´ıch pˇr´ıpadech je ˇzluto-modr´ y ent ovládán uˇzivatelem a druh´ y, tentokrát hnˇedo-b´ıl´ y, je ent strojov´ y. Jeho u ´kolem je proj´ıt vˇsechny m´ıstnosti a v kaˇzdé krátce zahrát na vˇsechny hudebn´ı nástroje, které v té chv´ıli má. Jeˇstˇe pˇred cestou do prvn´ı m´ıstnosti, pokoje knihovn´ıka, vˇsak pˇridá do svého on-line hledac´ıho seznamu vˇsechny tˇri druhy hudebn´ıch nástroj˚ u, které ve svˇetˇe ent˚ u existuj´ı: flétnu, harmoniku a housle. V pokoji knihovn´ıka uspˇeje podm´ınka globáln´ıho interruptu navˇeˇseného skriptem hledejASbirejLazy_Pridej/2 t´ım, ˇze ent uvid´ı housle. Sebere je, zahraje na nˇe a vydá se do sousedn´ı chodby. Tam, ani v dalˇs´ı m´ıstnosti, pokoji ˇclovˇeka, ˇzádné nové nástroje nenajde, zahraje tedy pouze na housle. Aˇz v pokoji hudebn´ıka a kuchaˇre najde postupnˇe flétnu a harmoniku, takˇze se jeho nástrojáˇrsk´ y park rozˇs´ıˇr´ı a v posledn´ı m´ıstnosti si uˇz zahraje na nástroje vˇsechny tˇri.

40

Kapitola 6 Z´ avˇ er 6.1

Budouc´ı pr´ ace

Obor umˇelé inteligence se neustále rozv´ıj´ı a s rostouc´ım v´ ykonem poˇc´ıtaˇc˚ u se nab´ız´ı mnoho moˇznost´ı, jak chován´ı umˇel´ ych bytost´ı dále zlepˇsovat. Chceme-li z˚ ustat u pohybov´ ych skript˚ u v projektu ENTI, dalˇs´ı pokraˇcován´ı by se mohlo ub´ırat následuj´ıc´ımi smˇery. Optimalizace A* a HPA*. Z test˚ u vyplynulo, ˇze pˇri hledán´ı velmi krátk´ ych cest nová implementace s heuristick´ ymi algoritmy zaostává nad p˚ uvodn´ı verz´ı. Obecnˇe plat´ı, ˇze ˇc´ım sloˇzitˇejˇs´ı algoritmus, t´ım vˇetˇs´ı nutná reˇzie – toto chován´ı je tedy pˇrirozené. Pˇresto by jistˇe bylo zaj´ımavé se v budoucnu pokusit tento deficit odstranit. Dlouhodob´ e sledov´ an´ı obˇ eti. Pˇri pronásledován´ı ent˚ u se nové skripty snaˇz´ı co nejdˇr´ıve reagovat na nastalé zmˇeny v pohybu obˇeti a vˇzdy hledat nejkratˇs´ı cestu na nové m´ısto stˇretu. Bez zaj´ımavosti by ale jistˇe nebylo sledovat a odhadovat entovu dlouhodobˇejˇs´ı strategii a pokusit se ji vyuˇz´ıt, napˇr´ıklad k nadb´ıhán´ı do sousedn´ıch m´ıstnost´ı. Implementovat by se daly i jiné techniky umˇelé inteligence jako tzv. reinforcement, tedy na základˇe u ´spˇechu nebo ne´ uspˇechu posledn´ıho postupu upravovat pˇr´ıˇst´ı strategie. Sn´ıˇ zen´ı n´ aroˇ cnosti vyh´ yb´ an´ı. Pokud by se podaˇrilo naj´ıt nˇejak´ y nov´ y zp˚ usob v uchováván´ı vˇetˇs´ıho mnoˇzstv´ı dat, nejlépe v poli, hardwarová nároˇcnost vyh´ ybán´ı 41

by se pravdˇepodobnˇe dala sn´ıˇzit aplikac´ı nˇekteré z incremental heuristic search methods. Cesta pˇres m´ıstnost by se pak nemusela hledat pˇri kaˇzdé zmˇenˇe smˇeru druh´ ych ent˚ u celá znovu, ale aktualizovat by se mohla jen inkriminovaná ˇcást mapy. Buzen´ı on-line hledac´ım skriptem. Pokud by se do jazyka E doplnilo v dokumentaci uvedené us´ınán´ı a probouzen´ı skript˚ u, byla by moˇznost skript závisl´ y na sebran´ ych pˇredmˇetech po navˇeˇsen´ı hledan´ ych pˇredmˇet˚ u uspat a po nalezen´ı potˇrebného vybaven´ı opˇet vzbudit. Tento postup by pak spojoval v´ yhody obou nyn´ı dostupn´ ych variant.

6.2

Dalˇ s´ı aplikace

Aˇc se u ´pravou a implementac´ı nov´ ych prohledávac´ıch algoritm˚ u zab´ yvá podstatná ˇcást této práce, jako obecné prostˇred´ı pro jejich testován´ı se projekt ENTI, dle naˇseho názoru, pˇr´ıliˇs nehod´ı. Pathfinding v ENTECH je totiˇz dosti specifick´ y – svˇet je pevnˇe rozdˇelen na m´ıstnosti, enti se pohybuj´ı po pomˇernˇe velk´ ych dlaˇzdic´ıch jen ve ˇctyˇrech smˇerech, je pouˇzit diskrétn´ı ˇcas, nen´ı vyˇreˇsené ukládán´ı vˇetˇs´ıho mnoˇzstv´ı dat apod. Kdybychom chtˇeli postupovat opaˇcn´ ym smˇerem a pouˇz´ıt námi upravenou verzi HPA* v jin´ ych aplikac´ıch, ve vˇetˇsinˇe pˇr´ıpad˚ u bychom asi také narazili na nemalé mnoˇzstv´ı problém˚ u. Jeden pˇr´ınos, se kter´ ym jsme se nesetkali v ˇzádn´ ych jin´ ych zdroj´ıch, vˇsak tato ˇcást práce pˇrinesla: pouˇzit´ı hierarchické formy A* na mapy s v´ıce patry. V dneˇsn´ı dobˇe tˇeˇzko najdeme 3D hru, jej´ıˇz svˇet by nebyl v´ıce´ urovˇ nov´ y. I kdyˇz pˇresnˇe nev´ıme, jak ˇreˇs´ı v´ıce pater napˇr´ıklad boti v Unrealu, vˇeˇr´ıme, ˇze náˇs pˇr´ıstup je dobr´ ym kandidátem na zlepˇsen´ı. Právˇe to, co je pro n´ızko´ urovˇ nové algoritmy“ nev´ yhodou, je v´ıtan´ ym zjed” noduˇsen´ım v algoritmech u ´rovnˇe vyˇsˇs´ı. Pro plánován´ı cel´ ych u ´loh a pˇrep´ınán´ı mezi nimi nab´ız´ı jazyk E praktické nástroje, které spolu s mnoˇzstv´ım zjednoduˇsen´ı (napˇr´ıklad diskrétn´ı ˇcas i prostor) dávaj´ı moˇznost soustˇredit se na dan´ y problém a nezab´ yvat se implementaˇcn´ımi detaily. Praktick´ y pˇr´ınos práce v jin´ ych programech a aplikac´ıch tedy bude sp´ıˇse v postupech spadaj´ıc´ıch do druhého c´ıle práce, tedy ve vˇerohodnˇejˇs´ım chován´ı agent˚ u.

42

Pˇr´ıkladem m˚ uˇze b´ yt pronásledován´ı ent˚ u. Popsaná metoda, která dokáˇze jednoduch´ ym zp˚ usobem uˇcinit chován´ı postav uvˇeˇritelnˇejˇs´ım, by dobˇre mohla naj´ıt uplatnˇen´ı napˇr´ıklad ve strategi´ıch nebo jin´ ych simulac´ıch vyuˇz´ıvaj´ıc´ıch dlaˇzdicové mapy.

6.3

Shrnut´ı

Prvn´ım c´ılem práce bylo zrychlen´ı prohledávac´ıch algoritm˚ u. Abychom ho naplnili, provedli jsme pr˚ uzkum souˇcasn´ ych algoritm˚ u a pˇr´ıstup˚ u, které rozv´ıj´ı základn´ı prohledávac´ı algoritmus A*. Práce pˇrináˇs´ı pˇrehled nejv´ yznamnˇejˇs´ıch zástupc˚ u. Pro pouˇzit´ı v projektu ENTI byl vybrán a dále upraven HPA*. Je to hierarchická u ´prava algoritmu A*, která ve své základn´ı verzi abstrahuje pravidelné oblasti a stav´ı z nich graf. Tento postup se m˚ uˇze opakovat a lze tak vytvoˇrit z abstrakc´ı hierarchii. Z praktick´ ych test˚ u plyne, ˇze v´ ysledn´ y algoritmus skuteˇcnˇe zrychlen´ı na stˇredn´ıch a delˇs´ıch vzdálenostech pˇrináˇs´ı. Pouˇzit´ı dvou vrstev abstraktn´ıch graf˚ u v´ ysledky jeˇstˇe o málo zlepˇsuje, nezaruˇcuje vˇsak nalezen´ı nejkratˇs´ı cesty. Objevil se (do jisté m´ıry oˇcekávan´ y) negativn´ı jev – pˇri hledán´ı krátk´ ych cest m˚ uˇze b´ yt nov´ y algoritmus pomalejˇs´ı neˇz p˚ uvodn´ı. To potvrzuje teorii, ˇze nové, sloˇzitˇejˇs´ı algoritmy maj´ı vˇetˇs´ı nutnou reˇzii, ˇc´ımˇz se vyplác´ı aˇz pˇri rozsáhlejˇs´ıch problémech. Druh´ y c´ıl, vˇerohodnˇejˇs´ı chován´ı ent˚ u, se realizoval ve ˇctyˇrech základn´ıch zlepˇsen´ıch. Uvolˇ nován´ı cesty zatarasené pˇredmˇety, tzv. bagrován´ı, funguje rychle a podle pˇredpoklad˚ u. Pˇri pouˇz´ıván´ı pˇr´ıbuzného vylepˇsen´ı, hledán´ı cesty okoln´ımi m´ıstnostmi, je potˇreba opatrnˇe pouˇz´ıvat jeho prvn´ı verzi. Ve sloˇzitˇejˇs´ıch skriptech m˚ uˇze zp˚ usobovat nepˇrirozené chován´ı napˇr´ıklad t´ım, ˇze se ent bude rychle vracet do m´ıst, kde byl pˇred chv´ıl´ı. V druhém pˇr´ıstupu k obcházen´ı, kter´ y pouˇz´ıvá upraven´ y HPA*, jsme slabiny nenaˇsli. Pronásledován´ı ostatn´ıch ent˚ u prob´ıhá tak, jak jsme si pˇredstavovali. V nejhorˇs´ım pˇr´ıpadˇe se enti chovaj´ı stejnˇe jako podle p˚ uvodn´ıch skript˚ u, pokud ale obˇet’ ut´ıká správn´ ym“ smˇerem, zlepˇsen´ı je zˇretelnˇe vidˇet. ” Vyh´ ybán´ı koliz´ım s ostatn´ımi enty je patrnˇe nediskutabilnˇejˇs´ı ˇcást´ı práce. Pravdou je, ˇze enti do sebe naráˇz´ı jen ve v´ yjimeˇcn´ ych pˇr´ıpadech. Cena, která je za to zaplacena, je vˇsak pomˇernˇe vysoká: jiˇz pˇri tˇrech vyh´ ybaj´ıc´ıch se entech m˚ uˇzeme c´ıtit zpomalen´ı chodu celého systému. Mnoˇzstv´ı interrupt˚ u, které je 43

potˇreba dohromady navˇesit, totiˇz roste s druhou mocninou poˇctu ent˚ u v m´ıstnosti. Interrupty v jazyce E, které se zprvu zdaj´ı jako praktické zjednoduˇsen´ı, se tak d´ıky malé rychlosti zpracován´ı stávaj´ı slabinou. Posledn´ı novou schopnost´ı ent˚ u je tzv. on-line hledán´ı, neboli hledán´ı pˇredmˇet˚ u bˇehem jin´ ych ˇcinnost´ı. Zátˇeˇz procesoru je zv´ yˇsena o jeden krátk´ y interrupt, a tak tato ˇcást funguje nejen správnˇe, ale i rychle. Z uvedeného plyne, ˇze i pˇres jistá negativa, zp˚ usobená pˇreváˇznˇe implementaˇcn´ımi detaily, byly stanovené c´ıle splnˇeny a projekt ENTI tak byl v uveden´ ych bodech skuteˇcnˇe rozˇs´ıˇren a vylepˇsen.

44

Literatura [1] Bojar, O., Brom, C. et al.: Dokumentace studentského softwarového projektu ENTI. MFF UK, Praha, 2002. [2] Botea, A., M¨ uller, M., Schaeffer, J.: Near Optimal Hierarchical Path-Finding. Journal of Game Development, 1:7–28, 2004. ˇ [3] Capek, K.: R. U. R., Rossum’s Universal Robots. Artur, Praha, 2004. [4] Dijkstra, E. W.: A note on two problems in connection with graphs. Numerische Mathematik 1, 269–271, 1959. [5] Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, Vol. 4, Issue 2, p. 100–107, 1968. [6] Henderson, F. et al.: The Mercury Language Reference Manual. The University of Melbourne, Melbourne, 2002. [7] Higgins, D. F.: Pathfinding Design Architecture, How to Achieve LightningFast A*, AI Game Programming Wisdom. Charles River Media, Inc., 2002. [8] Jansen, M. R., Buro, M.: HPA* Enhancements. University of Alberta, Alberta, 2007. [9] Koenig, S., Likhachev, M.: D* Lite. American Association for AI, Atlanta, Pittsburgh, 2002. [10] The Mercury Project – homepage [online]. [cit. 30.7.2007] Dostupn´ y z WWW: [11] The Mercury Library Reference Manual. The University of Melbourne, Melbourne, 2002. 45

[12] Reynolds, C. W.: Steering Behaviors For Autonomous Characters [online]. Sony Computer Entertainment America, California, 1999. [cit. 30.7.2007] Dostupn´ y z WWW: [13] Skalsk´ y, V.: Wolfgang Kempelen: Bratislavský faust [online]. [cit. 31.7.2007] Dostupn´ y z WWW: [14] Sturtevant, N., Buro, M.: Partial Pathfinding Using Map Abstraction and Refinement. The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, 2005. [15] Sturtevant, N. R.: Memory-Efficient Abstractions for Pathfinding. American Association for AI (www.aaai.org), Alberta, 2007.

46

Pˇ r´ıloha: Obsah CD Souˇcást´ı práce je pˇriloˇzen´ y CD-ROM, kter´ y obsahuje • videa, která ukazuj´ı jednotlivá zlepˇsen´ı chován´ı ent˚ u (popis v textu) • struˇcnou instalaˇcn´ı, uˇzivatelskou a programátorskou dokumentaci • instalaci projektu ENTI • zdrojové soubory, kter´ ymi je potˇreba nahradit nˇekteré soubory p˚ uvodn´ı • testovac´ı svˇety a skripty, které demonstruj´ı popsaná vylepˇsen´ı • tuto práci ve formátu PDF

47

Pohyb v projektu ENTI

Recommend Documents