Flashback na ZX Spectrum Next – 1. Cutscény

Proč zrovna cutscény a co to vlastně je

Cutscény jsou poměrně uzavřený kus hry a současně se v nich potkává skoro všechno, co je na podobném portu zajímavé: čtení původních dat, interpretace jednoduchého programu, převod souřadnic, body, čáry, elipsy, vyplněné polygony, palety, stránkování paměti, přepínání obrazovek i výkon. Výsledek je navíc okamžitě vidět, což je trochu past – postava se hýbe přibližně správně a mozek už hlásí „hotovo“. Jenže u vektorové animace stačí jeden pixel mimo na hraně polygonu a obraz začne jemně cukat, špatná barva znamená probliknutí celé plochy a chybně obnovené pozadí stopu po minulém snímku.

A hlavně: cutscény ve Flashbacku nejsou série bitmap. Jsou to vektorové animace složené z barevných ploch, což je taky jediný důvod, proč se jich všech devětadvacet vejde do necelých čtyř set kilobajtů. Kdyby to byly obrázky, bavíme se o desítkách megabajtů a celý díl by skončil dřív, než by začal.

Co je v těch souborech

Každá scéna má dva soubory. .CMD je program a .POL je zásoba tvarů, ze které kreslí. Program je překvapivě malý: celý interpret má patnáct příkazů a bajt příkazu nese své číslo v bitech 2 až 7, takže se stream čte po bajtech a posouvá o dva doprava. Bajt se sedmým bitem scénu ukončí. Příkazy umí vyčistit obrazovku, nahrát paletu, nakreslit tvar (volitelně zvětšený nebo otočený), počkat, zobrazit hotový snímek, vypsat text a odskočit podle kláves. Na začátku souboru je slovo s počtem vstupních bodů a vlastní programy začínají až za tabulkou, tedy na offsetu (počet + 1) × 2.

Zrádné je, že tři z těch patnácti příkazů nemají pevnou délku operandů. Otočený tvar nese zvětšení a dva ze svých tří úhlů jen tehdy, když to řeknou příznakové bity ve slově tvaru. Polohovaný text čte dva bajty pozice, ale jen pokud identifikátor řetězce není 0xFFFF. A obsluha kláves prochází tabulku dvojic až po ukončovací bajt 0xFF – za kterým už žádný cíl skoku není, na rozdíl od všech ostatních položek. Číst kteroukoli z nich pevnou délkou znamená být o bajt nebo dva vedle a od té chvíle se každý další bajt interpretuje jako něco jiného. Přehrávač přitom ještě dlouho něco kreslí, takže chyba vypadá kreativně a pošle vás hledat úplně jinam: mně takhle úvodní scéna DEBUT ujela 1391 bajtů, než narazila na něco, co už nešlo dekódovat vůbec.

Geometrie v .POL je postavená na tabulkách. Hlavička souboru je pět big-endian offsetů na pevných místech: na 0x02 tabulka offsetů tvarů, na 0x06 palety, na 0x0A tabulka offsetů seznamů vrcholů, na 0x0E data tvarů a na 0x12 data vrcholů. Tvar je číslo – z něj se přes první tabulku dostanu na jeho data, kde je počet částí a pak tolik záznamů. Každý záznam je číslo seznamu vrcholů (jeho horní bity jsou příznaky: 0x8000 znamená „nesu si vlastní posun jako dvě slova“, 0x4000 „tahle část se míchá s pozadím“), volitelně ten posun a nakonec bajt barvy. Barva se zvýší o šestnáct, když obrazovka není v čisticím režimu – tak jedna sada dat nakreslí jednou pozadí a podruhé pohyblivé části v jiných šestnácti barvách.

A teprve pod tím je vlastní obrazec, jehož první bajt je počet vrcholů a zároveň přepínač. Má-li sedmý bit, jde o elipsu – střed a dva poloměry, čtyři big-endian slova. Je-li nula, jde o jediný bod, dvě slova. Jinak je to polygon: první vrchol jako dvě slova a každý další už jen jako dvojice znaménkových bajtů, tedy rozdíl proti předchozímu. Právě tohle drží velikost dole – celá úvodní scéna má 13 644 bajtů geometrie. A je tam jedno pravidlo, které vypadá jako detail a není: běh čistě vodorovných kroků splyne v jeden vrchol. Když má dvojice nulové dy a ta následující taky, souřadnice se posune a žádný vrchol se nevytvoří. Počáteční bajt tedy není počet bodů, které vylezou. Zabírá to jen na 1,70 % polygonů, které hra kreslí – 2207 ze 129 903 – ale bez něj dostane vyplňovač víc vrcholů, než má, a hrany skončí jinde.

Do čeho to ukládáme my

Tady je možná nejzajímavější rozhodnutí celého dílu: cutscény neukládáme do ničeho vlastního. Místnosti, sprity, kolizní mřížky i objektové skripty se na PC převádějí do formátů ušitých Nextu na míru – místnost se třeba přeskládá do sloupcového pořadí, které chce Layer 2, aby se dala nasypat na obrazovku osmi přímými kopiemi. U cutscén jsem po dlouhém uvažování neudělal nic z toho. .POL i .CMD jdou do sestavení bajt po bajtu tak, jak jsou, rozsekané jen do 8KB stránek, a Z80 čte původní tabulky za běhu.

Důvod je prostý: rozbalit ty tabulky předem by data zvětšilo. Formát je už tak hustý, opakovaně používá stejnou geometrii s jinou polohou a barvou, a nepřímost stojí pár instrukcí. Předpočítat by se vyplatilo jen tehdy, kdyby Z80 trávil hledáním víc času než kreslením – a měření říká, že tráví. Kreslení je přes devadesát procent, hledání pod deset.

Cenou za věrnost je stránkování, protože soubory jsou větší než jakékoli okno, které Z80 může mít otevřené. Geometrie dostala 16KB okno ze dvou stránek posouvané tak, že stránka, do které offset patří, je z těch dvou první – záznam pak smí přesáhnout o celých 8 kB, aniž vypadne z konce, a nic v tomhle formátu se tomu ani nepřiblíží. Program dostal jednu 8KB stránku a čte se po bajtech, takže slovo přes hranici stránky jsou prostě dvě čtení. Stránka se přemapuje jen tehdy, když se opravdu mění, což při procházení jednoho tvaru znamená obvykle vůbec. Bez toho by se největší scény ani nenačetly: INTRO1 má 57 813 bajtů geometrie a VOYAGE 21 881 bajtů programu.

Palety jsou jediné místo, kde k převodu skutečně dochází, a je triviální: šestnáct položek po dvanácti bitech ve tvaru 0RGB jako big-endian slova, z nichž každá složka při cestě do devítibitové palety Layeru 2 ztratí spodní bit. Obraz sám drží indexy nula až 31, ne barvy, takže se paleta může měnit mezi snímky a nic se nepřekresluje.

Reference dřív než assembler

Než jsem začal psát jedinou instrukci, napsal jsem si referenční přehrávač na PC. Čte stejná data, interpretuje stejné příkazy a umí vypsat vrcholy, vodorovné úseky, paletu i celé obrazové buffery. Není to demo – je to měřicí přístroj. Stejný vstup projde referencí i verzí pro Z80 a porovnávají se konkrétní čísla nebo bajty, ne dojmy. Obrázek je dobrý pro oko, ale jako jediný test je mizerný: řekne, že je něco jinak, ne kde vznikl první rozdíl.

Dneska na tom stojí sedm kontrol, každá nad svou vrstvou – od pevné řádové čárky přes seznamy vodorovných úseků a jejich zápis do Layeru 2 až po celé snímky scény porovnané bajt po bajtu. Když sáhnu do rychlé části rendereru, nemusím zírat na animaci a doufat, že si všimnu probliknutí. A protože Z80 v emulátoru neumí nic vypsat, výsledky si zapisuje na kartu přes esxDOS a porovnávají se na PC. U pevné řádové čárky by mi screenshot stejně neřekl, kde se to rozchází.

Přibližně správná aritmetika nestačí

Nejvíc času mi nevzalo rozluštění dat, ale přesné napodobení aritmetiky původního rendereru. První verze používala běžný scanline polygon, klasického Bresenhama a obvyklou elipsu z odmocniny. Staticky to vypadalo skoro stejně – jenže „skoro“ je u animace přesně ten rozdíl, který bliká. Když jsem si obě varianty nechal porovnat úsečku po úsečce, vyšlo, že 23 % čar kreslí jiné pixely, v nejhorším případě o padesát. U elipsy se lišilo 745 řádků z 1365, až o čtrnáct pixelů. Přitom hra za jeden běh všech scén nakreslí 730 824 bodů, 72 094 polygonů, 57 809 čar a 5 744 elips – na takových počtech se „skoro“ pozná.

Hrany polygonů se počítají v pevné řádové čárce 16.16, takže na Z80 vzniká dost 32bitové znaménkové aritmetiky, a zvlášť záporné hodnoty jsou zábavné. Dělení směrem k nule a aritmetický posun doprava nedávají stejný výsledek; u kladných čísel si toho nevšimnete, u záporného sklonu si polygon vybere sousední pixel. Dělení je proto znaménko a velikost – absolutní hodnoty, nezaznaménkové dělení, negace na konci – protože to je ořezávání k nule. A porovnání, které rozhoduje o větvi, musí být znaménkové: sbc nastavuje carry podle nezaznaménkové výpůjčky a dy je stejně často záporné jako kladné, takže čtení carry by vybralo špatnou větev pro každou hranu mířící vzhůru. Tuhle chybu jsem si mimochodem o dvě stě řádků níž zopakoval, přestože jsem k ní o kus výš měl napsaný odstavec komentáře.

Obrazovka, okraje a co se opravdu láme

Cutscéna má 256 × 224 bodů a Layer 2 v režimu 320 × 256 ukládá obraz po sloupcích, což pro vodorovnou výplň vypadá jako naschvál – sousední pixely na obrazovce nejsou sousední bajty v paměti. Ukázalo se to ale skoro jako nejlepší případ: spodní bajt adresy je řádek a ten se podél vodorovného úseku nemění, takže krok na další pixel je jediné inc h. Jedenáct taktů na pixel, žádná adresní aritmetika. Geometrie navíc vyšla hezky, protože obraz sedí 32 pixelů zleva a 16 shora a 32 sloupců je přesně jedna 8KB stránka.

Kreslím do tří ploch – přední, zadní a pomocné pozadí. Zobrazení hotového snímku je jediný zápis do registru: NR_12 říká, ze které 16KB banky Layer 2 čte, takže ukázat právě dokreslenou plochu nestojí nic. Původně jsem místo toho kopíroval 64 kB na obrazovku, což bylo 1,37 milionu taktů na snímek, tedy 49 ms skutečného Nextu. Velké přesuny, které zbyly, dělá zxnDMA – dva takty na bajt proti jedenadvaceti u LDIR.

A právě na hranicích těchhle částí vznikají ty nejhorší chyby, ne uvnitř složitých rutin. Dvě za všechny. První: vyčištění plochy pracovalo s celými 8KB stránkami, tedy 256 řádky na sloupec, jenže obraz jsou řádky 16 až 239 – takže mi šestnáct řádků nad obrazem a šestnáct pod ním drželo barvu nula scény místo okrajové. Šířka správná, okraj špatně. Druhá byla tři řádky dlouhá a stála celou animaci: rutina na čtení slova z programu odkládala první bajt do registru D, jenže následující čtení bajtu začíná naplněním DE ukazatelem, takže ho pokaždé přepsalo. Počet položek se přečetl jako nula, interpret začal dva bajty do souboru, přečetl kus tabulky offsetů jako příkazy a po osmadvaceti bajtech to vzdal. Výsledek: jeden nehybný obrázek ze dvou tvarů a scéna, která se netváří jako chyba, ale jako by prostě nic nedělala.

Nenašel jsem to úvahou. Třikrát po sobě jsem uhádl špatné místo, tak jsem nakonec do interpretu přidal počítadlo pro každý z těch patnácti příkazů a nechal si ho vysypat na kartu. Jeden běh a bylo jasno. Od té doby je to v kódu natrvalo za přepínačem.

Optimalizoval jsem až podle měření – a stálo to za to

Jakmile byl výsledek přesný, začal jsem měřit, a to tak, že jsem jednotlivé fáze kreslení postupně vypínal. Vyšlo, že zhruba polovina času padne na procházení hran a vodorovných úseků, víc než čtvrtina na jejich zápis do paměti, desetina na dekódování vrcholů a zbytek na čáry a elipsy dohromady. Samotné dělení v pevné řádové čárce spolykalo pětinu celého kreslení. Měřit je přitom potřeba na nižší frekvenci, protože emulátor na 28 MHz nestíhá – tentýž build běžel proti 3,5 MHz jen 4,7krát rychleji místo osmi, takže část toho, co člověk vidí, je emulátor, ne port.

Jedna úprava zabrala: dělenec je dx × 256, kde dx je rozdíl dvou vrcholů, takže hodnota je skoro vždycky pod 65 536 – ale smyčka jela 32 kroků bez ohledu na to a šestnáct z nich jen zasouvalo nuly a ani jednou neodečetlo. Posunout hodnotu o bajt nahoru a ubrat osm kroků za každý je totéž za poloviční práci, což dělá devět procent celého kreslení. A dvě úpravy nezabraly vůbec: rozvinutí 32bitového sčítání a vypsání vnitřní smyčky místo volání daly obojí rozdíl na úrovni šumu. To je podstatnější než ten zisk, protože dvě nezávislá měření říkají totéž – procházení úseků netráví čas per-řádkovou aritmetikou, a kde ho tráví, zatím nevím. Příště to rozřežu uvnitř, ne kolem.

Bez měření bych optimalizoval něco efektního a nedůležitého. S měřením mám jeden skutečný zisk, dva poctivé neúspěchy a docela přesnou představu, kam se dívat dál – a to je lepší výchozí pozice než pocit, že „to bude tím dělením“.