14/11/21

David Crane, Pitfall a 4K

 V roce 1982, kdy se do popředí začínaly tlačit osmibitové počítače vybavené desítkami kilobajtů paměti, zde stále bylo staré dobré Atari 2600 s jeho 128 bajty RAM v I/O čipu a až (!) 4 kilobajty ROM v cartridge. Jedna z nejprestižnějších firem vydávající hry pro tuto konzoli – americká Activision, rozhodla zrealizovat koncept „běžícího muže“ jednoho z jejích nejtalentovanějších programátorů, a zároveň spoluzakladatele, Davida Crane. Hra Pitfall fascinovala na tehdejší poměry obrovským světem džungle, který se skládal z 255 místností. To vše na holém Atari VCS a standardní 4 kB cartridge. Pojďme se nyní podívat, jak to filuta David dokázal.

Jedinou možností, jak reprezentovat rozsáhlý svět na tak limitovaném hardware, bylo neukládat jej celý do paměti, ale naživo vytvářet kódem v průběhu hry. Dnes bychom toto asi nazvali procedurálním generováním (procedural generation). David Crane jakožto všichni programátoři Atari 2600 byl navyklý na velké limity konzole a trénovaný ždímat veškerý potenciál za hranice představivosti. Každý bajt paměti měl cenu zlata a nepřicházelo do úvahy jakékoliv plýtvání s jakýmkoliv bitem.

Pitfall jako hra se odehrává pouze v horizontální perspektivě a je možno jít oběma směry. Crane se rozhodl, že každá obrazovka bude reprezentována jako jedno osmibitové číslo, tedy bajt. Jeden a tentýž bajt v paměti, který popisuje, co se nám vykreslí za scénu. Bajt může z principu jakožto jednotka vždy nabývat hodnot od 0 do 255 a každé toto decimální číslo je reprezentováno jako kolekce 8 bitů. Bity nejsou nic jiného než elementární jednotky počítačové paměti, které odpovídají stavu elektrického signálu 0 = vypnuto, 1 = zapnuto. Bajt velikosti 0 bude mít kolekci osmi nulových bitů. Bajt s hodnotou 255 kolekci osmi bitů s hodnotou 1.


Crane vylaboroval vlastní rutinu, která stručně řečeno generuje pevně danou sekvenci 255 hodnot s hodnotami 196, 137, 18, 37, 75 atd. Při pohybu místnostmi doprava posune bity v našem „obrazovkovém“ bajtu doleva, a navíc na bitech 3, 4, 5 a 7 s výstupem do bitu 0 provede tzv. XOR neboli exkluzivní OR, což je v podstatě operace kdy dvě stejné hodnoty vždy končí výstupem 0, různé hodnoty pak jedničkou. Tento algoritmus navíc vytvoří každou kombinaci 8 bitů s výjimkou všech nul – proto 255 místností protože vypadává možnost s hodnotou 0. Základ úspěchu byla však rutina druhá, která se použije pro pohyb doleva. Tato v podstatě provádí přesný opak té první a bity jsou naopak posunuty doprava, resp. se navrací na hodnotu jaká by byla na pozici předešlé – nezapomínejme, že se neprovádí jen posun bitů ale i XOR operace jejíž výsledek plní bit 0. Tím je zajištěno to nejdůležitější: že jsme vždy schopni v obou směrech jít po stejné posloupnosti hodnot, a tedy náš svět je napevno definován. Tedy, téměř. Jinde v kódu je ošetřeno, kde se má např. zobrazit zeď, a samozřejmě je také v paměti nutné definovat samotné objekty, které se budou zobrazovat.


Jak už jsme si uvedli, hra používá jeden bajt, jehož hodnota rozhoduje o tom, co se v dané místnosti zobrazí. Zde vidíme na schématu rozdělení bajtu na 3 resp. 4 sekce: bity 0-2 určují, jaké objekty mohou být zobrazeny, bity 3-5 pak rozhodnou o tom, jaký typ jámy a překážky bude stát hrdinovi v cestě, bity 6-7 slouží pro výběr pozadí se stromy a bit 7 navíc zda bude případná zeď zobrazena vlevo či vpravo.


Suma sumárum je spotřeba tohoto geniálního postupu paměťově tak nízká, že se hra s 255 místnostmi vlezla do pouhé 4 kB cartridge, bez potřeby bank switchingu. Otázkou zůstává, jak zábavná je hra, která možná až příliš striktně drží všechny objekty na stejném místě, kde by možná neškodilo trochu více náhodné volby. Buď jak buď, Pitfall byl revoluční a jeho následovník Pitfall II Lost Caverns, již s využitím bank switchingu, přinesl násobně rozmanitější svět.


A teď si představte, že máte k dispozici počítač s 65 536 bajty, anebo 67 108 864, anebo… no raději stop. Možná nebudu daleko od pravdy, když pronesu, že dnešní hry jako No Man’s Sky více či méně používají podobnou filozofii jak dostat do omezeného paměťového prostoru neomezené světy. Jak neomezené nebo naopak omezené jsou, samozřejmě záleží na představě programátorů a celkové implementaci. Myslím si, že v budoucnu bude význam procedurálního generování nadále stoupat, aby tak nahradil neúměrně vysoké nároky na lidskou sílu při tvorbě nejen herních světů.


Odkazy:

10 comments:

  1. ... v 48 KB spectre bez dohravania bezi cele Sim City tak ako ho poznate na 16 bitoch .. berte to ako referencny bod ako vyzera jeden z prikladov nesmierne efektivneho kodingu.

    ... aj dnes /alebo prave dnes/ sa na 8 bitoch pouziva ultra low level asm kodovania s vyuzitim uplne bizarnych trikoch, je to state of the art sucasneho kodingu .. nic z toho sa neda aplikovat na moderne engines.

    ... sef timu co stoji za Unreal enginom niekolko krat povedat, ze musime akceptovat ze bezne 1/4 vykonu HW leti hore kominom vymenou za komfort pri high level tvorbe kodu .. proste raketoplan nie je mozne postavit ako lietadlo s vrtulkou na gumicke .. alebo inak .. nie je mozne aby pri stavbe raketoplanu JEDEN clovek riadil a schvaloval, kontroloval KAZDY proces, musite tu moc delegovat na desiatky inych borcov.

    ... ked vidim napriklad dnes Returnal na UE na PS5 ako sa tam trapi na 1080p60, tak mi je jasne, ze minimalne 50-100% vykonu islo okamzite do odpadu, je to ako programovat spectrum v cecku alebo v kompilovanom basicu.

    ... ak chcem vidiet ako sa to ma robit musim pozerat na low end stroje ako 8 bity alebo 2060ka


    ReplyDelete
    Replies
    1. Sim City ale předpokládám drží v paměti celou mapu, protože si musí pamatovat co jsi kde postavil nebo zbořil. To Pitfall řešit nemusí, kromě posbíraných pokladů. Článek je ale spíše o tom, že generovat věci se dají bez potřeby je vůbec někde ukládat...

      Delete
  2. ... iste .. tie clanky uz nenajdem ale nejaky cesky textovkar na spektre vysvetloval ako dostat do enginu textovky 999 miestnosti .. bit na vychody, bit na popis veci, bit na hento, bit na tamto .. hovori, ze keby to mal ukladat ako "bitmapu" .. teda miestnost = halda textu, tak je to grecka hra o jednom dejstve, heheh.
    ... a ten iny ftak je 3D Sentinel .. takmer nekonecne more generovanej grafiky.

    ReplyDelete
    Replies
    1. A potenciál generování za chodu znamená že můžeš mít lokaci vždy trochu jinak, což teda Pitfall nedělá, ale copak je to za zábava když procházím furt dokola ty samé lokace...

      Delete
    2. ... som uplne isty, ze dnes by sme vedeli kod upravit ku randomizacii a diera v zemi by mohla byt napr. na 8 roznych miestach.

      Delete
    3. Už se myslím i stalo! Viděl jsem na Atariage vlákno, kde Thomas Jenstzsch (guru který Pitfall disassembloval) vykoumal 256 map....

      Delete
  3. Replies
    1. ... tu to mas maiki, co som spominal .. mne to pripomina "datovu" formu tilesetu namiesto bitmapy .. alebo ako rozdiel medzi midi setom a plne samplovanou hudbou.

      Delete
    2. ... prvykrat co ten loading screen vidim.

      Delete

**** pre vloženie hypertextového odkazu do komentára použi CSS kód: hyperlink ****