又一版Doom克隆（13KB JavaScript实现）

今年我参加了JS13K 2019比赛，要求用不超过13KB的JavaScript开发游戏。我提交了一款名为"…又一版Doom克隆"的Doom类游戏。

点击上方视频（或此处）可进入游戏。源代码可在此处获取。

为何制作Doom克隆？

为什么要在总共13KB（压缩后）的JavaScript中创建第一人称射击游戏？有几个原因。但最好的答案可能是JS13K比赛FAQ对"能否使用WebGL？“的回答：“可以，但如果你想做FPS游戏，可能很难将其压缩到13KB。”

除了这个事实之外，我刚完成一个3D渲染器并想继续完善它。同时，编写高度压缩的代码是我喜欢做的事情（例如，多年前我曾创建一种语言并为专门用于代码高尔夫的新语言编写编译器）。

那么为什么选择FPS？关于"为什么选择Doom？“这个问题答案更简单。如果你要写一个FPS并想保持小巧，Doom是你能得到的最简约的选择。

Doom如此简单（按当今标准）的原因很明显：Doom必须在比今天慢五个数量级的硬件上运行。以相同的价格 today，完全有可能构建一台能够完成1994年奔腾十万倍工作的机器。因此，我认为尝试重新创建类似Doom的东西会很有趣，但不是处理性能限制，而是处理空间限制。

起点：JavaScript中的3D渲染器

我将游戏引擎基于我之前一直在开发的3D渲染器，旨在尽可能简单。结果发现，通过保持简单，它也非常小：核心3D渲染引擎只有约5KB的压缩JavaScript，因此剩下8KB用于游戏本身。我认为这状态还不错，只要我不使用任何大型游戏精灵或对象文件，应该就能成功。

玩家移动

从3D渲染器到3D游戏引擎基本上只需要一个改变：玩家可控制的摄像机移动，以及每次移动后重新渲染。为此，我将玩家放在一个盒子内部，并花了一些时间使移动感觉正确。Doom有一种非常独特的移动风格，我试图重现。

实现这一点的第一步是让玩家朝他们面对的方向加速，直到某个（快速）最大速度。我设置的加速度比原始Doom大，因为现在这似乎更正常。最重要的是使事物感觉像Doom的是在玩家移动时添加摄像机摆动。

在稳定状态下，这只是一个正弦波，但有一些必要的细节以使从停止到移动的感觉正确。

如果你不做任何额外的事情，玩家将从他们停止时的任何位置恢复摆动。这看起来非常错误。修复它实际上只是一些非常小的调整：玩家维护一个变量来跟踪动画在其周期中的位置（模2π），当玩家停止向任何方向移动时，该变量重置为零。这确实清理了运动，使启动和停止感觉正确。

我添加的一个Doom没有的功能是每一步添加少量摄像机滚动。（Doom没有这个，因为它只允许绕z轴旋转，玩家甚至不能向上看。）

从那里我添加了裁剪。如果玩家可以穿墙，就没有理由创建复杂的Doom式迷宫。现在，处理裁剪的"正确"方法是使玩家成为一个球体，墙壁是平面，然后检测球体-平面相交。我担心这会在13KB的预算中占用太多空间。

相反，游戏从当前玩家位置延伸出八条射线，并检测是否有任何射线与墙相交。如果有，我将玩家向后移动，使其至少离该墙五个单位远。这起到了穷人版球体碰撞检测的效果，同时只占用几百字节。

正确实现这一点有些棘手，特别是当射线同时与多个墙相交时。在某些情况下它仍然有问题，因此在设计关卡时，我手动测试了故障，并围绕碰撞检测错误设计了关卡。（嘿，如果它有效…）

对象旋转

为了在游戏中有任何对象，我需要以某种方式表示它们。一种自然的方法是使用.obj文件格式。不幸的是，这相当大且繁琐。（这是我之前为3D渲染器加载必备茶壶所做的。）

相反，我决定编写一个极简的对象旋转方法：给定一个表示为点序列的2D路径，旋转将点绕圆旋转以生成3D对象。这让你可以用非常小的空间创建一些非常好的对象。例如，上面图片中的水壶只用约二十字节代码表示。

在游戏开发的很长一段时间里，我还创建了一个高度简化的300字节表面细分实现（我之前用于3D渲染器）。但最后，我空间不足，不得不削减它——我对此并不感到太糟糕，因为它确实没有为游戏增加任何东西。

游戏循环

到目前为止，一切都是完全静态的。只有玩家摄像机在世界中移动。然而，制作游戏需要交互性。这就是游戏循环的用武之地。

这里的游戏循环只是完全标准的游戏循环。最初它实际上是以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function game_step(now) {
    if (game_is_over) return;
    frame = requestAnimationFrame(game_step);
    player_check_dead();
    player_move();
    player_clip_walls();
    player_fall();
    player_set_position();
    lights.map(light => light.compute_shadowmap());
    camera.draw_scene();
    objects.map(object => object.update(dt));
    garbage_collect();
}

虽然这确实是漂亮代码，但那里的每个函数只被调用一次。所以它们都被内联了，循环变得丑陋。

枪与敌人

没有东西射击或射击目标的第一人称射击游戏并不有趣。

我从"射击"问题开始。我不确定是否有足够空间容纳多于一把枪（叙述者：没有），对于一个围绕射击设计的游戏，我认为从Doom链枪开始是自然选择。

枪模型只是用对象旋转制作的几个圆柱体。这里的首要步骤是使移动枪感觉正确。为此，我重用了行走时上下移动的现有跟踪：枪根据玩家在行走周期中的位置上下移动以及左右移动。

下一个必要步骤是使射击感觉满意。那有三个组成部分。首先，每次射击都有小的后坐力。第二，它旋转。最后，每次射击都有小的闪光。所有这些都有助于游戏的感觉。对于一个围绕射击的游戏，它必须如此。

命中检测实现为简单的射线投射命中扫描（使用与玩家移动的墙壁碰撞检测相同的代码），然后创建一些爆炸粒子和小的闪光。

我必须对命中扫描的射线投射做一些更改。首先，因为初始实现只检查水平碰撞，我必须检查碰撞到达时是否是正确的z高度。这并不太难：计算物体离玩家有多远，查看玩家的俯仰角确定子弹高度，如果这在物体的高度边界框内，那么就是碰撞。

（另一个小细节是允许射击天花板和地板。否则，当瞄准太高时，不会有爆炸效果，看起来全错了。所有其他碰撞检测只检测水平碰撞，但这些是垂直方向的，因此需要一些特殊用途的代码。这样做实际上并不太难：记录起始z高度和俯仰角（与xy平面的角度），然后对于整个地图中的每个多边形，检查射线必须延伸多远才能击中该多边形的地板和天花板；然后检查步进那么远是否最终在该位置的多边形中。）

之后，我对所有潜在碰撞进行排序并选择最近的一个。

射击还有一些屏幕抖动，并且因为没有弹药，会减慢玩家移动速度。给玩家一个理由不在整个游戏中按住扳机是很重要的。

然后我转向"射击目标"问题。我最初创建了一个非常基本的人物块模型。它完全基于立方体，这使得存储非常容易：通过保存单个立方体模型，我可以在任意方向拉伸它并获得敌人。基本敌人然后由八个盒子组成。

死亡动画开始时很简单，敌人只会倒下。这看起来并不那么糟糕，但射击感觉软弱和无聊。因此，我做了一些调整，使敌人记住组成它的每个组成立方体，然后当它被击中时，爆炸成碎片。这感觉好多了。

最初，组成敌人的方块会穿墙飞离屏幕。这有些令人不安，因此我添加了一个效果使它们从墙上弹起。弹跳完全物理上不可能以保持简短。碰撞再次用射线相交实现。然后，如果最近的墙完全在xz平面上，物体反射其y速度。如果完全在yz平面上，x速度被反射。在所有其他情况下，x和y速度都被反射。

当物体位置低于当前房间的地板高度时，z速度被取反并减少20%。每秒物体减慢50%（仿佛有某种假设的摩擦）。

敌人AI

对于一个学位和职业表面上在（带很多引号）“AI"的人来说，这里的敌人真的相当不智能。敌人有位置和旋转。它们永远来回踱步，直到被唤醒，要么（a）因为玩家在视线内，要么（b）因为视线内的敌人被射击。

检测视线再次用射线投射实现，该实现从检测枪命中位置和碰撞检测中重用。为了不消耗更多射线投射的CPU周期，敌人每秒只检查一次敌人。

一旦唤醒，敌人将沿直线直接向玩家移动。如果有东西挡路，敌人将选择一个新的随机方向并移动几步，然后返回向玩家移动。偶尔，行走的敌人会向玩家射击。

此外，每当敌人死亡时，它会请求它能看见的所有其他敌人的帮助（再次通过射线投射）。这使得躲在角落一个一个消灭敌人变得困难，这是一种无聊的游戏机制，不应鼓励。

纹理

到目前为止，一切都很单调，只有一种纹理。我知道我无法容纳任何手动绘制的纹理——即使很小的——因此我改为程序化生成它们。我选择只使用三种纹理：瓷砖地板、墙壁的砖图案以及熔岩和爆炸的简单Perlin噪声。

砖生成有些琐碎。每N步绘制水平线，然后每N步绘制垂直线，当我们在偶数行时偏移N/2。代码只是以下内容：

1
2
3
4
5
6
7
8

make_texture(cartesian_product_map(range(256),range(256),(y,x) => {
    if ((y%64) <= 2 || Math.abs(x-(((y/64)|0)%2)*128) <= 2) {
        return [0,0,0,1];
    } else {
        var r = .9-perlin_noise[x*256+y]/20;
        return [r,r,r,1];
    }
}).flat())

瓷砖生成有点棘手。首先我创建了一个六边形格子。然后，对于瓷砖中的每个像素，我计算到格子上最近两个点的距离。如果到更近点的距离等于第二接近点距离的两倍，那么我画一条线。这给出了标准瓷砖图案。

Perlin噪声在视觉上是一种比其他噪声好得多的噪声类型。它看起来比纯白噪声更自然随机。Perlin噪声生成足够复杂，我只会指向维基百科文章并说"我做了那个”。我还添加少量Perlin噪声到砖图案以使其不那么无聊。

敌人动画

让敌人在地图上滑行并不非常视觉有趣，因此接下来我添加了行走动画。这占用的空间出奇地少，只包括像钟摆一样移动肢体。

只有一种敌人类型不行且相当无聊，因此从这里我添加了一个更小的飞行敌人，移动更快且更难击中。表示再次非常极简：只是两个看起来像翅膀的梯形和一个矩形身体。为了使它看起来像在飞行，翅膀拍打一点，它上下颤动，再次重用了行走敌人的动画代码。

音频

添加音频的明显选择似乎是JSFXR。但此时空间变得紧张。快速查看代码后，我意识到有很多优化空间。

我通过一系列小调整成功将其缩短了近一半。最大的节省来自移除从数组到可播放WAV文件的映射，并用直接接受浮点数组的WebAudio调用替换。下一个最大的是一堆case语句，我用数组查找替换。也就是说，我做多路复用器的事情，在数组内计算所有情况，然后只索引出我想保留的那个。更慢，但更短。在用映射替换for循环并编写一个clamp辅助函数后，它足够短以允许编写一些好的音效。

然后我想让音频系统响应玩家在3D空间中的位置。我认为这部分需要大量努力，但结果发现它相当容易，因为现在有一个createStereoPanner函数可以为你精确完成这个。

对于背景音乐，我转录了Toccata and Fugue的中间部分。这只是永远循环播放。

地图表示

Doom的定义特征之一是你通过的关卡。每个地图感觉更像一个迷宫，玩家跑来跑去寻找出路。这是必须正确实现的组成部分。

然而，天真地存储地图将占用太多空间：即使只存储一些基本关卡，当天真表示时（例如，通过存储所有墙的位置）也超过一千字节。因此，地图由一组（可能非凸）多边形表示。每个多边形可以有地板高度和天花板高度，当两个相邻多边形共享边缘时，玩家可以从一个传递到另一个（可能相应地上升或下降）。

将多边形转换为实际三维房间的代码需要一点工作。虽然围绕每个多边形放置墙壁很容易，但确定何时不应该有墙——因为有两个相邻边缘——通常很困难。为了简化这个过程，只有当两个墙完全共享两个坐标时才创建开口。

最初我只是通过手动编码多边形位置开始创建地图，但这有两个问题：首先，它们占用大量空间，但更重要的是，制作它们需要永远。如果我想设计足够多的地图，我需要做更好的事情。

认为可能同时解决这两个问题，我实现了一个微小的、微小的海龟编程语言来定义地图区域的位置。也就是说，我不是用海龟来绘制，而是用它通过用多边形制作函数替换绘图笔来创建多边形。最初这种语言非常像海龟：命令会通过旋转它并让它移动特定距离来移动海龟。

有一次我甚至添加了函数以允许循环和调用/返回，以便我可以，例如，创建楼梯，然后每次想要楼梯时重用"制作楼梯"函数。

不幸的是，这仍然难以设计地图，因为它需要在一个设计为尽可能密集的汇编语言中编程海龟。只有一个月时间构建整个游戏，我无法 afford 花几天时间只设计地图。更糟的是，它实际上没有节省那么多空间。因为13KB限制是关于压缩源代码的大小，重复相同的函数两次完全可以：zip压缩将为我节省空间。

因此海龟代码字面上变成这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

function run_turtle(commands) {
    var regions = []
    var turtle_location = [ZERO];
    var floor_height = 4;
    var ceil_height = 40;

    var do_later = [];
    for (var i = 0; i < commands.length;) {
        var cmd = commands[i++];
        // 获取命令的"操作码"和"参数"
        var [low, high] = [cmd&31, cmd>>5];
        // 操作码0是"制作多边形"命令
        if (high <= 1) {
            var coordinates = [turtle_location[0]]
            coordinates.push(...range(low).map(x=> {
                var dydx = NewVector(((commands[i]>>4)-7)*8,
                                     ((commands[i++]%16)-7)*8, 0)
                turtle_location.unshift(turtle_location[0].add(dydx));
                return turtle_location[0];
            }));
            regions.push(new MapPolygon(coordinates,
                                        floor_height,
                                        ceil_height))

            // 操作码1是"goto"命令
            if (high == 1) {
                regions.pop();
            }
        }
        // 操作码4: 调整天花板
        floor_height += 2*(low-15)*(high==4);
        // 操作码5: 调整地板
        ceil_height += 4*(low-15)*(high==5);
        // 操作码6: 回溯
        turtle_location.splice(0,low*(high==6));
    }
    return [regions, do_later];
}

为了更容易创建地图，我废弃了大部分海龟语言并制作了一个更简单的语言。我移除了循环、函数调用、旋转运动，并只实现了两个操作码：制作多边形和goto。制作多边形操作码接受顶点数量，然后有一个字节序列，其中高4位给出沿x轴移动多远，低4位给出沿y轴移动多远。到达最终顶点后，循环关闭，海龟在那里创建一个多边形。移动操作码只是将海龟移动到新位置以放置另一个多边形。

制作几个地图后，我查看了我的海龟语言哪些部分占用最多空间。我意识到我在将海龟从一个多边形移动到另一个多边形上浪费了大量空间。这怎么能变得更短？嗯，注意多边形通常不是孤立的：它们通过顶点连接到其他多边形。因此，我添加了另一个称为回溯的函数。每次海龟移动时，它将其位置添加到堆栈。回溯将海龟的位置弹出堆栈一些值以前。这非常有效：超过95%的海龟移动被回溯命令替换。

地图编辑器

为了让我高效制作地图，我快速黑客了一个WYSIWYG界面来帮助我设计地图。这个编辑器然后将这些地图编译到海龟语言，以便它们可以在游戏中使用。

在编辑器中更新地图实时更新渲染的游戏，让我准确看到发生了什么。上图显示了我创建新地图的一般过程。

因为这个编辑器不会与实际可玩游戏捆绑，我不担心代码质量或编辑器的可用性。它非常丑陋和黑客，使用它的键绑定是神秘的（想添加新多边形？选择现有顶点并键入shift-A以突出显示相邻边缘，然后e（挤出）。想在现有边缘上添加顶点？shift-A s（分割）。删除现有多边形？shift-Q。如果你知道它们做什么，它们都有意义，但非常不直观。）

关于节省空间的思考

成功在13KB压缩JavaScript中创建完整游戏需要不断关注代码空间。

在13KB中使一切工作的主要必要目标是始终意识到代码大小。我更新了Python脚本以监视每次源文件更改时重新构建包，并显示游戏本身剩余的可用字节数，以便它始终可见，我会问自己刚刚引入的任何更改是否值得复杂性。

编写一堆我在整个程序中使用的辅助函数也很有帮助。这里只是我发现最有用的几个：

1
2
3
4
5
6
7
8
9

var pairs = (lst,fn) => lst.slice(0,-1).map((x,i)=>fn(x,lst[i+1],i))
var transpose = (mat) => mat[0].map((x,i) => mat.map(x => x[i]))
var range = (N,a) => Array(N).fill().map((_,x)=>x+(a||0));
var reshape = (A,m) =>
    range(A.length/m).map(x=>A.slice(x*m,(x+1)*m));
var urandom = _ => Math.random()*2 - 1;
var push = (x,y) => (x.push(y), x);
var clamp = (x,low,high) => Math.min(Math.max(low, x), high)
var sum = (x) => x.reduce((a,b)=>a+b)

我还定义了自己的矩阵和向量数学以使一切尽可能极简。旋转都定义为4x4矩阵乘积：四元数会更高效，但也占用更多空间，因此我没有使用那些。

在我写的一些最丑陋的代码中，我使4x4矩阵乘法既非常高效又非常短，这需要一些工作：

1
2
3

var mat_product_symbolic = B =>
    `(a,b)=>[${reshape(range(16),4).map(c=>B[0].map((_,i)=> B.reduce((s,d,j)=>`${s}+b[${d[i]}]*a[${c[j]}]`,0))).flat()}]`;
multiply = eval(mat_product_symbolic(reshape(range(16),4)); 

不断显示当前构建大小需要一个自动化构建过程。构建脚本最初只是运行uglifier后跟标准zip来跟踪空间。我很快意识到有一些优化我可以自动化以帮助更好地压缩东西。我写了一个短脚本来识别所有webgl变量名并将变量名重写为短单字母名称（因为uglify不这样做）。然后我修改了这个程序来重写长WebGL函数名，如framebufferTexture2D，用短三字符代码e2m（我分别取倒数第8、倒数第2和倒数第3个字符）。开发接近结束时，我遇到了advzip，它有助于更好的压缩。