Jak jsem hledal cestu z bodu A do bodu B – a našel ji až napočtvrté

Pokus první: prostě jdi

První chůze byla taková, jakou by napsal každý, kdo věří, že svět je dobré místo: podívej se, kde je cíl, a udělej krok tím směrem. Jednu osu, pak druhou, každý krok se přes MayStep zeptá, jestli je cílová pozice průchozí. Když ne, počkej. Když čekáš moc dlouho (STUCK_LIMIT), prohlas, žes dorazil, a sedni si. Ano, i uprostřed lesa. Postavička si nestěžovala, což jsem si vykládal jako souhlas.

Vypadalo to dobře. Vypadalo to dobře i s chybou, kterou jsem tam měl od začátku: Passable si držel sloupec dlaždice v registru C a o pár instrukcí níž ho přepsal ld bc,8. Každá jednotka na mapě se tedy ptala na průchodnost sloupce 8 svého řádku. A protože sloupec 8 leží v lesním pásu, vojáci se lesu vyhýbali a shlukovali na louce — přesně jak mají. Odhalil to až rozdíl dvou screenshotů s odstupem šestnácti vteřin: 1 540 změněných pixelů znamená, že se skoro nikdo nehýbe. Od té doby mám pravidlo, které si čtu častěji, než bych chtěl: vizuálně věrohodné není ověřené.

Pokus druhý: objížďka

Když se voják zastaví o strom, ať ho obejde. DetourOpen se podívá dvanáct pixelů dopředu, sestaví čtyři směry v pořadí „podél zdi k cíli, podél zdi od cíle, a teprve pak ty dva zpátky do ní“ a vydá se prvním otevřeným. Elegantní. Tři chyby v jedné rutině, každá živená tou předchozí.

Nejlepší z nich: dvě správná rozhodnutí, která dohromady dávají nekonečno. Voják vyrazí podél budovy dolů, ujde šest pixelů a zastaví, protože dvanáct pixelů před ním už je zavřeno. Další snímek se seznam postaví úplně stejně — dolů první, nahoru druhé — jenže dolů je teď zavřené, takže vyhraje nahoru. Šest pixelů nahoru, kde je dolů zase otevřené. A tak pořád, do konce hry. Pravidlo na zaseknutí to nemohlo chytit, protože voják kroky dělá, několik za vteřinu, tam a zpátky. Podle všech definic byl v pohybu. Dostal nový bajt UNIT_TRIES, po osmi objížďkách bez skutečného postupu k cíli to vzdá, a přišel zákaz vracet se směrem, odkud přišel, dokud vede cokoli jiného.

Pokus třetí: roh

Krok po jedné ose znamená, že šikmá mezera mezi dvěma stromy je zeď. Vodorovný krok vede do jednoho stromu, svislý do druhého, a díra, kterou hráč vidí, je pro engine neprůchozí. Simulováno přes čtyři tisíce kroků: neprošel ani jednou. Tak když jsou odmítnuté oba osové kroky a úhlopříčná pozice je skutečně průchozí, jde tam jedním krokem. Jedna šikmá řada stromů přestala být zeď. Postavičky teď procházely tam, kudy bylo vidět, a já jsem si myslel, že mám hotovo.

A pak jsem to změřil

Vzal jsem Warcraftovu vlastní mapu forest1, náhodně vylosoval čtyři sta dvojic dlaždic, o kterých záplavové vyplnění říká, že spojené jsou, a nechal simulaci chodit.

Sto šest ze čtyř set. Přibližně tři čtvrtiny testovaných rozkazů nedošly tam, kam měly, a já to prostě nevěděl, protože voják, který uvízne u lesa a sedne si, vypadá jako voják, který si sedl u lesa. Sledování zdi (klasický Bug2) bylo lepší, ale ne těsně: při trojnásobku kroků došlo pořád 295krát. Některé tvary prostě neopustí.

Pokus čtvrtý: přestat být chytrý

Řešení, na které jsem nakonec přišel, je hloupé v tom nejlepším smyslu. Neplánuje se cesta. Plánuje se terén.

Od cílové dlaždice se pustí průchod do šířky ven: cíl má nulu, sousedi jedničku, jejich sousedi dvojku, stromy a budovy se přeskočí. Výsledek je jeden bajt na megadlaždici — kolik kroků je odtamtud k cíli. Jednotka pak nedělá nic jiného, než že jde z kopce: podívá se na čtyři dlaždice kolem sebe a šlápne na tu s menším číslem. V použité čtyřsměrné mřížce je to nejkratší cesta a v běžném kroku to znamená jen několik čtení a porovnání sousedních hodnot. Žádné objížďky, žádné rohy, žádný čítač pokusů.

Proč je to elegantní zrovna na Nextu: pole bydlí na $E000, ve stránce, kterou stroj nechává v sedmém slotu a nikdo jiný ji nechce. V hlavní smyčce je namapovaná pořád, takže se ke čtení nic nestránkuje. Staví se po kouscích, 96 dlaždic za snímek — čtyři tisíce naráz by byly tři snímky, což by na kliknutí cuklo. A ani nemusí být hotové: záplava roste od cíle ven, takže jakmile dorazí k vojákovi, ten ji může začít sledovat, zatímco zbytek mapy se ještě počítá. Jedno pole pro všechny, kdo jdou na totéž místo; pole ví, ke kterému místu patří, a kdo jde jinam, chodí postaru.

Chyby, které jsem si k tomu vyrobil sám

Aby to nevypadalo, že jsem to napsal na první dobrou. Nenapsal. Postupně:

1. Fronta byla přímka, ne kruh. Ocas počítal každou dlaždici, která kdy na frontu přišla — čtyři tisíce proti dvěma tisícům míst — takže záplava došla uprostřed mapy a druhá půlka pole zůstala prázdná. Jedenáct polí z dvanácti vyšlo jinak než referenční průchod. V kruhu se musí vejít jen živý okraj, a ten je malý: nejširší, jaký tahle mapa kdy měla, byl 51. Proto 256 položek a hlava s ocasem jako bajty — kruh se uzavírá tím, že přetečou.
2. Test „je ta dlaždice blíž“ vracel příznak od CP, ne od A. ld a,0 / ret nc se vrátí s tím, co nechal cp, a cp nechává NZ pro dlaždici, která je dál. Volající to četl jako „lepší“. Jednotky chodily od cíle pryč, sebevědomě.
3. Kdo stál na dlaždici, kterou záplava nikdy neoznačila, zůstal venku. Dělník u zlata stojí na dole, a důl není zem — záplava ho obešla. Pole pro něj nemělo odpověď, spadl na starou chůzi a tlačil se do nejbližší stěny. Teď se 255 nezahazuje: každý soused s číslem je blíž než 255, takže první krok vede z díry ven. Ze 158 startů přímo na neprůchozí dlaždici vylezlo a došlo 149.
4. Na cíli se roztřásl. Pole mluví v dlaždicích, cíl je pixel, a ti dva se neshodli, ve které dlaždici ten pixel je — pole bylo zaseté pod kurzorem, dlaždice jednotky je ta, kde má střed, o osm pixelů dál. Pole ho táhlo zpátky, chůze na cíl, a mezi tím se třásl, jak dlouho jste se dívali. Poslední dlaždici dělá prostá chůze.
5. Odmítnutí se vracelo s NZ. A volající četl NZ jako „pole odpovědělo“, takže použil StepX a StepY, které tam nechala předchozí jednotka. Poslal jsem jednoho vojáka a vyrazila za ním celá strana. Bylo to vlastně dojemné.

Dvě pole, protože chůze jsou dvě

Pole patřilo tomu, kdo si o ně řekl naposled. Já klikám pořád; orkská vlna si řekne jednou za vlnu. V praxi ho tedy nikdy neměla a pochodovala přes mapu po staré chůzi — a když dorazila, byla to náhoda. Teď jsou dvě: moje na $E000, vlny na $F000. Stránka je přesně osm kilobajtů, takže fronta se odstěhovala ke kódu; stačí jedna, protože roste vždycky jen jedno pole. A které si jednotka čte, určuje její rozkaz, ne pokus obě: pole vlny je zaseté na mé tvrzi, takže voják poslaný kamkoli poblíž propadl přes svoje pole, hned ho sebralo to orkské a táhlo ho do mé vlastní tvrze, zatímco chůze ho tlačila zpátky. Točil se. Hezky, rovnoměrně.

Poslední kus je předávka. Pole vede na jednu dlaždici, ale skupina na jednu dlaždici nejde — každý má své místo kolem ní, až tři dlaždice daleko. Kdo došel na semínko, byl pořád tři dlaždice od svého místa, a zase to třesení, tentokrát třikrát větší. Předává se na kruhu, ve kterém jeho místo leží: jakmile není od semínka dál než jeho vlastní místo, pole nemá co dodat a zbytek dojde chůzí. Plus jedna dlaždice vůle, aby se ten kruh nedal přešlápnout zpátky dovnitř — jinak je z toho další kolo.

Co si z toho beru

Tři pokusy jsem strávil tím, že jsem učil jednotku rozhodovat se — a každé rozhodnutí potřebovalo další pravidlo, které opravovalo to předchozí. Čtvrtý pokus jí rozhodování vzal: terén už ví, kudy se jde, a ona jen čte. Několik čtení a porovnání za krok. Kdybych to změřil dřív, ušetřil bych si spoustu času dojemných objížděk. Ale to je poučení, které si člověk nezapamatuje jinak než tak, že ho zaplatí.