Het artikel beschrijft de technische verkenning en implementatie van het Entombed-algoritme, een unieke methode voor het procedureel genereren van doolhoven uit het Atari 2600-spel Entombed (1983). Vanwege de extreme geheugenbeperkingen van de Atari 2600 (128 bytes RAM) genereert het algoritme het doolhof regel voor regel op basis van een opzoektabel en lokale celinformatie, zonder garanties over de oplosbaarheid van het doolhof.
De auteur heeft dit algoritme toegepast in een eigen project: een raycaster (geïnspireerd op Wolfenstein 3D). Na een initiële implementatie in C, is er ook een browserversie gemaakt met Three.js, waarbij de visuele stijl is aangepast naar een 'Backrooms'-thema.
Entombed in a Raycaster
Ongeveer een jaar geleden (misschien langer, mijn geheugen is soms wat selectief) ging ik door het ritueel waar bijna elke game-ontwikkelaar doorheen gaat: de raycaster. Ik bestudeerde de tutorial van Lode en keek naar de 'Make Your Own Raycaster'-serie op YouTube van 3DSage (beide zeer aanbevolen), toen ik stuitte op het Entombed-algoritme. Dit is een algoritme voor het genereren van doolhoven dat werd gebruikt in het Atari 2600-spel Entombed (1983), waarin de speler moet ontsnappen uit een doolhof terwijl hij wordt achtervolgd door zombies.
Wat mij intrigeerde aan dit algoritme is dat het doolhof procedureel werd gegenereerd op basis van een oude (inmiddels bijna arcane) logica. Deze logica bepaalde hoe de volgende regel werd gegenereerd, terwijl er strikt rekening werd gehouden met de beperkingen van de Atari 2600.
De Atari 2600 heeft slechts 128 bytes (ja, bytes) RAM. In Entombed scrolt het doolhof continu omhoog terwijl de speler er naar beneden loopt. Dat betekent dat het opslaan van een volledig doolhof praktisch onmogelijk is, gezien de geheugenbeperkingen van het apparaat. Het doolhof moet dus regel voor regel worden gemaakt en worden weggegooid zodra het uit beeld scrolt. Dit roept de vraag op: hoe bouw je een doolhof regel voor regel, als je slechts een handvol regels in het geheugen kunt houden? Hier komt de mysterieuze tabel om de hoek kijken.
De werkelijke reden dat Entombed de interesse van game-archeologen heeft gewekt, is de mysterieuze tabel achter de generatie van het doolhof, en het feit dat tot op de dag van vandaag niemand volledig heeft kunnen uitleggen waarom het werkt. Jarenlang ging het verhaal dat het was geschreven door iemand die "dronken was en compleet uit zijn plaat ging". Het blijkt dat het echte verhaal daar niet ver van afstaat: Paul Allen Newell en Duncan Muirhead, een student wiskunde, schetsen het op servetten tijdens een paar biertjes in een bar. Newell had het aan het einde van het weekend werkend op de Atari.
De mapping van de mysterieuze tabel die wordt gebruikt voor de doolhofgeneratie van Entombed. Aycock, J. and Copplestone, T. 2019. Entombed: An archaeological examination of an Atari 2600 game. The Art, Science, and Engineering of Programming 3(2). doi:10.22152/programming-journal.org/2019/3/4. CC BY 4.0.
Hoe de logica werkt
Zo werkt de logica: elke cel van het doolhof wordt gegenereerd op basis van vijf buren: twee cellen links ervan in dezelfde rij, en drie cellen uit de rij erboven. Deze vijf bits vormen een index van 0 tot 31 in de bovenstaande opzoektabel, die vervolgens een muur (1), een doorgang (0) of een muntworp (willekeurig) teruggeeft. En dat is alles. Geen backtracking, geen zoekacties: de rij wordt in één beweging gevuld, waarbij een tetromino-achtig venster cel voor cel over de rij schuift.
De manier waarop een cel wordt gegenereerd. Newell, P.A., Aycock, J. and Biittner, K.M. 2022. Still Entombed After All These Years: The continuing twists and turns of a maze game. Internet Archaeology 59. doi:10.11141/ia.59.3. CC BY 3.0.
Men zou zo ver kunnen gaan het algoritme te karakteriseren als een cellulair automaat, maar volgens Paul Allen Newell, John Aycock en Katie M. Biittner:
"Het algoritme laat zich niet eenvoudig categoriseren en is wellicht uniek. Vanwege de afhankelijkheid van enkel lokale informatie is het verleidelijk om het algoritme te zien als gebaseerd op cellulaire automaten (Sarkar 2000), maar het gebrek aan parallellisme en de vreemde vorm van de 'buurt' van cellen rondom X maakt het concept van cellulaire automaten geforceerd."
Dit is vrijwel het tegenovergestelde van hoe doolhof-algoritmen normaal gesproken werken. Meestal houd je het hele raster in het geheugen en garandeert het algoritme dat je eindigt met een doolhof dat daadwerkelijk oplosbaar is. Entombed ziet nooit meer dan elf regels tegelijk en garandeert helemaal niets. Het genereert simpelweg iets dat eruitziet als een doolhof.
Omdat er in het geval van Entombed geen garanties zijn, zijn er twee correctie-passes geïntroduceerd. Deze worden uitgevoerd zodra een regel voltooid is en kijken terug naar de regels daarachter: als het doolhof zichzelf is begonnen te herhalen of secties volledig heeft afgesloten, dan wissen ze de hele regel, of de helft ervan.
Implementatie in een Raycaster
Na het bestuderen van alle referenties die ik kon vinden, begon ik direct na te denken over manieren om deze logica te implementeren in een raycaster! Dit bleek een erg leuk zijproject te worden, waarbij het leren over de details van raycasting en het maken van een eenvoudige Wolfenstein 3D-renderer werd gecombineerd met de uitzondering dat de kaart procedureel gegenereerd moest worden door logica uit dit oude Atari-spel.
Ik heb besloten de status van elke rij van het doolhof te representeren als een uint32, waarbij elke bit aangeeft of er een muur is of niet. Dit zou de berekeningen vereenvoudigen en het geheugenefficiënt maken naarmate het doolhof groeit terwijl de speler verder naar binnen loopt.
Gameplay van Entombed, opgenomen via Archive.org. Let op de symmetrie: slechts de helft van het speelveld wordt gegenereerd, de rest is een spiegelbeeld.
Mijn versie verschilt op een paar punten van het origineel: ik heb de spiegeling (te zien in de bovenstaande screenshot) weggelaten, het speelveld verbreed naar 30 cellen, en ik gooi regels nooit weg zodra ze zijn gegenereerd, aangezien geheugen tegenwoordig geen probleem is (of is dat wel?).
Ook heb ik de speler en de vijanden de mogelijkheid gegeven om de muren voor hen te slopen. In theorie zou dit teruggekoppeld kunnen worden naar de doolhofgeneratie, maar in de praktijk gebeurt dit nooit: regels worden ver genoeg vooruit gegenereerd dat de generator allang voorbij is op het moment dat je iets sloopt.
Het grappige is dat ik onlangs besefte dat het originele spel de spelers ook dezelfde mogelijkheid om muren te slopen bood. Dat is logisch, want je moet spelers een gemakkelijke manier bieden om uit doodlopende wegen te komen... vooral als je wordt achtervolgd door mysterieuze entiteiten.
Ik heb de C-implementatie gebaseerd op die van 3DSage en enkele edge-cases opgelost waarbij de speler en de vijanden vast konden komen te zitten. Over het algemeen was het een zeer leuke en unieke ervaring.
Nadat ik het werkend had gekregen, ben ik het eigenlijk vergeten. Een paar weken geleden, na het kijken naar de 'Backrooms'-film, werd ik herinnerd aan dit korte experiment. Ik dacht dat ik het kon opfrissen, enkele kleine problemen kon oplossen, het kon stylen als een 'Backrooms'-achtig spel en het aan de wereld kon laten zien.
Als kers op de taart heb ik Claude gevraagd om een Three.js-versie ervan te schrijven die in de browser speelbaar is met wat extra effecten (ik heb mijn best gedaan om een Diablo-achtige minimap na te maken), voor het geval je geen zin hebt om een C-game op je machine te compileren en uit te voeren.
De Three.js-variant van de Entombed raycaster.
Hoe ver kun jij komen voordat je 'entombed' (gevangen) raakt?
Referenties
- Wikipedia artikel over het Atari-spel Entombed
- Het eigenlijke Atari 2600 Entombed spel, speelbaar in Archive.org
- Explaining the Entombed Algorithm door Leon Mächler en David Naccache
- Still Entombed After All These Years: The continuing twists and turns of a maze game door Paul Allen Newell, John Aycock en Katie M. Biittner
- Entombed: An archaeological examination of an Atari 2600 game door John Aycock en Tara Copplestone
- BBC: The mysterious origins of an uncrackable video game
- Interview met Steven Boykey Sidley over Entombed door John Aycock
Entombed in a Raycaster
Ongeveer een jaar geleden (misschien langer, mijn geheugen is soms wat selectief) ging ik door het ritueel waar bijna elke game-ontwikkelaar doorheen gaat: de raycaster. Ik bestudeerde de tutorial van Lode en keek naar de 'Make Your Own Raycaster'-serie op YouTube van 3DSage (beide zeer aanbevolen), toen ik stuitte op het Entombed-algoritme. Dit is een algoritme voor het genereren van doolhoven dat werd gebruikt in het Atari 2600-spel Entombed (1983), waarin de speler moet ontsnappen uit een doolhof terwijl hij wordt achtervolgd door zombies.
Wat mij intrigeerde aan dit algoritme is dat het doolhof procedureel werd gegenereerd op basis van een oude (inmiddels bijna arcane) logica. Deze logica bepaalde hoe de volgende regel werd gegenereerd, terwijl er strikt rekening werd gehouden met de beperkingen van de Atari 2600.
De Atari 2600 heeft slechts 128 bytes (ja, bytes) RAM. In Entombed scrolt het doolhof continu omhoog terwijl de speler er naar beneden loopt. Dat betekent dat het opslaan van een volledig doolhof praktisch onmogelijk is, gezien de geheugenbeperkingen van het apparaat. Het doolhof moet dus regel voor regel worden gemaakt en worden weggegooid zodra het uit beeld scrolt. Dit roept de vraag op: hoe bouw je een doolhof regel voor regel, als je slechts een handvol regels in het geheugen kunt houden? Hier komt de mysterieuze tabel om de hoek kijken.
De werkelijke reden dat Entombed de interesse van game-archeologen heeft gewekt, is de mysterieuze tabel achter de generatie van het doolhof, en het feit dat tot op de dag van vandaag niemand volledig heeft kunnen uitleggen waarom het werkt. Jarenlang ging het verhaal dat het was geschreven door iemand die "dronken was en compleet uit zijn plaat ging". Het blijkt dat het echte verhaal daar niet ver van afstaat: Paul Allen Newell en Duncan Muirhead, een student wiskunde, schetsen het op servetten tijdens een paar biertjes in een bar. Newell had het aan het einde van het weekend werkend op de Atari.
De mapping van de mysterieuze tabel die wordt gebruikt voor de doolhofgeneratie van Entombed. Aycock, J. and Copplestone, T. 2019. Entombed: An archaeological examination of an Atari 2600 game. The Art, Science, and Engineering of Programming 3(2). doi:10.22152/programming-journal.org/2019/3/4. CC BY 4.0.
Hoe de logica werkt
Zo werkt de logica: elke cel van het doolhof wordt gegenereerd op basis van vijf buren: twee cellen links ervan in dezelfde rij, en drie cellen uit de rij erboven. Deze vijf bits vormen een index van 0 tot 31 in de bovenstaande opzoektabel, die vervolgens een muur (1), een doorgang (0) of een muntworp (willekeurig) teruggeeft. En dat is alles. Geen backtracking, geen zoekacties: de rij wordt in één beweging gevuld, waarbij een tetromino-achtig venster cel voor cel over de rij schuift.
De manier waarop een cel wordt gegenereerd. Newell, P.A., Aycock, J. and Biittner, K.M. 2022. Still Entombed After All These Years: The continuing twists and turns of a maze game. Internet Archaeology 59. doi:10.11141/ia.59.3. CC BY 3.0.
Men zou zo ver kunnen gaan het algoritme te karakteriseren als een cellulair automaat, maar volgens Paul Allen Newell, John Aycock en Katie M. Biittner:
"Het algoritme laat zich niet eenvoudig categoriseren en is wellicht uniek. Vanwege de afhankelijkheid van enkel lokale informatie is het verleidelijk om het algoritme te zien als gebaseerd op cellulaire automaten (Sarkar 2000), maar het gebrek aan parallellisme en de vreemde vorm van de 'buurt' van cellen rondom X maakt het concept van cellulaire automaten geforceerd."
Dit is vrijwel het tegenovergestelde van hoe doolhof-algoritmen normaal gesproken werken. Meestal houd je het hele raster in het geheugen en garandeert het algoritme dat je eindigt met een doolhof dat daadwerkelijk oplosbaar is. Entombed ziet nooit meer dan elf regels tegelijk en garandeert helemaal niets. Het genereert simpelweg iets dat eruitziet als een doolhof.
Omdat er in het geval van Entombed geen garanties zijn, zijn er twee correctie-passes geïntroduceerd. Deze worden uitgevoerd zodra een regel voltooid is en kijken terug naar de regels daarachter: als het doolhof zichzelf is begonnen te herhalen of secties volledig heeft afgesloten, dan wissen ze de hele regel, of de helft ervan.
Implementatie in een Raycaster
Na het bestuderen van alle referenties die ik kon vinden, begon ik direct na te denken over manieren om deze logica te implementeren in een raycaster! Dit bleek een erg leuk zijproject te worden, waarbij het leren over de details van raycasting en het maken van een eenvoudige Wolfenstein 3D-renderer werd gecombineerd met de uitzondering dat de kaart procedureel gegenereerd moest worden door logica uit dit oude Atari-spel.
Ik heb besloten de status van elke rij van het doolhof te representeren als een uint32, waarbij elke bit aangeeft of er een muur is of niet. Dit zou de berekeningen vereenvoudigen en het geheugenefficiënt maken naarmate het doolhof groeit terwijl de speler verder naar binnen loopt.
Gameplay van Entombed, opgenomen via Archive.org. Let op de symmetrie: slechts de helft van het speelveld wordt gegenereerd, de rest is een spiegelbeeld.
Mijn versie verschilt op een paar punten van het origineel: ik heb de spiegeling (te zien in de bovenstaande screenshot) weggelaten, het speelveld verbreed naar 30 cellen, en ik gooi regels nooit weg zodra ze zijn gegenereerd, aangezien geheugen tegenwoordig geen probleem is (of is dat wel?).
Ook heb ik de speler en de vijanden de mogelijkheid gegeven om de muren voor hen te slopen. In theorie zou dit teruggekoppeld kunnen worden naar de doolhofgeneratie, maar in de praktijk gebeurt dit nooit: regels worden ver genoeg vooruit gegenereerd dat de generator allang voorbij is op het moment dat je iets sloopt.
Het grappige is dat ik onlangs besefte dat het originele spel de spelers ook dezelfde mogelijkheid om muren te slopen bood. Dat is logisch, want je moet spelers een gemakkelijke manier bieden om uit doodlopende wegen te komen... vooral als je wordt achtervolgd door mysterieuze entiteiten.
Ik heb de C-implementatie gebaseerd op die van 3DSage en enkele edge-cases opgelost waarbij de speler en de vijanden vast konden komen te zitten. Over het algemeen was het een zeer leuke en unieke ervaring.
Nadat ik het werkend had gekregen, ben ik het eigenlijk vergeten. Een paar weken geleden, na het kijken naar de 'Backrooms'-film, werd ik herinnerd aan dit korte experiment. Ik dacht dat ik het kon opfrissen, enkele kleine problemen kon oplossen, het kon stylen als een 'Backrooms'-achtig spel en het aan de wereld kon laten zien.
Als kers op de taart heb ik Claude gevraagd om een Three.js-versie ervan te schrijven die in de browser speelbaar is met wat extra effecten (ik heb mijn best gedaan om een Diablo-achtige minimap na te maken), voor het geval je geen zin hebt om een C-game op je machine te compileren en uit te voeren.
De Three.js-variant van de Entombed raycaster.
Hoe ver kun jij komen voordat je 'entombed' (gevangen) raakt?
Referenties
- Wikipedia artikel over het Atari-spel Entombed
- Het eigenlijke Atari 2600 Entombed spel, speelbaar in Archive.org
- Explaining the Entombed Algorithm door Leon Mächler en David Naccache
- Still Entombed After All These Years: The continuing twists and turns of a maze game door Paul Allen Newell, John Aycock en Katie M. Biittner
- Entombed: An archaeological examination of an Atari 2600 game door John Aycock en Tara Copplestone
- BBC: The mysterious origins of an uncrackable video game
- Interview met Steven Boykey Sidley over Entombed door John Aycock
Groetjes,