求推箱子自动解题算法

tjpanda88

我正在编一个改良版的推箱子游戏,这个游戏在前期需要一个自动完成最优推法的算法.我试着编过一些可能都太慢.不知道大家有没有好的方法.

林原猫猫

这个挺复杂啊

游戏之家

我论坛有：（但下载需要在论坛注册用户名字）
http://sega.okserver.com.cn/bbs/dispbbs.asp?boardID=8&ID=59&page=1

tjpanda88

游戏之家: Re:求推箱子自动解题算法

我论坛有：（但下载需要在论坛注册用户名字）
http://sega.okserver.com.cn/bbs/dispbbs.asp?boardID=8&ID=59&page=1

我之前看过你的那个游戏,我要的不是一个推箱子的程序,那个程序我以前做的。我现在要做的是一个改良版的。当然这个改良是否能成功要看那个自动解题程序所运行出的结果是否和我想的一样。
我要的是一个自动解题的程序。也就是给出任意一个推箱子的面。用这个程序可以求出这面的最优推法，所谓最优就是用最少的步数。其它我是主要那个最少的步数，和这面的可行性，至于最优推法过程就无所谓了。
我想把它做成幻想游戏那样.

sandy_zc_1

还得用动态规划。

其实有时候算法还挺烦人的。（所以有些人会回避它）

tjpanda88

我现在想做的这个游戏很需要这个函数
我开始想的是用穷举的方法，以是箱子移动一次为单位的。人的行动是用A*计算出来的。开始设一个最大的步数，之后如果最到了解就用解的步数来换这个步数。可是我还是运行的太慢了。我需要一个快一点的方法。

sandy_zc_1

怎么能用穷举法，那样时间复杂度要在a^n，我想这种问题就应该用动态规划来解决了，设箱子所在的位置为一个状态，将全局问题分成n个阶段，关键是如何搞定状态转移方程。

bigbook2000

动态规划只是一种思想，我的理解就是不能独立存在的一种算法，尤其在计算机算法应用中，这种问题即使是使用动态规划，那么每个状态的最优值还是需要依赖于搜索算法确定，因为每个状态没有明显的联动关系

我是这么理解的，不知道对不对

hlsl

动态规划是正解。使用A*就可以，它能满足楼主说得“求解”和“最小代价”的要求。很多时候A*能发挥的作用比寻路大得多。

就拿推箱子来说：
Init状态就是游戏开始时的箱子位置；
Goal状态就是游戏结束时的箱子位置；
为“推箱子”的游戏规则定义状态迁移规则，例如“箱子不能往墙里推”、“不能拉动箱子”和“箱子的位置按照推动箱子的逆方向走一格的地方要有一个人能通过的空间”；
有了Init、Goal以及状态迁移的规则，我们就可以启动A*了。而代价值和启发值可以用Init状态和Goal状态的箱子之间简单的几何距离来求得。
最终A*成功结束时，你就能获得一个状态迁移得序列。而这个序列就是“最少步骤”的推箱子的顺序。
而如果A*最终失败，那这局是无解的。

tjpanda88

hlsl: Re:求推箱子自动解题算法

动态规划是正解。使用A*就可以，它能满足楼主说得“求解”和“最小代价”的要求。很多时候A*能发挥的作用比...

关于A*我现在还不是很了解，我只知道他可以用在路径搜寻方面，而且他好像还有需要一个评估函数。
能不能把方法写的再在清楚一点。如果可以的话能不能写个代码来看看或是写个基本程序的基本流程。