Katedra informatiky
AI Clash AI Clash
2012 Tom ´aˇs Worek
robota, tvorby bitevn´ıho pole a simulace bitvy. N´avrh robota bude prob´ıhat nejprve na- staven´ım technick´eho vybaven´ı robota v GUI a n´aslednˇe naprogramov´an´ım AI pomoc´ı API funkc´ı specificky vytvoˇren´eho jazyka. Tento jazyk umoˇzn´ı reagovat na ud´alosti jako kolize se zd´ı, z´asah stˇrelou, robot na radaru, apod. V ˇc´asti tvorby bitevn´ıho pole bude moˇzno generovat ˇci vytv´aˇret vlastn´ı bitevn´ı pole. V posledn´ı ˇc´asti, pak bude moˇzno vy- brat bitevn´ı pole a spouˇstˇet samotnou simulaci. Implementace bude prob´ıhat v jazyce C#.
Kl´ıˇcov ´a slova: AI Clash, roboti, programovac´ı hra, simulace
Abstract
Goal of this work is to create application to simulate battles of the robots. Application will contains of creation of a robot, creation of a battlefield and simulation of the battle.
Design of the robot will contains robot hardware settings in the GUI and AI program- ming using API functions of specifically constructed language. In this language will be able respond to events such as collisions with the wall, hit a shot, a robot on the radar, etc. In a section of creating the battlefield will be able to generate or create your own battlefield. In the last section, it will be possible to choose the battlefield itself and run the simulation. Implementation will be in C#.
Keywords: AI Clash, robots, programming game, simulation
AI – Artificial Intelligence
API – Application Programming Interface
GUI – Graphical User Interface
MARS – Memory Array Redcode Simulator
PLATO – Programmed Logic for Automated Teaching Operations
RPN – Reversion Polish Notation
Obsah
1 Uvod´ 5
2 Historie a hlavn´ı pˇredstavitel´e 6
2.1 Darwin . . . 6
2.2 Core War . . . 6
2.3 RobotWar . . . 7
3 Specifikace syst´emu 8 3.1 Simulace . . . 8
3.2 Bitevn´ı pole . . . 9
3.3 Robot . . . 10
4 Cyklus simulace 13 4.1 Vygenerov´an´ı powerballu . . . 13
4.2 Interpretace robot ˚u . . . 13
4.3 Aktualizace polohy objekt ˚u . . . 14
4.4 Vyˇreˇsen´ı koliz´ı . . . 14
4.5 Smaz´an´ı a vytvoˇren´ı objekt ˚u . . . 15
4.6 Aktualizace parametr ˚u robot ˚u . . . 16
4.7 Ovˇeˇren´ı ukonˇcen´ı simulace . . . 17
5 Jazyk RoboCode 18 5.1 Jm´eno robota . . . 18
5.2 Koment´aˇre . . . 18
5.3 C´ısla . . . .ˇ 19 5.4 Label . . . 19
5.5 Registry . . . 19
5.6 Instrukce . . . 20
5.7 Oddˇelovaˇce . . . 20
6 Pˇrekladaˇc 24 6.1 Tˇr´ıda Tokenizer . . . 24
6.2 Tˇr´ıda Compiler . . . 25
7 Interpreter 27 7.1 Counter, Stack a CallStack . . . 27
7.2 Krok interpretace . . . 27
7.3 V ´yjimky . . . 28
8 Z´avˇer 30 8.1 Pl´anovan´a vylepˇsen´ı . . . 30
9 Reference 31
Seznam tabulek
1 Z´asobn´ık . . . 18
2 Matematick´e instrukce . . . 21
3 Logick´e instrukce . . . 22
4 ˇR´ıd´ıc´ı a ostatn´ı instrukce . . . 23
Seznam obr ´azk ˚u
1 Aplikace Darwin . . . 6
2 Aplikace Core War . . . 6
3 Aplikace RobotWar . . . 7
4 Aplikace AI Clash . . . 8
5 Battlefield Editor . . . 9
6 Robot Editor . . . 11
Seznam v ´ypis ˚u zdrojov ´eho k ´odu
1 Algoritmus oce ˇnuj´ıc´ı roboty. . . 16
2 Pˇr´ıklad k ´odu v jazyce RoboCode . . . 24
3 Seznam lex´em ˚u po lexik´aln´ı anal ´yze odˇr´adkovan ´y po deseti . . . 25
4 Seznam k ´od ˚u firmwaru po pˇrekladu odˇr´adkovan ´y po deseti . . . 26
5 Zdrojov ´y k ´od operace If . . . 28
1 Uvod ´
Aplikace AI Clash je simul´ator bitev robot ˚u a patˇr´ı mezi tzv. programovac´ı hry. Uˇzivatel´e tˇechto her nemaj´ı moˇznost ˇr´ıdit ˇci jinak ovliv ˇnovat pr ˚ubˇeh simulace. M´ısto toho je v tomto typu aplikac´ı ´ukolem uˇzivatele v pˇredem jasnˇe dan´em, nejˇcastˇeji specificky vytvoˇren´em, programovac´ım jazyce naprogramovat umˇelou inteligenci charakteru (ob- vykle robota ˇci bakterie), kter ´y je pak do dan´e simulace postaven proti charakter ˚um ostatn´ıch uˇzivatel ˚u, at’ uˇz za ´uˇcelem pˇreˇzit´ı, nasb´ır´an´ı nejvˇetˇs´ıho poˇctu bod ˚u, ˇci splnˇen´ı jin ´ych c´ıl ˚u.
Prvn´ı ˇc´ast pr´ace je vˇenov´ana historii programovac´ıch her a pˇredstaven´ı mezn´ık ˚u.
V t´eto ˇc´asti budou pˇredstaveny hry Darwin, Core War a RobotWar. V druh´e ˇc´asti bude pops´ana specifikace syst´emu, co umoˇz ˇnuje a jak´e maj´ı vlastnosti bitevn´ı pole, roboti, powerbally a stˇrely. V n´asleduj´ıc´ı ˇc´asti pak bude pops´an specificky vytvoˇren ´y jazyk RoboCode, kter ´y slouˇz´ı k naprogramov´an´ı umˇel´e inteligence robot ˚u. V dalˇs´ıch ˇc´astech bude postupnˇe pops´an pˇrekladaˇc, kter ´y slouˇz´ı k pˇrekladu z k ´odu v jazyce RoboCode do interpreterem srozumiteln´eho k ´odu, n´asledovan ´y popisem samotn´eho interpreteru.
V z´avˇeru pak budou shrnuty hlavn´ı body, zhodnoceny dosaˇzen´e v ´ysledky a probˇehne n´astin smˇeru, kter ´ym se bude v ´yvoj t´eto pr´ace d´ale ub´ırat.
2 Historie a hlavn´ı pˇredstavitel ´e
2.1 Darwin
Prvn´ı aplikace, kter´a se ˇrad´ı do skupiny programovac´ıch her, jm´enem Darwin, byla vy- tvoˇrena uˇz v roce 1961 v Bell Labs p´any Douglesem McIlroyem, Robertem Morrisem a Victorem Vyssotskym (Metcalf, 2011a). C´ılem uˇzivatel ˚u aplikace bylo napsat IBM 7090 program takov ´y, aby byl co nejv´ıce ˇzivotaschopn ´ym replik´atorem v pamˇeti. Pro tento c´ıl byly k dispozici 3 funkce (test dan´eho m´ısta, zabr´an´ı pr´azdn´eho m´ısta a smaz´an´ı ob- sazen´eho m´ısta) a zpoˇc´atku jen 15 instrukc´ı, jejichˇz poˇcet se pozdˇeji rozrostl aˇz na 44 instrukc´ı.
Obr´azek 1: Aplikace Darwin
2.2 Core War
V roce 1984 byla p´any D. G. Jonesem a A. K. Dewdneyem pˇredstavena desetistr´ankov´a pˇr´ıruˇcka Core War Guidelines (Jones, Dewdney, 1984) popisuj´ıc´ı programovac´ı jazyk Redcode urˇcen ´y pro virtu´aln´ı poˇc´ıtaˇc MARS. Jeˇstˇe t´ehoˇz roku vydal Kevin A. Bjorke zdrojov ´y k ´od vytvoˇren ´y v jazyce C implementuj´ıc´ı virtu´aln´ı poˇc´ıtaˇc MARS a o dva roky pozdˇeji, roku 1986, byl v Bostonu uspoˇr´ad´an prvn´ı mezin´arodn´ı turnaj v programovac´ı hˇre Core War. Turnaje v Core War prob´ıhaj´ı v m´ırnˇe pozmˇenˇen´e formˇe dodnes.
Obr´azek 2: Aplikace Core War
2.3 RobotWar
Avˇsak jeˇstˇe pˇredt´ım byla v roce 1981 publikov´ana pod z´aˇstitou MUSE Software hra jm´enem RobotWar, prvn´ı programovac´ı hra, kter´a simulovala bitvy robot ˚u (Metcalf, 2011b). Byla naps´ana Silasem Warnerem pro poˇc´ıtaˇcov ´y syst´em PLATO. Prvn´ı turnaj byl pak uspoˇr´ad´an hned o rok pozdˇeji. ´Ukolem uˇzivatele bylo naprogramovat umˇelou inteli- genci robota, kter´a by uspˇela v souboji proti jin ´ym robot ˚um. V´ıtˇezem tˇechto simulac´ı byl pak posledn´ı pˇreˇzivˇs´ı.
Obr´azek 3: Aplikace RobotWar
3 Specifikace syst ´emu
3.1 Simulace
Ukolem simulace v aplikaci AI Clash je vyhodnotit a vizu´alnˇe zobrazit pr ˚ubˇeh bitvy na´ z´akladˇe vstupn´ıch dat. Vstupn´ımi daty jsou v tomto pˇr´ıpadˇe jedno bitevn´ı pole, viz ka- pitola 3.2, a pˇr´ısluˇsn ´y poˇcet robot ˚u, viz kapitola 3.2.2, ´uˇcastn´ıc´ıch se kl´an´ı. Uˇzivatel m´a umoˇznˇeno spouˇstˇet simulaci opakovanˇe pro r ˚uzn´a vstupn´ı data, avˇsak po spuˇstˇen´ı si- mulace uˇz nem´a moˇznost jakkoli zas´ahnout a zmˇenit pr ˚ubˇeh jiˇz zapoˇcat´e simulace. M´a vˇsak moˇznost nastavit d´elku simulace pˇred zapoˇcet´ım a v pr ˚ubˇehu simulace dokonce mˇenit rychlost simulace. D´elka simulace je ud´av´ana v cyklech a moˇzn ´ymi hodnotami jsou”500“,
”1 000“,
”2 000“,
”5 000“, ˇci
”10 000“. Rychlost simulace je pak moˇzno nastavit na”Rychl´a“,
”Stˇredn´ı“, nebo
”Pomal´a“, ˇcemuˇz odpov´ıdaj´ı rychlosti 100 cykl ˚u za vteˇrinu, 10 cykl ˚u za vteˇrinu a 1 cyklus za vteˇrinu.
Sn´ımek z pr ˚ubˇehu bitvy je zobrazen na Obr´azku 4.
Obr´azek 4: Aplikace AI Clash
3.2 Bitevn´ı pole
Bitevn´ı pole je m´ısto, na kter´em se odehr´av´a simulace jednotliv ´ych kl´an´ı. Pˇri tvorbˇe bi- tevn´ıho pole m´a uˇzivatel moˇznost zvolit poˇcet robot ˚u, ´uˇcastn´ıc´ıch se kl´an´ı, poˇc´ateˇcn´ı s´ılu robot ˚u a tak´e s´ılu powerball ˚u.
Obr´azek 5: Battlefield Editor
3.2.1 Rozm ˇer, osy a ´uhly
Bitevn´ı pole m´a z nadhledu ˇctvercov ´y tvar o rozmˇerech 400 x 400 pixel ˚u a je po okraj´ıch bezprostˇrednˇe ohraniˇceno nepr ˚uchodn ´ymi a nepr ˚ustˇreln ´ymi zdmi. Osa x bitevn´ıho pole je line´arn´ı, m´a poˇc´atek v lev´em horn´ım rohu a smˇerem vpravo nab ´yv´a kladn ´ych hod- not. Osa y je tak´e line´arn´ı, tak´e m´a poˇc´atek v lev´em horn´ım rohu, avˇsak kladn ´ych hod- not nab ´yv´a ve smˇeru dol ˚u. ´Uhly v t´eto soustavˇe souˇradnic jsou vyj´adˇreny ve stupn´ıch a nab ´yvaj´ı hodnot z intervalu (-180 ; 180i. Pˇri pr´aci s hodnotami mimo tento interval je hodnota automaticky upravov´ana pˇriˇc´ıt´an´ım ˇci odeˇc´ıt´an´ım periody 360◦. ´Uhel 0◦ je ori- entov´an ve smˇeru nahoru, resp. v z´aporn´em smˇeru osy y. ´Uhel 90◦je orientov´an vpravo, resp. v kladn´em smˇeru osy x. ´Uhel tedy roste po smˇeru hodinov ´ych ruˇciˇcek.
3.2.2 Roboti
Roboti jsou z´akladn´ımi bitevn´ımi prvky v poli a pˇri simulaci jsou od sebe navz´ajem odliˇseni barvou. Roboti ´uˇcastn´ıc´ı se kl´an´ı jsou omezeni pohybem pouze v oblasti bi- tevn´ıho pole ohraniˇcen´eho zdmi. Poˇcet robot ˚u, ´uˇcastn´ıc´ıch se kl´an´ı, je volen pˇri tvorbˇe bitevn´ıho pole, viz Obr´azek 5. Uˇzivatel m´a na v ´ybˇer z poˇctu ”2“ a ”4“ robot ˚u a m´a tak´e moˇznost pro dan´e kl´an´ı nastavit s´ılu robota z moˇznost´ı
”50“,
”100“ a
”150“, viz Obr´azek 5. Dalˇs´ı popis robota a jeho vlastnost´ı jsou uvedeny v kapitole 3.3 a odpov´ıdaj´ıc´ıch pod- kapitol´ach.
3.2.3 Powerbally
Powerbally jsou z nadhledu kruhov´e objekty o polomˇeru 10 pixel ˚u, kter´e se objevuj´ı v bi- tevn´ım poli na n´ahodn ´ych pozic´ıch v pr ˚ubˇehu simulace a jeˇz dod´avaj´ı s´ılu robot ˚um. Tyto objekty maj´ı po vytvoˇren´ı pevnˇe danou pozici a d´ale se jiˇz nepohybuj´ı. V nastaven´ı bi- tevn´ıho pole m´a uˇzivatel moˇznost nastavit s´ılu powerball ˚u, viz Obr´azek 5. Na v ´ybˇer jsou moˇznosti
”0“,
”50“ a
”100“ jednotek s´ıly. Pˇri volbˇe
”0“ bude simulace prob´ıhat bez power- ball ˚u. Pokud uˇzivatel vybere jednu z dalˇs´ıch moˇznost´ı, bude pˇri sebr´an´ı powerballu to- muto robotu pˇriˇctena s´ıla dle nastaven´ı.
3.2.4 Stˇrely
Stˇrely jsou kulov´e objekty o polomˇeru 2 pixely a rychlost´ı 10 pixel ˚u za cyklus, kter ´ymi robot ˇskod´ı ostatn´ım robot ˚u. Prvn´ı pˇr´ıpad ukonˇcen´ı existence stˇrely je pˇri stˇretu stˇrely se zd´ı. V takov´em pˇr´ıpadˇe stˇrela jednoduˇse pˇrestane existovat. Druh ´ym pˇr´ıpadem je stˇret 2 stˇrel, ve kter´em obˇe stˇrely pˇrestanou existovat a to bez ohledu na s´ılu jednotliv ´ych stˇrel.
Tˇret´ım a posledn´ım pˇr´ıpadem je stˇret stˇrely s robotem. Tehdy se odeˇcte od s´ıly robota s´ıla stˇrely. Ve vˇsech pˇr´ıpadech nem´a zruˇsen´ı stˇrely ˇz´adn ´y jin ´y n´asledek na okoln´ı objekty, kter´e se stˇrelou nepˇriˇsly do styku, kromˇe pˇr´ıpadn´eho pˇriˇcten´ı bod ˚u robotovi vlastn´ıc´ımu stˇrelu.
3.3 Robot
Robot je z´akladn´ı bojovou jednotkou. Uˇzivatel m´a z hardwarov´e ˇc´asti robota moˇznost nastavit rozmˇer(ˇs´ıˇrka a dosah) radaru, softwarov´a ˇc´ast robota pak d´av´a uˇzivateli povin- nost naprogramovat chov´an´ı robota v jazyce RoboCode, kter ´y je popsan ´y v kapitole 5.
Po ´uspˇeˇsn´em pˇrekladu (kompilaci) je robot pˇripraven ke kl´an´ı.
3.3.1 Stavy
Robot se m ˚uˇze vyskytovat ve tˇrech stavech:
• ˇZiv´y - V tomto stavu je robot schopen vykon´avat libovoln´e akce a je v kaˇzd´em cyklu simulace ocenˇen 2 body.
• Zmrzl ´y - V tomto stavu je robot neschopen akce, avˇsak i pˇresto se st´ale ´uˇcastn´ı kl´an´ı. Je vˇsak v kaˇzd´em cyklu ocenˇen pouze 1 bodem.
• Mrtv ´y - V tomto stavu se robot jiˇz d´ale ne ´uˇcastn´ı kl´an´ı a nen´ı mu tedy pˇripoˇc´ıt´av´ano bodov´e ohodnocen´ı.
3.3.2 Rozm ˇer a rychlost
Robot m´a z nadhledu kruhov ´y tvar o polomˇeru 10 pixel ˚u. Rychlost robota je ud´av´ana v celoˇc´ıseln ´ych hodnot´ach vyjadˇruj´ıc´ıch poˇcet pixel ˚u za cyklus. Tato rychlost se pohybuje v intervaluh-5 ; 5i.
Obr´azek 6: Robot Editor
3.3.3 S´ıla a Energie
S´ıla robota ud´av´a jeho ˇzivotaschopnost v bitvˇe. Pokud robotu klesne hodnota na 0, pak je robot mrtev a d´ale se boje ne ´uˇcastn´ı.
Energie je hodnota, kterou m ˚uˇze robot spotˇrebovat a vyuˇz´ıt ji k pohybu ˇci akci. Tato energie se nav´ıc po kaˇzd´em cyklu nav ´yˇs´ı o 1 jednotku. ´Ubytek energie aˇz na nulovou hodnotu nem´a ˇz´adn ´y omezuj´ıc´ı vliv na robota, avˇsak nen´ı moˇzno pˇri nedostatku energie vyuˇz´ıvat pˇr´ıkaz ˚u, jeˇz energii spotˇrebov´avaj´ı (zmˇena smˇeru pohybu, stˇrelba, apod.).
3.3.4 Radar
Radar slouˇz´ı k prohled´av´an´ı okol´ı. Uˇzivatel m´a na v ´ybˇer 3 moˇznosti nastaven´ı radaru, viz obr.5. Nastaven´ım moˇznosti
”Vˇetˇs´ı ˇs´ıˇrka radaru“ bude ˇs´ıˇrka radaru robota nastavena na 75◦ a dosah na 80 pixel ˚u. Moˇznost
”Vˇetˇs´ı dosah radaru“ nastav´ı ˇs´ıˇrku radaru na 15◦ a dosah na 160 pixel ˚u. V ´ybˇerem stˇredn´ı moˇznosti je pak nastavena ˇs´ıˇrka radaru na 30◦ a dosah na 125 pixel ˚u.
3.3.5 Firmware
Firmware je softwarov´a ˇc´ast robota, obsahuj´ıc´ı pˇrekladaˇcem pˇreloˇzenou uˇzivatelem vytvoˇrenou umˇelou inteligenci robota. Uˇzivatel nejprve naprogramuje chov´an´ı robota v jazyce RoboCode. Zdrojov ´y k ´od v tomto jazyce je n´aslednˇe pˇrekladaˇcem pˇreloˇzen do vnitˇrn´ıho k ´odu (firmware) robota. Tento k ´od je pak v pr ˚ubˇehu simulace interpretov´an.
V´ıce k pˇrekladaˇci a interpreteru v kapitole 6, resp. v kapitole 7.
3.3.6 Registry
Registry jsou m´ısta v pamˇeti robota a slouˇz´ı mu k z´aznamu a vyˇc´ıt´an´ı dat.
4 Cyklus simulace
Cyklus simulace je jednotka pr ˚ubˇehu simulace. Cel´a simulace prob´ıh´a v nˇekolika stovk´ach cykl ˚u (dle nastaven´ı). Kaˇzd ´y cyklus se sest´av´a z n´asleduj´ıc´ıch ˇc´ast´ı:
1. Vygenerov´an´ı powerballu, viz kapitola 4.1.
2. Interpretace robot ˚u, viz kapitola 4.2.
3. Aktualizace polohy objekt ˚u, viz kapitola 4.3.
4. Vyˇreˇsen´ı koliz´ı, viz kapitola 4.4.
5. Aktualizace robot ˚u v kolizi, viz kapitola 4.4.
6. Prvn´ı smaz´an´ı zruˇsen ´ych objekt ˚u, viz kapitola 4.5.
7. Vytvoˇren´ı nov ´ych objekt ˚u, viz kapitola 4.5.
8. Druh´e smaz´an´ı zruˇsen ´ych objekt ˚u, viz kapitola 4.5.
9. Aktualizace s´ıly a energie robot ˚u, viz kapitola 4.6.
10. Nastaven´ı ˇcasu pˇreˇzit´ı a poˇrad´ı robot ˚um, viz kapitola 4.6.
11. Ovˇeˇren´ı ukonˇcen´ı simulace, viz kapitola 4.7.
4.1 Vygenerov ´an´ı powerballu
Powerball je vygenerov´an na n´ahodn´em m´ıstˇe v bitevn´ım poli, pokud jsou splnˇeny n´asleduj´ıc´ı podm´ınky:
• C´ıslo cyklu je rovno 0 nebo n´asobku desetiny d´elky simulace.ˇ
• S´ıla powerballu pˇri tvorbˇe bitevn´ıho pole byla zvolena 50, nebo 100.
• Nebylo dosaˇzeno maxim´aln´ıho poˇctu powerball ˚u v poli. Tento poˇcet je pevnˇe na- staven na 5.
4.2 Interpretace robot ˚u
Interpretace jednotliv ´ych robot ˚u prob´ıh´a postupnˇe, avˇsak akce ovliv ˇnuj´ıc´ı okol´ı jsou ak- tualizov´any aˇz v dalˇs´ıch ˇc´astech cyklu, aby nebyli dˇr´ıve interpretovan´ı roboti zv ´yhodnˇeni oproti n´aslednˇe interpretovan ´ym. Interpretace kaˇzd´eho robota prob´ıh´a v tˇechto kroc´ıch:
1. Pˇriˇcten´ı bod ˚u robotovi dle stavu, ve kter´em se nach´az´ı. Robot ve stavu
”ˇZiv´y“ je ocenˇen 2 body, robot ve stavu
”Zmrzl ´y“ jedn´ım bodem a robot ve stavu
”Mrtv ´y“
nen´ı ocenˇen ˇz´adn ´ym bodem.
2. Pokud je robot
”Zmrzl ´y“ nebo
”Mrtv ´y“, ukonˇc´ı se interpretace tohoto robota a pˇrejde se k interpretaci dalˇs´ıho.
3. Zjiˇstˇen´ı, kolik m´a robot energie. Podle dostupn´e energie bude robotovi pˇri interpre- taci k ´odu povoleno ˇci zak´az´ano prov´adˇet akce spotˇrebov´avaj´ıc´ı energii.
4. V tomto kroku se prov´ad´ı dle rychlosti procesoru robota poˇcet interpretovac´ıch krok ˚u firmwaru robota. Rychlost procesoru kaˇzd´eho robota je pevnˇe nastavena na 20 krok ˚u.
Pˇri interpretaci robot ˚u jsou zachyt´av´any definovan´e i nedefinovan´e v ´yjimky vyvo- lan´e interpreterem firmwaru. Po zachycen´ı libovoln´e v ´yjimky je stav robota zmˇenˇen na ”Zmrzl ´y“. Interpreter firmwaru a j´ım definovan´e v ´yjimky jsou pops´any v kapitole 7.
4.3 Aktualizace polohy objekt ˚u
Aktualizace polohy objektu se t ´yk´a pohybuj´ıc´ıch se objekt ˚u, tedy robot ˚u a stˇrel. Mo- ment´aln´ı pozice je z´alohov´ana a pot´e zmˇenˇena dle smˇeru a rychlosti objektu.
4.4 Vyˇre ˇsen´ı koliz´ı
Jelikoˇz je pˇri vytv´aˇren´ı powerballu v prvn´ım kroku cyklu poˇc´ıt´ano s rozmˇerem bitevn´ıho pole a je ˇreˇsena kolize se st´avaj´ıc´ımi powerbally a jelikoˇz se powerbally nepohybuj´ı, nem ˚uˇze tedy doj´ıt dodateˇcnˇe k jejich vz´ajemn´e kolizi ˇci kolizi se zd´ı, a tak tyto kolize ne- musej´ı b ´yt ˇreˇseny. Avˇsak zb ´yvaj´ıc´ı jednotky v bitevn´ım poli jsou schopn´e pohybu, mus´ı se tedy ˇreˇsit vˇsechny ostatn´ı kolize, kter´e jsou pops´any v n´asleduj´ıc´ıch podkapitol´ach.
Odeˇcten´ı ˇci pˇriˇcten´ı jednotek s´ıly a energie je fakticky provedeno aˇz v ˇc´asti cyklu, kter´a m´a na starosti aktualizaci s´ıly a energie robot ˚u, nikoli ihned pˇri ˇreˇsen´ı koliz´ı. Stejnˇe tak, pokud m´a b ´yt objekt pˇri ˇreˇsen´ı koliz´ı odstranˇen, je pouze pˇriˇrazen do seznamu objekt ˚u urˇcen ´ych ke smaz´an´ı a smaz´an v pozdˇejˇs´ıch kroc´ıch cyklu.
4.4.1 Kolize stˇrely se zd´ı
Pˇri t´eto kolizi je stˇrela pˇriˇrazena do seznamu objekt ˚u urˇcen ´ych ke smaz´an´ı. Zed’ nen´ı nijak poˇskozena.
4.4.2 Kolize robota se zd´ı
Pˇri t´eto kolizi je robotu odeˇcteno 5 jednotek s´ıly a je navr´acen na minulou pozici.
4.4.3 Kolize robota s robotem
Pˇri t´eto kolizi jsou oba roboti pˇrid´ani do seznamu koliduj´ıc´ıch robot ˚u. Tento seznam se proch´az´ı a ˇreˇs´ı aˇz po vyˇreˇsen´ı vˇsech ostatn´ıch koliz´ı a sesb´ır´an´ı vˇsech koliduj´ıc´ıch robot ˚u, aby se pˇredeˇslo zv ´yhodnˇen´ı nˇekter´eho z robot ˚u.
4.4.4 Kolize robota se stˇrelou
Tato kolize je br´ana jako z´asah robota stˇrelou. Robotu je odeˇctena s´ıla rovnaj´ıc´ı se s´ıle stˇrely. Vlastn´ıkovi stˇrely je d´ale pˇriˇcten ke st´avaj´ıc´ım bod ˚um desetin´asobek s´ıly stˇrely.
Nakonec je stˇrela pˇriˇrazena do seznamu objekt ˚u urˇcen ´ych ke smaz´an´ı.
4.4.5 Kolize robota s powerballem
Pˇri t´eto kolizi je robotu pˇrid´ana energie rovnaj´ıc´ı se s´ıle powerballu. Powerball je pot´e pˇrid´an do seznamu objekt ˚u urˇcen ´ych ke smaz´an´ı.
4.4.6 Kolize stˇrely se stˇrelou
Pˇri t´eto kolizi jsou obˇe stˇrely pˇriˇrazeny do seznamu objekt ˚u urˇcen ´ych ke smaz´an´ı. Nen´ı tedy br´an ohled na s´ılu jednotliv ´ych stˇrel.
4.4.7 Kolize stˇrely s powerballem
Tento stˇret nen´ı br´an jako kolize, jelikoˇz pomysln´a v ´yˇska powerballu je n´ıˇze neˇz p´asmo putov´an´ı stˇrel. Stˇrela tedy dan ´y powerball pˇrelet´ı a ke kolizi nedojde, aˇc to tak z nadhledu vypad´a.
4.4.8 Vyˇre ˇsen´ı koliduj´ıc´ıch robot ˚u
Po vyˇreˇsen´ı vˇsech koliz´ı a nalezen´ı vˇsech koliduj´ıc´ıch robot ˚u se pˇristoup´ı k vyˇreˇsen´ı ko- liduj´ıc´ıch robot ˚u. Vˇsem takov ´ymto robot ˚um je odeˇcteno 5 jednotek s´ıly a jsou navr´acen´ı na pˇredchoz´ı pozici.
4.5 Smaz ´an´ı a vytvoˇren´ı objekt ˚u
Tato f´aze se skl´ad´a ze tˇr´ı po sobˇe jdouc´ıch ˇc´ast´ı:
1. Prvn´ı smaz´an´ı zruˇsen ´ych objekt ˚u.
2. Vytvoˇren´ı nov ´ych objekt ˚u.
3. Druh´e smaz´an´ı zruˇsen ´ych objekt ˚u.
4.5.1 Prvn´ı smaz ´an´ı zru ˇsen ´ych objekt ˚u
V t´eto ˇc´asti jsou smaz´any vˇsechny objekty, jeˇz byly v r´amci ˇreˇsen´ı koliz´ı pˇrid´any do se- znamu objekt ˚u urˇcen ´ych ke smaz´an´ı. Tento seznam je po smaz´an´ı objekt ˚u vypr´azdnˇen.
4.5.2 Vytvoˇren´ı nov ´ych objekt ˚u
V t´eto ˇc´asti jsou vytvoˇreny nov´e objekty v bitevn´ım poli. Jelikoˇz v pr ˚ubˇehu kl´an´ı nen´ı moˇzno vytv´aˇret roboty a o tvorbu powerballu se star´a jin´a ˇc´ast cyklu, jedin ´ymi takto vy- tvoˇren ´ymi objekty mohou b ´yt stˇrely. Ty se pˇriˇrazuj´ı do tohoto seznamu pˇri interpretaci firmwaru robot ˚u a vytv´aˇreny jsou aˇz v t´eto ˇc´asti, aby se pˇredeˇslo zv ´yhodnˇen´ı dˇr´ıve in- terpretovan ´ych robotu pˇred pozdˇeji interpretovan ´ymi. Jelikoˇz je moˇzn´e, ˇze pˇri vytv´aˇren´ı tˇechto stˇrel doˇslo k dalˇs´ım koliz´ım, jsou analogicky ke kapitole 4.4, zjiˇstˇeny a ˇreˇseny ko- lize, avˇsak pouze kolize s tˇemito nov ´ymi stˇrelami. Seznam s novˇe vytvoˇren ´ymi objekty je po proveden´ı vypr´azdnˇen.
4.5.3 Druh ´e smaz ´an´ı zru ˇsen ´ych objekt ˚u
V pˇr´ıpadˇe, ˇze pˇri vytv´aˇren´ı nov ´ych objekt ˚u doˇslo ke kolizi ˇci koliz´ım, kter´e si vyˇzaduj´ı smaz´an´ı nˇekter ´ych objekt ˚u, resp. se v seznamu objekt ˚u urˇcen ´ych ke smaz´an´ı vyskytuj´ı dalˇs´ı objekty, jsou tyto objekty smaz´any a seznam vypr´azdnˇen.
4.6 Aktualizace parametr ˚u robot ˚u Tato f´aze prob´ıh´a ve dvou kroc´ıch:
1. Aktualizace s´ıly a energie robot ˚u.
2. Nastaven´ı ˇcasu pˇreˇzit´ı a poˇrad´ı robot ˚um.
4.6.1 Aktualizace s´ıly a energie robot ˚u
V t´eto ˇc´asti se kaˇzd´emu robotovi ´uˇcastn´ıc´ımu se kl´an´ı aktualizuj´ı hodnoty s´ıly a energie.
Pokud s´ıla klesla na hodnotu menˇs´ı nebo rovnu nule je robot oznaˇcen jako ”Mrtv ´y“. S´ıla robota m ˚uˇze nab ´yvat hodnot od 0 do 250. Energie pak od 0 aˇz po aktu´aln´ı hodnotu s´ıly robota.
4.6.2 Nastaven´ı ˇcasu pˇreˇzit´ı a poˇrad´ı robot ˚um Robot ˚um, kteˇr´ı jsou ve stavu
”ˇZiv´y“ nebo
”Zmrzl ´y“, je aktualizov´an ˇcas pˇreˇzit´ı na index prob´ıhan´eho cyklu.
Poˇrad´ı robot ˚u je poˇc´ıt´ano speci´aln´ım algoritmem, viz V ´ypis 1, kter ´y je sestaven na z´akladˇe
”Selection sortu“ berouc´ı v ´uvahu stav robota a poˇcet bod ˚u. Tento algoritmus je sestaven tak, aby upˇrednost ˇnoval aktivn´ı roboty, kteˇr´ı jsou oce ˇnov´ani, kdyˇz jejich stˇrela zas´ahne jin´eho robota a/nebo za rychl´e ukonˇcen´ı simulace zniˇcen´ım ostatn´ıch robot ˚u.
Jsou vˇsak tak´e vyzdvihov´any body i pˇres ´umrt´ı robota. V jist ´ych pˇr´ıpadech m ˚uˇze tedy robot, kter ´y byl v boji dostateˇcnˇe aktivn´ı, ale pˇred ukonˇcen´ım simulace zemˇrel, vyhr´at.
List<Robot>list = robots;
shortn = countOfRobots;
shorti ; shortmax;
shortprize = 1;
for ( i = 0; i <n; i ++) {
max = i;
for (shortj = (short)(i + 1); j <n; j ++) {
if ( list [ j ]. points > list [max].points ||
list [ j ]. points == list [max].points && list [ j ]. status < list [max].status)) {
max = j;
} }
if (max != i) {
Robot tmp = list [ i ];
list [ i ] = list [max];
list [max] = tmp;
}
// ud ˇelen´ı ocen ˇen´ı if ( i == 0) {
list [ i ]. prize = prize ; }
else {
list [ i ]. prize = ( list [ i −1].points == list [ i ]. points && list [ i −1].status == list [ i ].
status) ? prize : ++prize;
} }
V ´ypis 1: Algoritmus oce ˇnuj´ıc´ı roboty.
4.7 Ov ˇeˇren´ı ukon ˇcen´ı simulace
Ukonˇcen´ı simulace probˇehne pˇri splnˇen´ı jak´ekoli z tˇechto podm´ınek:
• Index cyklu je roven d´elce simulace.
• Bitevn´ı pole neobsahuje ani jednoho robota ve stavu
”ˇZiv´y“ a ˇz´adn´e stˇrely.
• Bitevn´ı pole obsahuje jedin´eho robota ve stavu
”ˇZiv´y“, ˇz´adn´eho robota ve stavu
”Zmrzl ´y“ a ˇz´adn´e stˇrely.
V pˇr´ıpadˇe, ˇze je simulace ukonˇcena pˇred dosaˇzen´ım ´upln´e d´elky simulace, tedy v pˇr´ıpadˇe splnˇen´ı 2. ˇci 3. podm´ınky, jsou robot ˚um, kter´e nejsou ve stavu
”Mrtv ´y“
pˇripoˇc´ıt´any body za neprobˇehnut´e cykly. Robotu ve stavu ”ˇZiv´y“ je k dosavadn´ım bod ˚um pˇripoˇcten dvojn´asobek poˇctu zb ´yvaj´ıc´ıch cykl ˚u, robot ˚um, ve stavu
”Zmrzl ´y“ je k dosavadn´ım bod ˚um pˇripoˇcten poˇcet zb ´yvaj´ıc´ıch cykl ˚u.
5 Jazyk RoboCode
Jazyk RoboCode je speci´alnˇe navrˇzen ´y jazyk vych´azej´ıc´ı z jazyka RoboTalk, avˇsak nen´ı s n´ım zpˇetnˇe kompatibiln´ı, jelikoˇz je pˇrizp ˚usoben pro syst´em v aplikaci AI Clash. Robo- Code je z´asobn´ıkov ´ym programovac´ım jazykem dodrˇzuj´ıc´ım postfixovou notaci, nebo t´eˇz RPN. Jazyk je navrˇzen tak, aby byl co nejsnadnˇejˇs´ı k pochopen´ı uˇzivatelem, co nejjed- noduˇsˇs´ı pro interpretaci a pˇritom dostateˇcnˇe rychl ´y.
Tento jazyk slouˇz´ı k naprogramov´an´ı umˇel´e inteligence robota a skl´ad´a se ze jm´ena robota, koment´aˇr ˚u, ˇc´ısel, label ˚u, registr ˚u, instrukc´ı a oddˇelovaˇc ˚u. RoboCode nen´ı case- sensitive, takˇze je na uˇzivateli, zda bude k ´od ps´at pouze mal ´ymi znaky, pouze velk ´ymi znaky, nebo bude pouˇz´ıvat libovolnou kombinaci mal ´ych a velk ´ych znak ˚u.
Z´asobn´ık Z´asobn´ık slouˇz´ı k doˇcasn´emu ukl´ad´an´ı dat a pracuje s daty tak, ˇze data uloˇzen´a jako posledn´ı budou ze z´asobn´ıku vyˇctena jako prvn´ı. Uk´azka manipu- lace s daty v z´asobn´ıku je pops´ana Tabulce 1. Tato uk´azka pracuje s matematickmi instrukcemi, jenˇz jsou pops´any v Tabulce 2.
Vstup Z´asobn´ık
5 5
20 5 20
+ 25
-1 25 -1
7 25 -1 7
45 25 -1 7 45
sin 25 -1 5
* 25 -5
abs 25 5
/ 5
Tabulka 1: Z´asobn´ık
5.1 Jm ´eno robota
Jm´eno robota je voliteln´e. Pokud je vypl ˇnov´ano, mus´ı b ´yt um´ıstˇeno na prvn´ım ˇr´adku k ´odu v hranat ´ych z´avork´ach bez dalˇs´ıho k ´odu v ˇr´adku.
5.2 Koment ´aˇre
Koment´aˇre slouˇz´ı uˇzivateli k z´aznamu nejr ˚uznˇejˇs´ıch pozn´amek pˇr´ımo do k ´odu. Zaˇc´ınaj´ı znakem
”#“ a jsou ukonˇceny koncem ˇr´adku.
5.3 C´ıslaˇ
C´ısla v RoboCodu jsou celoˇc´ıseln´a ˇc´ısla z intervaluˇ h-29 999 ; 29 999i. Je povoleno bez- prostˇrednˇe pˇred ˇc´ıslem pouˇz´ıt znam´enka kladu a z´aporu,
”+“ resp.
”-“.
5.4 Label
Labely jsou textov´e ˇst´ıtky slouˇz´ıc´ı jako reference k m´ıstu k ´odu o maxim´aln´ı d´elce 30 znak ˚u. Skl´adaj´ı se ze 2 typ ˚u: reference a odkaz. Oboj´ı se skl´ad´a ze stejn ´ych znak ˚u, avˇsak reference je zakonˇcena znakem”:“.
5.5 Registry
Registry jsou virtu´aln´ı m´ısta v pamˇeti robota, jeˇz dovoluj´ı uˇzivateli vyˇc´ıtat ˇci ukl´adat hodnoty. Registry Angle, Speed a uˇzivatelsk´e registry jsou urˇceny ke ˇcten´ı i z´apisu. Re- gistry X, Y, Power, Energy, Radar, RobotOnRadar, PowerballOnRadar, AngleToClosest, AngleToClosestRobot, AngleToClosestPowerball, Collision, Hit, AngleToHit jsou urˇceny pouze ke ˇcten´ı. Registr Shoot pak slouˇz´ı pouze pro z´apis.
Registr Angle urˇcuje ´uhel smˇeru, ve kter´em je robot natoˇcen. Je ud´av´an ve stupn´ıch v in- tervalu ( -180 ; 180i. Pˇri z´apisu do tohoto registru je robotu nastaven smˇer dan ´y nastavovanou hodnotou. To je ale provedeno pouze v pˇr´ıpadˇe, ˇze m´a robot do- stateˇcnou energii na tento ´ukon. Potˇrebn´a energie se vypoˇc´ıt´av´a z tohoto vzorce:
energy = (speed+ 1)∗(change)
9 ;
kde ”energy“ je potˇrebn´a energie,
”speed“ je rychlost robota a
”change“ je delta zmˇeny smˇeru robota.
Registr Speed obsahuje hodnotu velikosti rychlosti pohybu robota. Povoleno je nastavo- vat rychlost z intervaluh-5 ; 5i. Pˇri nastaven´ı hodnoty menˇs´ı neˇz -5, resp. vˇetˇs´ı neˇz 5, bude hodnota nastavena na -5, resp. 5. Dan´a rychlost se vˇsak nastav´ı pouze tehdy, m´a-li robot dostatek energie. Potˇrebn´a energie je rovna velikosti zmˇeny rychlosti.
Pokud m´a tedy robot aktu´aln´ı rychlost 2 pixely za vteˇrinu a nastavov´ana je rychlost 5 pixel ˚u za vteˇrinu, je zmˇena rovna 3 a je tedy potˇreba 3 jednotek energie.
Registr Shoot slouˇz´ı ke stˇrelbˇe. Z´apis do tohoto registru zp ˚usob´ı stˇrelu o s´ıle zapsan´e hodnoty, avˇsak pouze v pˇr´ıpadˇe, ˇze m´a robot energii rovnu zapsan´e hodnotˇe.
Zasaˇzen´emu robotu se odeˇcte tato hodnota od v ´ykonu. I kdyˇz tento registr slouˇz´ı pouze pro z´apis, je moˇzno z tohoto registru tak´e ˇc´ıst, avˇsak n´avratov´a hodnota je vˇzdy”0“.
Registr X vrac´ı x-ovou pozici robota vzhledem k bitevn´ımu poli.
Registr Y vrac´ı y-ovou pozici robota vzhledem k bitevn´ımu poli.
Registr Power vrac´ı hodnotu s´ıly robota.
Registr Energy vrac´ı hodnotu energie robota.
Registr Radar vrac´ı
”1“, pokud se na radaru nach´az´ı jin ´y robot ˇci powerball. V opaˇcn´em pˇr´ıpadˇe vrac´ı
”0“.
Registr RobotOnRadar vrac´ı
”1“ pokud se na radaru nach´az´ı jin ´y robot. V opaˇcn´em pˇr´ıpadˇe vrac´ı
”0“.
Registr PowerballOnRadar vrac´ı
”1“ pokud se na radaru nach´az´ı powerball.
V opaˇcn´em pˇr´ıpadˇe vrac´ı
”0“.
Registr AngleToClosest vrac´ı ´uhel k nejbliˇzˇs´ımu objektu (robot nebo powerball) na ra- daru. V pˇr´ıpadˇe, ˇze na radaru ˇz´adn ´y objekt nen´ı, je vr´acena
”0“.
Registr AngleToClosestRobot vrac´ı ´uhel k nejbliˇzˇs´ımu robotovi na radaru. V pˇr´ıpadˇe, ˇze na radaru ˇz´adn ´y robot nen´ı, je vr´acena ”0“.
Registr AngleToClosestPowerball vrac´ı ´uhel k nejbliˇzˇs´ımu powerballu na radaru.
V pˇr´ıpadˇe, ˇze na radaru ˇz´adn ´y powerball nen´ı, je vr´acena
”0“.
Registr Collisions vrac´ı
”1“ v pˇr´ıpadˇe, ˇze je robot v kolizi s jin ´ym robotem. V opaˇcn´em pˇr´ıpadˇe vrac´ı”0“.
Registr Hit vrac´ı
”1“ v pˇr´ıpadˇe, ˇze byl robot zasaˇzen nˇekdy v pr ˚ubˇehu posledn´ıch 5 cykl ˚u. V opaˇcn´em pˇr´ıpadˇe je vr´acena”0“.
Registr AngleToHit vrac´ı ´uhel ke stˇrele v okamˇziku z´asahu.
Uˇzivatelsk´e registry jsou registry, jeˇz slouˇz´ı uˇzivateli k ukl´ad´an´ı hodnot. Tˇechto registr ˚u je 64 a maj´ı pevnˇe dan´e n´azvy skl´adaj´ıc´ı se z pˇeti znak ˚u. Prvn´ı tˇri znaky jsou
”reg“
a zb ´yvaj´ıc´ı dva znaky oznaˇcuj´ı dvojcifern´e ˇc´ıslo v hexadecim´aln´ı soustavˇe v roz- mez´ı
”00“ -
”3F“. Pˇr´ıklady n´azv ˚u takov ´ych registr ˚u jsou tedy
”reg00“,
”reg1B“, ˇci
”reg33“.
5.6 Instrukce
Instrukce slouˇz´ı jako pˇr´ıkaz pro interpreter k vykon´an´ı urˇcit´e operace. RoboCode obsa- huje celkem 37 instrukc´ı, matematick´e jsou pops´any v Tabulce 2, logick´e v Tabulce 3, ˇr´ıd´ıc´ı a ostatn´ı instrukce pak v Tabulce 4.
5.7 Odd ˇelova ˇce
Jako oddˇelovaˇce mezi str´ankami slouˇz´ı znaky:
”mezera“
”tabul´ator“
”nov ´y ˇr´adek“.
Poˇcet hodnot
Instrukce vstup v ´ystup Popis
+ 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a souˇcet uloˇz´ı zpˇet.
- 2 1 Vyˇcte 2 hodnotyAa B ze z´asobn´ıku a rozd´ıl Ba A uloˇz´ı zpˇet.
* 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a souˇcin uloˇz´ı zpˇet.
/ 2 1 Vyˇcte 2 hodnoty A a B ze z´asobn´ıku a pod´ıl B a A uloˇz´ı zpˇet.
% 2 1 Vyˇcte 2 hodnoty A a B ze z´asobn´ıku a zbytek
po celoˇc´ıseln´em dˇelen´ıBbAuloˇz´ı zpˇet.
abs 1 1 Vyˇcte hodnotu ze z´asobn´ıku a jej´ı absolutn´ı hodnotu uloˇz´ı zpˇet.
sqr 1 1 Vyˇcte hodnotu ze z´asobn´ıku a jej´ı druhou mocninu uloˇz´ı zpˇet.
sqrt 1 1 Vyˇcte hodnotu ze z´asobn´ıku a jej´ı druhou odmocninu uloˇz´ı zpˇet.
sin 2 1 Vyˇcte 2 hodnotyAaBze z´asobn´ıku a souˇcinBa si- nus(A) uloˇz´ı zpˇet.
cos 2 1 Vyˇcte 2 hodnotyAaBze z´asobn´ıku a souˇcinBa co- sinus(A) uloˇz´ı zpˇet.
tg 2 1 Vyˇcte 2 hodnotyAaBze z´asobn´ıku a souˇcin
tan Ba tangens(A) uloˇz´ı zpˇet.
Tabulka 2: Matematick´e instrukce
Poˇcet hodnot
Instrukce vstup v ´ystup Popis
= 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a pokud jsou si rovny, uloˇz´ı zpˇet”1“, jinak”0“.
!= 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a pokud si nejsou
<> rovny, uloˇz´ı zpˇet
”1“, jinak
”0“.
> 2 1 Vyˇcte 2 hodnotyAaBze z´asobn´ıku a pokud jeBvˇetˇs´ı neˇzA, uloˇz´ı zpˇet
”1“, jinak
”0“.
< 2 1 Vyˇcte 2 hodnoty A a B ze z´asobn´ıku a pokud je B menˇs´ı neˇzA, uloˇz´ı zpˇet
”1“, jinak
”0“.
>= 2 1 Vyˇcte 2 hodnotyAaBze z´asobn´ıku a pokud jeBvˇetˇs´ı
nebo rovnoA, uloˇz´ı zpˇet”1“, jinak”0“.
<= 2 1 Vyˇcte 2 hodnoty A a B ze z´asobn´ıku a pokud je B
menˇs´ı nebo rovnoA, uloˇz´ı zpˇet ”1“, jinak ”0“.
not 2 1 Vyˇcte hodnotu ze z´asobn´ıku a pokud je nenulov´a, uloˇz´ı zpˇet
”0“, jinak
”1“.
and 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a pokud jsou obˇe ne- nulov´e, uloˇz´ı zpˇet
”1“, jinak
”0“.
or 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a pokud je alespo ˇn jedna nenulov´a, uloˇz´ı zpˇet
”1“, jinak
”0“.
nor 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a pokud nen´ı alespo ˇn jedna nenulov´a, uloˇz´ı zpˇet”1“, jinak ”0“.
xor 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a pokud je pr´avˇe jedna nenulov´a, uloˇz´ı zpˇet
”1“, jinak
”0“.
xnor 2 1 Vyˇcte 2 hodnoty ze z´asobn´ıku a pokud nen´ı pr´avˇe jedna nenulov´a, uloˇz´ı zpˇet
”1“, jinak
”0“.
Tabulka 3: Logick´e instrukce
Poˇcet hodnot
Instrukce vstup v ´ystup Popis
if 2 0 Vyˇcte labelAa hodnotuBze z´asobn´ıku a pokud jeB nenulov´e zavol´a m´ısto odpov´ıdaj´ıc´ı labeluA.
ifg 2 0 Vyˇcte labelAa hodnotuBze z´asobn´ıku a pokud je ifgo Bnenulov´e pˇrejde na m´ısto odpov´ıdaj´ıc´ı labeluA.
ife 3 0 Vyˇcte labelyAaBa hodnotuCze z´asobn´ıku a pokud ifelse jeCnenulov´e zavol´a m´ısto odpov´ıdaj´ıc´ı labeluB, ji-
nak zavol´a m´ısto odpov´ıdaj´ıc´ı labeluA.
ifeg 3 0 Vyˇcte labelyAaBa hodnotuCze z´asobn´ıku a pokud ifelsego jeCnenulov´e pˇrejde na m´ısto ve fimwaru labeluB,
jinak na m´ısto odpov´ıdaj´ıc´ı labeluA.
jump 1 0 Vyˇcte label ze z´asobn´ıku pˇrejde na m´ısto odpov´ıdaj´ıc´ı labelu.
call 1 0 Vyˇcte label ze z´asobn´ıku zavol´a m´ısto odpov´ıdaj´ıc´ı labelu.
ret 0 0 Vykon´av´an´ı firmwaru se vr´at´ı na m´ısto odkud bylo naposledy zavol´ano.
set 2 0 Vyˇcte registrAa hodnotuBze z´asobn´ıku a uloˇz´ı
store hodnotuBdo registruA.
drop 1 0 Vyˇcte hodnotu ze z´asobn´ıku a zahod´ı ji.
dup 1 2 Vyˇcte hodnotu ze z´asobn´ıku a uloˇz´ı ji zpˇet dvakr´at.
duplicate
swap 2 2 Vyˇcte hodnoty A a B ze z´asobn´ıku a zpˇet uloˇz´ı nejdˇr´ıveAa pot´e B, ˇc´ımˇz tyto hodnoty v z´asobn´ıku pˇrehod´ı.
sync 0 0 Instrukce spotˇrebuje veˇsker´e interpretaˇcn´ı kroky ro- bota pro pr´avˇe prob´ıhaj´ıc´ı cyklus simulace.
nop 0 0 Pr´azdn´a instrukce spotˇrebov´avaj´ıc´ı pr´avˇe jeden inter- pretaˇcn´ı krok.
Tabulka 4: ˇR´ıd´ıc´ı a ostatn´ı instrukce
6 Pˇreklada ˇc
Pˇrekladaˇc (Compiler) je tˇr´ıda urˇcen´a k pˇrekladu (Vyskoˇcil, 2006) zdrojov´eho k ´odu v Ro- boCodu umˇel´e inteligence robota do vnitˇrn´ıho k ´odu (Firmware) robota, jeˇz je srozumi- teln ´y pro interpretov´an´ı chov´an´ı robota interpreterem v pr ˚ubˇehu kl´an´ı. Tˇr´ıda Compiler pouˇz´ıva tˇr´ıdu Tokenizer, jeˇz slouˇz´ı k lexik´aln´ı anal ´yze. Samotn´a pˇrekladaˇc m´a pak na sta- rosti syntaktickou anal ´yzu a pˇreklad do firmwaru.
6.1 Tˇr´ıda Tokenizer
Tˇr´ıda Tokenizer, jak uˇz bylo ˇreˇceno v ´yˇse, slouˇz´ı k pˇrevodu zdrojov´eho k ´odu v jazyce RoboCode na tokeny. Pro bliˇzˇs´ı pˇredstavu V ´ypis 2 pˇredstavuje uk´azku k ´odu, jeˇz se bude v pr ˚ubˇehu pˇrekladu po jednotliv ´ych anal ´yz´ach mˇenit.
[Small Circle Robot]
# zaˇc ´atek start :
speed 3 + speed store
# ot ´aˇcen´ı o 45 stup ˇn ˚u turn :
0 reg00 store
angle 45 + angle store
# kontrola radaru wait :
radar shooting ifg sync
reg00 1 + reg00 store reg00 10<= wait turn ifeg
# stˇrelba shooting:
5 shoot store sync
wait jump
V ´ypis 2: Pˇr´ıklad k ´odu v jazyce RoboCode
6.1.1 Pr ˚ub ˇeh lexik ´aln´ı anal ´yzy
Vstupem tokenizeru je text v jazyce RoboCode, kter ´y je podroben tˇemto krok ˚um:
1. Odstranˇen´ı koment´aˇr ˚u z textu.
2. Vyˇcten´ı jm´ena robota z hranat ´ych uvozovek z prvn´ıho ˇr´adku. V pˇr´ıpadˇe, ˇze robot nem´a uvedeno jm´eno, je pojmenov´an ”Unnamed“.
3. Parsov´an´ım vytvoˇren´ı pole lex´em ˚u z textu.
Pokud v pr ˚ubˇehu tohoto procesu doˇslo k vyvol´an´ı v ´yjimky, je tato v ´yjimka odchytnuta.
6.1.2 V ´yjimky
V ´yjimky definovan´e ve tˇr´ıdˇe Tokenizer jsou typu TokenizerException. V pˇr´ıpadˇe, ˇze je vyvol´ana nˇekter´a z definovan ´ych ˇci nedefinovan ´ych v ´yjimek, je text t´eto v ´yjimky zobra- zen uˇzivateli v oknˇe se zpr´avou. Definovan´e v ´yjimky:
Jm´eno robota m´a ˇspatn ´y form´at. Tato v ´yjimka je vyvol´ana v pˇr´ıpadˇe, ˇze se nˇekde na prvn´ım ˇr´adku textu sice nach´az´ı znak
”[“, avˇsak bud’ nen´ı na prvn´ı pozici v tomto ˇr´adku a/nebo na posledn´ı pozici nen´ı”]“.
Jm´eno robota nen´ı vyplnˇeno. Tato v ´yjimka je vyvol´ana v pˇr´ıpadˇe, ˇze jsou sice prvn´ım a posledn´ım znakem na ˇr´adku
”[“ resp.
”]“, avˇsak m´ısto mezi nimi neobsahuje text.
start : speed 3 + speed store turn: 0 reg00 store angle 45 + angle store wait : radar shooting ifg sync reg00 1 + reg00 store reg00 10<= wait turn
ifeg shooting: 5 shoot store sync wait jump
V ´ypis 3: Seznam lex´em ˚u po lexik´aln´ı anal ´yze odˇr´adkovan ´y po deseti
6.2 Tˇr´ıda Compiler
Tˇr´ıda Compiler prov´ad´ı pˇreklad z tokenizerem rozparsovan´eho RoboCodu do posloup- nosti celoˇc´ıseln ´ych k ´od ˚u, jenˇz je po pˇrekladu vr´acena do firmwaru robota.
6.2.1 Pr ˚ub ˇeh syntaktick ´e anal ´yzy a pˇrekladu do firmwaru
Po lexik´aln´ı anal ´yze, o kterou se postaral tokenizer, pˇrich´az´ı na ˇradu syntaktick´a anal ´yza a pˇreklad do firmwaru. Oba kroky prob´ıhaj´ı z´arove ˇn v tomto sledu:
1. Pro kaˇzd ´y token se provede:
(a) Ovˇeˇren´ı, zda je token ˇc´ıslo. Pokud ano, a je v povolen´em rozmez´ı, pˇrev´est token na ˇc´ıslo a pˇrej´ıt na dalˇs´ı token.
(b) Ovˇeˇren´ı, zda je tokel label. Pokud ano, pˇridat do seznamu label ˚u, vyˇreˇsit od- kazy na tento label a pˇrej´ıt na dalˇs´ı token.
(c) Ovˇeˇren´ı, zda je token registr. Pokud ano, pˇrev´est token na k ´od registru a pˇrej´ıt na dalˇs´ı token.
(d) Ovˇeˇren´ı, zda je token odkaz na label. Pokud ano, dosadit pozici labelu a pˇrej´ıt na dalˇs´ı token.
(e) Ovˇeˇren´ı, zda je token oper´ator:
• Pokud ano, je token nahrazen k ´odem odpov´ıdaj´ıc´ım operaci.
• Pokud ne, pak je nutno povaˇzovat token za doposud nevyˇreˇsen ´y label a nahradit token k ´odem oznaˇcuj´ıc´ım nevyˇreˇsen ´y label.
2. Ovˇeˇren´ı, zda k ´od neobsahuje nevyˇreˇsen ´y label.
Pokud v pr ˚ubˇehu tohoto procesu doˇslo k vyvol´an´ı v ´yjimky, je tato v ´yjimka odchytnuta.
6.2.2 V ´yjimky
V ´yjimky definovan´e ve tˇr´ıdˇe Compiler jsou typu CompilerException. V pˇr´ıpadˇe, ˇze je vy- vol´ana nˇekter´a z definovan ´ych ˇci nedefinovan ´ych v ´yjimek, je text t´eto v ´yjimky zobrazen uˇzivateli v oknˇe se zpr´avou. Definovan´e v ´yjimky:
Pˇr´ıliˇs kr´atk ´y robocode. Tato v ´yjimka je vyvol´ana v pˇr´ıpadˇe, ˇze d´elka textu po lexik´aln´ı anal ´yze je rovna nule.
Byla pˇrekroˇcena celkov´a kapacita firmwaru. Tato v ´yjimka je vyvol´ana v pˇr´ıpadˇe, kdy byla dosaˇzena maxim´aln´ı kapacita firmwaru a chceme pˇridat dalˇs´ı k ´od do firm- waru.
C´ıslo je mimo povolen ´y rozsah.ˇ Tato v ´yjimka je vyvol´ana v pˇr´ıpadˇe, kdy je token roz- pozn´an jako ˇc´ıslo, avˇsak nen´ı v povolen´em rozsahu.
Label je pˇr´ıliˇs dlouh ´y. Tato v ´yjimka je vyvol´ana v pˇr´ıpadˇe, ˇze n´azev labelu je pˇr´ıliˇs dlouh ´y.
Token nen´ı kl´ıˇcov´e slovo, label, ani registr. Tato v ´yjimka je vyvol´ana v posledn´ı ˇc´asti pˇrekladu, kdy se ovˇeˇruje, zda se ve firmwaru nal´ez´a nevyˇreˇsen ´y label.
30501 3 30000 30501 30028 0 32000 30028 30500 45 30000 30500 30028 31004 28 30026 30035 32000 1 30000 32000 30028 32000 10 30020 13 5 30027 5 30502
30028 30035 13 30032
V ´ypis 4: Seznam k ´od ˚u firmwaru po pˇrekladu odˇr´adkovan ´y po deseti
7 Interpreter
Interpreter firmwaru slouˇz´ı k interpretaci k ´odu pˇreloˇzen´eho pˇrekladaˇcem z k ´odu v jazyce RoboCode. Neinterpretuje tedy pˇr´ımo RoboCode k ´od. Interpreter pracuje po kroc´ıch a to tak, ˇze v kaˇzd´em kroku zpracuje jednu poloˇzku z k ´odu firmwaru.
7.1 Counter, Stack a CallStack 7.1.1 Counter
Counter je ukazatel na konkr´etn´ı m´ısto ve firmwaru a slouˇz´ı k ˇr´ızen ´ym odskok ˚um v r´amci firmwaru.
7.1.2 Stack
Stack je hlavn´ım z´asobn´ıkem interpreteru, do kter´eho se pˇri interpretaci firmwaru ukl´adaj´ı hodnoty. Stack je omezen na 1024 poloˇzek.
7.1.3 CallStack
CallStack je vedlejˇs´ım z´asobn´ıkem interpreteru a slouˇz´ı k uchov´av´an´ı index ˚u ukazatele pˇri vol´an´ı podprogramu. CallStack je omezen na 512 poloˇzek.
7.2 Krok interpretace
Kaˇzd ´y krok interpretace se sest´av´a z n´asleduj´ıc´ıho postupu:
1. Ovˇeˇren´ı pozice ukazatele.
2. Vyˇcten´ı k ´odu.
3. Ovˇeˇren´ı, zda je k ´od ˇc´ıslo.
4. Ovˇeˇren´ı, zda je k ´od registr.
5. Ovˇeˇren´ı, zda je k ´od operace.
7.2.1 Ov ˇeˇren´ı pozice ukazatele
V t´eto ˇc´asti se ovˇeˇr´ı, zda ukazatel ukazuje st´ale na m´ısto ve firmwaru. Pokud ne, je vy- vol´ana InterpreterException v ´yjimka
”Skonˇcila interpretace robota“.
7.2.2 Vy ˇcten´ı k ´odu
Do odpov´ıdaj´ıc´ı promˇenn´e je vyˇcten k ´od z firmwaru, nach´azej´ıc´ı se na pozici, kam odka- zuje ukazatel.
7.2.3 Ov ˇeˇren´ı, zda je k ´od ˇc´ıslo
V tomto kroku se ovˇeˇr´ı, zda je k ´od ˇc´ıslo. Pokud ano, n´aslednˇe se provede uloˇzen´ı k ´odu do Stacku. Pokud byl vˇsak Stack pln ´y, je vyvol´ana InterpreterException v ´yjimka
”Z´asobn´ık je pln ´y“.
7.2.4 Ov ˇeˇren´ı, zda je k ´od registr
Zde se ovˇeˇr´ı, zda k ´od odpov´ıd´a nˇekter´emu z registr ˚u. Pokud ano, je n´aslednˇe provedeno uloˇzen´ı tohoto k ´odu do Stacku, opˇet s ovˇeˇren´ım kapacity Stacku a pˇr´ıpadn ´ym vyvol´an´ım v ´yjimky.
7.2.5 Ov ˇeˇren´ı, zda je k ´od operace
V pˇr´ıpadˇe, ˇze k ´od odpov´ıd´a k ´odu nˇekter´e z operac´ı, provede se pˇr´ısluˇsn´a operace.
Uk´azka zdrojov´eho k ´odu operace If (z´akladn´ı podm´ınka) je vidˇet na V ´ypisu 5.
private int opIf () {
shorttmp1 = stack.Pop();
shorttmp2 = stack.Pop();
tmp2 = readNumberOrLoadRegister(”If”, tmp2);
if (tmp2 != 0) {
if (isInFirmware(tmp1)) {
if (callStack .Count == CALLSTACK SIZE) {
throw newOperationException(”If”, ”CallStack je pln´y.”) ; }
callStack .Push(counter);
counter = tmp1;
} else {
throw newOperationException(”If”, ”Skok odkazuje mimo firmware.”);
} } return1;
}
V ´ypis 5: Zdrojov ´y k ´od operace If
7.3 V ´yjimky
Interpreter m´a 2 typy definovan ´ych v ´yjimek: InterpreterException a OperationException.
7.3.1 InterpreterException
Tento typ v ´yjimky je vyvol´an, pokud nastane jedna z n´asleduj´ıc´ıch situac´ı:
• Skonˇcila interpretace robota.
• Z´asobn´ık je pln ´y.
7.3.2 OperationException
V ´yjimka OperationException je vyvol´ana, pokud nastane chyba v prov´adˇen´ı nˇekter´e z operac´ı. Tyto chyby jsou:
• V ´ysledek je mimo rozsah.
• Tangens z ´uhlu 90 nebo 270 nelze vypoˇc´ıtat.
• Z´asobn´ık je pln ´y.
• CallStack je pln ´y.
• CallStack je pr´azdn ´y.
• Skok odkazuje mimo firmware.
• Ukl´ad´an´ı do read-only registru.
• Ukl´ad´an´ı mimo registry.
• V registru nen´ı ˇc´ıslo.
• C´ıslo nen´ı v rozsahu ˇc´ısel.ˇ
8 Z ´av ˇer
V ´ysledkem t´eto pr´ace je plnˇe funkˇcn´ı simul´ator bitev robot ˚u AI Clash, kter ´y pouˇz´ıv´a vlastn´ı specificky navrˇzen ´y jazyk RoboCode, aby interpretoval chov´an´ı robot ˚u v bitvˇe.
Implementaci tohoto simul´atoru jsem si zvolil hlavnˇe proto, abych si osvojil pravidla a postupy pˇri implementaci pˇrekladaˇc ˚u a interpreter ˚u. Nav´ıc se mi tato pr´ace zd´ala zaj´ımav´a jak po implementaˇcn´ı, tak po vizu´aln´ı str´ance.V pr ˚ubˇehu implementace jsem pˇrich´azel na r ˚uzn´a dalˇs´ı vylepˇsen´ı, jenˇz souvisela se simulac´ı, a kter´a p ˚uvodnˇe nebyla pl´anov´ana. Nˇekter´a z nich byla jiˇz implementov´ana, jin´a budou dodˇel´ana v budoucnu.
Pˇri implementov´an´ı simul´atoru jsem si postupem ˇcasu osvojil dovednosti souvisej´ıc´ı s nejnovˇejˇs´ımi verzemi jazyka C# a technologii .NET, kter´e mi jistˇe poslouˇz´ı pˇri progra- mov´an´ı dalˇs´ıch prac´ı.
8.1 Pl ´anovan ´a vylep ˇsen´ı
I kdyˇz jsem si postupem ˇcasu postfixovou notaci osvojil, pro nˇekter´e uˇzivatele by toto mohlo b ´yt pˇrek´aˇzkou a tak je m ´ym c´ılem do budoucna pro umˇelou inteligence robota vytvoˇrit jeˇstˇe druh ´y jazyk, kter ´y by mˇel jin´a pravidla a mohl by pˇr´ıpadnˇe uˇzivatel ˚um jeˇstˇe v´ıce vyj´ıt vstˇr´ıc pˇri programov´an´ı chov´an´ı robota.
V pr ˚ubˇehu ukonˇcov´an´ı pr´ace mˇe tak´e napadlo, ˇze by kolize, ˇci jin´e stavy nast´avaj´ıc´ı v simulaci mohly u robota vyvol´avat vyvol´an´ı v ´yjimky a tedy by se v tom pˇr´ıpadˇe za- volala jin´a ˇc´ast k ´odu bez ohledu na pr´avˇe prov´adˇenou. Uˇzivatel by pak mohl zvolit, zda chce odchyt´avat tyto v ´yjimky, ˇci je ignorovat a zjiˇst’ovat stavy v simulaci pomoc´ı registr ˚u.
Posledn´ım z´asadn´ım pl´anem je zmˇena zapoˇc´ıt´av´an´ı bod ˚u a ocenˇen´ı robot ˚u. Dosud je tento v ´ypoˇcet zaloˇzen na m´em odhadu a ´usudku, kter´e situace vyzdvihovat a bodovat je tedy v´ıce a kter´e se naopak snaˇzit potlaˇcit. Tyto v ´ypoˇcty budou v budocnu upravov´any na z´akladˇe zpˇetn´e vazby uˇzivatel ˚u, po nasazen´ı aplikace a po mnoha testov´an´ıch.
Tom´aˇs Worek
9 Reference
[1] METCALF, John,Darwin: Survival of the Fittest among Programs[online], Posledn´ı aktualizace 27.1.2011a 13:40,
Dostupn´e na WWW:<http://corewar.co.uk/darwin/>
[2] METCALF, John,RobotWar: the Battlefield of the Future[online], Posledn´ı aktualizace 27.1.2011b 13:46,
Dostupn´e na WWW:<http://corewar.co.uk/robotwar/>
[3] JONES, D. G.; DEWDNEY, A. K.,Core War Guidelines[online], Posledn´ı aktualizace 5.2.2006 18:00,
Dostupn´e na WWW:<http://corewar.co.uk/cwg.txt>, 1984 [4] VYSKO ˇCIL, Michal,Seri´al: Jazyky a pˇrekladaˇce[online],
<http://www.abclinuxu.cz/serialy/jazyky-a-prekladace>, 2006
