作者：Michael Cook

大多数程序生成器用于内容生成（如生成地下城格局或3D世界）是非常成功的——布置内容的过程进展得很稳定，就算偶尔有一棵树浮在半空中，游戏也不会受影响。然而，这种技术不太适用于更加严谨的游戏内容如谜题或剧情；即使是一个小错误，也可能被玩家利用来跳过大半进程或大大降低游戏难度。但是，你怎么判断一个谜题能否按合适的方式被解决？借本文，我们来看看程序生成器如何按照你希望的特征智能地设计谜题。

Gunpoint(from gamesbyangelina.org)

这次我们要解读的文章是Adam Smith、Eric Butler和Zoran Popovic所写的《Quantifying over Play: Constraining Undesirable Solutions in Puzzle Design》。在给教育类数学益智游戏《Refraction 2》设计谜题生成器时，该文作者作对AI和游戏设计展开调查，并在文中解释了他们如何确保程序谜题生成器产生具有特定解决方法的谜题，还要保证没有其他破坏性的解决方法能解决这些谜题。为此，他们设计了一个聪明的程序设计系统，它可以保证产生的结果满足某些目标——这是一个完全可重复利用的、适用于各种游戏设计项目的东西。

Puzzle(from gamesbyangelina)

我们再说说约束求解，那是我们几周以前在一篇关于“在地下城中布局怪物和道具”的文章中读到的。该文提供了更详尽的回顾和一些优秀的教程链接，但它的要点是：约束求解从程序而不是写指令产生你想要的结果。如果你可以用比较好的方式表现你的问题——一开始会很棘手，那么约束求解器就可以快速生成解决方案，即在匹配你给它的条件时，制作和取消可能的设计选择。

《Refraction 2》是一款关于分数的游戏。在游戏中，玩家要在激光束的路径上放小道具，使之转向、分裂、合并等，使激光束最终射进目标飞船，给它充能。游戏设计的谜题要求玩家分裂和合并激光束，如合并两个1/16激光束，给需要1/8能量的飞船充能，以测试玩家的分数算术能力和其他概念。事实上，上文作者已经就此写了另一篇关于使用线束求解法设计谜题的系统的文章。那么，这次他们想说的是什么呢？

Puzzle(from gamesbyangelina)

如上图，你可以看到左半图是一个非常漂亮的解决方法——把激光束分裂成两速避开陨石后又合并为一束，最后达到飞船处（相当完美的对称）。而在右半图，你可以看到图中的解决方法太偷懒了，完全回避了谜题的关键部分。避免这种捷径出现，方法之一是制作一种系统，由它对谜题做各种可能的测试，以保证没有任何解决方法会破坏你给这个关卡设计的规则（如告诉玩家如何分裂激光）。但鉴于文章中指出的大量理由，这种系统实在算不上高明——一方面，太费时间，特别是如果线束条件根本无法满足；另一方面，这种系统不能利用失败信息，这就导致它不断地尝试用相同的思路来解决某个约束性问题。

如果我们可以把捷径当成约束条件表达出来，像谜题设计系统的其他部分一样，那会怎么样呢？这将是会是飞跃的进步，因为回答集编程（游戏邦注：即answer set programming，或者简称为ASP，上述文章中使用的一种特殊的约束求解器）通过使用失败的解决方法来避免以后尝试糟糕的设计，大大改进了。但是，我们如何把那种东西编写到ASP中？文章揭露的答案一开始会让人觉得费解，特别是如果你以前没有使用过ASP的话。这里，我打算简要地介绍那个思路，但我强烈建议大家去阅读原文。

puzzles(from gamesangelina)

（改良后的求解器制作的谜题。注意右图根本不需要陨石！）

首先，想象一下我们在运行求解器以前给它两样东西：一是我们希望所有解决办法都包含的定义（我们称之为概念）；二是一系列关卡设计特征，求解器可以用它们来描述关卡。例如，关卡设计特征可以是“飞船A需要1/2能量”或“在坐标(2,2)处有一陨石”，而概念可以是“玩家必须把两个1/4的激光束合并起来”。现在假设我们的求解器想到一个变量-解决办法的对子，且通过测试，它知道这个对子具有我们希望玩家执行的关键概念。问题是，我们怎么知道这个谜题是否有其他可以解决它的方法——绕过我们的概念的的的捷径？

我们要寻找（希望我们不会找到！）的是所有具有相同一套关卡设计特征，但又不满足我们的概念的谜题-解决方法的对子。以下是我们期望的结果：

{“飞船需要1/2能量”, 特征2…, 特征X, “玩家必须把1/4和1/4的激光束合并起来才能获胜”}

以下是一个卑鄙的捷径，我们提出的概念被完全无视了：

{“飞船需要1/2能量”, 特征2…, 特征X}

在数学中，后一种做法是前一种做法的子集。文章作者们的办法是，只在几行ASP中，告诉求解器禁止像后一种做法的那种解决办法，也就是，如果他们找到那些偷懒的做法，他们就知道关卡设计需要修改了。原理跟我之前说的系统一样，但显然更聪明了。因为ASP寻找失败的解决方法，有助于提高搜索速度，直到找到合适的谜题设计。

这种子集检查法的优势在于，它是完全常规性的，所以作者们写的代码也是。只要你能写出某个谜题的被破坏的或被绕开的概念，你就可以把这个为《Refraction 2》开发的系统用到你自己的程序内容生成器中。文章指出，这个系统也许不只适用于谜题设计，还适用于交互性剧情或工匠系统等。总之，它使程序生成器开发者得以在ASP中建模最棘手的问题，同时保留了相同的设计任务：关卡设计选择和你想在所有玩家的解决办法中看到的目标概念。

《Gunpoint》的另一张截图(from gamesbyangelina)

这个系统可以生成一些相当漂亮的谜题。正如作者指出的，虽然人性化设计使用如不可通行的陨石之类的东西来屏蔽捷径式的解决方法（使直观地检查谜题更容易），ASP求解器却更严格，通常可以满足概念性约束条件，如聪明地在关卡中布局激光束和飞船，且仍然有丰富多样的输出。考虑到《Refraction》是一款教育游戏， 这种系统却能做出教授特定数学知识的谜题，我感到非常兴奋。

自《Gunpoint》上周一发布，我一直在玩这款游戏。在开发者评论中，设计师Tom Francis说道：

“……如果我做的谜题太开放了，玩家会觉得太容易……那么我就提高限制级，使谜题只有一个解决办法，但玩家又抱怨太困难……结果是，我只能把这种谜题放在开放性关卡中。我发现这么做达到了更加平衡的效果。”

这个研究让我非常欣赏的一点是，它不是只针对约束求解，还清楚地告诉我们，更加智能的程序生成器可以使我们设计出完全开放的、但所有解决办法都满足概念的谜题——正是Tom在描述他对《Gunpoint》的处理过程中所说的，或者设计出所有解决办法看起来都一样可行的谜题、明确要求玩家去使用他不怎么使用的道具的谜题。

许多人遇到的障碍可能是，怎么做出回答集程序。作者很热心地提供了大约可以帮助开发者使用ASP的工具、系统和语言，而且不要求学习大量复杂的新编程知识。在这一段，我本来打算以这么一句话开头“这是一个值得克服的障碍”，但我改变主意了，我要引用Adam Smith在讨论本文的邮件中跟我说的一句话：

我很感谢你说“它是一个值得克服的障碍”，但我认为我应该告诉人们如何克服那个障碍，因为我已经想到一些不太困难的办法了。

正如你在他们在文章中看到的，他们的研究成果给我们指出一条光明的道路。我期待看到更大的突破。（本文为游戏邦/gamerboom.com编译，拒绝任何不保留版权的转载，如需转载请联系：游戏邦）

The Saturday Paper: Goldilocks And The Three Puzzles

by Mike

Most procedural generators have it pretty easy. Generation techniques for content like dungeon layouts or 3D worlds can’t really fail – they proceed very steadily, laying down content as they go, and if the occasional tree ends up floating in mid-air it’s not going to break the game. This attitude won’t cut it for more critical game content like puzzles or narratives, however. One small mistake might shortcut half of the plot or render a game trivially easy. How can you tell if a puzzle is solvable in the right way, though? This week on The Saturday Paper we look at how procedural generators can intelligently design puzzles with just the features you want – no more, no less.

We’re reading Quantifying over Play: Constraining Undesirable Solutions in Puzzle Design by Adam Smith, Eric Butler and Zoran Popovic. The paper describes their work investigating AI and game design when building a puzzle designer for the game Refraction 2 (you can play the original for free here), an educational maths puzzle game, and the steps they took to make sure the procedural puzzle generator would not only generate puzzles with particular solutions, but puzzles which didn’t inadvertently have additional, unwanted solutions either. The result is a clever procedural design system that can precisely ensure certain goals are met in its output – something that is completely reusable, and could come in handy in all manner of game design projects.

We’re back in the realm of constraint solving here, which we saw recently when reading about populating dungeons with monsters and items a few weeks back. There’s a longer overview there as well as some links to good tutorials, but the upshot is this: constraint solving lets you describe the results you want from a program, rather than writing the instructions to get there like you would with normal ‘imperative’ programming. If you can find a good representation for your problem – which can be tricky at first – then constraint solvers can rapidly build a solution, making and undoing possible design choices as it tries to match the criteria you give it.

Refraction is a game about understanding fractions. Players place pieces in the path of laser beams to redirect, split, combine or change the beams in some way, in order to provide a particular amount of power to some target spaceships. By allowing the player to split up and combine laser streams the game can test fractional arithmetic and other concepts by designing puzzles that require certain kinds of solution – like merging two 1/16 lasers to power up a spaceship needing 1/8 of power. The authors have already written a paper on a system using constraint solving to design puzzles for this purpose, in fact. So what was their next step?

If you look at the picture above, you can see a nice puzzle solution on the left, demonstrating splitting and joining laser beams (with some rather elegantly symmetrical puzzle design to boot), and on the right you can see a nasty shortcut that completely bypasses the whole point of the puzzle. One way to avoid these shortcuts is to generate a puzzle, and then exhaustively test every possible solution to make sure there are no solutions that break the rules you had in mind for this level (such as teaching the player about splitting lasers, as above). This isn’t great for a number of reasons pointed out in the paper – for one thing, this might take ages, especially if the constraints can’t actually be satisfied. Equally importantly, such a system can’t use information about failed designs to stop trying the same idea out for a particular constraint problem.

What if we could express the idea of shortcuts as constraints, just like the rest of the puzzle design system? This would be a huge improvement, because answer set programming (or ASP, the special type of constraint solving used in the paper) improve dramatically over time by using failed solutions to avoid bad designs in future attempts. How do we encode something like that into an ASP, though? The solution uncovered in the paper is initially mind-bending, particularly if you’ve not used ASP before. I’m going to try and give a brief idea here, but I highly recommend reading the paper and contacting the authors to find out more details.

Some puzzles made by the improved solver. Notice how the one on the right doesn’t need rocks at all! It’s all in the elegant placement of the lasers and spaceships.

First, imagine that before we run our solver we give it two things: first, a definition of what we want every solution to include (call it the concept); second, a list of level design features that the solver can define to describe a level. A level design feature might be “Spaceship A needs 1/2 Power” or “There’s a rock at (2,2)”, while a concept might be “The player had to add 1/4 and 1/4 together”. Now suppose our solver comes up with a puzzle-and-solution pair, and through testing it knows it embodies that key concept we want the player to practice. The question is, how do we know if this puzzle has other solutions that pair with it – ones that shortcut our concept?

What we’re looking for (or rather, hoping we don’t find!) is any puzzle-and-solution pair which has exactly the same set of level design features, but that doesn’t have our concept satisfied. If you look at what that means, here’s our initial outcome:

{“Ship needs 1/2 power”, feature2…, featureX, “The player had to add 1/4 and 1/4 together to win”}

And here’s the dastardly shortcut, in which the concept we hoped was required is actually missing:

{“Ship needs 1/2 power”, feature2…, featureX}

In mathematics, the bottom list is a subset of the top list. What Adam and co. do, in just a few lines of ASP, is tell their solver to forbid subsets like this, meaning that if they find them then they know that something about that level design has to change. It’s a little more involved and a lot more clever than I’ve made out, but the principle is the same. And because of the way ASP works, these failures help make the search faster and faster, until a puzzle design is found.

The beauty of this subset checking is that the idea is completely general, and so is the code that Adam and co. have written. As long as you can write down what it means for a concept to be broken or shortcutted for a particular puzzle-and-solution pair, you can use the system developed for Refraction 2 in your own procedural content generator. The paper itself suggests this might be used not just for puzzles, but everything from interactive stories to crafting systems. In essence, it gives developers of procedural generators access to modeling the trickiest problems possible in ASP while staying anchored on the same design task: level design choices and a target concept you wish to see in all player solutions.

Another screen from Gunpoint

The system can produce some really elegant puzzles. As the authors point out, while human designs use things like impassable rocks to block off shortcut solutions (making it much simpler to check the puzzle over visually), the ASP solver is so rigorous it can often satisfy conceptual constraints just by cleverly placing the lasers and their spaceships on the level – and still have a huge diversity of output. I’m really excited to see where this goes next – given that Refraction is a game with education in mind, this could lead to tailored puzzles that teach specific mathematical ideas to people.

I’ve been playing Gunpoint a whole lot since it came out last Monday. In the developer commentary, designer Tom Francis says:

“…if I made the puzzles too open-ended, people found them too easy… then I tried a more restricted version where there was generally only one solution, but people complained it was restrictive … [I ended up with] a puzzle nested within an open-ended level. I found that balance worked much better.”

One of the things I really like about this research – and it’s not exclusive to constraint solving but it’s illustrated so well here – is that with a bit of intelligence in our procedural generators, we could feasibly design puzzles that are perfectly open-ended but where all solutions pass through the same point – exactly as Tom describes his process for Gunpoint worked. Or puzzles where all solutions seem equally feasible (for some definition of ‘feasible’, of course). Or we could design puzzles that explicitly require gadgets the player hasn’t been using very much.

The barrier for many will probably be getting into answer set programming in the first place. The authors here are keen on building better tools, systems and languages that might help developers use the power of ASP without learning a lot of complex new programming ideas though. I originally wrote here, “It’s a barrier worth getting over”, but instead I’ll leave you with a quote from Adam Smith on this very topic, in an email to me about today’s post:

I appreciate your effort in saying “it’s a barrier worth getting over”, but I think I shouldn’t be asking people to cross that particular barrier when I know of not-so-difficult ways to build tunnels through it.

As you can see from the work in their paper, there are some very enticing lights to be seen down the end of this tunnel. I’m looking forward to seeing more of it.(source:gamesbyangelina)