作者在独自度假时玩《Cocoon》游戏,起初享受游戏氛围和谜题,后来遇到难题便想通过写计算机程序来解决。
- 游戏介绍:玩家扮演小蜜蜂,在孤独抽象世界解艺术谜题,通过四个发光球体在世界中穿梭,还能进入球体中的其他世界并相互嵌套,最终谜题需要按正确顺序携带所有球体。
写求解器过程:
- 建模游戏逻辑:用有限状态机(Finite State Machine)建模游戏逻辑,《Cocoon》世界简单,可视为由节点(如球体、开关)和边(连接可直接到达节点的路径)组成的图,状态由玩家所在节点、持有的球体、其他球体位置等定义,状态间转换通过有限的动作,如走到相邻节点、捡起或放下球体、跳进或跳出球体等,为写求解器,作者写了一个不含图形但包含游戏逻辑的简化版游戏。
- 找出从起始到目标状态的路径:用广度优先搜索(Breadth-First Search,BFS)算法找出从谜题起始状态到目标状态的动作序列,BFS从初始状态同时向每个新状态迈出一步,跟踪探索的路径,直到找到目标状态,保证找到的是最短路径,将求解器返回的动作序列输入真实游戏可进入下一关。
- 探索谜题难度:作者写了一个脚本探索每个谜题的所有可能状态和转换,生成一个状态和转换的图,展示谜题中的所有动作序列,发现《Cocoon》谜题虽看似复杂,但写下来后很简单,只是在图形和游戏机制下的简单迷宫。
- 生活教训:现实生活不是有限状态机,大问题不能简化为小图,无法通过简单搜索解决,但写求解器的过程让作者更严谨地思考游戏,发现一些被忽略的关键,也说明即使是简单问题,系统搜索也能带来帮助。最后作者与家人通话,展示所做,儿子询问是否通关,作者称已超越游戏,创建了其整个可能性空间的数学表示。作者还提供了求解器的代码,但建议好好玩游戏。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。