Qt: 推箱子游戏及其最短路径

时间：大三《算法分析实践环节》 2016年1月

首先贴一下下载链接：

Qt源码链接：   http://download.csdn.net/detail/mahabharata_/9766082

演示程序链接： http://download.csdn.net/detail/mahabharata_/9766084

我做的另外一个程序，OpenGL版 3D推箱子游戏博客链接：http://blog.csdn.net/mahabharata_/article/details/58592503

这个程序是我大三上学期的一门课程的作业。IDE是Qt5.2.0。在这里将代码和演示程序分享给大家，虽说不难，但是也希望大家能关注一下程序所用到的一些设计模式。

程序实现的基本功能如下：

1.  基本的推箱子游戏：WASD移动小人（小人会根据前进方向而改变动作）。

2. 动画演示推箱子的最短路径（QSequencialAnimation)，并展示布线结果。

        3. 切换地图，程序和《魔兽》的地图管理比较相似，会自动检测./res/map/路径下的.map文件

        4. 提供给用户自己绘制地图的功能。

程序的截图如下：

程序中所用的核心算法参照布线问题，使用分支限界法求解最短路径。但是与传统布线问题不同的是，推箱子最短路径的每次探索，还需要增加一步判断，及判断”人是否能找到路径到达箱子后方推动箱子“，这其实也是一步寻路，这里不需要过多叙述，大家可以看一下我提供的源码链接参考一下。

下面给出核心算法——分支限界法的布线过程及逆向构造最短路径的代码：

bool MazeBox::getShortestPath(){    if(map == NULL)        return false;    Node cur,nbr;               // cur记录当前扩展方格，nbr记录扩展方向的方格    cur.pos = startBox;         // 初始cur.pos()为箱子初始位置    cur.playerPos = curPlayer;  // 初始cur.playerPos为玩家初始位置    pathMap[cur.pos.y()*width+cur.pos.x()] = 0;    QQueue<Node> que;    do{        for(int i=0; i<4 ; i++)        {            nbr.pos.setX(cur.pos.x()+offset[i].x());  // nbr的pos为cur向四个方向探索的情况            nbr.pos.setY(cur.pos.y()+offset[i].y());            nbr.playerPos.setX(cur.pos.x()+offset[(i+2)%4].x());            nbr.playerPos.setY(cur.pos.y()+offset[(i+2)%4].y());            if(isOutOfBound(nbr.pos))                continue;            // 箱子未走 && 下个位置不为墙 && 人能到达            // canArrived()函数即 判断人能否到达仙子后面推动箱子的寻路函数            if( pathMap[nbr.pos.y()*width+nbr.pos.x()] == -1               && map[nbr.pos.y()*width+nbr.pos.x()] != 1                && canArrived(cur,nbr))              {                nbr.playerPos = cur.pos;                pathMap[nbr.pos.y()*width+nbr.pos.x()]                        =pathMap[cur.pos.y()*width+cur.pos.x()]+1;                que.push_back(nbr);            }            if( map[nbr.pos.y()*width+nbr.pos.x()] == 4 && canArrived(cur,nbr)) // 到达终点                break;        }        if(que.isEmpty())  // 如果扩展结点用完了,则到无解.        {            return false;        }        if(map[nbr.pos.y()*width+nbr.pos.x()] == 4)  //到达终点 退出循环            break;        cur = que.front();        que.pop_front();    }while(true);    // 逆向构造最短布线方案    int PathLen = pathMap[endBox.y()*width+endBox.x()];    cur.pos = endBox;    for(int j=PathLen-1; j>=0; j--)    {        shortestPath.push_front(cur.pos);        for(int i=0; i<4; i++)        {            nbr.pos.setX(cur.pos.x()+offset[i].x());            nbr.pos.setY(cur.pos.y()+offset[i].y());            if(pathMap[nbr.pos.y()*width+nbr.pos.x()] == j)                break;        }        cur = nbr;    }    shortestPath.push_front(startBox);    qDebug()<<"该地图路径：";    for(int i=0; i<shortestPath.size();i++)    {        qDebug()<<QString("(%1,%2)").arg(shortestPath[i].y()).arg(shortestPath[i].x());    }    return true;}