动手编写视频游戏求解器：从状态机到广度优先搜索的编程实践
我的妻子和两个小儿子有时会去看望那些并非严格需要我出现的朋友或家人。当我的妻子预订航班时，我会装模作样地权衡我的选择，并询问如果我不去是否真的可以。最终我被说服了：对我来说，独自度过五到七天，没有尿布和任天堂游戏，确实对我们所有人都是最好的事。
我的妻子点击了“立即付款”按钮，当确认邮件发来时，我打电话给我的秘书，告诉他清空我的日程表。当没人接听时，我才想起我既没有秘书，也没有那么多事情要做。于是，我找了一部精品电视剧、一些当地外卖菜单，以及一款简短但沉浸式的视频游戏。这次我给我的好友发了信息，问他们我应该玩什么。史蒂夫对一款名为《Cocoon》的游戏赞不绝口；莫里斯说他一年前玩过，感觉“还行”。成交。
一个月后，拥抱、亲吻、挥手告别出租车、关上门、HDMI线在哪、它怎么跑到水槽下面了、我有任天堂账户吗、我的密码是什么、算了我要创建一个新的……好了，开始吧，预计下载时间45分钟，开始处理报税，我现在放松了吗？
最终我成功启动了《Cocoon》。我了解到我将扮演一个小蜜蜂人，在一个孤独、抽象的世界中解决艺术性谜题，且没有充分解释的原因。蜜蜂人使用四个发光的球体在世界中穿行。他可以拾起球体、携带它们，并将它们放回开关上以打开门和展开桥梁——标准的球体操作。然而，蜜蜂人很快发现这些球体还包含着其他世界，他可以跳进跳出这些世界来帮助解决谜题。如果他在携带一个球体世界时跳进另一个球体世界，他就可以将球体世界互相嵌套。他甚至可以在游戏后期将一个世界放入自身之中。难题随之而来。
到我假期第一天结束时，我的乐趣大约只有我希望的四分之三。《Cocoon》的氛围很吸引人，它的谜题让我会心一笑；我只希望除了关于熵和衰退的模糊隐喻外，能有一点故事情节。尽管如此，我继续前进，跋涉在崩溃的废墟和令人窒息的象征主义之中。到第二天结束时，我完成了游戏的51%。我开始下一个谜题，却完全卡住了。我确信我只是累了，我想，于是我看了一集《黑道家族》就上床睡觉了。第二天早上我6点起床，煮了些咖啡，走进我的办公室继续攻关。但我仍然卡住了。我花了一个小时把我不喜欢的玩具装进垃圾袋，因为周围没人阻止我。我又试了一次。还是卡住了。
然后我意识到了。我不知道如何解决这个谜题，但我知道如何编写一个计算机程序来为我解决它。那可能会更有趣，而且我可以辩称这实际上不算作弊。我不想在有机会系统地搜寻答案之前就让解决方案自己显现出来，所以我冲过房间去关掉了游戏机。
我想洗个澡，但我担心如果我洗了澡，灵感可能会涌现，我自己就能想出答案。所以我跑上楼到我的办公室，启动了我的番茄钟计时器，刷了刷Twitter来热身大脑，休息了一下，创建了一个JIRA面板，在Slack上给我的妻子发了一条状态更新，没有回复，她一定是没信号了。最后，我启动了我首选的辅助专业工具。是时候享受真正的假期了。
如何编写《Cocoon》求解器
为了编写《Cocoon》求解器，我需要：
- 使用有限状态机对游戏逻辑进行建模
- 使用这个模型找出一系列动作，使我从谜题的起始状态到达结束状态
1. 对游戏逻辑进行建模
《Cocoon》的机制简单而优雅。在第一关中，你会发现一个橙色球体放在一个支架上。显然，你把它捡起来，开始携带它。你来到一扇门前，旁边有一个球体支架。你把球体放在支架上，门就开了。你再次把它捡起来，穿过门。
最终，你来到一个小水池，中间有一个看起来特殊的球体支架。没有明显的路可走，所以你把你橙色的球体放在支架上。你站在它旁边并按A键，因为那是游戏中唯一有作用的按钮。你看着自己跳进球体，进入另一个世界。你现在在橙色球体内部。你开始行走。你发现了一个新的绿色球体，你用它来继续解决谜题、开门、在橙色球体世界中前进。在整个游戏过程中，你总共找到四个球体，最后的谜题要求你拖着它们四处走动，并以正确的顺序跳进跳出它们，以便穿过下一座桥。
举个例子：在一个谜题中，你需要把你的红色球体带到藤蔓顶端，以便用它来显示一条通往下一个区域的魔法通道。但是，你只有在拿着绿色球体时才能爬上藤蔓，而且你一次只能拿一个球体。这意味着你无法带着红色球体爬上藤蔓。因此，解决方案是：拿起红色球体，跳进绿色球体，放下红色球体，跳出来，用绿色球体爬上藤蔓，跳回绿色球体内部，取回红色球体，然后再跳出来。
为了让我的求解器分析《Cocoon》，它需要能够以编程方式操作它的一个副本。我的求解器需要知道世界的布局、允许的动作，以及是否已经完成谜题解决。最简单的方法不是让求解器与真实的游戏交互，而是编写一个新的、精简的游戏副本，包含所有逻辑但没有图形。
我所卡住的每个谜题都可以表示为一个有限状态机，这使事情变得更容易。有限状态机是一个系统，它在任何给定时间都只能处于有限数量状态中的一个。系统能够使用一组已知的规则在一些状态对之间转换。
大多数具有大型3D世界的游戏无法用有限状态机建模，因为它们有太多可能的状态和太多的可能转换。玩家可能处于近乎无限个略微不同的位置；他们的敌人也是如此。玩家可能携带大量物品，并可能采取过大量行动，每一项都可能以某种重要方式影响世界。游戏的某些部分可能取决于时机和敏捷性，这些很难在有限状态机中表示。在大多数游戏关卡中，对于像有限状态机这样的简单模型来说，发生的事情太多了。
然而，《Cocoon》的世界很简单。没有敌人。你能携带的唯一物品是4个球体。虽然它的3D景观看起来很漂亮，但它掩盖了一个可以建模为小图的简单拓扑结构——即节点（重要位置，如球体和开关）和边（连接彼此可直接访问的节点的路径）的集合。除了这些特征，世界的精确布局很少重要。
这意味着在《Cocoon》中定义一个“状态”很容易。一个状态由以下组合定义：
- 你最近的那个节点
- 你拿着哪个球体
- 其他球体在哪里
- （可能还有一些其他东西，取决于具体的谜题）
状态之间的转换同样受到限制。玩家只能通过一小部分动作在游戏状态之间转换，例如：
- 走到相邻节点
- 拿起或放下球体
- 跳入或跳出球体
这意味着编写一个程序相对简单，该程序：
- 定义谜题世界的布局
- 定义游戏当前的状态
- 能够在状态之间转换
- 知道如何识别目标状态
一旦我编写了这个程序，我就有了一个可以以编程方式操作的游戏表示。我可以告诉我的游戏做诸如“执行某某动作”或“告诉我从当前状态可以采取的所有可能的下一个动作”之类的事情。这意味着我可以用我简化的游戏来分析和解决真实的游戏。
2. 找出如何从起始状态到达目标状态
要解决一个谜题，我需要找到一系列动作，将我从事谜题的起始状态带到其目标状态（例如，打开一扇门）。这需要使用一种称为广度优先搜索的算法。
广度优先搜索从有限状态机中的一个初始状态开始，同时向从该状态可以到达的每个新状态迈出一步。例如，假设一个谜题开始时，蜜蜂人拿着绿色球体，旁边有一扇门和一条通往另一个区域的走廊。
我的求解器同时向穿过门和沿着走廊两个方向迈出一步，并开始跟踪每条路径。从这些新状态中的每一个，它再向从它们可以到达的每个更远的状态迈出一步。
它不断迈步并跟踪其正在探索的不断扩展的路径数量，直到其中一条路径到达目标状态（例如，特定球体位于特定支架上的状态，这打开了通往下一个区域的桥梁）。此时，求解器停止，并返回到达目标状态的路径。因为求解器同时沿着每条可能路径迈出一步，所以它找到的第一条到达目标状态的路径保证是可能的最短路径。
然后，我可以将求解器返回的动作序列输入到真实游戏中（例如：拿起红色球体，走到球体支架，放下红色球体，等等），然后进入下一关，无需做任何思考。这是我的代码。
这些谜题到底有多难？
我的求解器一旦到达目标状态就会停止。然而，我也对完整地绘制出在谜题内可以采取的每一个可能的动作序列感兴趣。我想看看这些谜题实际上有多大、多难。
为此，我编写了一个脚本，探索所有可能的状态和转换。它不断遍历状态转换，即使其中一条路径已经到达了目标状态。只有当它正在探索的路径都没有任何可用的动作能引向一个它之前未见过的新状态时，它才会停止。
这个脚本生成一个新图，其中每个节点是一个状态，每条边是一个转换。该图显示了你在谜题内可以采取的每一个动作序列。例如，这是我发现最难的那个谜题，表示为状态和转换的图：
绘制这样一个完全展开的有限状态机图，可以显示出《Cocoon》的谜题一旦被写下来是多么小而简单。右边绿色和红色节点之间的那条路径，要求你将一个球体放入另一个球体，然后再放入另一个球体，然后以特定方式将它们移动来移动去。这是一个违反直觉的策略，如果你像正常人一样玩游戏，很难找到它。
然而，把所有东西写下来就变得显而易见。把所有东西写下来使所有动作都可见，并消除了所有误导性的启发式方法，这些方法使人类专注于某些策略而完全忽略其他策略。它将一个谜题简化为“找到一条从绿点到其中一个红点的路径”，正如你上面看到的，这可以由一个天赋一般的两岁孩子解决。说得非常刻薄一点，《Cocoon》只是一个难以置信的简单迷宫之上覆盖的一层毛茸茸的图形和游戏机制。
这并不是要贬低这款游戏。《Cocoon》是一个整洁的脑筋急转弯，并非设计来承受穷举搜索。如果你写一个程序来为你解决《Cocoon》谜题，那你只是在欺骗自己。或者至少，如果编写这样一个程序不是那么有趣的话，你可能会这样认为。
人生启示
然而，现实生活不是一个有限状态机。我的求解器真正证明的只是，小的、低维度的问题可以很容易地通过穷举搜索解决。相比之下，世界有无限的状态。很难确定哪些属性是重要的，并且状态之间允许的转换定义得非常糟糕。没有任何重要问题可以简化为一个微小的图，这意味着即使是最坚定的两岁孩子也无法帮助你应对生活中的任何重大挑战。
然而，你不需要探索所有可能的解决方案就能从系统化搜索中受益。正如我所担心的那样，编写求解器的过程迫使我非常严谨地思考游戏，以至于在我完成编程之前，我已经解决了用它来处理的全部3个挑战。当我在程序中编码地图上的每个位置和转换时，我被迫至少分别关注每一个几秒钟，即使是那些游戏诱使我忽略的部分。这帮助我看到，一些我认为无关紧要的节点和动作实际上是整个事情的关键。
那天晚上，我和我的家人通了电话。我给他们看了我创建的所有图表以及我享受到的乐趣。他们给我看了他们在圣彼得大教堂里面的照片。我儿子问我是否打败了我的游戏。我解释说，我通过创建其整个可能性空间的数学表示，已经超越了它。他问这是否意味着“没有”。
这是我的求解器代码，但你真的应该好好玩游戏。