TL;DR

  • Atari 2600 게임 Entombed의 미스터리 테이블 알고리즘을 레이캐스터에 적용해, 한 줄씩 미로를 생성하는 게임을 구현함.
  • 알고리즘은 같은 줄의 왼쪽 두 칸과 윗줄의 세 칸, 총 5개 이웃 셀을 인덱스로 삼아 32개 항목 룩업 테이블에서 벽·통로·무작위 결과를 결정함.
  • 원작은 메모리 제약으로 한 번에 최대 11개 줄만 유지하며 미로의 해결 가능성을 보장하지 않고, 반복이나 구역 차단을 완화하는 보정 단계를 사용함.
  • 구현에서는 각 줄을 uint32 비트로 표현하고, 원작의 좌우 대칭을 제거해 30칸 너비로 만들었으며 생성된 줄을 보존함.
  • C 레이캐스터 구현과 효과를 추가한 Three.js 브라우저 데모를 제공함.

Entombed 알고리즘의 기원과 메모리 제약

  • 약 1년 전 레이캐스터 제작을 배우던 중, 1983년 Atari 2600 게임 Entombed에 쓰인 미로 생성 알고리즘을 접함. 참고 자료는 Lode의 튜토리얼과 3DSage의 유튜브 시리즈 ‘Make Your Own Raycaster’임.
  • Atari 2600에는 128바이트 RAM만 있으며, Entombed에서는 미로가 계속 위로 스크롤되는 동안 플레이어가 아래로 이동함. 메모리 제한 때문에 미로 전체를 저장하기 어려워 한 줄씩 생성하고 화면에서 사라지는 줄은 버려야 함.
  • 알고리즘의 핵심은 미스터리 테이블임. 다음 줄의 각 칸을 결정하는 오래된 규칙으로, Atari 2600의 제약 안에서 작동하도록 구성됨.
  • 여러 해 동안 테이블을 만든 사람이 술에 취해 정신이 나간 상태였다는 이야기가 돌았지만, 실제로도 Paul Allen Newell과 수학 대학원생 Duncan Muirhead가 술집에서 맥주를 마시며 냅킨에 알고리즘을 그렸고, Newell은 주말이 끝날 무렵 Atari에서 실행되도록 구현함.
  • 미스터리 테이블 도해 출처: 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.

한 줄씩 미로를 만드는 규칙

  • 각 미로 칸은 이웃한 다섯 칸으로 생성됨. 같은 줄에서 이미 채워진 왼쪽 두 칸과 바로 위 줄의 세 칸이 입력임.
  • 다섯 비트는 0부터 31까지의 룩업 테이블 인덱스를 만들며, 결과는 벽(1), 통로(0), 또는 무작위 선택임.
  • 역추적이나 탐색은 없으며, 테트로미노와 비슷한 모양의 창이 한 칸씩 이동하면서 줄 전체를 한 번에 채움.
  • 칸 생성 방식 도해 출처: 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.
  • 이 알고리즘을 셀룰러 오토마톤으로 볼 수도 있지만, Paul Allen Newell, John Aycock, Katie M. Biittner는 다음과 같이 설명함.

이 알고리즘은 쉽게 분류하기 어려우며 독특할 수도 있음. 국소 정보만 사용하므로 셀룰러 오토마톤에 기반한다고 볼 수 있지만, 병렬성이 없고 X 주변 셀의 ‘이웃’ 모양이 특이하므로 셀룰러 오토마톤이라는 해석은 억지스러움.

  • 일반적인 미로 알고리즘은 전체 격자를 메모리에 두고 해결 가능한 미로를 보장하는 반면, Entombed는 한 번에 최대 11개 줄만 살펴보며 해결 가능성을 전혀 보장하지 않고 미로처럼 보이는 구조를 생성함.
  • 미로가 반복되거나 일부 구역이 막히는 문제를 다루기 위해 줄 생성이 끝난 뒤 두 차례 보정 단계를 수행함. 문제가 발견되면 해당 줄 전체 또는 절반을 비움.

레이캐스터 구현

  • 알고리즘을 레이캐스터에 적용하는 프로젝트를 진행하며 레이캐스팅의 세부 사항을 익히고 간단한 Wolfenstein 3D 렌더러를 구현함.
  • 미로 각 줄의 상태는 각 비트가 벽 여부를 나타내는 uint32로 표현함. 이 방식은 계산을 단순하게 하고 플레이어가 더 멀리 이동할 때도 메모리를 효율적으로 사용함.
  • Archive.org에서 캡처한 원작 게임 화면에는 대칭성이 나타남. 플레이 영역의 절반만 생성하고 나머지는 거울상으로 만듦.
  • 구현에서는 원작의 좌우 대칭을 제거하고 플레이 영역을 30칸 너비로 확장함. 현대에는 메모리가 큰 문제가 아니라고 보고 생성된 줄도 버리지 않음.
  • 플레이어와 적은 앞에 놓인 벽을 부술 수 있음. 이론상 벽 파괴가 미로 생성에 영향을 줄 수 있지만, 줄이 충분히 앞서 생성되므로 실제로는 생성기가 해당 위치를 지나간 뒤 벽이 부서져 영향을 주지 않음.
  • 원작에도 플레이어가 벽을 부수는 기능이 있었다는 점을 나중에 알게 됨. 막다른 길에서 빠져나올 방법을 제공한다는 점에서 자연스러운 기능임.
  • C 구현은 3DSage의 구현을 바탕으로 했으며, 플레이어와 적이 움직이지 못하게 되는 일부 예외 상황을 수정함.

브라우저 버전과 게임 자료

  • ‘Backrooms’ 영화를 본 뒤 실험작을 다시 떠올려 일부 문제를 손보고 Backrooms 분위기의 게임으로 꾸밈.
  • Claude에 Three.js 버전 작성을 요청해 브라우저에서 플레이할 수 있도록 했으며, Diablo 스타일의 미니맵을 재현하려는 효과도 추가함.
  • 게임플레이 화면은 Archive.org에서 캡처한 Entombed 장면이며, Three.js 버전 화면도 제공함.
  • 게임 질문: 얼마나 멀리 가야 미로에 파묻히게 되는가?
  • GitLab 저장소
  • Three.js 브라우저 데모

참고 자료

  • Entombed Atari 게임 위키백과 문서
  • Archive.org에서 플레이할 수 있는 Atari 2600 Entombed 원작
  • Leon Mächler와 David Naccache의 Entombed 알고리즘 설명
  • Paul Allen Newell, John Aycock, Katie M. Biittner의 “Still Entombed After All These Years: The continuing twists and turns of a maze game”
  • John Aycock과 Tara Copplestone의 “Entombed: An archaeological examination of an Atari 2600 game”
  • BBC: “The mysterious origins of an uncrackable video game”
  • John Aycock의 Steven Boykey Sidley Entombed 인터뷰