Flashback na ZX Spectrum Next – 3. Animace a skripty

Všechno je entita

Všemu, co se v levelu může změnit, říká REminiscence PGE – podle francouzského piège, past. Je to Conrad, stráže a roboti, ale stejně tak dveře, výtahy, miny a předměty, které leží na zemi. První level jich má 107, druhý 256. Výchozí stav každé entity je v souboru .PGE: poloha, místnost, životy, příznaky a dvě čísla, na kterých stojí všechno ostatní – stav (upstream mu říká obj_type) a uzel, tedy seznam záznamů, podle kterého se entita řídí.

Stav je jediné číslo, a přesto říká skoro všechno. Patří k němu dvě věci: animační tabulka v .ANI, která říká, co se během stavu děje na obrazovce, a záznamy v .OBJ, které říkají, kam se dá ze stavu pokračovat. Conrad, který stojí, je stav 1. Když se rozejde, je to stav 231, chůze je pak 2 a 3 pořád dokola, otočka je 0 a vstávání na začátku hry 99. Hra tiká třicetkrát za sekundu a v každém tiku projde všechny entity, které jsou vzhůru. Jedné entitě se za jeden tik stane tohle:

1. ZprávyJestli jí někdo poslal zprávu, může animace přeskočit rovnou k záznamu, který na tu zprávu čeká.
2. Doběhla animace?Pokud ne, ukáže se další snímek, entita se posune o jeho dx a dy a tím její tik končí.
3. ZáznamyPokud ano, zkoušejí se záznamy jejího stavu shora dolů. První, jehož podmínky platí, provede akci, přepne stav a nová animace začne ještě v tomtéž tiku.
4. Žádný neplatíEntita zůstane, jak je, a příští tik se ptá znovu.
5. Konec tikuZprávy se zahodí. Každá žije přesně jeden tik.

Podstatné je pořadí druhého a třetího kroku. Skript se neptá každý tik – ptá se, až když animace doběhne. Animace tu není film, který běží vedle logiky. Je to její hodiny.

Animace jako hodiny

.ANI začíná tabulkou šestnáctibitových offsetů, jedním na každý stav – v prvním levelu jich je 1 165 –, a za ní jsou samotné tabulky. Každá má šestibajtovou hlavičku: počet snímků, číslo zvuku, který zazní, když entita do stavu vstoupí, jeden bajt, na který se můžou ptát ostatní entity (k němu se ještě vrátím), a příznak „kresli mě jako předmět, ne jako postavu“. Za hlavičkou jsou snímky po čtyřech bajtech: číslo spritu, jehož horní bit znamená zrcadlení, a znaménkové dx a dy, o které se entita s tím snímkem posune.

Snímek je tedy jeden tik, ne jeden obrázek. Conradovo vstávání na začátku hry má 28 snímků, ale jen 15 různých obrázků – skoro každý je v tabulce dvakrát za sebou, takže při třiceti ticích za sekundu běží animace rychlostí patnácti obrázků za sekundu. A pohyb není rychlost, ale součet posunů. Jeden krok chůze, stav 2, má dvanáct snímků a Conrada posouvá jen na těch, kde se mění obrázek: o 4, 3, 1, 4 a 4 body dopředu. Dohromady šestnáct, přesně jeden sloupec kolizní mřížky, takže krok, který začne na mřížce, na ní i skončí. A aby na ní začínal, Conrad, který stojí a nic nedrží, se na mřížku každý tik zarovná – uvidíme za chvíli.

Teď ten háček s hodinami. Stojící Conrad má animaci o jediném snímku, takže se na skript ptá každý tik. Krok má dvanáct snímků, takže o tom, jestli jít dál, nebo zastavit, se rozhoduje jen jednou za dvanáct tiků – za 0,4 sekundy. To je ta známá setrvačnost Flashbacku: rozešlý krok se nedá zastavit v půlce, protože v půlce kroku se na klávesy nikdo neptá. Není to vlastnost ovládání, je to vlastnost formátu. Jediné, co animaci utne dřív, je zpráva. Rutina pge_setupNextAnimFrame projde záznamy stavu, najde ten, který na zprávu čeká, a zbytek animace dožene najednou – včetně posunů všech přeskočených snímků, takže entita skončí přesně tam, kde by skončila, kdyby animace doběhla.

Na Next jdou tabulky převedené, a to ne kvůli formátu, ale kvůli stránkování. .ANI prvního levelu má 19 100 bajtů, tedy tři 8KB stránky, a getAniData vrací ukazatel kamkoli do ní. Dřív nebo později by se našla tabulka, která přeteče přes hranici stránky – a Z80 ji čte jediným oknem MMU. Převodník proto napřed zjistí, do kterých stavů se entity levelu vůbec můžou dostat (z Conradova startu do 191, ze všech entit prvního levelu do 420), každou tabulku zkopíruje celou do jedné stránky a index postaví znovu. Stav, kam se dojít nedá, dostane offset $FFFF, takže dotaz na něj je chyba, kterou Z80 pozná, a ne divoký ukazatel.

Záznam: dvě otázky, akce a skok

.OBJ začíná tabulkou uzlů – v prvním levelu 230 čísel, která ale ukazují jen na 50 různých seznamů – a za ní jsou seznamy záznamů po osmnácti bajtech. Záznam patří k jednomu stavu a nese tři opkódy se třemi argumenty, nový stav, index záznamu, odkud v něm pokračovat, bajt příznaků a vlastní posun dx a dy. První a druhý opkód jsou mimochodem v souboru uložené v obráceném pořadí, což při psaní převodníku stojí za jednu kontrolu navíc.

Celý pge_execute se dá převyprávět v pár větách. Spustí první opkód s prvním argumentem, a vrátí-li nulu, záznam padá a na řadu přijde další. Totéž s druhým opkódem. Třetí je akce a provede se vždycky. Pak entita přejde do nového stavu, animace se vynuluje a přijdou na řadu příznaky: horní čtyři bity vyberou, kolik bodů připsat do skóre, bit 0 entitu otočí, bit 1 ubere život, bit 2 přidá a bit 3 nastaví život na −1. Úplně nakonec se entita posune o dx a dy ze záznamu – zrcadlově, je-li otočená. Na tenhle poslední řádek si ještě vzpomeneme. Takhle to vypadá, když Conrad stojí:

Prvních pár záznamů se neptá na klávesy, ale na zprávy. Zásah ve Flashbacku totiž není průnik dvou obdélníků: kdo útočí, pošle zprávu těm, s nimiž sdílí kolizní buňku, a zasažený na ni odpoví vlastním záznamem – tady přechodem do jednoho ze stavů zásahu, u některých i s ubraným životem. Teprve potom přijdou klávesy. Na pořadí záleží, protože vyhrává první záznam, který projde, a záznam 50 na konci nemá podmínku žádnou: znamená „jinak stůj dál“. Takových záznamů bez podmínky je v prvním levelu 491 z 1 838 a nejsou to výjimky, ale obyčejné „animace doběhla, pokračuj“. Otočka jsou dva stavy za sebou – pět snímků, záznam bez podmínky s nastaveným bitem 0 a dalších devět snímků. Otočit se tedy není bit nastavený klávesou, ale malý příběh o čtrnácti snímcích.

Tři záznamy pro „vpřed“ se liší jen dotazem do mřížky a podle odpovědi Conrad zůstane stát, sejde o patro níž (stav 128, jehož animace ho posune o 72 bodů dolů), nebo se rozejde. Dotazy do mřížky jsou skoro všechny tatáž funkce, col_getGridData – „co je v buňce o tolik řádků a sloupců ode mě“ –, jen s jiným pevným posunem a jiným testem odpovědi, a jméno jako collides1u1o je zkratka toho posunu. Skripty přitom neznají vlevo a vpravo, jen vpřed a vzad. isInpForward je doleva, nebo doprava podle toho, kam se entita dívá, a stejně se otáčí i sloupec, na který se mřížky ptá. Jeden skript tak slouží oběma směrům a zrcadlení je jen příznak.

Vstupní opkódy navíc porovnávají masku kláves na rovnost, a Flashback nezná diagonály – a to tak, že je zahodí: drží-li hráč zároveň svislý a vodorovný směr, pge_getInput vezme místo toho poslední čistě vodorovné čtení. Nahoru a doprava tedy znamená „pořád doprava“. První verze tohle neměla, maska nahoru+doprava se nerovnala ničemu a Conrad se prostě zastavil. Vypadalo to, jako by klávesnice polykala stisky. A skok na směr a nahoru, který každý zkusí jako první, ve Flashbacku není vůbec.

Šestnáct bajtů místo osmnácti

Na Z80 se všechno, co interpret čte, musí vejít do 8KB stránek za jedním oknem MMU, a to tvar dat omezuje víc než jejich velikost. Původně jsem záznam nechal na osmnácti bajtech a v commitu jsem si pochvaloval, že násobit osmnácti je levné – krát šestnáct a krát dva, dva posuny a sčítání. Pravda, a úplně vedle: 8 192 není násobek osmnácti, takže by se našel záznam, který leží přes hranici stránky a polovinou sahá do paměti, která zrovna namapovaná není. Šestnáct bajtů dělí stránku beze zbytku, 512 záznamů ji vyplní přesně a číslo stránky je index záznamu posunutý o devět bitů doprava.

Do šestnácti se vejde všechno kromě dvou argumentů – a ty se vejdou s posunem. První argument má rozsah −2 až 240 a druhý −16 až 180, takže po přičtení dvou a šestnácti jsou z obou bezznaménkové bajty. Převodník všechno mimo ten rozsah odmítne. Třetí argument je šestnáctibitový – a i tak jsem ho napřed četl jako bajt. Přišlo se na to až v posledním levelu, kde se jím posouvá výtah o 216 bodů a zpátky o 146.

Tabulka skoků se generuje z upstreamové _pge_opcodeTable a těla se k číslům párují podle jména, takže číslo opkódu není nikde napsané dvakrát a přečíslování by nic tiše neposunulo. Opkód dostane argument v A a odpověď vrací taky v A: nula je ne, cokoli jiného ano. Upstream vrací 0xFFFF nebo 1 a volající stejně testuje jen spodní bajt, takže osm bitů nese přesně totéž. A samotný skok do těla jsou dvě instrukce, push de a ret.

Entity jsou na Z80 uložené naruby. Upstream má každou jako 32bajtovou strukturu a sto sedm struktur za sebou je převod, který se nabízí – jenže pak je každé pole index krát 32. Port má místo toho jednu tabulku na každé pole, takže slovo je základ + index × 2 a bajt základ + index. Nečekaně se tím z většiny načítání levelu staly blokové přesuny: sedm polí se jen zkopíruje a šest se nastaví na konstantu, což je v tomhle uspořádání šest LDIR a šest výplní přes celé tabulky, kde by pole struktur chtělo sto sedm od každého. Interpret a těla opkódů jsou pak psané proti pevným proměnným – PgeObjType, PgePosX a dalších sedm –, do kterých se běžící entita na začátku svého tiku zkopíruje a na konci zase zpátky. Je to stejný tvar, jaký má upstream: i tam opkódy sahají na entitu přes tu jedinou, kterou dostal pge_execute.

Když se pak data rozšířila z Conradova dosahu na celý level, tiše selhaly dvě věci dimenzované na menší data – a ani jedna nebyla v novém kódu. SAVENEX ukládal z animačních tabulek jedinou 16KB banku. Dokud se tabulky vešly do dvou stránek, stačila; když přibyla třetí, do NEXu se nikdy nedostala a 37 stavů animovalo z toho, co v paměti nechala ROM. Nic nespadlo, bajty se dokonce daly přečíst jako text. A smyčka přes záznamy porovnávala jejich index jen horním bajtem, takže všechno od 1 792 do konce – posledních 46 záznamů prvního levelu – se odmítlo, aniž by se na ně kdo podíval. Conradův uzel je na začátku souboru, takže se to neprojevilo, dokud běžel jen on. Jakmile běžely všechny, ty, jejichž záznamy leží na konci, prostě nedělaly nic. O dvacet řádků vedle přitom visel můj vlastní komentář o úplně stejné chybě.

Kolik interpretu je doopravdy potřeba

Tabulka opkódů má 140 položek, tři z nich prázdné. První level jich používá 105. Kdybych je psal podle seznamu, začal bych sto pěti rutinami, které by nikdo nemohl ověřit, protože by je nic nevolalo. Tak jsem nejdřív měřil: od Conradova startu se dá po záznamech dojít do 191 stavů a ty potřebují 60 opkódů. A i to číslo je menší, než vypadá: 11 z nich jsou vstupní testy a všechny jsou jen porovnání s maskou kláves, 21 kolizních je pořád tatáž col_getGridData s jiným pevným posunem a samostatných rutin bylo osmadvacet.

Pak přišly ostatní entity. Statický průchod záznamů říkal, že dosáhnou ještě 45 opkódů, které Conrad nepotřebuje. Když jsem je ale v referenci doopravdy pustil na 70 tiků, chtěly jich devět. Po dopsání těch nejjednodušších zbylo šest, pak tři, pak žádný – a nebyly rozházené: polovina chtěla kolizní sloty, polovina inventář. Statická dosažitelnost počítá každou větev, i tu za podmínkou, která nikdy neplatí. Je to horní mez, ne požadavek. A je to měření, které se musí opakovat, protože každý dopsaný opkód odemkne entity, které pak dojdou zase o kus dál.

Aby tohle měření fungovalo, musí reference na neznámém opkódu spadnout. Vrátit nulu vypadá jako bezpečná volba a je to ta špatná: nula znamená „podmínka neplatí, zkus další záznam“, takže chybějící opkód tiše pošle entitu jinou větví a hra pořád vypadá věrohodně. Na Z80 spadnout nejde, tam neznámý opkód odpovídá „ne“ – a proto převodník vypisuje dosažitelné, ale nenapsané opkódy do souboru, který je seznamem úkolů. Dnes je prázdný: port umí 125 ze 140 položek tabulky, data všech sedmi levelů sahají na 121 různých a žádný level nepoužije opkód bez těla.

Nejvíc mě překvapilo, které opkódy jsou nejčastější. Nejsou to klávesy ani mřížka. V prvním levelu se záznamy nejvíc ptají na zprávy – hasPiegeSentMessage se v nich objeví 286krát a isToggleable 202krát. Zpráva je dvojice „od koho a jaké číslo“, navěšená na seznam adresáta; ten si ji přečte na začátku svého tiku a na konci tiku se zahodí. Tak se otevírají dveře a tak se stráž dozví, že ji něco zasáhlo. A ty dva podsystémy z měření jsou podobně nenápadné. Dveře se nezavírají tím, že se nakreslí, ale tím, že zapíšou vlastní buňky do kolizní mřížky, po které chodí všichni ostatní, a co přepsaly, si schovají. Sebraný předmět zase nepřestane být entitou: jen se mu místnost nastaví na $FF a navlékne se na seznam, který vede přes entity samotné. Přestane být kdekoli, ale pořád je.

Druhé čtení téhož zdroje

Než interpret vznikl na Z80, napsal jsem ho pro PC, stejně jako jsem u cutscén napsal referenční přehrávač. Tentokrát s jedním pravidlem navíc: reference se píše z piege.cpp, ne podle Z80. Jinak to nejsou dvě čtení zdroje, ale jedno čtení dvakrát, a dvě kopie téže chyby se spolu vždycky shodnou. Z80 si pak stav entit zapíše na kartu a kontrola porovnává čísla, ne obrázky: všech 107 entit a stav generátoru náhody po 5, 40, 130 a 400 ticích, ve třech rozehrách – Conrad stojí, jde doprava a jde doleva, dokud z levelu nevypadne. Každý ze sedmi levelů se pak krokuje 150 až 300 tiků čtyřmi způsoby a porovná se každé pole každé entity, ve druhém levelu všech 256.

Psát to dvakrát se vyplatilo hned. Upstream počítá polohu entity v mřížce jednou za tik, před pge_process, a nechá ji tak, i když se entita během tiku posune. Přepočítat ji při každém dotazu je to, co člověk napíše automaticky, a tiše to dá jinou hru. A pge_setupDefaultAnim čte příznak zrcadlení z počtu snímků, ne ze snímku. V originále to vypadá jako přehlédnutí a port to přebírá přesně tak, jak to je: neopravuju originál, opravená hra by byla jiná hra.

Nejlevnější nástroj na hledání rozdílu se ale ukázal až u kolizí. Conrad se při šplhání na vyšší plošinu ocital dole a dlouhá chůze doleva ho protáhla stropem do místnosti −1. Místo hledání v emulátoru jsem tu rutinu ze Z80 přepsal zpátky do Pythonu – přesně tak, jak je napsaná, i s osmibitovým maskováním – a pustil ji proti referenci přes všechny kombinace místnosti, polohy, dy a dx, na které chůze může narazit. 616 neshod a u každé konkrétní vstupy. Příčina: col_getGridData přičítá řádek × 16 s původním řádkem i poté, co dotaz přejde do vedlejší místnosti vlevo nebo vpravo, takže tam řádek klidně může být −1 a součet záporný. V bajtu se z −14 stane 242 a odpověď přijde z úplně cizí buňky. Žádný emulátor, žádné snímky – a výstup rovnou říká kde.

Když se dva modely shodnou

Dvě nezávislé verze chytí chybu v přepisu. Nechytí ale krok, který jsem vynechal v obou – pak se shodnou a kontrola je zelená na hře, která se chová špatně. Tohle se mi v celém portu stalo častěji než cokoli jiného.

Pamatujete na poslední řádek pge_execute, posun o dx a dy ze záznamu? Chyběl v referenci i na Z80. Animační tabulky přitom skoro žádné dy nenesou – celý výstup na vyšší plošinu je jediné dy = −72 na záznamu, který ho spustí, jedno celé patro. Bez něj se vytahování přehrálo a Conrad skončil zpátky na plošině, na které stál. Obě strany se shodly a přišlo se na to až při hraní, dvakrát.

Horší byl bit 3 příznaků, který říká „kresli jako předmět, ne jako postavu“. Dva řádky pge_setupDefaultAnim, které ho nastavují z hlavičky animace, chyběly v referenci, na Z80 i v bajtu, který předpočítává převodník. Porovnání bylo zelené. Měření „kolik entit ten bit kdy má“ odpovědělo nula – a já jsem na základě té nuly kreslení předmětů nenapsal a připsal k tomu komentář, proč to v prvním levelu není potřeba. Je to 94 ze 107 entit. Tři z nich stály v úvodní místnosti a kreslily se jako postavy z PERSO.SPR, což je Conradův vlastní soubor, takže v místnosti ležely kusy Conrada. Měření, které se ptá modelu, jemuž chybí řádek, je kruhové: odpoví „nikdy“ a vynechávku tím ještě posvětí.

A dvě chyby na konci jedné a téže rutiny. Upstreamová pge_setupOtherPieges je if pro přechod přes okraj místnosti a za ním bezpodmínečně přeřazení entity do seznamu místnosti, ve které teď je. Nejdřív chybělo úplně, pod komentářem, že zbytek rutiny budí entity v nové místnosti, „a žádné zatím nejsou“ – pravda v době, kdy byl Conrad sám, a pořád to znělo pravdivě, když jich přibylo sto šest. Conrad tak zůstal navždy v seznamu výchozí místnosti a po přechodu do vedlejší zmizel. Potom jsem to napsal jako „nepřekročil okraj, tak return“ a předčasný návrat spolkl ocas funkce. Entita se totiž může přesunout i vlastním opkódem: zastřelený robot se pošle do místnosti $FE, sebraný předmět do $FF. Robot zůstal v seznamu místnosti, další tik ho pge_prepare našel a probudil a jeho výbuch se přehrával každých patnáct tiků. Tři existující scénáře tím celou dobu procházely, protože tu díru měly obě strany.

Otázka, na kterou hra odpovídá „ne“

Ten bajt v hlavičce animace, na který se můžou ptát ostatní, čtou opkódy kolem rutiny pge_ZOrder. Ta navzdory jménu nemá s pořadím kreslení nic společného: projde řetěz entit, které sdílejí kolizní buňku, a na každou se zeptá zadanou otázkou – je stejného druhu, dívá se opačně, má v hlavičce animace tohle číslo? Stojí na ní i zásahy z Conradova výpisu: zprávu dostane ten, koho tahle procházka najde.

Na tuhle rutinu jsem pustil sedm schválných chyb. Dvě, které měnily samotnou odpověď, chytila každá rozehra. Tři uvnitř procházky – čtení bajtu se zvukem místo toho vedle, entita počítaná jako vlastní soused, zastavení na první buňce místo projití celého řetězu – nechytila žádná, ačkoli se porovnávalo všech 107 entit. Proč, se dalo změřit: z 1 932 buněk přes všech 27 místností levelu je sdílených 137 a těch dvanáct entit, kvůli kterým by otázka mohla odpovědět „ano“, v žádné z nich nestojí. V rozehrané hře se tedy vždycky odpoví „ne“ a všechny tři chyby mění jen „ano“. Rutina se volá tisíckrát, pokrytí řádků je úplné – a rozbít se dá jen odpověď, ke které se nikdy nedojde.

Kontrola se jí proto ptá napřímo: 27 místností × 107 entit × 48 argumentů, a vyjde z toho 2 048 odpovědí „ano“ tam, kde 400 tiků hry nevyrobilo ani jednu. Padne na ní všech sedm sabotáží. Na Z80 přitom nejde seznam dotazů, jen tvar procházky – sedmadvacetibajtová tabulka místností a dvě počítané smyčky –, a obě strany ji projdou ve stejném pořadí. Cestují jen odpovědi.

Jednu chybu tohohle druhu ale krokování našlo samo, protože v ní bylo naopak „ano“ všude. Rutina, která porovnává sousedy, vrací odpověď v příznaku nuly, NZ znamená ano – a po porovnání stálo ret nz. Čte se to jako „liší se, končím“, jenže vrací příznak, který znamená ANO. Odpovídala tedy kladně vždycky a entita, která se ptá, co stojí vedle ní, brala přechod každý tik, kdy tam nestálo nic. V jedné instrukci jsou dvě věci – jestli se vrací a co se vrací – a čte se jen ta první. Oba výstupy jsou teď vypsané zvlášť.

A ani zelená přímá kontrola ještě neznamená pokrytí. Když Conrad dostal zbraň, přibylo naráz 43 opkódů a přímá kontrola, která se jich ptá na 88 místech – 237 776 dotazů, 48 390 kladných odpovědí –, prošla napoprvé. Pak jsem do kódu pustil osmnáct schválných chyb a pět jich prošlo. Díry měly tvary, které se budou opakovat: změny, které se vyruší (skript posune výtah o −2, 0 a +2 a výsledek je stejný, ať se náklad hýbe, nebo ne), stav, který v datech nenastane (nikdo neměl v inventáři to, co se má odebrat), a argument, při kterém se větve liší, jenže v datech není. Dnes kontrola chytí všech osmnáct a počet chycených sabotáží se píše do commitu.

Tik, který se vejde do snímku

Flashback tiká třicetkrát za sekundu a Next kreslí padesát snímků za sekundu. Ta čísla se nedělí a tik každý druhý snímek by celou hru zpomalil o šestinu. Hlavní smyčka proto každý snímek přičte k počítadlu 30, a když dosáhne padesáti, padesát odečte a odtiká – přesně třicet tiků v každých padesáti snímcích. Tiky ale přicházejí jeden nebo dva snímky po sobě, takže tik se musí vejít do jednoho snímku, do 20 ms. Který se nevejde, bere snímky dva.

V místnosti 28 prvního levelu, té se dvěma malými roboty, hra běžela na 62 %: tik trval 25 ms. Profiloval jsem na rastru: každá fáze tiku se měří v řádcích obrazu po 64 mikrosekundách emulovaného času, takže na rychlosti počítače, na kterém emulátor běží, nezáleží. A vyšlo něco, co bych netipoval: roboti stojí stejně jako Conrad. Čas nežraly entity, ale pevná režie kolem každé entity, která je vzhůru – a v té místnosti jich je patnáct. Kopírování entity do pracovních proměnných byla smyčka nad tabulkou polí, 3 400 taktů tam a stejně zpátky; rozvinutá ze stejného seznamu polí je kolem šesti set. Mapa sdílených buněk hledala každou buňku přes všechny záznamy před ní, 250 taktů na záznam, teď kolem osmdesáti. Kolizní tabulky leží na hranicích 256 bajtů, takže se sto dvacet volání pomocné rutiny změnilo na dvě instrukce, spící entita se přeskočí pěti instrukcemi a vzory spritů jdou do portu přes DMA.

Místnost 28 z 25,0 na 13,3 ms, místnost 27 z 18,9 na 9,6, nejtěžší místnost levelu (55) z 24,0 na 17,3. Každá změřená místnost teď tiká plnou rychlostí a engine se přitom o 350 bajtů zmenšil. Šest schválných rozbití těch zrychlení chytí kontroly všech šest – optimalizace, která mění chování, je jen jiný druh chyby.