游戏邦在:
杂志专栏:
gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

从Prolog系统看程序生成内容测试方法

发布时间:2013-12-26 09:15:57 Tags:,,,

作者:Michael Cook

对于某些开发者来说,这系列关于程序生成内容的文章真是喜忧惨半。如果你要生成一个世界地图,你可能就不会对它有太多要求。只要一小块地,没有太多山峰——除此之外,只要随机加点东西即可。但如果你有极为特殊的要求时要怎么办?那么你就要先测试一下你所生成的内容,以确保玩家看到的是合理的内容。对许多说,这是个棘手而骇人的任务。你究竟会怎么自动测试益智物理游戏呢?我们现在就来分享一个适用于测试即时物理游戏的新方法。

cut_the_rope(from gamasutra)

cut_the_rope(from gamasutra)

看过Mohammad Shaker、Noor Shaker和Julian Togelius所著的《以模拟方法扩展<割绳子>的可玩内容》这篇论文的人就会知道,该文章描述了Ropossum(《割绳子》的关卡生成器)的开发过程,尤其是他们如何为这款、物理即时游戏植入解算器的方法。它本身只是一个小小的项目,但论文作者希望这一方法也可以运用于其他类型的游戏。

这三名作者对Ropossum做了大量研究,写了多篇论文分析该项目的不同元素。关卡生成器使用了计算演变来放置游戏世界中的对象,以便形成谜题,然后再使用一系列方法评估这些关卡——人类设计师可以针对混合型方法提供反馈;正如我们现在所见,它还可以自动校正其生成关卡的可玩性。也许某天我们会再见到关于Ropossum系统的其他专栏文章,但今天我们主要探讨它的可解性问题。

程序生成内容主要涉及不可预见性与可靠性之间的平衡。一方面,我们想生成人们之前没有见过、不需要人类设计师动手的内容。但如果没有人类设计师来调整内容,我们就很难确保其生成的东西具有可用性和趣味性。如果我们生成谜题,就需要确信它存在解决方案。

对于回合制或基于网格的益智游戏来说,这并不算太棘手。事实上,解决这方面问题的人工智能面世已有一段时间了,它可以创造象棋迷题或者生成当前桌游的修改版本。制作回合制以基于网格的游戏意味着,它很容易用电脑来表示,你可以轻松探索其潜力。但如果是即时游戏,并且像物理游戏一样每一帧都需要大量复杂系统时,这里的问题就会成倍放大。

所以在此的问题就是:针对《割绳子》这类游戏的关卡设计,确定它是否能解决问题,如果可能的话还要提供能够引向解决方法的一系列操作。这篇文章所提议的方法是使用一个Prolog解决器与模拟游戏同时运行。

在每个时步中,游戏会被转换为Prolog能够理解的描述,之后解决器会使用这个表示法来算出当前可以执行哪个步骤。如果你从来没听说过Prolog,不用担心,你将从以下短例中领悟其要旨。下面就是该论文对于《割绳子》关卡的Prolog表示法描述:

candy(527, 140). velocity_up. velocity_to_right.
frog(390, 330). rope(550, 50, 105).
rope(440, 50, 195). air_cush(507, 195, 4).
reachable(rocket).

其中有些是真实情况,例如candy(X,Y)代表糖果在2D空间的坐标轴。其他元素则更为微妙——reachable(C)意味着组件C在当前的轨道有可能触及糖果,所以如果糖果向上漂浮,那么下面的对象就无法触及糖果。

这有助于系统推断出哪些步骤可行或不可行——如果糖果无论你等多久都不会靠近某个组件,那么就没有必要去激活它。

现在,假设我们正在看这个游戏状态描述,我们要找到下一步操作。在某个《割绳子》关卡中,我们能执行的只有几个操作,例如推动气垫或割绳子。我们怎么知道哪些操作会生效呢?该论文作者指出了Prolog能够查看某一操作当前是否“合理”的一系列规则。例如,按压气垫我们可能会检查:

air-cush_press :- air-cush(X,Y,Dir), candy_in_dir_of_air-cush(X,Y), distance(X, Y, 80).

换句话说,如果关卡中有一个气垫,糖果恰好位于气垫的方向,并且离气垫够近,我们就可以摁压气垫,否则就没有意义了。论文作者称这些操作可使用启发法——如果你正在为自己的游戏编写方法,你可以想象一下为自己所处理的机制创建自己自己的启发法。重要的是,这些规则包括一个相当于等待或者不采取行动的“无效”操作。多数时候,这正是模拟器将发挥作用的情况。

游戏本身也会和这个Prolog系统一起运行。这个系统通过模拟游戏引擎的时间间隔来运行,之后会向Prolog系统发送游戏状态,以便查看玩家可采取哪个操作。如果当前玩家有多个可执行操作,该系统就会扩散其模拟游戏,并以深度优先的方式继续检索游戏。下图显示了在系统探索选项的过程中,一系列可行操作树的创建方式。当它到达一个失败状态时,系统就会简单地回溯,直至发现一个它从未探索到的选项。

tree of possible moves(from gamasutra)

tree of possible moves(from gamasutra)

当然,如果游戏每秒更新60次,那么任何两个时步之间可能没有什么情况发生了。作者指出如果你用Prolog系统检查每一帧的话,那么你的系统会很快降速。所以,他们部署了一个在完成一个操作后的延迟中加入的变量时间步,此时Prolo引擎不会执行任何检查。有些操作有较小的延迟,因为它们之后通常很快就会跟上其他新操作(游戏邦注:例如割绳子)。而其他操作,例如引爆火箭,则有更长的延迟。这全部取决于你所分析的游戏类型,但通常情况下,游戏设计师很容易想到这些启发法。

所以该系统的实质可归结为游戏原生、持续、即时模拟以及Prolog中简洁的逻辑表示法之间的关系。Prolog系统通过选择合理的时间间隔,以及检测合理操作的良好直觉,生成了一系列完成关卡的操作。当然,有些游戏设计可能不适合这种方法。《割绳子》只是让玩家与屏幕上的东西互动,这里没有什么新组件或者那样复杂的东西。游戏中的许多操作实际上是在减少可行空间,例如扎气球或割绳子。虽然如此,该论文还是清楚地描述了一个解决这类问题的良好框架。我认为这可以扩展到更广泛的游戏类型。

我们无暇一一提及该论文中的内容——正如我在开篇所言,我们还可以找到其他关于Ropossum的论文,因为这是一个庞大的研究课题。例如,渐进关卡生成器能够与人类设计一起执行关卡设计。人类设计师可以修改特定的设计环节,并要求系统重新设计其余元素。像这种混合型的工具将成为未来游戏设计的重要特征。(本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转载,如需转载请联系:游戏邦

The Saturday Paper – Guaranteed Candy

by Michael Cook

For some developers, all this talk of procedural content generation is bittersweet. If you’re generating a world map, for instance, you probably don’t have too many requirements of it. A bit of land, not too many mountains – other than that, the randomness is part of the appeal. But what if you have very specific requirements? Well, then you’d need to test the content you generate to make sure it’s okay to give to the player. For many games this is a tricky and daunting task. How on earth would you automatically test a physics puzzle game, for instance? I’m glad you asked. This week on The Saturday Papers – a novel approach to simulation that can test real-time physics-based games (and more).

We’re reading Evolving Playable Content for Cut the Rope through a Simulation-Based Approach by Mohammad Shaker, Noor Shaker and Julian Togelius. The paper describes the development of Ropossum, a level generator for Cut The Rope, and specifically talks about how they implemented a solver for the game, despite the fact that it’s complex, physics-driven and real-time. It’s a neat little project in its own right, but the authors are hopeful that the approach could be applied to many other types of game, too.

The authors have done a lot of work on Ropossum, and written multiple papers about different elements of the project. The level generator uses computational evolution to place objects in the game world to form a puzzle, and then can evaluate those levels using a variety of approaches – human designers can give feedback for a mixed-initiative approach; it can use a selection of custom heuristics (more on those in this paper); and as we’re going to see today, it can also automatically verify playability of a level it generated. We’ll no doubt see the rest of the Ropossum system in another column some other day, but for now – solvability.

Procedural content generation is all about the balance between unpredictability and reliability. On the one hand, we want to generate content that no-one has seen before, without needing a human designer to be there to do it. But at the same time, if there’s no human designer to curate the content, we need to be confident that what comes out is usable, and hopefully fun. If we’re generating puzzles, we need to be confident that a solution exists.

For turn-based or grid-based puzzle games, this isn’t too tricky. In fact, artificial intelligence has been looking at this kind of problem for a long time, inventing chess puzzles or producing altered versions of existing boardgames. Making a game turn-based and grid-based means that it’s easy to represent within a computer, and you can easily explore the space of possibilities. When a game is real-time, though, and when it has lots of complex systems at work in each frame like a physics-based game, then the problem gets many orders of magnitude harder.

So the problem is this: given a level design for a game like Cut The Rope, decide whether or not it can be solved, and if possible provide a series of actions that would lead to a solution. The way proposed in this paper uses a Prolog solver that runs alongside a simulation of the game. At each timestep, the game is translated into a description which Prolog can understand, and then the solver uses this representation to work out what sensible moves can be taken right now. If you’ve never heard of Prolog before, don’t worry – you’ll get the gist from a quick example. Below is a description of a Cut The Rope level in the paper’s Prolog representation:

candy(527, 140). velocity_up. velocity_to_right.
frog(390, 330). rope(550, 50, 105).
rope(440, 50, 195). air_cush(507, 195, 4).
reachable(rocket).

Some of these are obvious facts, like candy(X, Y) which states the candy’s co-ordinates in 2D space. Others are more subtle – reachable(C) means that the component C is accessible to the candy given its current trajectory, so if a candy is floating upwards then things below it aren’t reachable. This helps the system infer what moves are sensible or not – if the candy is never going to get near a component no matter how long you wait, then it’s not sensible to activate it.

Now, suppose we’re looking at this description of the game state, and we want to figure out what to do next. There are only a few moves we can make in a given Cut The Rope level, like pushing an air cushion or cutting a rope. How do we know which actions are likely to have an effect? The authors suggest a set of rules which Prolog can check to see if a move is ‘sensible’ currently. So for instance, for pressing an air cushion we might check:

air-cush_press :- air-cush(X,Y,Dir), candy_in_dir_of_air-cush(X,Y), distance(X, Y, 80).

In other words, we can press an air cushion if there is an air cushion in the level (obviously); if the candy is in the direction of the air cushion (otherwise there’s no point) and if the candy is near enough to the cushion to be affected by it. The authors suggest heuristics for each of these actions – if you were writing them for your own game, you can imagine inventing your own heuristics for whatever mechanics you’re dealing with. Crucially, this set of rules includes a ‘void’ action which equates to waiting, or not taking an action. Most of the time, this is what the simulator will be doing.

Running alongside this Prolog system is the physics engine of the game itself. The system works by simulating an interval of time in the game engine, and then sending the game state over to the Prolog system to see which actions, if any, are available to the player. If there’s more than one action available, the system branches its simulation of the game and continues to search, in a depth-first fashion, through the game. The image below shows how a tree of possible moves is built up as the system explore its options. When it reaches a failure state, the system simply backtracks until it finds an option it hasn’t explored yet.

Of course, if the game is updating sixty times a second then there probably isn’t much going on between any two timesteps. The authors note that if you check with your Prolog system every single frame then your system very quickly slows down. So instead, they implemented a variable timestep which adds in a delay after an action has been taken, where no checks are made with the Prolog engine. Some actions have small delays, because they often are followed very quickly by new actions (like cutting ropes). Others, like firing rockets, have longer delays. This is all unique to whatever game you’re trying to analyse, but these heuristics are normally easy to figure out for the game’s designer.

So the essence of the system boils down to the relationship between the game’s raw, continuous, real-time simulation, and the elegant logical representation in Prolog. By choosing reasonable time intervals, and having a good intuition of which moves are sensible at any moment, the Prolog system can help tame this huge state space, and figure out a sequence of actions that completes a level. Of course, some game designs may not suit this. Cut The Rope only lets the player interact with what’s on screen, there’s no placement of new components or anything complex like that. And many actions in the game actually reduce the possibility space, by popping bubbles or cutting ropes. Nevertheless, the paper clearly describes a really nice framework for solving these kinds of problems. I think it could easily be extended to a wide variety of game types.

I didn’t have time to cover everything mentioned in this particular paper – and as I mentioned in the introduction, there are other papers about Ropossum because it’s such a large piece of research. For example, the evolutionary level generator can work with a human designer to co-operate on a level design. The human designer can fix certain parts of the design and ask the system to redesign the remaining elements, for example – all the while ensuring the results are solvable. Mixed initiative tools like this are going to be an exciting feature of game design in the future.(source:gamasutra


上一篇:

下一篇: