关系型数据库

为了更好地布局数据，我们可以将现有的结构变换为线性的。将面向数据的方法应用于现有的代码和数据布局时，问题通常来自于，会隐藏，封装数据的编程范式中固有的状态复杂度。这些范式隐藏了内部状态，所以通常不会触及到，但当需要修改数据布局时，就会遇到阻碍。并不是因为它们不够抽象，无法做到在不影响用户代码正确性的前提下改变底层结构，而是因为数据结构被连接起来并赋予意义。这类耦合会很难消除。

在这一章中，我们将介绍关系模型、关系数据库技术、标准化的一些相关内容。它们是将高度复杂的数据结构和关系，变换为干净的、线性可存储数据条目集合的很好的例子。

当然做面向数据设计也不需要把数据变换到数据库风格，但很多时候，在简单的数组上工作会方便许多。本章将通过示例，告诉读者如何从有复杂连接的对象网络迁移到更简单的数组推理关系模型。

复杂状态

大多数软件中的数据，总有一些复杂或相互联系的特质。而在游戏开发中，为了保障玩家的沉浸感，需要在游戏内处理多种不同资源，在不同阶段实现听觉、视觉、甚至是触觉反馈。对于许多在面向对象设计中成长的程序员，把可用的结构类型减少到只有简单的数组似乎有些难以想象。从使用对象、类、模板、封装数据的方法，到一个只能访问线性容器的世界，是非常困难的。

Edgar F. Codd 在 A Relational Model of Data for Large Shared Data Bank[#!coddef!#] 中提出了关系模型，用于处理同数据交互的代理的，当下以及未来的需求。一个为插入、更新、删除和查询操作构建数据的解决方案。他认为这一建议在保证能良好利用数据的同时，不再那么依赖对数据布局的深刻理解；同时还能降低引入内部不一致的概率。

关系模型能够提供一个框架。Edgar F.Codd 在Further Normalization of the Data Base Relational Model[#!Codd1971FurtherNO!#]中, 提出了我们至今仍在用的标准化基本术语，能系统地将最为复杂的、相互关联的状态信息，减少到只有唯一独立元组的线性列表中。

为复杂的数据寻找计算框架

数据库能以结构化的方式存储高度复杂的数据，并提供一种语言来变换数据和生成报表。SQL 语言由 IBM 的 Donald D. Chamberlin 和 Raymond F. Boyce 于 20 世纪 70 年代发明，它在能够存储可计算的数据的同时，也可以按照关系模型的形式维护数据。可游戏里没有简单的可计算数据，有的只是类和对象。都是些枪、剑、汽车、宝石、日常活动、纹理、声音、成就。看起来，数据库技术在使用面向对象时不会有什么帮助。

游戏中的数据关系可能非常复杂，乍一看似乎并不能整齐地放入数据库的行中。CD 收藏则很适合放进数据库，专辑可以整齐地排列在一个表中。但是，对于许多游戏对象来说却不适用。对于没有经验的人来说，很难用正确格式的表列来描述一个关卡文件。在正确的列项描述赛车游戏里的汽车可能也不简单。要为每个车轮设置一列吗？要为每个碰撞基元设置一列？还是只为碰撞网格设置一列？

好吧，整齐划一的数据库思维或许并不适用于游戏。但其实，只是因为数据还未标准化。这里我们会逐步执行这些标准化步骤，用以说明如何从网络模型或层级模型变换为需要的形式。我们会从一个关卡文件开始，随后读者会发现这些有几十年历史的技术，是如何拓展视野，帮助我们了解游戏数据到底在做什么的。

用不了多久，我们就会发现，数据库技术已经考虑过所有需要的操作了，只不过存储数据的方式将其掩藏了起来。任何数据结构都是在性能、可读性、可维护性、面向未来、可扩展性、可复用性之间做权衡。例如，常见的最灵活的数据库是文件系统。它有一个两列的表。一列是作为主键的文件路径，另一列是作为数据的字符串。这种简单的数据库简直就是完美的面向未来的系统。文件中可以存储任何东西。表越复杂，就越不具备未来性，也越不容易维护，但性能和可读性就越高。例如，文件没有自己的文档，但只需要数据库的模式(Schema)，就足以理解一个设计得足够好的数据库。这也是为什么，游戏甚至看起来都没有数据库。它们复杂到了，为了性能，已经忘了自己只是种数据变换。这种可变尺度的复杂度也影响了可扩展性，这就是为什么有人转向 NoSQL 数据库，以及文档存储这类数据归档。这些系统更像是一个文件系统，文件按名字访问，而且对结构的限制较少。同时也有利于横向扩展，如果不需要在不同机器上的多个表中保持数据一致，增加硬件就会更容易些。或许有一天，内存与最近的物理 CPU 紧密相连时，或内存芯片本身处理能力更强时，又或者桌面设备中运行 100 个 SoC 比一片 CPU 更高效时，从上层迁移到文档存储可能对应用程序会更好。但至少现在，对于本地硬件上的任务，还看不出这种处理模式究竟能带来什么好处。

这里我们不打算深入研究如何利用大型数据基元最底层的细节，如网格、纹理、声音等。现在，只把这些原始资产（声音、纹理、顶点缓冲区等）看作是如同整数、浮点数、字符串和布尔值一样基元。这样做是因为关系模型要求在处理数据时要有原子性。什么是原子性，什么不是，至今仍在争论，还没有一个绝对的答案。但是对于开发供人消费的软件，颗粒度可以植根于从人类感知的角度考虑数据。现有的 API 根据使用方式，会以不同的方式呈现字符串。例如，人类可读的字符串（通常是 UTF8）和用于调试的 ASCII 字符串之间的区别。如果能意识到所有这些东西都是资源，把它们拆分成小块，就会失去原本具有辨识度的特征。那么把声音、纹理、网格添加到这上面就顺理成章了。例如，半个句子比整个句子的作用要小得多。而且由于拆分破坏了完整性，一个句子的片断显然不能在保持其意义的前提下，连同另一个不同句子的随机片断重复使用。即使是字幕也是沿着有意义的边界做分割的。正是这种对有意义的边界的需求，给出了我们对于面向人类的软件开发中，原子性的定义。为此，在处理数据、进行标准化处理时，尽量停留在名词的层面，即可命名的片段。一整首歌可以是一个原子，时钟的一次滴答声也可以是一个原子，一整页的文字是一个原子，玩家的账号也是一个原子。

标准化数据

**Figure:** 图示初始化代码

现在要处理一个游戏的关卡文件。这个游戏中，玩家要寻找钥匙开锁，然后进入出口所在的房间。关卡文件被一连串代码调用，用来创建和配置不同的对象集。这些对象一起组成了一个可玩的关卡，并且彼此之间也存在一些关联。首先，我们假设它包含了一些房间（有或没有陷阱），有门（可以上锁）通向其他房间。还包含一些道具（可拾取物），有些可以用来开门，有些影响玩家的状态（如治疗药水和护甲）。所有房间和道具都有好看的的纹理网格。其中一个房间包含出口标记，还有一个房间是玩家的出生点。

初始化的代码中 (代码

)，加载了一些资源，创建了一些拾取原型，建立了一些房间，在房间内添加了一些实例，然后将这些都联系起来。这里，可以看到一个处理相互引用的事物的标准方案。在把房间连接起来之前先创建房间，这是先决条件。在 C++ 中创建实体时，我们会假设它们被绑定在内存中，而唯一有效方式是通过指针引用。但在分配之前，还无法知道它们在内存中的位置。而且填充数据前，也无法分配它们，因为分配和初始化是通过 new 的机制绑定在一起的。所以很难在对象存在之前描述它们之间的关系，因而需要将内容创建这一步拆分为初始化、连接两个阶段。

$\begin{lstlisting}[caption={初始化代码}, label={lst:2.1}, captionpos=b] /... ... ( -27 ,13)); // ... SetRoomAsSpecial ( r5 , E_EXITROOM ); \end{lstlisting}$

要将这段初始化代码变成可用的数据库格式，或者说关系模型，我们要对其进行标准化处理。无论是何种类型的关系模型，引入新的元素都需要能放在表里。第一步，我们把所有的数据放到一个非常混乱的，但尽量完整的表。本例中，我们从创建对象的代码中获取数据的形式，然后将其放进表格。资源加载部分则可以直接转化为表格，如表

所示。

有了这些数据，就可以创建 Pickups 了。我们把对 CreatePickup 的调用变换为表格(表

)。注意，有一个 pickup 没有指定色调，这里我们用 NULL 表示该行没有这项内容。动画部分同理。如果只有钥匙( key )有动画，那所有非钥匙的行都用 NULL。

Table: 根据资源名称创建的表格

Meshes

MeshID	MeshName
msh_rm	"roommesh"
msh_rmstart	"roommeshstart"
msh_rmtrap	"roommeshtrapped"
msh_key	"keymesh"
msh_pot	"potionmesh"
msh_arm	"armourmesh"

Textures

TextureID	TextureName
tex_rm	"roomtexture"
tex_rmstart	"roomtexturestart"
tex_rmtrapped	"roomtexturetrapped"
tex_key	"keytexture"
tex_pot	"potiontexture"
tex_arm	"armourtexture"

Animations

AnimID	AnimName
anim_keybob	"keybobanim"

Table: 根据 CreatePickup 的调用创建表格

Pickups

PickupID	MeshID	TextureID	PickupType	ColourTint	Anim
k1	msh_key	tex_key	KEY	Copper	anim_keybob
k2	msh_key	tex_key	KEY	Silver	anim_keybob
k3	msh_key	tex_key	KEY	Gold	anim_keybob
p1	msh_pot	tex_pot	POTION	Green	NULL
p2	msh_pot	tex_pot	POTION	Purple	NULL
a1	msh_arm	tex_arm	ARMOUR	NULL	NULL

资源加载完成，并且 pickup 的原型创建成功后，就可以为房间创建表了。要在实例没有的属性位置用 NULL ，以确保有值可用。我们把对 CreateRoom、AddDoor、SetRoomAsSpecial 和 AddPickup 的调用变换为 Rooms 表中的列。参见表

，了解如何建立一个表示所有设置函数调用的表格。

Table: 根据 CreateRoom 和其他调用创建的表格

Rooms

RoomID	MeshID	TextureID	WorldPos	Pickups	...
r1	msh_rmstart	tex_rmstart	0, 0	NULL	...
r2	msh_rmtrap	tex_rmtrap	-20,10	k1	...
r3	msh_rm	tex_rm	-10,20	k2,p1,a1	...
r4	msh_rm	tex_rm	-30,20	k3,p2	...
r5	msh_rmtrap	tex_rmtrap	20,10	NULL	...

...	Trap	DoorsTo	Locked	IsStart	IsEnd
...	NULL	r2,r3	r3 with k1	true WorldPos(1,1)	false
...	10HP	r1,r4	r4 with k2	false	false
...	NULL	r1,r2,r5	r5 with k3	false	false
...	NULL	r2	NULL	false	false
...	25HP	NULL	NULL	false	true

根据 Setup 代码生成第一批表后，能看到表中出现了很多 NULL。如果实例没有某个元素，就都用 NULL 替换。还有有一些单元格包含多项数据。表中有多个门的房间就很难处理。如何知道它有哪些门呢？门是否锁住了？道具亦然。标准化的第一步，是将每个单元格中的元素数量减少到 1，并把为空的地方增加到 1。

标准化

SQL 最初应用时，明确定义的标准化阶段只有三个。而现在已经增长到了六个。如果要尽可能利用数据库技术，最好了每一个阶段，至少要知道为什么。这些范式能让增进对数据依赖的理解，若加以利用，可以帮助重排数据布局。对于游戏结构，BCNF (Boyce-Codd normal form，稍后会做解释) 应该已经足以应付大部分情况。此外，读者可能还希望针对热/冷访问模式标准化数据，不过这个主题并不属于常规的数据库标准化文献。如果读者除本书涉及的内容之外仍旧感兴趣，可以阅读 William Kent 写的 A Simple Guide to Five Normal Forms in Relational Database Theory[#!kwilliam!#] ，那句著名的 The key, the whole key, and nothing but the key. 就出自这里。

如果一个表格属于第一范式，那每个单元格都包含一个且只有一个原子值。也就是说，值中没有数组，也没有 NULL。第一范式还要求每一行都是独立的。不过在展开讨论之前，我们先来了解一下什么是主键。

主键(Primary key)

所有的表都由行和列组成。数据库中，每一行都必须是唯一的。这个约束非常重要。在接下来了解数据标准化过程里，我们很快就知道，为什么行重复毫无意义。从编程的角度，我们先把表看作集合，那一整行就是集合的值。集合是无序的，数据库中的表也是无序的，很接近真实情况。数据库管理系统(DBMS)会依赖于隐式的行 ID：行与行之间总会有点区别。不过最好不要依赖这一点，只有在数据库的用途与设计相匹配时，才能更有效地工作。表都需要一个键。键常用于排序物理介质中的表，进而优化查询。因此，键得是唯一且小的。可以把键想象成 map 或字典中的 key。由于具备唯一性，每个表都会有一个隐式的键。表在同时用到所有列时，也能精确识别到每一行。因此，也可以使用整个行来作为主键的定义，或用于精确查询。如果该行是唯一的，那么主键也是唯一的。但一般而言，需要尽量避免使用整行作为主键。虽然有时也别无他选，之后我们会看到这样的例子。

例如，在 Mesh 表中， meshID 和文件名的组合肯定是唯一的。但它是人为确保的：我们已经假定 meshID 是唯一的。即便是同一个 Mesh，从同一个文件加载，仍可能会有不同的 meshID。纹理表中的 textureID 和文件名也是如此。从表

看出，我们可以根据类型、网格、纹理、色调、动画来唯一地确定每个可拾取物的原型。

再来看 Rooms 表。可以看出，只用房间表中的 RoomID 以外的所有列的组合，就已经能唯一地定义房间了。从另一个角度想，如果某行有相同的数值组合，那实际上就是在描述同一个房间。因此，可以认为 RoomID 是作为其余数据的别名。我们已经把 RoomID 加到表里了，但它是怎么来的？首先，它来自于初始化代码。代码里有一个 RoomID，但创建阶段还用不到。后面用它来确定门通向哪里。换个角度，如果房间跟任何东西都没有逻辑关系，就不需要 RoomID 了，毕竟也用不到。

主键必须是唯一的。以 RoomID 为例，它能唯一地描述一个房间，因此能作为主键。而且由于其本身不包含数据，只是作为句柄，因此也可以将它理解为一个别名。某些情况下，主键也是信息，我们以后也会遇到。

顺便提一下，数据库中的一行也是键这一点，值得花时间去理解。如果数据库表是一个集合，插入一条记录，实际上只需要将特定的数据组合记录下来。一个数据库表就好像是巨大值域中的稀疏集合。在某些情况下，可能值的集合范围没多大，就可以很方便地用位集表示。举例来说，有一个表格，其中列出了 MMO 中当前在线的玩家。如果是服务器分区的 MMO，每个服务器上唯一的玩家数量可能有几千人的限制。这种情况下，将当前在线玩家存储为一个位集会更方便。如果在线玩家只有 10,000 个，并且无论何时，同时在线的玩家都只有 1000 个，那么位集的表示方法将占用 1.25kb 内存。而如果将玩家存储为用 short 的 ID，需要至少 2kb 的数据。而如果是 32bit，要保证在多个服务器上都是唯一的，就需要 4kb。这种情况的另一个好处是数据查询的效率。快速访问表中的 ID 需要先对其进行排序,其最佳情况是 $O(logn)$

。而位集则是

。

回到资源表，有个细节需要提及：即使有两个不同的 MeshID 指向同一个文件，大多数程序员也会凭直觉理解，一个 MeshID 基本不会指向两个不同的 Mesh 文件。基于这种不对称性，可以推断，看起来更有可能是唯一的那一列，就是可以作为主键的那一列。在这里我们选择 MeshID，因为其更易操作，而且基本不会有多个含义和用途。但是，我们也完全可以用文件名替代它。

如果把 TextureID、PickupID、RoomID作为这些表的主键，就可以考虑使用第一范式了。我们用 t1,m2,r3 等来作为类型安全的 ID 值。实际上也可以直接使用整型数。这里主要是为了保证可读性，同时表明，每种类型都有该类型唯一的 ID，也与其他类型有相同 ID。例如，房间有整数 ID，值为 0 (译注：r0)，但纹理也有（译注：t0）。拥有跨类型唯一 ID 的好处是方便调试，比如只用高位的几 bit。如果不是每个类型都拥有上百万个实体，那就有足够的位来处理上千个不同的类。

第一范式 (1st Normal Form)

第一范式可以理解为，消除元素的稀疏性。首先需要确保表中没有空指针，且元素中没有数组。可以通过将重复内容及可选项转移到其他表中来实现。任何有 NULL 的地方，表示该列为可选项。我们先来处理 Pickups 表，它有可选元素： ColorTint 和Animation。现在创建两个新表：PickupTint 和 PickupAnim，这里直接与 Pickups 使用相同的主键。表

是变换后的结果，可以看出，现在这里已经没有 NULL 了。

Table: 1NF的 Pickups

Pickups

PickupID	MeshID	TextureID	PickupType
k1	msh_key	tex_key	KEY
k2	msh_key	tex_key	KEY
k3	msh_key	tex_key	KEY
p1	msh_mpot	tex_pot	POTION
p2	msh_mpot	tex_pot	POTION
a1	msh_marm	tex_arm	ARMOUR

PickupTints

PickupID	ColourTint
k1	Copper
k2	Silver
k3	Gold
p1	Green
p2	Purple

PickupAnims

PickupID	Anim
k1	anim_keybob
k2	anim_keybob
k3	anim_keybob

可能你已经发现了两点不同：其一，标准化创建了更多的表，但每个表的列更少；其二，重要的事物才有行。前者令人担忧，它表示会占用更多内存。而后者就有意思了：在面向对象方法中，允许对象有可选属性；也就意味着在使用前需要判断其是否为空。但如果像现在这样存储数据，我们就知道所有的属性都不为空。不需要检查空值，代码可以更简洁。基于此，在尝试推理整个系统时，要考虑的状态也更少。

再来看 Rooms 表。这个表中有不少包含多个原子值的元素。由于不符合第一范式的规则，我们要先把它们从表里删去。首先删除对 Pickups 的引用，因为它的元素数量不定。然后是 Trap，尽管一个房间最多只有一个陷阱，但也可能没有。最后是 Doors，虽然每个房间都有门，但往往不止一个。这里重申一下规则，在每一个行与列的交汇处都有且只有一个条目。表

展示了如何只保留与 RoomID 有一对一关系的列。

Table: 1NF 的 Rooms

Rooms

RoomID	MeshID	TextureID	WorldPos	IsStart	IsExit
r1	msh_rmstart	tex_rmstart	0,0	true	false
r2	msh_rmtrap	tex_rmtrap	-20,0	false	false
r3	msh_rm	tex_rm	-10,20	false	false
r4	msh_rm	tex_rm	-30,20	false	false
r5	msh_rmtrap	tex_rmtrap	20,10	false	true

现在我们为 Pickups、Doors、Traps 制作新的表格。在表

中，可以看到为了满足第一范式而做出的诸多选择。我们把类似数组的元素拆分为独立的行。注意，这里用了多行来指定同一房间里的多个 Pickups。还有，门现在需要两个表了。第一个表用于确定门的位置和通向。第二个表看着类似，但只包括了被锁住的那些。实际情况是：需要通过 LockedDoors 表中的主键识别哪些门是锁的。再来看 Doors 表，显然这两列都不能作为主键：两列值都有重复。但这里数值组合是唯一的，因而主键是由两列组成的。在 LockedDoors 表中，FromRoom 和 ToRoom 均可用于查询 Doors 表中的内容。这种被称为外键(Foreign Key)，表示这些列能够直接映射到另一个表的主键。在这里，主键是由两列组成的，所以 LockedDoors 表有一个大外键，并且在外表(Foreign Table)中有关于该条目的额外细节。

Table: 应用1NF 的 Rooms 补充表格

PickupInstances

RoomID	PickupID
r2	k1
r3	k2
r3	a1
r3	p1
r4	k3
r4	p2

Doors

FromRoom	ToRoom
r1	r2
r1	r3
r2	r1
r2	r4
r3	r1
r3	r2
r3	r5
r4	r2

LockedDoors

FromRoom	ToRoom	LockedWith
r1	r3	k1
r2	r4	k2
r3	r5	k3

Traps

RoomID	Trapped
r2	10hp
r5	25hp

随关卡文件变得复杂，空条目和数组的量也会随之增加。因而像这样布局数据，在大型项目中的空间占用反而会比较少。同时还能够在避免重新评估原始对象的前提下，添加新的功能。比如要添加怪物，通常情况下，不仅要为怪物添加一个新对象，还要把它们添加到房间对象中。而在新的格式下，要做的就只是添加一个新的表格，如表

所示。

于是，在没有触及任何关卡原始数据的情况下，我们就已经知道怪物的信息及其刷新点了。

Table: 添加怪物

Monsters

MonsterID	Attack	HitPoints	StartRoom
M1	2	5	r3
M2	2	5	r4

第二范式 (2nd Normal Form)

第二范式用于分离那些只依赖部分主键的列。或许会有需要复合主键的表，但其行中的某些属性，只依赖于该复合主键的一部分。例如，表

中由品质和类型定义的武器，可以看到主键必须是复合的，该表中没有元素唯一的列。

Table: 1NF 的武器

Weapons

WeaponType	WeaponQuality	WeaponDamage	WeaponDamageType
Sword	Rusty	2d4	Slashing
Sword	Average	2d6	Slashing
Sword	Masterwork	2d8	Slashing
Lance	Average	2d6	Piercing
Lance	Masterwork	3d6	Piercing
Hammer	Rusty	2d4	Crushing
Hammer	Average	2d4+4	Crushing

不难看出，该表的主键应该是WeaponType 与 WeaponQuality 的复合键。根据当前武器查询伤害和伤害类型，非常正常的操作。再仔细看，伤害类型并不依赖于 WeaponQuality，而只依赖于 WeaponType。这就是上文中，取决于部分键的意思。尽管每个武器的定义都符合第一范式，但其伤害类型对主键的依赖性太小，因而其不满足第二范式。我们在表

中将该表分离出来，删除了只依赖 WeaponType 的那一列。如果发现有一种武器的伤害类型还会依赖于其品质，那就把这个表再复原回去。比如武器：严重损坏的晨星，不再造成穿刺伤害，现在造成打击伤害。

Table: 2NF 的武器

Weapons

WeaponType	WeaponQuality	WeaponDamage
Sword	Rusty	2d4
Sword	Average	2d6
Sword	Masterwork	2d8
Lance	Average	2d6
Lance	Masterwork	3d6
Hammer	Rusty	2d4
Hammer	Average	2d4+4

WeaponDamageTypes

WeaponType	WeaponDamageType
Sword	Slashing
Lance	Piercing
Hammer	Crushing

考虑第二范式的关卡数据的时，可以留心一些转移回第一范式的捷径。首先，不一定要使用 PickupID，可以通过 PickupType和 TintColour 来引用可拾取物。不过实际操作时会比较麻烦，而且因为护甲没有色调，反而会引入空项。表

就是这种情况，其中因为引入了 PickupID, 使得其与房间之间的关系变得尤为复杂。如果没有 PickupID，要把可拾取物放进房间，就需要有两个表。一张是有色调的可拾取物，另一张是没有的。虽然没那么蠢，但这种特殊条件下，好像也没那么纯粹。但是这种情况迟早会有，也算是正确选择了。

Table: 0NF 和 1NF 的 Pickups

Weapons

MeshID	TextureID	PickupType	ColourTint
mkey	tkey	KEY	Copper
mkey	tkey	KEY	Silver
mkey	tkey	KEY	Gold
mpot	tpot	POTION	Green
mpot	tpot	POTION	Purple
marm	tarm	ARMOUR	NULL

使用 1NF 标准化：

1NF 的 Pickups

PickupType	MeshID	TextureID
KEY	mkey	tkey
POTION	mpot	tpot
ARMOUR	marm	tarm

1NF 的 TintedPickups

PickupType	ColourTint
KEY	Copper
KEY	Silver
KEY	Gold
POTION	Green
POTION	Purple

再回来看原先的 Pickup 表。已知 PickupID 是 PickupType 和 ColourTint 组合的别名，就可以应用之前变换到 1NF 时的方法。即，将 MeshID 和TextureID 移到他们自己的表中，用对 PickupType 的依赖替换掉原先 PickupType 与 ColourTint 的复合键。

Table: 2NF 的 Pickups

Pickups

PickupID	PickupType
k1	KEY
k2	KEY
k3	KEY
p1	POTION
p2	POTION
a1	ARMOUR

PickupTints

PickupID	ColourTint
k1	Copper
k2	Silver
k3	Gold
p1	Green
p2	Purple

PickupAssets

PickupType	MeshID	TextureID
KEY	msh_key	tex_key
POTION	msh_pot	tex_pot
ARMOUR	msh_arm	tex_arm

PickupAnims

PickupType	AnimID
KEY	key_bob

现在还无法对房间表做同样的标准化处理。表中的 RoomID 可能是整个行的别名，也可能只是 WorldPos 的别名。但两种情况下，MeshID、 TextureID、 IsStart 的值之间都有关联。关键是，它还依赖外表中的条目。这样看来，MeshID 和 TextureID 都直接依赖于表中的 RoomID。

第三范式 (3rd Normal Form)

在进一步标准化之前，得先清除传递式的依赖。这里指的是表中的任何一列都只跟主键有依赖。这里快速过一下当前表格，可以发现，所有资源引用都依赖于 MeshID 和 TextureID。每个有 MeshID 的东西都有相应的 TextureID。所以，可以从所有表中剥离其中一个，生成一个新表用作查询。这里随机用了TextureID作为主键，并将网格和纹理信息填进表里(表

)。

Table: 3NF 的资源

WeaponDamageTypes

TextureID	TextureName	MeshName
tex_room	"roomtexture"	"roommesh"
tex_roomstart	"roomtexturestart"	"roommeshstart"
tex_roomtrap	"roomtexturetrapped"	"roommeshtrapped"
tex_key	"keytexture"	"keymesh"
tex_pot	"potiontexture"	"potionmesh"
tex_arm	"armourtexture"	"armourmesh"

Boyce-Codd范式(Boyce-Codd Normal Form)

一个房间用到的资源跟是否有陷阱，或是否是起始点有关。这种属于功能上的依赖，而非直接依赖。所以我们引入一个新列来描述这些内容，同时需要有中间数据用于间接查询，并促成房间和资源间的解耦。房间里可以有陷阱，也能作为起始房间，而与房间产生关联的资源取决于这两个属性，而非房间本身。这就是为什么 Boyce-Codd 范式(或 BCNF)，能作为功能依赖的标准化阶段。

Table: BCNF 后的 Rooms 表

Rooms

RoomID	WorldPos	IsStart	IsExit
r1	0,0	true	false
r2	-20,10	false	false
r3	-10,20	false	false
r4	-30,20	false	false
r5	20,10	false	true

Rooms

IsStart	HasTrap	TextureID
true	false	tex_rmstart
false	false	tex_rm
false	true	tex_rmtrap

域键和领域知识

领域知识能够帮助发现问题：比如将人类的价值判断放入断言。试想一个捕捉物理系统爆炸的断言。加速度的有效范围是什么？将其乘以 10，在事情失控之前，就有了一个检查。

一些应用会使用模糊的倒计时，替代传统的易误判的单位。如几分钟后或喝杯咖啡的时间。但领域知识不仅仅能够呈现人对数据的解释。例如，声速、光速、特定道路网上的限速和平均速度、心理声学特性、水的沸点，以及人对特定视觉输入的反应时间。这些事实在某种意义上有其用处。但只在程序员将其转化为程序性的，或作为特定实例的属性专门添加进来时，才可用。

再来看关卡数据，可以根据基本名来推断完整的文件名。纹理和网格名称使用相同格式。所以避免存储完整的文件名，便是一个领域知识的范式。

caption = BCNF 后的资源表[!ht]

AssetLookupTable

AssetID	StubbedName
ast_room	"room%s"
ast_roomstart	"room%sstart"
ast_roomtrap	"room%strapped"
ast_key	"key%s"
ast_pot	"potion%s"
ast_arm	"armour%s"

领域知识能让我们剔除一些不必要的数据。编译器的工作是分析代码输出（抽象语法树），为自己提供数据，在此基础上推断并使用其领域知识，了解哪些操作可以被省略、重排、变换，以产生更快或更低占用的汇编。而我们人的工作，是为编译器不知道的信息做同样的处理，例如，战斗中的人能够听到另一个房间里的硬币掉落的几率是多少？

领域知识催生了 JPEG 和 MP3 等格式。思考哪些是可能的，哪些能被感知，哪些会被用户行为影响，都能减少应用程序的工作量，并降低其复杂度。当玩家在有物理的游戏中跳跃时，也不必因为反作用力把世界向下移动几分之一纳米吧。

反思

对数据进行标准化处理时，我们看到的是一种按依赖关系分割数据的趋势。许多第三方引擎和 API 里，都能看到与这些标准化的影子。参与这些引擎设计和迭代的人，不可能拿着数据去应用数据库标准化技术。但有时对象和及其组成之间，可能分离的很明显，不需要标准的技术就能实现一些积极的结构变化。

一些游戏中，实体对象不单单是可以是任何东西的对象，而是游戏中实体类型的特定子集。例如，游戏中，可能有一个玩家角色的类，有不同类型的敌人角色的类，还有车辆类。玩家可能拥有不同于其他实体的属性，例如，无 AI 控制，玩家可控，可回复生命，有弹药等。这种面向对象的方法，在对象的类和实例之间划了一条线。虽然对用户来说不可见，但它会干扰开发者。同时也具备侵入性，类之间接触时，需要适应彼此。而如果几个类在不同的层次结构中，还必须通过抽象层传递信息。弥合这些差距所需的代码量或许不多，但终归只会让系统变得更加复杂。

实践中，常常是：实现对多个类执行操作的模板花费的时间，远多于将类向着离散化方向重构。就如同要考虑，是否有针对所有大于零的对象执行操作的可能，基本上属于浪费时间。而重构组件需要花费努力，通常与创建有效的模板操作不相上下。

如果没有类来定义边界，基于表的方法，将对数据的操作放到了同一水平线上。通过标准化关卡数据，我们已经知道，数据需要随同设计一起改变，并且尽量不要使状态变得不一致。我们常常在毫无必要的时候，把事情变得复杂，而能带我们走得更远的，只有实践和经验。

操作

在面向对象的情况下，可以直接通过调用方法对其执行操作。那在基于表的方法中，我们要如何打开门锁呢？总归是要有插入、删除、更新。在Edgar F. Codd 的文章中明确规定了这些行为。也即是操作关系模型的全部。

真正的数据库中，要找到需加载的网格，或检查某扇门是否上锁，通常需要表与表之间相互连接。数据库也会通过改变操作的顺序来优化连接，使预期开销尽可能小。但我们能做得更好。因为查看和请求表内数据的方式完全控制在我们手中。要检查一扇门是否上锁，这里不需要连接表，可以直接查到上锁的门的表。另外，虽然数据有跟数据库一样的布局，但不代表就必须得用查询语言访问。

涉及到改变状态的操作时，最好尽量模仿 DBMS 中常见的那种操作，意外的操作会引入复杂度。例如，假设分别有一份打开的门的表，和关闭的门的表。在表之间相互移动门显然是种浪费。所以可以考虑将其改为单表，所有关闭的门在一端，打开的门在另一端。将两个表合并成一个，并给数组设置截止点，隐式地定义 isClosed 属性。比如在代码

中，该表在某种程度上是有序的。这种内存优化也有其代价。在表中引入顺序，使得难以并行操作整个表。所以，这些改变就要多加留意，警惕其引入的复杂度，并整理好文档。

$\begin{lstlisting}[caption={setup 代码}, label={lst:2.2}, captionpos=b] type... ...gDoors_firstClosedDoor, d); gDoors_firstClosedDoor += 1; } \end{lstlisting}$

开一扇门锁可以被当做是一次删除操作。一扇门被锁住，是因为在 LockedDoors 表中有一个条目，对应玩家可能需要交互的门。如果门和玩家持有的钥匙匹配，那开锁就是一次“删除”。

玩家的背包则是一个只有 PickupIDs 的表。这就是之前提到的 "主键也是数据"。如果玩家进入一个房间，并拾取一个道具，那么将删除与该房间相对应的条目，而背包里会更新刚才的 PickupID。

数据库里有一个概念，触发器：对一个表的操作会引发一系列额外操作。捡起一把钥匙时，我们希望在放入背包时有一个触发器，将新的PickupID 与 LockedDoors 表连接起来。找到匹配的行，并删除它，门就解锁了。

总结

可以看出，数据库能胜任存储任何高度复杂的数据结构；即便是高度相关、设计快速变化的游戏数据，也不在话下。

游戏中有很多状态，而关系模型能提供一个强大的结构，可以保存静态、动态的信息。在这种结构下，实践中，相似的问题就有相似的方案，而相似的方案就会有相似的处理。使用时，数据布局更易推断，因而算法和技术也更易复用。

如果想找一种方法，能将相关联的复杂对象，变换为更简单扁平的内存布局。那可能很难比按照标准化形式来变换做得更好。

以数据库的形式存储数据还有一些比较有用的“福利”。它允许旧的可执行文件在新数据上运行，新的可执行文件也更容易在旧数据上运行。试想，如团队中有人分别使用新旧版本一起工作时，就会很有用。可以看到，有时添加新功能只需添加一个新表，或者在现有表中新加一列。此时，如果是用的数据库式的存储，这次修改就是非侵入性的；但如果要在类中添加一个新成员，恐怕就会是一次重大改变。

流处理

现在我们知道，游戏数据和运行时，都能用类似数据库的方式来实现。并且显然，游戏数据可以实现为流。如果长期存储是数据库，运行时的数据格式与磁盘上的一样，那么，我们能从中得到什么好处？数据库可以看作行或列的集合，也可以看作表的集合。此处的集合，指的是属性所有可能的排列组合。

对于大多数应用，用比特集来表示一个表会很浪费，大小很快就会超出任何硬件所能承受的范围。但从处理角度，这一点还是值得注意的。处理一个集合，将其转化为另一个，可以看作是遍历该集合并输出新集合。但集合有意思的点就在于，它是无序的。无序的表很容易并行处理。任何时候，只要有机会利用这种明显的并行性，就都能获得巨大好处；而由于面向对象方法的数据布局原因，我们通常无法接近这一点。

从另一个角度看，多年来，显卡供应商也一直朝着这个方向努力。我们现在也要以这种方式思考游戏逻辑。只要尽可能利用流处理或集合处理，并尽量减少随机存取，就能快速处理大量数据。这种情况下，流处理意味着，在处理数据时不写入进程外部的变量。意味着避免使用类似全局累加器这些，同时避免访问未被设置为进程输入的全局内存。这样就能够确保进程、变换能够并行。

想象为显卡准备图元渲染的场景：首先设置了一些常量，如变换矩阵、纹理绑定、光照值、着色器。运行着色器时，每个顶点和像素的可能都有自己的便签式存储(scratchpad)应对局部变量，但它们绝不会写入全局变量，也不会引用全局的便签式存储。通用 GPU 代码中的共享内存概念，如 CUDA 和 OpenCL 中使用的管理型缓存。没有哪一种 GPGPU 技术提供对全局内存的访问。因而它们能保持明确的领域分离，并持续保证，任意内核都能在其沙盒共享内存之外运行时，不会产生副作用。强制使用这种没有副作用的方法，就能确保这明显的并行性，因为操作顺序已经确定是不相关的。如果允许着色器写入全局，就会有锁，或者它会变成一个固有的串行操作。两种情况对于显卡这种的核心数目巨大的设备，都不是好事。所以一直以来，这都是从设计层面考量的，主动的限制。如果让共享内存参与进来，就会在整个过程中引入潜在的锁，因此需要明确地只在写计算着色器时使用。

经过一些列调整，没有了全局数据，我们可以清晰地看到一条高度并行化处理的路线。现在也更容易思考、检查、调试、扩展、乃至中断以适应新设计。只要能保证无序，就可以自由执行那些易出问题的测试。

为什么数据库技术很重要?

正如本章开头提到，关系模型目前非常适用于非稀疏数据布局的开发，一旦设计好了表，就可以操作，不太需要复杂的状态管理。然而，变化才是常态。现在还常用的，忽然可能就老办法，对于大型系统，关系模型也已不再提供所有需要的功能。

随着处理更大工作量的 NoSQL 方案出现，以及大公司在分布式计算方向的投入，处理巨大的数据集在技术方面已经取得了进展。在保持数据库的实时、分布式、一致性（在容许范围内）方面，也有了进展。现在的数据库经常包括 NULL 条目，甚至于 NULL 条目远远多于数值，这些高度稀疏的数据库，需要一个不同的解决方案。许多大型计算和进程，现在都通过一种叫 map-reduce 的技术运行。分布式工作负载已经变得足够普遍，以至于人们不得不提醒，做些加法运算不一定需要用到集群。

过去十年，已经很清楚的是，大多数证明有用的高级数据处理技术，都是类似于这种组合：函数式的高级算法应用于硬件感知的数据操作层。随着 PC 中的硬件变得越来越像互联网，这些技术将开始在个人硬件上占据主导地位，无论是个人电脑、手机、还是下一代的什么。面向数据设计的灵感来自于这样一种认知，即硬件已经发展到这种程度：我们过去用来抵御从 CPU 与硬盘的延迟的技术，现在也适用于内存。将来，如果能利用大量孤立的不可靠的计算单元来提高处理能力，那么我们在这个时代开发的服务器上的分布计算技术，可能会适用于下一个时代的桌面系统。