Show HN：基于 Raycaster 的 Entombed 复刻

# 被困于光线投射之中 来源：https://www.stelabouras.com/blog/entombed-raycaster/ 2026年9月25日，星期五 大约一年前（也可能更久，我的记忆有时不太可靠），我经历了一次几乎所有游戏开发者都会走过的"光线投射仪式"。当时我正在阅读 Lode 的教程（https://lodev.org/cgtutor/raycasting.html），同时观看 3DSage 在 YouTube 上的 "Make Your Own Raycaster" 系列（https://www.youtube.com/watch?v=gYRrGTC7GtA）（顺便说一下，这两个资源都强烈推荐），在这过程中我发现了 Entombed 算法：一种出自 Atari 2600 游戏《Entombed》（https://en.wikipedia.org/wiki/Entombed_(Atari_2600%29)）（1983）的迷宫生成算法，在这款游戏中玩家需要在僵尸的追逐下逃出迷宫。 让我对这个算法着迷的地方在于：迷宫是基于某种古老（如今几乎堪称玄学）的逻辑程序化生成的，这套逻辑规定了下一行该如何生成，同时还要在 Atari 2600 的硬件限制下工作。 Atari 2600 只有 128 字节（是的，b 开头的那个字节）内存，而在《Entombed》中，迷宫不断向上滚动，而玩家则向下行走进去。考虑到该设备的内存限制，存储整个迷宫几乎是不可能的。因此迷宫必须一行一行地生成，并在滚出屏幕时被丢弃。这就引出了一个问题：当你在内存中只能保留几行的时候，你要如何一行一行地构建一个迷宫？答案就是神秘表（mystery table）！ 《Entombed》之所以引起游戏考古学家兴趣的真正原因，是迷宫生成背后那张神秘表，以及时至今日几乎没有人能完全解释清楚它为何有效。多年来，流传的说法是它是某个"喝醉了、脑子已经不正常（https://intarch.ac.uk/journal/issue59/3/full-text.html#2)的人写的。事实证明，真实故事也差不了多少：Paul Allen Newell 和一名数学研究生 Duncan Muirhead 在酒吧里一边喝了几杯酒，一边在餐巾纸上勾勒出了它，而 Newell 在那个周末结束前就让它在 Atari 上跑起来了。 *《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 (https://doi.org/10.22152/programming-journal.org/2019/3/4). CC BY 4.0. 这套逻辑是这样运作的：迷宫中的每个单元格由它的五个邻居生成：同一行左侧已填充的两个单元格，以及上方一行的三个单元格。这五个比特构成一个 0 到 31 的索引，输入上面那张查找表，返回一堵墙（`1`）、一条通道（`0`）或者一次抛硬币（`random`）。就这么简单。没有回溯，没有搜索：整行一次扫描就填充完毕，一个类似俄罗斯方块形状的窗口沿着它逐格滑动。 *单元格的生成方式。* 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 (https://doi.org/10.11141/ia.59.3). CC BY 3.0. 有人甚至把这个算法描述为一种元胞自动机，但根据 (https://intarch.ac.uk/journal/issue59/3/full-text.html) Paul Allen Newell、John Aycock 和 Katie M. Biittner 的说法： > 这个算法难以简单归类，也许是独一无二的。它完全依赖局部信息，这让人不禁想将其视为基于元胞自动机的算法（Sarkar 2000），然而它缺乏并行性，而且围绕 X 单元格的"邻域"形状古怪，使得元胞自动机的概念显得牵强附会。 这与迷宫算法通常的工作方式几乎完全相反。通常你会把整个网格保存在内存中，算法会保证你最终得到一个可以真正解开的迷宫。而《Entombed》一次最多只看到十一行，什么保证都没有。它只是生成出一个看起来像迷宫的东西。 鉴于《Entombed》的情况下没有任何保证，人们引入了两道修正流程。它们在每一行完成后运行，回溯查看后面的行：如果迷宫开始自我重复或者把区域封闭起来，它们就把整行（或半行）全部清空。 在读完我能找到的所有参考资料后，我立刻开始思考如何把这套逻辑应用到光线投射（raycaster）上！结果证明这是一个相当有趣的副项目，它将学习光线投射的方方面面与创建一个简单的 Wolfenstein 3D 渲染器结合在一起——唯一的不同是地图必须用取自这款古老（取决于你的年龄）的 Atari 游戏的逻辑来程序化生成！ 我决定用 `uint32` 来表示每一行迷宫的状态，每个比特表示该位置是否有墙。这样不仅计算起来更方便，而且随着玩家不断深入、迷宫不断增长时也更节省内存。 *《Entombed》在 Atari 2600 上的画面，游戏区域以中心为轴对称。* *《Entombed》的游戏画面，截取自 Archive.org (https://archive.org/details/atari_2600_entombed_maze_chase_1982_u.s._games_corporation_paul_allen_newell_stev)。* 注意对称性：只生成了游戏区域的一半，其余部分是它的镜像。 我的版本与原作有几处不同：我去掉了镜像效果（见上面的截图），把游戏区域拓宽到 30 个单元格宽，而且一旦生成了行就绝不丢弃——毕竟如今内存已经不是什么大问题了（是吗？）。 我还给玩家和敌人增加了破坏面前墙壁的能力，这（理论上）可以反馈到迷宫生成中，但实际上从来不会发生：行被生成得足够靠前，等到你破坏任何东西时，生成器早已推进过去了。 有趣的是，我直到最近才发现，原版游戏其实也赋予了玩家同样的破墙能力。不过这也很合理，因为你需要给玩家提供一条从死胡同中脱身的简易途径……尤其是当你正被神秘实体追赶的时候。 我的 C 实现基于 3DSage 提供的代码，并修复了我能找到的一些边界情况，比如玩家和敌对实体可能卡住的问题。总的来说，这真的是一次非常有趣且独特的经历。 等它跑起来之后，我几乎就把它忘了。直到几周前看完《Backrooms》（https://www.imdb.com/title/tt26657236/) 电影后，我想起了这个小小的实验，于是想把它稍微美化一下，解决一些小问题，套上一层类似 Backrooms 的皮肤（求别告我哈哈），然后展示给世界看。 作为锦上添花，我让 Claude 写了一个可以在浏览器中游玩的 Three.js 版本 (https://entombed.netlify.app/)，加入了一些额外的特效（尽力重现了类似 Diablo 的小地图），以防你不想在自己的电脑上编译并运行一个 C 游戏。 *Three.js 中的 Entombed* *Entombed 光线投射器的 Three.js 版本 (https://entombed.netlify.app/)。* 你能走多远才会被活埋？ - Gitlab 仓库 (https://gitlab.com/stelabouras/entombed/) - Three.js 浏览器演示 (https://entombed.netlify.app/) ### 参考资料 - Wikipedia 上关于 Entombed Atari 游戏的条目 (https://en.wikipedia.org/wiki/Entombed_(Atari_2600%29) - 可在 Archive.org 上游玩的原版 Atari 2600《Entombed》游戏 (https://archive.org/details/atari_2600_entombed_maze_chase_1982_u.s._games_corporation_paul_allen_newell_stev) - Leon Mächler 和 David Naccache 撰写的《Explaining the Entombed Algorithm》(https://arxiv.org/pdf/2104.09982) - Paul Allen Newell、John Aycock 和 Katie M. Biittner 撰写的《Still Entombed After All These Years: The continuing twists and turns of a maze game》(https://intarch.ac.uk/journal/issue59/3/full-text.html) - John Aycock 和 Tara Copplestone 撰写的《Entombed: An archaeological examination of an Atari 2600 game》(https://programming-journal.org/2019/3/4/) - BBC：《The mysterious origins of an uncrackable video game》(https://www.bbc.com/future/article/20190919-the-maze-puzzle-hidden-within-an-early-video-game) - John Aycock 对 Steven Boykey Sidley 关于《Entombed》的访谈 (https://ucalgary.scholaris.ca/items/d378421b-b557-4719-9f25-26b220642685)