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:

How Pitfall Builds its World

Pitfall Classic Postmortem With David Crane Panel at GDC 2011

Pitfall Walkthrough (All 32 Treasures & Kill Screen) Atari 2600