作者：Daniel van der Meulen

生成程序的发展

基于程序创造关卡似乎能够有效地减少开发时间。但是每次当你去运行它时都要去创造一个能够生成理想结果的算法，而这与设计一组关卡一样需要消耗大量时间。通常大量开发时间都是用于评估生成结果并添加某些限制因素去确保所创造的内容具有可玩性。通过将这种生成内容验证法作为一种优化问题，我们便可以使用现有的算法去找出适合预期结果的解决方法。

像爬山法等简单的优化算法便足以帮我们找到一个有关单一变量的解决方法，但在关卡生成环境中并不存在一种单一的最优解决方法，并且这里可能存在多种变量去推动生成算法的演变。因此遗传算法便是帮助我们找出可行解决方法的内容。遗传算法模仿了自然选择一个问题解决方法的过程。这会生成一组解决方法，然后它们能否解决问题的能力将得到评估。最终最佳解决方法会脱颖而出，并与其特征（变量）结合在一起去创造出全新，且更厉害的解决方法。

geneticAlgorithmOnLevels(from gamasutra)

在我们随着时间的推动去发展我们的关卡前，我们首先需要一个程序内容生成算法。像这样的生成程序可能会是一个非常复杂的算法，但即使是一个只有一些变量的简单执行方法也是足够的。这里所存在的必要条件在于需要一些让我们能够调整算法结果的变量。这些变量将作为生成解决方法的“染色体”并且会随着全新生成内容的出现而发生改变。

生成内容

对于《Captain Collo》，我正致力于创造一个使用细胞自动机去生成2D网格中的大陆和岩石的生成器。在这里大陆和岩石将通过形成阻碍玩家的元素去影响整体的游戏玩法。玩家（和敌人）可以朝地面射击但却不能穿过它，并且玩家不能击破岩石层。在生成地面和岩石后，我便能够找到一个可以放置像敌人等兴趣点的适当位置。

前面几个关卡都是随机生成的。为了发展这些关卡，我们必须基于它们如何带给玩家满足感去评估它们（游戏邦注：也就是一个关卡的乐趣度）。然后我们可以使用这些评分去衡量这些关卡并尝试着将这些关卡的有效功能结合在一起以创造出一个更优秀的新关卡。

但是我们该如何评价这些关卡呢？我们如何才能知道哪个是好的哪个是糟糕的？在大多数遗传算法中都存在一个适应度函数能够评估生成解决方法。但我们却很难去编写一个能够解释生成关卡并分配给它一个适当分数的函数。

适应度函数

有些游戏摸清了玩家行为并权衡了各种游戏数据和玩家输入内容去创造适合玩家的游戏模式。这种玩家模式能够用于在线，实时或离线创造匹配该模式的游戏内容。不过这一方法也拥有一些弊端，特别是在扯到可移植性时，即说明它是针对于特定游戏的。对于独立开发者来说，玩家模式或玩家分析是非常耗时间的，并且可能在其它游戏中就不适合了，尽管这是作为一种有效的适应度函数。正是因为这些限制因素，我选择了基于玩家反馈的进化算法。

我想要使用明确的玩家反馈，即问清楚玩家对于生成内容的看法。我的游戏关卡一般持续时间都较短。每当玩家完成一个关卡时，我便会询问他们对刚刚玩过的关卡的看法。一开始我使用了一个5颗星的评级系统。除此之外还有很多寻求玩家反馈的方式。例如让玩家决定关卡的好与坏或者询问他们是否喜欢该关卡。

evolution loop(from gamasutra)

为了在不破坏游戏流的前提下找出获取反馈的最佳方式，我们需要进行更多的研究。而这种反馈的主要作用便是推动遗传算法的发展。基于这一算法的本性，我们向玩家寻求反馈的主要原因便是避免创造出更糟糕的关卡，即将玩家函数变成生成解决方法中真正的适应度函数。只要这么做能够创造出可以延伸到下一个关卡中的结果，我们便不再需要从玩家身上获取反馈。

个人和全局选择

基于这种方式使用玩家反馈去推动遗传算法存在一个显著问题。遗传算法的根本理念在于我们可以通过人为进化和随着时间发展的变化去创造解决方法。当我们在计算机上使用一个编写好的适应度函数去模拟完整的进化过程时，我们可以在几秒钟内模拟出几百甚至是几千个全新生成内容。而在面对基于玩家的适应度函数时，我们需要等待玩家去尝试并评价关卡生成内容。

当遗传算法只运行于一个玩家的一台设备上时便会形成一个问题。即在你看到一些有意义的结果前它可能会创造许多生成内容。所以这种方法或许更适合用于完整的玩家社区中。通过在一个服务器上运行遗传算法，在玩家上线时分配给他们全新关卡，我们便能够在较短时间内检索到许多关卡的适应度。这种进化方式虽然不能生成匹配单一玩家喜好的关卡，但却能够从整体上推动游戏的发展。

全新生成内容

在本文中，我提供给了你们使用遗传算法和明确的反馈去创造各种关卡以及更适合玩家的关卡的相关理念。

为了验证这一方法，我发行了一个基于该系统的游戏版本。一开始，概念验证拥有所有适当的基本成分；即关卡生成系统，面向玩家的评级系统以及将基于这些评价去创造全新解决方法的遗传算法。在这里最重要的问题便是这一系统是否能够创造出比生成随机结果的生成程序更有效的结果。

最后我想基于一个更广的研究范围去创造一个在线共享系统，即不仅整合区域生成内容，同时也将包含基于该方式所诞生的游戏机制。一旦完成了该系统，我们便能够看到游戏的进化方式以及与最初游戏间的区别。

（本文为游戏邦/gamerboom.com编译，拒绝任何不保留版权的转发，如需转载请联系：游戏邦）

Self-evolving game content using player feedback

by Dani?l van der Meulen

Self-evolving generator

Creating levels procedurally may seem like a good way to reduce development time. However, creating an algorithm that produces a desirable result every time you run it can be just as time consuming as designing a set of levels. A lot of development time goes into evaluating the generated result and adding constraints and checks to make sure the created content is playable. By approaching this validation of the generated content as an optimization problem, we can use existing algorithms to find a solution that fits the anticipated result.

Simple optimization algorithms, such as hill climbing or variations thereof, would be sufficient to find a good solution for a single variable, but in the context of level generation there won’t be a single optimal solution and there are probably multiple variables driving the generation algorithm. Therefor a genetic algorithm might just be what we need to find a solution that is applicable and playable. A genetic algorithm mimics the process of natural selection to find a solution to a problem. A set of solutions is generated and then its fitness is evaluated on how well it solves this problem. The best solutions are then selected and its traits (variables) can be combined to produce new, potentially better, solutions.

Before we can evolve our levels to become better over time, we first need a procedural content generating algorithm. A generator as such can be a very complex algorithm, but even a simple implementation with only a few variables may be sufficient. The requirement here is that there need to be variables which will allow us to tweak the outcome of the algorithm. These variables will function as the “chromosomes” of the generated solutions and will change every new generation.

The generation

For Captain Collo, I am working on a generator which uses an implementation of cellular automata to generate landmass and rocks on a 2D grid. The landmass and rocks influence the overall gameplay of a level by forming obstacles a player has to maneuver through. The player (and enemies) can shoot over land but not sail through it, but the player cannot shoot through rock formations. After the generation of land and rock formations, suitable places are found to place points of interest such as enemies.

The first few levels are randomly generated. To evolve these levels, the levels must be evaluated and scored on how well they satisfy the player, in other words, how much fun a level is to play. We can then use this score to evaluate how good these levels are and attempt to combine successful features of these levels to produce new, and hopefully better, levels.

But how do we score these levels? How do we know which ones are good or bad? In most genetic algorithms, there is a fitness function that evaluates the generated solution. But it would be very hard to write a function that can interpret the generated levels and assign it a proper score.

Survival of the fitness function

There are examples of games [1], [2] that adapt to player behavior and measure a lot of game statistics and player input to model the player. This player model can then be used to make the game content adapt to this model, either online, on the fly, or offline. This method has a couple of downsides, especially when it comes to portability, meaning it is generally very game specific, but also in creating a model that works. Player modeling, or player profiling, can be too time consuming for indie developers and may not be useful beyond a single game, even though it could be used as an effective fitness function. Due to those limitations, I chose to base the evolution of the algorithm on player feedback.

I want to use explicit player feedback, asking them what they think of the content generated. The levels in my game generally have a short play time. Every time a player finishes a level, they are asked what they think of the level they just played. For the first implementation I will use a 5-star rating system. There are, however, many different ways to ask the player for this feedback. Different approaches would be, for example, to ask the player to rank the levels they play from bad to good, or an even simpler implementation would be to ask whether the player liked the level or not.

More research needs to be done to find the best way to get this feedback, without breaking the flow of the game too much. However, the main function of this feedback is to drive the genetic algorithm forward. By the nature of this algorithm, the main reason to ask for this feedback is to eliminate the worst levels, making the player function as the actual fitness function of a generated solution. As long as it allows the best results to endure and reproduce into the next generation of levels, the way we gather that feedback from the player is less important.

Personal or global selection

There is one obvious issue with using player feedback in such a way to drive a genetic algorithm. The idea behind the genetic algorithm is that we can produce solutions by artificial evolution and evolution takes time. When we simulate the complete evolution on a computer, using a written fitness function, we can simulate hundreds or even thousands of new generations in a couple of seconds. With a player driven fitness function, we will have to wait until a generation of levels has been played and scored by the player.

This may form an issue when the genetic algorithm is run solely on one device for one player. It would probably take many a generation until you will see some profound results. Therefore this approach may be better suited to being applied to an entire community of players. By running the genetic algorithm on a server, distributing new levels to the players when they come online, we would be able to retrieve the fitness of a lot of levels in a small amount of time. The evolution would then not generate levels that adapt to a single player’s preference, but it would evolve the game as a whole.

The new generation

In this article I have given you an idea of the potential of using a genetic algorithm in combination with explicit player feedback as a solution to generate a wide variety of levels whiles also generating levels better suited for the player.

To validate this approach, I intend to release a version of the game with a working system like this in place. Initially the proof of concept will have all the basic ingredients in place; a level generation system, the rating system for the player and the genetic algorithm which will produce new solutions based on these ratings. The most important question would be whether or not such a system will produce better results than a generator which generates completely random results.

Ultimately I would like to build an online shared system with a much wider search-space, incorporating not only terrain generation, but also evolving game mechanics in this way. Once such a system is released, it would be very interesting to see in what way a game might evolve and how different that would be from the game that it was at the beginning.（source：Gamasutra）