学习游戏机制 - 环境树

英文原文： http://www.squidi.net/three/entry.php?id=4

中文原文发布在： https://www.indienova.com/u/dualface/blogread/2838

这篇文章阐述了如何用树形结构来构建游戏环境，并且在环境中放置谜题的同时保证谜题有解。

这篇文章是 300 游戏机制网站上的内容，我觉得对我正在开发的独立游戏很有帮助，所以将其做了简单的翻译，以加深自己对原文的理解。

Introduction 介绍

Procedurally generated content (like random dungeons) is something of a holy grail for game design. The ability to instantly generate any and as much content as you’d like with infinite variety represents a game that could be played forever. Even games with the most rudimentary procedural content, like Diablo II or NetHack, represent some of the most popular and replayable games available.

程序生成内容（例如随机地下城）就像游戏设计中的圣杯（意为具有神奇的力量）。可以按照期望那样生成无限的游戏内容，让游戏可以永远玩下去。即便使用最基础的程序生成内容，例如 Diablo II 或者 NetHack，也是市面上最流行和最具重玩性的游戏。

Unfortunately, procedural generation is at best simplistic and obvious right now, used almost exclusively to design dungeon layouts - and even then, it rarely surpassed the quality of a kid with a level editor. I believe that procedural content could be used to design full games, beginning, middle, and end to a quality at least above the average game designer’s. That day is far, far off.

不幸的是程序生成现在充其量只能实现一些简单和浅显的内容，几乎主要用于生成地牢布局。即便如此，程序生成的地牢布局甚至很少超过一个孩子使用关卡编辑器设计的品质。我相信程序生成可以用来设计一个完整游戏，直到超过一般游戏设计师的水平，但这一天还很远。

This idea is less an gameplay mechanic and more of a gameplay design mechanic. In simple terms, by describing the game world in a tree structure, it becomes very easy to intelligently place puzzles without worrying about creating an unwinnable situation.

这篇文章的内容更少谈及游戏玩法机制，而是更多偏向设计机制。简单来说，通过在一个树形结构中描述一个游戏世界，可以很容易的在世界中增加谜题，又不至于造成谜题不可解。

Description 说明

This is the map I’ll be using as an example. It consists of two floors and the roof. The blue doors are simple doors that can be closed or open, while the light gray doors are invisible doors - seemless divisions between two rooms. We can close and lock regular doors, but there’s nothing there to close seemless doors. We can still block off the seemless doors, but we have to place an obstacle there, like a fire or barrade. The difference is mostly cosmetic (ie what kind of barrier is required).

这是我用来作为例子的地图。它包含两个楼层和一个屋顶。蓝色的门可以直接关闭或者打开，而灰色的门是隐形门（用于区分两个房间）。我们可以关闭和锁上一般的门，但不能关闭这些隐形门。我们仍然可以堵住隐形门，但我们需要放置一些装饰物，例如灭火器或者障碍。障碍物的差异主要在视觉上（例如选择什么类型的障碍物）。

作者这段话的意思，是说地图中有两种门：一般的门和隐形门。一般的门可以打开或者关闭，而隐形门是不可以关闭的。隐形门的作用是将每一层的地图划分为一个个的房间，方便我们在树形结构中描述整个地图。

This is the spatial tree that represents the logical spaces within this building and you’ll notice that they follow the same order that you would encounter them. This is a very simple tree as there’s no loop backs, one way doors, or multiple points of entry (ie stairs and elevator), but you get the point.

这是一个描述地图中逻辑空间的树形结构，按照你在地图中遇到的顺序。这是一个非常简单的树形结构，因为房间没有回路、单向门或者多个入口（例如楼梯和电梯）。

这一段说得不是很清楚，因为这张树形结构的图和前面房间地图没有标注出对应关系。所以我重新做了一张图，并标注了房间和树形结构之间的对应关系。

按照我这张新做的图，就可以很容易把房间和树形结构对应起来了。

Here’s where the magic happens. Let’s say we want three puzzles total, and for the sake of simplicity, they will be simple key/door puzzles - they could be anything that requires X and rewards Y. In this case, the puzzle requires X (a key) to access a new area, which will either contain a key or victory.

魔法就发生在这里（树形结构）。假设我们想要三个谜题。为了简单起见，谜题是简单的寻找开门钥匙（或者是需要 X 来获得 Y 的任何谜题）。在这个例子里，谜题需要 X （一把钥匙）来（打开锁上的门）访问一个新区域。进入新区域将让玩家获得一把钥匙或者取得胜利。

You’ll notice in the above tree that each of the blue lines corresponds directly with a doorway, and if we lock one of those connections, than all nodes below are equally locked. That is, we cannot get to any room through that door and the tree makes it really easy to tell which rooms those are. For instance, say we wanted the final victory to be in the shed on the roof. If we were to lock the roof, it would look like this:

在上面的树形结构中，你会注意到蓝色线条通过每个房间之间的门。如果我们锁定其中一条连接（关上一个门），那么这条线上所有的节点都会被锁定。也就是说，我们无法通过那扇门进入其中的房间，而树形结构可以很容易确定那里有哪些房间。例如，如果我们希望获胜的区域在屋顶的棚子里，那我们就像下图一样锁住屋顶：

This tells us one very, very important thing. All white nodes are a valid location for the key to the red area. So long as we keep this in mind, we can build the puzzle tree backwards, and always have a valid and solvable experience. Let’s place the key on the second floor, then lock the second floor, putting the key to that in the back room. Then we’ll lock the back room, and put the key to that in one of the rooms off the hallway.

这张图告诉我们一个非常非常重要的事情。所有白色节点都是到达红色区域的有效位置。只要我们记住这一点，我们可以向后搜索树来构造谜题，并且能够确保谜题总是有解。让我们把（进入屋顶的）钥匙放在二楼 R6 房间，然后锁住二楼，再把（打开二楼的）钥匙放在后面（向后搜索树）的房间里。最后我们锁定这些放有钥匙的房间，并将第一把钥匙放在一楼走廊旁边的 R4 房间里。

See? It’s a very simple algorithm to implement and understand, even if you include criteria for where to place locked doors (ie don’t lock off an empty area, don’t lock too large an area, etc). We can even make it a little more interesting by changing the keys into puzzles. For instance, a room could have a boss monster in it that you have to defeat to get the key, or there could be a safe that requires a combination from another room (at equal or lesser locked level) to open. Each puzzle requires a number of inputs (even zero, such as finding a key on the floor) and yields a number of outputs. The puzzle tree can be created (again, backwards) be using the environment tree as reference.

看见了没？这是一个非常容易理解和实现的算法，只要在锁定房间时包含一些条件（不要锁定任何空白区域，也不要锁定太大的区域）。我们甚至可以将钥匙变成更有趣的谜题。例如，一个房间里可能有一个 BOSS 怪物，你必须击败它才能拿到钥匙。或者房间里可能是一个保险柜，必须从其他房间（在相等或更早锁定的级别）中寻找密码来打开它。每一个谜题需要一组输入（甚至为 0，例如在地板上找到一把钥匙），并产生多个输出。谜题树可以参考环境树来创建（注意，向后搜索）。

这两段里反复提到了 向后搜索 。所谓向后搜索，就是在树形结构里，从叶子节点往父节点搜索。从玩家更后到达的区域往更早到达的区域搜索，例如设置谜题时应该从 屋顶 往 二楼 搜索，再往 一楼 搜索。

Hopefully, it should be obvious that defining the world environment in this tree format could also be used to generate an environment. If you created a rule set which defined what kind of nodes can be children of each other, it could be a relatively simple process that could create very logical and usable spaces that could far exceed the potential of traditional random generated areas.

如果顺利的话，可以用这种树形结构来定义世界环境。如果你创建了一组规则来定义节点可以有什么类型的子节点，那么它可能是一个创建出非常符合逻辑和可用性空间的相对简单的过程，远远超出传统的随机生成区域。

Considerations 考虑

• This is a very simplistic version of the system that requires exploration to be multi-linear. This version does not include, for example, the ability to enter a room from two different directions. Most adventure games are not really that wide open in practice. For instance, a game like Silent Hill only allows you to enter a zone from one entrance, but may open a one-way locked door back to a previous zone to shorten the trip. Something like that would be trivial to add and work in a manner similar to the puzzle locking.

• 这是一个多线探索系统的简单版本。这个版本不包括从从两个不同方向进入房间的能力。实践中，大多数冒险游戏并非那么开放。例如 Silent Hill 只允许从一个入口进入一个区域，但也许可以打开一个单向锁定的门来缩短返回之前区域的行程。像这些功能可以用类似密码锁的方式来实现（我猜测应该是解决某个谜题后，才能找到那个单向门，让玩家可以少跑路）。

• A strictly non-linear zone would probably be a single node in the graph, but could still benefit from it. For instance, the path you take through the oil refinery may be open pathed, but you will still do the oil refinery after the sewers. Or perhaps a large open area may be broken into smaller zones, such that a node doesn’t refer to a single room but a collection of rooms that are all unlocked simultaneously upon entering.

• 严格意义上的非线性区域或许应该是 图 （一种数据结构）中的单个节点，但我们仍然可以从树形结构中获得好处。例如，通过炼油厂的路径是开放式的，但你仍然可以在设置路径后再设置炼油厂。或者说可以把一个大的区域分解为多个小区域，只不过树形结构上的一个节点不再对应单个房间，而是对应一组房间，并且在进入时同时解锁这些房间。

这一段有点迷糊。我仔细思考了一下，原作者应该是想表达这样的意思：

从游戏设计上，炼油厂是一个很大的区域，允许玩家在里面自由行动（开放区域）。但在逻辑上，我们可以把炼油厂划分为很多小区域（房间），这些小区域作为一个整体对应到树形结构的一个节点上。当玩家进入炼油厂（或者解开某个谜题）的任何一个区域时，就同时解锁炼油厂的所有区域。

• One could probably take a pre-created floorplan and build a tree from it. Based on the assumptions made (for instance, you start by going in the back door instead of the front), it could generate a very different looking tree. Perhaps there could be a method for creating a union of multiple trees to factor in multiple points of entry. For example, there could be a hallway and adjacent rooms that can only be entered from one entrance no matter how many door enter the floor - thus it can be assumed to be a single subtree, shared between the two different versions of the world. Or if you locked an area in one tree, how the changes are reflected in the other tree could tell you whether it was a good idea.

• 人们可能会基于一个预先创建的平面图来构建树形结构。基于所做的假设（例如，你从后门开始进入地图而不是从前门），那么会得到一个看上去有很大区别的树。也许可以有种方法创建多个树的并集来实现多入口。例如，从走廊到相邻的房间只有一个入口，而不管有多少门可以进入楼层 - 这（从走廊到相邻房间）可以视为一个单独的子树，在世界的不同版本之间共享。或者，你可以尝试在一个树中锁定一个区域，并思考如何在另一个树中如何反应这种改变，就可以告诉你这是否是一个好主意。

这应该是原作者的一种假设。根据一块区域的不同入口，为这块区域制作多个树形结构，然后找到如何在多个树形结构间同步改变的方法。我个人认为这是一个可行的方案。

• Multiple points of entry is definitely a tricky subject. Luckily, most adventure games have absolutely no use for it. It can be faked, ignored, or carefully avoided in most cases. Coming up with a good solution to multiple points of entry is more a subject of pride and curiosity than a pragmatic solution to a desperate problem.

• 多个入口绝对是一个棘手的问题。幸运的是大多数冒险游戏都没有用到多入口。多数情况下可以通过一些手段来伪装成多入口，或者避免出现多入口。解决多入口的方案，是一个值得骄傲和满足好奇心的主题，但不是对一个棘手问题的务实解决方案。

我想原作者的意思是不要在这种坑爹的问题上浪费时间，赶紧把你的游戏撸出来才是正事 ^_^

后记

原作者在这篇文章的基础上，还写了几篇其他文章，进一步探讨了用树形结构来实现程序化内容生成的主题。我会在接下来的时间里继续学习，顺便把文章翻译出来。

-EOF-