Home > 程序/算法 > 推箱子游戏的AI求解算法(一)

推箱子游戏的AI求解算法(一)

February 24th, 2008 Leave a comment Go to comments

只有算法,没有代码,希望不会编程的也能看懂(俺每次都这么说,但结果每次都很受伤……)

推箱子游戏大家都玩过吧,在封闭的关卡里分布着若干箱子,玩家控制主角把所有箱子推到指定位置即可过关。

以下是关于游戏规则的一些表述:

  • 关卡中的每一格要么是墙,要么是空地
  • 主角和箱子只能呆在空地上,不能穿墙
  • 主角不能穿过箱子
  • 箱子的目标位置在空地上
  • 箱子数量和目标位置数量相等(但每个箱子并不和唯一的目标位置一一对应)
  • 主角只能往前推动箱子,不能向后或向侧面拉箱子

这是个典型的递归/回溯(好像是这个字吧)搜索问题,栈数据结构的典型应用。和算法课上常常举的老鼠走迷宫的例子差不多,只是一些细节上稍稍复杂一点。

递归/回溯的意思是进入某个状态时,先列出该状态下所有可能的移动,然后从第一个开始尝试进入新的状态(具体从哪个开始可以用一些启发信息以便更快找到结果),都尝试完了还不行就退一步继续尝试下一种可能……直到找到解或者尝试了所有分支之后决定无解。

这类算法基本上属于深度优先搜索,优点是能比较快找到解(如果存在的话),但不保证是最优解。加上一些启发信息可能能得到比较好的解。和广度优先搜索相比,它的优点是速度较快而且需要保存的中间状态数据比较少,因为回溯时很容易根据当前状态和操作还原出上一个状态。

ok,开始。

俺是边想边敲字的,所以这里可以看到我整个思路的展开过程。

首先,算法肯定要维护一个“当前状态”,也就是游戏关卡的一个状态,每一格是什么东西,墙还是空地,空地是空的还是站着主角或者放着箱子等等。这个可以用一个简单的二维数组来保存,不多说了。

其次,要对每一步的“移动”作出定义。对于推箱子这个游戏,最容易理解的“一步”就是主角移动一格,但我们今天不这么设定,因为主角移动而没有推动箱子的话对于关卡状态实际上没有本质影响。取而代之我们把“主角推箱子移动一格”定义为移动单元。至于主角是怎么移动到箱子旁边的,我们作为另外一个子问题(子问题1)来单独解决。

然后要设计一下,需要哪些信息来描述一个“移动”,也就是移动一步后需要将哪些信息压栈。压栈的信息有两个作用,一个是当前方所有可能都尝试失败,需要回溯(栈顶数据pop)的时候要根据压栈的信息还原出之前的状态(相当于undo);另一个作用是前方找到解时需要逆向推导出移动的步骤。压栈的信息一方面要足够充分以便能够还原出之前的状态,另一方面应该尽量少以便实现算法的时候节省计算机内存。根据我们前面对一步移动的定义,需要保存的信息大致是:主角位置,推动箱子的方向。没经验的人可能觉得这两个信息就够还原出前一个状态了(事实也的确如此:)),但是别忘了还原状态之后还要继续尝试下一个可能的移动,那么当前状态下一共有几种移动的可能?我们将要尝试的是第几种可能?当然,这两个信息也可以不保存,只要回溯之后重新计算所有可能以及根据出栈的信息判断出刚刚试过的是第几种,但是下面会看到,省了一点内存相对于找出所有可能移动的开销是很不值得的。

所以我们现在要入栈的信息是:所有当前状态下的可能移动方式以及目前尝试的是哪一个移动。其中每种移动方式包括主角位置和推动方向(当然,算法本身要保证主角在当前位置上可以到达推动位置,推动位置在推动方向上相邻格子是箱子,并且箱子移动方向上是空地)

ok,现在思路清楚多了,开始描述算法,在一个状态下,我们要:(顺序执行,除非指定跳转)

1. 是否是目标状态,所谓目标状态是所有箱子都在目标位置上

是(嘿嘿算法描述一般都把甜头放在前面):输出结果(子问题2),结束

否:继续

2. 当前状态以前是否出现过。这个很重要,必须防止一个箱子被来回推,或者不同的箱子构成相同的布局,但这里有一个细节就是要考虑主角所在的子空间,也就是说即使所有箱子布局相同但主角在不同的分割空间,那也是不同的状态(子问题3)

是:转5

否:继续

3. 寻找当前状态下所有可能的移动。大致思路是主角当前所在的子空间(被墙和箱子封闭起来的空间)能够到的箱子,挨个看哪些箱子可以被推动,可以向几个方向推动,把每个可能都存下来。(子问题4)判断

一个能推动的都没有:转5

否则继续

4. 在前一步统计出的所有可能移动中取第一个,把需要的信息压栈,计算出推动箱子后关卡的新状态,转1

5. 判断是否栈空

是:输出失败

否:继续

6. 栈顶数据出栈,退到前一个状态,判断前一个状态的剩余未尝试移动:

已经是最后一个,转5

取下一个未尝试移动,信息压栈,更新关卡状态,转1

没了。比想象的简单吧 ?上面6个步骤本来可以更少,为了使每个步骤足够简单所以分的比较细。

上面留下了4个拆分出来没有详细解决的子问题,下一篇再讲。

Categories: 程序/算法 Tags: ,
  1. Kaili
    October 24th, 2013 at 01:32 | #1

    你好~
    我在写一个推箱子求解的程序,用bfs, dfs, uniformed cost, greedy 和A*, 遇到了一些问题,实在不知道怎么解决。然后马上要交作业了,不知道可不可以跟您直接问一下,电话什么的?
    多谢呀!

  1. No trackbacks yet.

 

Spam Protection by WP-SpamFree