游戏关卡设计_设计游戏关卡的人工智能

A couple of months ago, my son Hugo (12) and I decided to learn to develop games with Unity. We would do that by actually making one. We thought up a puzzle game called Elemaze, were little guys representing the four elements have to collaborate to figure out a path to a chest in a maze. We learned a lot about coding, graphics, game mechanics, etc. Hugo went on to create his own game, “A.I. Will survive”, as a challenge to himself (see it on itch.io and on Google Play) and we participated in 2 game jams (we didn’t do great really, but it is all about the experience and the fun). What we really learned however is that, once the basics are in, it is not the coding or mechanics or music or graphics that take time, it is making the levels.

几个月前，我的儿子雨果(12岁)和我决定学习与Unity一起开发游戏。 我们可以通过实际制造一个来做到这一点。 我们想到了一款名为Elemaze的益智游戏，是代表这四个要素的小家伙必须合作才能找出迷宫中通往箱子的路径。 我们学到了很多有关编码，图形，游戏机制等方面的知识。Hugo继续创作自己的游戏“ AI会生存”，这是对自己的挑战(请在i tch.io和Google Play上查看)，我们参加了2次游戏卡纸(我们并没有做得很好，但这全都与体验和乐趣有关)。 然而，我们真正了解到的是，一旦掌握了基础知识，花时间就不是编码，机制，音乐或图形所花费的时间。

So, this is a story of how we created a genetic algorithm to design levels for Elemaze. It is also a story of how more traditional approaches to AI are still incredibly relevant, much easier to implement, and, especially in the case of genetic algorithms, can come up with completely new, creative and impressive solutions to problems that would have us scratch our heads endlessly.

因此，这是一个关于我们如何创建遗传算法为Elemaze设计关卡的故事。 这也是一个故事，说明传统的AI方法仍然具有令人难以置信的相关性，更容易实现，并且尤其是在遗传算法的情况下，可以提出全新的，创造性的且令人印象深刻的解决方案，以解决那些使我们无所适从的问题我们的头不休。

Elemaze：游戏 (Elemaze: The Game)

The game we created is relatively simple, with emphasis on relatively. Each level is a maze, in a grid, where each cell/tile has a floor of one of four colours: white for air, blue for water, red for fire and green for earth. There is a chest somewhere in the maze, and the goal is for one of the four characters — airman, waterman, fireman and earthman — to get to the chest. Each character can be told to go to any other unoccupied cell in the maze and will follow the shortest path to get there. Simple enough so far, but obviously there is more. Each of the characters might get killed by a certain tile colour, and can change one colour to another. Namely:

我们创建的游戏比较简单，重点比较 。 每个级别都是一个迷宫，位于一个网格中，每个单元/瓦片的地板都具有以下四种颜色之一：白色代表空气，蓝色代表水，红色代表火，绿色代表地球。 迷宫中的某个地方有一个箱子，目标是让四个角色之一(飞行员，水手，消防员和土工)到达胸部。 可以告诉每个角色去迷宫中其他任何未被占用的牢房，并按照最短的路径到达迷宫。 到目前为止足够简单，但是显然还有更多。 每个角色可能会被某种特定的瓷砖颜色杀死，并且可以将一种颜色更改为另一种颜色。 即：

• Airman dies if walking on earth
  如果在地球上行走，飞行员死亡
• Waterman dies if walking on air, and changes fire into water
  沃特曼在空中行走时会死亡，并将火变成水
• Fireman dies if walking on water, and changes earth to fire
  如果在水上行走，消防员会死亡，并将大地变成火
• Earthman dies if walking on fire, and changes water into earth
  如果在火上行走，地球人会死亡，并将水变成地球

That creates a lot of interesting possibilities where one character will have to go change colours somewhere so, that another could get moving, but not before another one has gotten out of the way. Levels can be simple (move one character to open the way for another) or more complicated (several back and forth movements until one character can finally get to the chest). Coming up with those more complicated levels is, however, very hard. We created 18 levels by hand, most of them simple (2 to 4 steps), some slightly harder (5 and 6 steps), before deciding that we needed help.

这就创造了许多有趣的可能性，其中一个角色必须去某个地方改变颜色，以便另一个可以移动，但不能在另一个摆脱之前。 级别可以很简单(移动一个角色为另一个角色开路)，也可以更复杂(几个来回移动，直到一个角色最终到达胸部)。 但是，要想出那些更复杂的级别非常困难。 在决定需要帮助之前，我们手动创建了18个级别，其中大多数很简单(2至4个步骤)，有些难度稍大(5和6个步骤)。

准备基础 (Getting the foundations ready)

The perspective of spending hours to create enough levels for the game to be releasable did not fill us with happiness. We often came up with a level that we believed to be hard until we tested it and realised that there was a simple solution to it or no solution at all. Laziness being the driver of innovation, that’s when we thought: “Maybe we can AI this problem away!”. I have been doing research in AI and have taught many different AI techniques for a very long time. I knew the ingredients we had (a “design” problem with a relatively measurable success criterion: The level should be hard to solve), and the ones we didn’t have (thousands of examples of good levels, rules on how to make a level, etc). Genetic algorithms seemed ideally suited for this, but before starting, we had to put a lot of things in place, including a way to represent levels and a way to automatically (and preferably quickly) solve them.

花几个小时为游戏创造足够的关卡来释放游戏的观点并没有使我们感到高兴。 我们常常想出一个我们认为很难的水平，直到我们对其进行测试，并意识到有一个简单的解决方案或根本没有解决方案。 懒惰是创新的驱动力，那时候我们想到：“也许我们可以解决这个问题！”。 我一直在从事AI研究，并在很长一段时间内教授了许多不同的AI技术。 我知道我们所拥有的要素(一个具有相对可衡量的成功标准的“设计”问题：水平应该很难解决)和我们所没有的要素(成千上万个良好水平的例子，关于如何制定标准的规则)级别等)。 遗传算法似乎非常适合此操作，但是在开始之前，我们必须做很多事情，包括表示水平的方法和自动(最好是快速)求解它们的方法。

Skipping about a million details, we created a basic JSON format for the representation of levels (position of the chest, of each of the characters, and a matrix of cells with for each information about its colour and the directions a character could follow from it). We also came up with a way to display a level in the terminal (see below), because loading Unity every time we wanted to see a result was not going to work.

跳过了大约一百万个细节，我们创建了一个基本的JSON格式来表示级别(胸部位置，每个字符以及一个矩阵)，其中包含有关颜色和字符可能遵循的方向的每个信息)。 我们还想出了一种在终端中显示一个关卡的方法(见下文)，因为每次我们想要查看结果时都加载Unity是行不通的。

Given any level, we then needed to be able to solve it, so we could know, first, that it had a solution, and second, how hard it was to solve it (how many steps it took). Skipping many more details, we implemented the A* search algorithm where every step of the search corresponds to moving one character to a given cell in the level. The evaluation of the next step to try was based on the number of steps already done (g(n)) and, as an estimate of the cost of extending the path (h(n)), the minimum distance between a character and the chest, ignoring the walls. Since this is always underestimating the cost of reaching the chest from a given position, we are guaranteed, according to the properties of the A* algorithm, that the solution found is optimal. It will always find the solution with the shortest number of steps.

在任何级别上，我们都需要能够解决它，因此，我们首先可以知道它有解决方案，其次，我们知道解决它有多困难(采取了多少步骤)。 跳过更多细节，我们实现了A *搜索算法，其中搜索的每一步都对应于将一个字符移动到关卡中的给定单元格。 对下一个尝试步骤的评估基于已完成的步骤数( g(n) )，以及作为扩展路径成本( h(n) )的估算值，字符与字符之间的最小距离胸部，无视墙壁。 由于这总是低估了从给定位置到达胸部的成本，因此，根据A *算法的属性，我们可以保证找到的解决方案是最优的。 它总是会找到步骤最短的解决方案。

遗传算法 (Genetic Algorithm)

You would think that being able to solve a level does not get us very close to being able to invent one, right? Well actually, that’s the whole point of genetic algorithms: The one thing you need to make it work is to know what you are looking for in a way that can be tested. Genetic algorithms are based on the theory of evolution: Species become better adapted to their environment because of natural selection (“survival of the fittest”) and small modifications to the gene pool that add up over time (mutations). So the first thing we need is to be able to know how “fit” a level is. We need a fitness function that tells us whether a level is a good one.

您会认为能够解决一个关卡并不能使我们非常接近能够发明一个关卡，对吗？ 好吧，实际上，这就是遗传算法的全部要点：要使它起作用，需要做的一件事就是以一种可以测试的方式知道您要寻找的东西。 遗传算法基于进化论：由于自然选择(“适者生存”)和对基因库的微小修改(随着时间的推移而累积)，物种变得更好地适应其环境。 因此，我们需要做的第一件事就是能够知道“适合”某个级别的程度。 我们需要一个适应度函数，该函数可以告诉我们某个级别是否不错。

适合度 (Fitness)

So how do we know if a level is good? We want levels that are not too easy to solve, so for which solutions require a certain number of steps. So we can say that a level is fitter if it gets closer to an ideally large number of steps S to be solved. And it’s that simple. Say our solver returns (as it does) not only the solution for a given level l, but also the number of steps in that solution nsol(l). Our fitness function for level l can be as basic as

那么我们如何知道一个水平是否合适呢？ 我们希望级别不太容易解决，因此对于哪种级别的解决方案需要一定数量的步骤。 因此，我们可以说，如果某个级别接近于要解决的理想步骤S ，则该级别更合适。 就这么简单。 说我们的求解器不仅返回(给它)给定级别l的解决方案，而且返回该解决方案中的步骤数nsol(l) 。 我们对l级的适应度函数可以像

fitness(l) = min(S,nsol(l))/max(S,nsol(l))

适应度(l)= min(S，nsol(l))/ max(S，nsol(l))

If S is 12 for example, and the current level requires a 7 step solution, the fitness value of this level is 7/12, or 0.583. Note that in the code we use something slightly more complicated, as we added a component to the function that nudges levels towards being more compact (taking less space), but that can be mostly be ignored.

例如，如果S为12，并且当前级别需要7步求解，则此级别的适用性值为7/12或0.583。 请注意，在代码中，我们使用了稍微复杂一些的东西，因为我们在函数中添加了一个组件，该组件可将级别推向更紧凑的位置(占用更少的空间)，但大多数情况下可以忽略。

突变 (Mutation)

Assuming that we have a level, the next question is, what very small changes can be made to it so it might move towards a better solution (or, more likely, become an unsolvable, non-viable member of the species). Here, we can randomly change 3 things: The location of one of the characters, the colour of the floor in one cell or the walls in one cell. So what we do is randomly choose one of those changes, and apply them, on a random character or cell.

假设我们有一个水平，那么下一个问题是，可以对其进行很小的更改，以使其可能寻求更好的解决方案(或更可能成为该物种无法解决的，不可行的成员)。 在这里，我们可以随机更改三件事：字符之一的位置，一个单元格中的地板颜色或一个单元格中的墙壁的颜色。 因此，我们要做的是随机选择这些更改之一，然后将其应用到随机字符或单元格上。

产生人口0 (Generating Population 0)

We have fitness and we have mutation. We would normally, to be complete, also add crossover, i.e. the mixing of pairs of selected individuals so to create new solutions. We leave this out here for two reasons: To simplify an already long story, and because our first tests were done without crossover, and the results were great. With those two elements in place, the general process of the genetic algorithm is the following:

我们有健康，我们有突变。 通常，完整地讲，我们还将添加交叉，即将选定的个体对混合在一起，以创建新的解决方案。 我们将其保留在这里有两个原因：简化一个已经很长的故事，并且因为我们的第一个测试没有交叉就完成了，结果很好。 有了这两个元素，遗传算法的一般过程如下：

One bit that I haven’t talked about is Step 1: Generating an initial population. It turns out that creating a process by which a random but valid level could be generated was the most tedious part to do. Attributing random positions to the characters, random colours to the cells and placing random walls is not so much the issue, as is making sure that the level “made sense”. Characters should be placed on non-empty cells and not on top of each other (or on top of the chest). Walls should be placed so that you could not fall-off the level, or onto an empty cell, etc. To avoid unnecessary boring details, let’s assume we have that done, so on to selection!

我没有谈论的一点是步骤1：生成初始种群。 事实证明，创建一个可以生成随机但有效级别的过程是最繁琐的工作。 将角色随机分配给角色，将随机颜色分配给单元并放置随机墙壁并不是问题，而是要确保级别“有意义”。 字符应放置在非空单元格上，而不能彼此重叠(或在胸部顶部)。 墙的位置应确保您不会掉落到水平仪上或落在空的单元格等上。为避免不必要的无聊细节，让我们假设已完成此工作，然后选择！

选择和创造新一代 (Selection and creation of a new generation)

Selecting individuals for the next generation is done using “Roulette Wheel Selection” (or “Fitness Proportionate Selection”). The short version of describing it is that it is a way to “not completely randomly” select individuals in a population so that an individual with a fitness double the one of another would be twice more likely to be selected. In other words, it is a way to implement “survival of the fittest” that’s not as binary as the phrase makes it sound (it should be “highest probability of survival for the fittest”). It is like throwing, as many times as there are individuals in the population, a loaded dice where the weight on each face is proportional to the fitness of the corresponding individual. We then pick whichever individual the dice says we should pick, with the less fit individuals being likely not to go further, and the really fit ones possibly being picked more than once.

使用“ 轮盘选择 ”(或“健身比例选择”) 选择下一代个人。 描述它的简短形式是，它是一种“不完全随机地”选择总体中的个体的方法，这样，具有适应性两倍的人被选择的可能性就会增加两倍。 换句话说，这是一种实现“优胜劣汰”的方法，它不像短语听起来那样二元化(应该是“优胜劣汰的最高概率”)。 这就像掷骰子一样多，就像人口中有多少个人一样，掷骰子时每张脸的重量与相应个体的健康状况成正比。 然后，我们选择骰子说我们应该选择的那个个体，不太适合的个体可能不会走得更远，而真正适合的个体可能会被选择不止一次。

Now that we have a new population selected, we simply have to mutate some of them. As you might have realised by now, randomness is a big part of the process, so that’s what we do again: We randomly select a sub-section of the population (the size of which is given by the mutation rate) to which we apply the random mutation described above.

现在我们选择了一个新的种群，我们只需要突变其中一些即可。 正如您可能已经意识到的那样，随机性是该过程的重要组成部分，所以我们再次这样做：我们随机选择要应用的总体子部分(其大小由突变率确定 )上述随机突变。

那行吗？ (So, does it work?)

That’s it. We run fitness, selection, mutation for many generations, on a population with enough individuals in it, and in theory, something should happen.

而已。 我们在人口众多的人群中进行适应，选择，变异的世代相传，理论上应该会发生一些事情。

But what? The thing that amazes me most with genetic algorithms is that, if you describe it like this, as a process where completely random things are changed completely randomly through “generations” of almost randomly selected individuals, how could it possibly give you anything other than random results?

但是呢 遗传算法让我最惊讶的是，如果您这样描述，作为一个过程，其中几乎随机选择的个体的“世代”完全随机地改变了事物，除了随机性之外，它还能给您带来什么结果？

The answer to that is in the word “almost” in “almost randomly”: The fitness-driven probability of selection. Because individuals that are more fit are more likely to go ahead, on average, every new generation should be fitter. And because random mutations occur, new kinds of individuals (“mutants”) emerge which can either be fitter (and therefore more likely to pass the mutation on to future generations) or not (and therefore be more likely to disappear through not being selected).

答案就是“几乎随机”中的“几乎”一词：适应性驱动的选择概率。 因为更健康的人更有可能继续前进，所以平均而言，每个新一代都应该更健康。 而且由于随机突变的发生，出现了新的个体(“突变体”)，它们可能更适合(因此更可能将突变传递给后代)，或者不适合(因此更可能因未被选中而消失) 。

And that’s really the beauty of it. The only thing you need is to know how to recognise that something is good, and it will evolve your initially random solutions to be better and better. The final results look like they have been designed, but there is no information in the process about how to design a good solution, only about what is a good solution. It is incredibly exciting to see something being created like this, something that looks clever and that looks designed, but that is really only emerging from mutations having survived selection over several generations.

这确实是它的美。 您唯一需要做的就是知道如何识别某件事情是好的，它将使您最初的随机解决方案变得越来越好。 最终结果看起来像已经设计好了，但是在此过程中，没有关于如何设计好的解决方案的信息，只有什么是好的解决方案。 看到这样创建的东西，看起来很聪明并且看起来很设计的东西真是令人兴奋，但这实际上只是从经过数代选择幸存下来的突变中出现的。

Did we see this magic when we tried it on Elemaze levels? Absolutely!

在Elemaze等级上尝试时看到了这种魔法吗？ 绝对！

We initially ran the process multiple times looking for mazes of 4x4 cells with an ideal number of steps per solutions of 9, populations of 30 individuals, a mutation rate of 30% and a limit at 100 generations. Because solving that many levels takes time, each run took several hours (we ran everything multiple times on multiple computers). Naturally, the first generations were not very promising: most levels generated had no solution, and sometimes, we would have one with a solution in 1 step (i.e. move one character to the chest). However, in most of the processes, it eventually got to find levels requiring 4 steps or even 5. Several of the runs got to 7 steps, and a couple even found levels solved in 8, 9 and 10 steps. The graph below shows the number of steps of the best solution for one of the runs that led to a valid, playable 8-step level.

我们最初多次运行该过程，以寻找4x4细胞的迷宫，每个溶液有9个，理想的步数是9个，人口为30个，突变率为30％，限制为100代。 因为解决多个级别需要时间，所以每次运行都需要几个小时(我们在多台计算机上多次运行了所有内容)。 自然，第一代并不是很有希望：生成的大多数关卡都没有解决方案，有时，我们会一步一步解决(即将一个角色移到胸部)。 但是，在大多数过程中，最终要找到需要4个步骤甚至5个步骤的级别。一些运行达到7个步骤，还有几个甚至找到了需要8、9和10个步骤解决的级别。 下图显示了导致有效，可玩的8步级别的运行之一的最佳解决方案的步数。

As you can see, this follows the expectation: The population mostly becomes better, as it evolves across generations. The 8-step level in question was one of the first ones we tested in the game. It looks like this:

如您所见，这符合预期：人口随着代代相传的发展而变得越来越好。 有问题的8步级别是我们在游戏中测试的第一个级别。 看起来像这样：

It might not feel super impressive to you, but we had spent hours trying to figure out how to make levels for this game and how to construct them so that they are challenging enough to be interesting. This AI process invented a level— actually dozens of levels — that is not only playable but sophisticated, interesting and hard. The only thing it had to go on is: “we want levels that should take a lot of steps to solve”. Each run generated much more than one valid level (the one above also had interesting 6-step and 5-step, and even 10 step levels), from a few hundred lines of Python (using modules that are all shipped with Python2.7), on a laptop (without parallel processing, so only using one core) for a couple of hours.

它可能不会给您带来令人印象深刻的印象，但是我们花费了数小时试图弄清楚如何为该游戏制作关卡以及如何构建关卡，以使它们具有足够的挑战性以至于变得有趣。 这个AI流程发明了一个级别-实际上是几十个级别-不仅可以玩，而且复杂，有趣且困难。 它唯一要做的是：“我们希望应该采取很多步骤来解决的关卡”。 每次运行都从几百行Python(使用Python2.7附带的模块)中生成了不止一个有效级别(上述一个级别也具有有趣的6步和5步，甚至10步级别)。 ，在一台笔记本电脑上(无需并行处理，因此仅使用一个内核)几个小时。

The elegance of this kind of “intelligent” process is what makes it more interesting to me, especially if you compare it to something that would need multiple GPUs and thousands of training examples to achieve something remotely comparable. It is this elegance that also makes it more applicable, understandable and teachable. Hugo is 12, and for the last few days, we have been constantly talking about what size of populations would be best, how many generations we should leave the process to run for, which of our laptops should be given which configuration depending on the strength of its CPU, etc. We have also been sharing our amazement at seeing how levels were evolving, shouting across the house when one of the processes got anything above a 7-step level, and bursting with impatience at the idea of testing it.

这种“智能”过程的优雅之处使它对我来说更加有趣，尤其是将它与需要多个GPU和数千个训练示例以实现远程可比性的事物进行比较时。 正是这种优雅，使其更加适用，可理解和可教。 雨果(Hugo)是12岁，在过去的几天里，我们一直在讨论什么规模的人口才是最好的，应该让这个进程运行几代人，应该给哪种笔记本电脑配置哪种配置，取决于强度我们也一直惊讶于看到级别如何演变，当其中一个进程的任何事情超过7步级别时都在整个房子里大喊大叫，并对测试的想法感到不耐烦。

Our game is finished: You can download it from Google Play or on itch.io. 18 of the levels were made manually. The other 34 were designed by the genetic algorithm. Can you spot which ones they are?

我们的游戏完成了：您可以从Google Play或itch.io上下载它。 其中18个级别是手动制作的。 另外34个是通过遗传算法设计的。 你能发现他们是谁吗？