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

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

February 25th, 2008 Leave a comment Go to comments

上篇。前面有4个小问题没有解决。具体的问题可以在上篇搜“子问题n”

  • 问题1

这实际上是一个寻路问题,最简单的用一个广度优先搜索就可以找到最短路径。从角色当前位置开始,每次向所有可能方向展开一层,如下图直到扩展到目标位置。根据节点的父子关系能反推出移动步骤。如下图

25_000807_pusher

  • 问题2

输出结果很简单,从当前栈底到栈顶,每个元素代表一步移动。由于移动步骤只记录了主角推动箱子的位置,可以根据上一个问题的解决办法,能得到当前主角位置到主角推动位置的路径。

  • 问题3

要判断当前局面是否在之前的移动步骤上出现过,这个问题到现在我还没有想出特别好的方法。容易想到最笨的方法的是从上到下访问当前栈内所有元素,恢复出之前的所有状态逐一比较,包括主角是否在同一封闭空间。聪明一点的话可以根据关卡状态计算出某种唯一的特征值记录在压栈数据中,只要比较该特征值就可以了。

  • 问题4

仍然使用问题1的广度优先扩展,容易找出所有和主角所在空间相邻的箱子,判断箱子是否可以从主角所在空间推动也不难,先看是哪一面相邻,再看箱子另一面是否为空。

以为会写很多,结果只有这么一点,对不起观众了……

Categories: 程序/算法 Tags: ,
  1. Demos
    December 14th, 2010 at 19:25 | #1

    hello..
    我看了你的文章好牛13呀….饿为什么B 分开了…

    已订阅你了。
    对了我也是个游戏开发者…不过只是flash 游戏开发…呵呵…

    挺牛的….求解推箱子的ai….我一般都不去想这种事情….

  2. coneo
    February 13th, 2012 at 11:07 | #2

    精辟,获益匪浅

  1. No trackbacks yet.

 

Spam Protection by WP-SpamFree