Programování a vývoj SWNěco málo o programování a světě vývojářů

Jak jsem řešil Saboteura 2

Publikováno 23.04.2017 v 13:43 v kategorii Výzvy, přečteno: 290x

Klasická hra z r. 1987 jako pokračování slavné jedničky je oproti hrám podobného druhu i proti svému předchůdci něco zcela jiného. Ale nepředbíhejme, zkusím to osvětlit od začátku.

Na počátku celého příběhu je hra Saboteur 1 z r. 1986, známá asi nejvíce z platformy ZX Spectrum. Klasická ninjovská arkáda, kde jste museli v ne příliš rozlehlém domě najít disk, umístit bombu a uletět pryč vrtulníkem. Na cestě byla spousta nepřátel - včetně čtyřnohých -, což se ovšem dalo za pomoci drobného repertoáru hmatů a chvatů vyřešit.

O rok později se od firmy Durell Software a autora Clive Townsenda objevilo na platformu ZX Spectrum volné pokračování s názvem Saboteur II - Avenging Angel. Jak z názvu vyplývá, jednalo se o ninju-saboteurku, jemnou a zároveň ostrou to ženu, která před sebou měla nepoměrně náročnější úkol než její mužský předchůdce.

Dům je mnohokráte větší, má i rozsáhlé podzemní prostory, zahrady, skladiště, tajné místnosti, raketu, stožáry či výtahy. Ale úkol není tak obligátní jako v jedničce. Jde o hlavolam, před kterým se svojí saboteurkou stojíte: V celém tomto domě jsou rozmístěny kousky pásek, které musíte posbírat a uložit je do terminálu rakety. Mezitím je třeba ještě vypnout elektrický plot. Hra má samozřejmě více misí, od té jednodušší po nejtěžší. Já se zde budu věnovat výhradně té nejtěžší, poslední misi.

Oficiální remake 2017 můžete hrát a soutěžit online na stránkách odkaz. Stojí jednorázově 2,99 GBP, což je méně než stokoruna, a rozhodně se vyplatí.

Remake je oproti originálu o něco vylepšen. Nastává změna počasí, můžete přepínat grafiku (ZX/C64/CPC), hudbu, vidíte energii nepřátel, jsou tam schodiště a další místnosti. Má vylepšené zvuky, v podzemí občas nějaký ten působivý efekt (ukápne kapka), ale záměrně se to jinak drží originálu.


Ještě než začneme, povím něco málo ke hře samotné. O historii domu a dalších detailech se dozvíte až v remaku, kde jsou umístěny tzv. Intel Points, které určité lokality objasňují a dokreslují příběh.

Dům vypadá jako šílený experiment miliardáře Elona Muska. Jediný rozdíl asi je, že náš miliardář se jmenuje Ricardo Alphonso Verdi II a v domě visí jeho portrét v nadživotní velikosti. Dá se usuzovat, že peníze zdědil po svém otci (Verdi I) a rozvíjí dál jeho aktivity, byť nezřízeným směrem. Ten je získal na vybudování úspěšné telekomunikační firmy Viridis, která má v 90. letech pobočky po celém světě a strmě stoupá.

V domě plném experimentů a umělé inteligence nenajdete živou duši. Velmi sympatické totiž je (což jako stoupenec Play with Love! vítám), že v Saboteur 2 se nezabíjí. Ve hře jsou sice všude strážci, ale jsou to robotičtí strážci, androidi, kteří jsou asi celí dost plechoví, protože když je udeříte, ozve se dutý kovový zvuk. Občas chodí ve dvojici s pumou, což je sice zvíře, ale i ve hře se v jednom Intel Pointu pochybuje, zda to nejsou rovněž roboti. Najdete jakési cívky ke stimulaci z radiových signálů a malé radiové jednotky, jež se starají o to, aby pumy nikdy neodpočívaly a jenom divoce pobíhaly poblíž svého pána. Každopádně, pokud někoho zabijete, bude to maximálně puma. Může to být ale hypoteticky i jaguár anebo levhart, obarvení načerno, kteroužto teorii se dozvíte úplně vpravo na jedné zahradě směrem z domu.


Na druhé straně vlevo na zahradě mají být laboratorní prostory (cleanrooms). Stojí tam cedule "No Entry!", ovšem jsou to ve skutečnosti zbrojnice. Mají prý zbraně takové síly, že by se dalo vést malou válku. Vy tam ovšem najdete maximálně hvězdici a nůž.

Nad kancelářským komplexem stojí dvě věže. Jsou plné antén - pravděpodobně určených ke komunikaci. Zaznamenávají váš pohyb a ovládají elektrické dveře po celém komplexu. Skrz ně svítí měsíc a tak nějak nepřímo nabádá, abyste se vydali na dobrodružství připravenou raketou.

Ohromná raketa lákala hráče vždycky. Předpokládám, že nikdy mu nedošlo, proč zrovna ninja by měl umět řídit raketu :) Vlastně ani není jasné, kam by měl letět. Ale letět do vesmíru je prostě vzrušující! Raketa je pokřtěná jako Colonel Briggs Explorer. Satelit uvnitř je totiž plukovník Briggs a další dva satelity se dvěma dalšími plukovníky už byly vypuštěny. To jako součást plánu s názvem Operace Fullbright. K radosti všech, kdo toužili v originále na ZX vzlétnout, podotýkám, že v remaku se odletět dá ;)


Ve hře najdete spousty tajemných míst. Je tam věžový jeřáb, který vykládal kamiony. Najdete tam šrotiště s vyřazenými kousky neúspěšných robotických experimentů. Je tam dokonce zlomený procesor Zilog Z80 i rozbité 16K RAM. S tímto vším měly být roboti ovládáni. Dále narazíte na obří frézu, se kterou se dělaly podzemní chodby a těžilo se uhlí. Je u ní pro zajímavost uvedeno, že je 125 tun těžká a je čínské výroby. Jsou tam ultrazvukové vysílače, které ovládají netopýry. Pak je tam experimentální palivo pro raketu nebo na velké balistické rakety. Laboratoře s protetickými končetinami a neúplnými roboty, laboratoře s kvantovými pokusy atd. atd. Nechybí samozřejmě ani teleport, který vás odvane do tří velmi vzdálených lokalit v domě. Ale nebudu vše prozrazovat.


Jakmile dům proslídíte a pochopíte, postaví vás před jednu z nejobtížnějších matematických úloh. Obecně vešla tato úloha ve známost jako "problém obchodního cestujícího" (odkaz) a vy její tvrdost pocítíte při sbírání pásek.

Ve hře je 15 kousků pásek. Vy jich potřebujete sebrat 14. Tyto pásky musíte umístit do terminálu u rakety a kdykoli během hry ještě vypnout plot. Otázka tedy zní: Kterých 14 pásek z 15 máte posbírat (resp. kterou tu jednu vynechat) - a v jakém pořadí je máte posbírat, abyste to stihli v daném čase? Sbírat můžete navíc z jakéhokoli místa, neboť na začátku se snášíte nad dům rogalem a můžete seskočit v libovolném bodě.

Ještě o rozměr víc dostává remake, kde se čas měří a hráči se předhánějí, kdo celou hru projde dříve. Nejde tedy primárně už o to hru dohrát, ale dohrát ji lépe než soupeř. Musíte tedy (abstraktně řečeno) oběhnout 16 bodů (14 pásek, 1 terminál, 1 plot). Pokud vypustíme, že terminál můžete navštívit až po sebrání 14 pásek, tak máte přesně 15 bodů k oběhu. Na první pohled jich není moc, ale počet možných cest (permutací) mezi 15 body je neuvěřitelně velký, je to tzv. 15 faktoriál

15! = 1.307.674.368.000, tj. přes 1.300 miliard cest.

Vybrat z ní tu nejkratší je intuitivně velice obtížné. Navíc je zde problém umocněn tím, že v našem případě nejde o vzdálenost, ale o čas, protože čas z bodu A do bodu B není stejný jako z bodu B do bodu A. Někde skočíte do jámy a zpátky do stejného bodu se musíte vyškrábat mnoha žebříky. Někde nelze jen seskočit, ale musíte seskočit z určitého úhlu atp.

Takhle vypadá mapa hry s částmi pásek:

Jakmile pásky posbíráte, umístíte je do terminálu a vypnete plot, můžete se vydat na tu nejdelší cestu dole a ujet z objektu motorkou. Tím hra končí.

Vzhledem k tomu, že jsem programátor a ne matematik, snažil jsem se hru vždy vyřešit nějakou simulací, kde by počítač zkoušel cesty procházet a počítal si celkový čas každé z nich. Cestu s nejkratším časem si zaznamená. Bude se tak přibližovat ideálnímu řešení.

K takové simulaci je ale potřeba velmi dobře optimalizovaný program, protože projít 1300 miliard kombinací je hodně i na výkonný 64-bit. Musí je procházet rychle a nejlépe zbytečně nekombinovat nesmyslné trasy (asi jako když programujete šachy, tak je vhodné zakomponovat nějaké minimum umělé inteligence, aby program neztrácel čas nad absurdními tahy). Je nutno se též rozhodnout, jestli je vhodnější procházet je všechny, nebo kombinace "ostřelovat" náhodně, tzv. heuristický proces či brute force.

Já jsem se rozhodl pro heuristiku. Program se dá napsat v jakémkoli jazyce, různé jazyky nabízí různé možnosti, jednou je to rychlost, podruhé zase lepší optimalizace pseudonáhodných čísel.

Nejprve je zapotřebí změřit časové úseky mezi jednotlivými body. Když saboteurka letí nad domem, může seskočit nejblíže 4 místům s páskou. Dá se tedy říci, že svou misi můžete plnit od jednoho z těchto 4 míst, protože jakmile byste jí počítali od jakéhokoli bodu z 15, bude trasa vždy časově náročnější. Tím získáme jedno významné omezení hned pro začátek a můžeme vyloučit první nesmyslné trasy.


Kombinace mezi body zvlášť musíte pečlivě změřit. Jde o to, aby to bylo přesné (takže stopky), protože rozhodují pak časové nuance. Za druhé - a to už není tak snadné - musíte předvídat, co na trase bude za překážky. Přece jen hra není jen o tom běhat z bodu A do bodu B atd., ale vypořádat se také na cestě se strážci, kteří vás dokáží dost pozdržet. Pokud tím samým místem probíháte podruhé, už budou pravděpodobně mrtví (protože je zabijete na cestě tam), ale napoprvé tam budou.

Čili, je třeba uvažovat o reálné situaci ve hře a předvídat, ne jen jako o časově abstraktní, geometrické. Např. cesta z bodu č. 12 do bodu č. 11 je sice krátká, pokud ji změříte jen jako úsek s plnou energií, ale pokud začínáte cestu na 12, tak je třeba si uvědomit, že už při seskoku z provazu budete mít sotva 1/3 energie a dole pod 12 čekají 2 strážci. Takže cesta z bodu 12 do bodu 11 se zdrží minimálně o 10 sekund. Obdobně je cesta A-B-C, kde A je na 1. místě, jinak dlouhá, než cesta A-B-C, kde je A třeba na 4. místě. Nejlepší je tedy projít to vícekrát za reálných podmínek a měřit to důsledně.

Pozor je třeba dát na to, abyste opravdu změřili tu nejkratší cestu mezi body A a B. Někdy jsou body dost daleko od sebe a jen intuitivně se můžete domnívat, že běžíte po té nejkratší. Časem ale zjistíte, že se to dalo někde ještě zkrátit. Clive nám to taky v remaku nadto dost zamotal tím, že všude v kancelářských prostorech jsou schodiště a i když ty bývají časově náročnější, nabíráte na nich nepatrně energie, takže pak nemusíte ztrácet čas prostojem.


Další věc, kterou můžeme algoritmus zrychlit, je spojení pásek 3 a 4. Ty jsou vedle sebe a je tudíž zbytečné, aby se procházely kombinace z 3 na 15 a pak ze 4 na 14... Můžeme je tak zafixovat k sobě.

Otázkou je páska č. 17. Ať jsem to procházel jakkoli a kombinoval vše možné, vždy mi páska 17 vypadávala jako nadbytečná. Ačkoli na cestě nejsou skoro žádní strážci, přesto je časově hodně daleko a po cestě nejde vyřídit nic jiného ani na ní nijak navázat. Domnívám se, že z algoritmu ji tak můžeme vyřadit a získat tím další optimalizační prvek.

Asi poslední věc, kterou se dá optimalizovat, je svázání bodů 14, 15, 16. Jsou tak blízko sebe, že není možné najít kombinaci, která by byla časově výhodnější a zároveň by tyhle 3 body nespojovala. Č. 16 je terminál, tam musíme vložit všechny části pásek po sesbírání, č. 14 je elektrický plot. Takže poslední sebraná páska bude č. 15, pak terminál a plot. Tuto podmínku můžeme do algoritmu zafixovat.

Výsledný program je tím pádem kupodivu dost jednoduchý, jen je potřeba tyhle věci co nejoptimálněji ošetřit a domyslet. Napsal jsem ho tedy v několika jazycích, abych nebyl závislý na rychlosti jednoho. A to v PureBasic (odkaz), BlitzMax (odkaz), FreeBasic (odkaz), MonkeyX (odkaz), AGK2 (odkaz) a Python (odkaz).

Nejrychlejší vůbec se ukázal být MonkeyX a k mému překvapení FreeBasic. Řešení najdou za několik desítek minut, dá se říci, že do 24h máte 100% jistotu, že neexistuje lepší řešení. PureBasic má zase výhodu v tom, že nemusíte programovat funkci na generování náhodného pole, ale že má přímo příkaz RandomizeArray().


Je zajímavé, že existuje více cest, které začínají od 12 (a jdou po úplně jiné trase) a jsou časově téměř identické. Proto je taky těžké řešit to jen strojově. Některé cesty, které jsou o sekundu delší jsou sice delší, ale můžete během nich potkat méně strážců a nebezpečí. Podle mě je nejlepší projít si ty časově nejkratší trasy, zjistit rizika a jednu z nich se pořádně naučit. Soupeři můžou mít sice o nějakou sekundu trasu výhodnější, jestliže nezapočítávají zdržení nepřátel, ale pokud pojedete tu svojí delší s menším zdržením, můžete to stihnout nakonec dřív.

Pokud jde o samotné rekordy ve hře Saboteur II, je nutné odlišit originál od remaku. Remake je pro mě osobně mnohem komfortnější, neboť engine jde libovolně zrychlit a čas si nemusíte měřit sami. Mezi hráči na špičce je dost velká konkurence, na některých misích jde vyloženě o setiny sekundy. Na té poslední misi držím zatím rekord. V originále na ZX mě jeden Rus překonal o necelou 1 sekundu, zvolil při tom úplně jinou trasu a napsal o tom článek. I video v tom článku se odkazuje na moje mezičasy (odkaz). Jeho trasa je určitě o něco kratší, ale co do rizika je možná obtížnější, takže celkově vychází ty trasy skoro nastejno a je jen otázkou, kolik času jste schopni se zdržet se strážci. Myslím, že při svém rekordu měl trochu víc štěstí :)

Remake jsem byl schopen zaběhnout za 9:26.06. Možná se vám povede to někdy překonat, neboť určité rezervy jsem tam zaznamenal, ale je to velice těžké. Musíte mít správnou trasu, všechno nacvičené a všechny mezičasy vám musí vyjít. Zdržení někde o půl sekundy těžko doženete, i když je ta trasa dlouhá.

Na závěr nechci zveřejnit explicitně svojí trasu, kterou běžím. Nechám si to jako know-how. Ale zkusit to naprogramovat a celé vyřešit byla pro mě výzva a neskutečná zábava trvající roky, dokonce už od mých mladých let :-)

Komentáře

Celkem 0 komentářů

  • Neregistrovaný uživatel

    Jméno: Přihlásit se

    Blog:

    Obsah zprávy*:

    Kontrolní kód*:
    Odpovězte na otázku: Co je dnes za den?