# 推箱子程序设计C++ **Repository Path**: CeasarSmj/sokoban_cpp ## Basic Information - **Project Name**: 推箱子程序设计C++ - **Description**: No description available - **Primary Language**: C++ - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-06-26 - **Last Updated**: 2024-06-26 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 推箱子程序设计 ## 目录结构 ``` . ├── Algorithm // 关卡求解的算法实现 / ├── gameSolver.hpp // 整合了下面两个文件里的类 / ├── navigation.hpp // 导航算法 / ├── operationTree.hpp // 求解箱子移动的步骤 / └── README.md ├── mapGenerator // 地图生成器 / ├── generator.hpp / └── README.md ├── visualDos // 在 DOS 窗口中实现可视化,不是主程序 / ├── dosMain_play.cpp // 用 WSAD 控制移动 / ├── dosMain_navigation.cpp // 输入位置实现移动和巡航 / ├── dosMain_auto.cpp // 实现自动求解 / ├── dosMain_generate.cpp // 自动生成一个地图 / ├── dosVisualize.hpp // 输出的支持文件 / └── README.md ├── visualWin // 在 Windows 窗口中实现可视化,是主程序 / ├── winMain.cpp // 主程序 / ├── winVisualize.hpp // 可视化和交互的支持文件 / └── README.md ├── maps // 里面是一些地图的示例包括 sokoban 中的 / ├── map1.txt / ├── map2.txt / ├── map3.txt / └── ... ├── bin // 编译产生的可执行文件 ├── base.hpp // 整个项目的基础文件,定义了数据的存储格式 ├── README.md ├── complie.bat // 编译脚本 └── 点我运行主程序.bat // 如果不想去翻代码可以直接点它 ``` ## 状态结构体 ```cpp /************ base.hpp ***************/ typedef struct _State{ vector> map; // 这里存储地图(只包含墙) vector target; // 目标点的位置 vector box; // 箱子的位置 Point2D man; // 人的位置 int step; // 当前是第几步操作 }; ``` 地图表示规范: ```cpp /************ base.hpp ***************/ #define SPACE " " #define WALL "WW" #define BOX "BB" #define MAN "PP" #define TARGET "XX" // 空:[空格] // 墙:WW // 箱:BB // 人:PP // 目标点:XX // --------------------- // 地图示例: // WWWWWWWWWW // W X W // W PB W // W WW W // W W W W // W B W W // W W // W X W // W W // WWWWWWWWWW ``` ### 2.主操作类 ```cpp /************ base.hpp ***************/ class MainProcess : public{ _State state; /// @brief 用给定状态初始化程序 /// @param state MainProcess(_State state); /// @brief 初始化程序 /// @param state 用给定地图初始化 MainProcess(string filepath); /// @brief 向指定方向移动 /// @param c 移动方向,取值为 W A S,分别代表 上 左 下 右 /// @return 0:成功;1:被墙阻挡;2:被两个箱子阻挡;3:被箱子和墙阻挡;-1:输入错误 int MoveToward(char c); }; ``` ## DOS可视化和交互 ```cpp /************** dosVisualize.hpp ************/ /// @brief 用 printf 的方式显示指定的 画面,包含地图、当前的步数和附加文本 /// @param state 要显示的状态 /// @param attachText 要显示的附加文本 /// @param ifClear 是否要清除屏幕 /// @param ifInput 是否要接收一个输入作为下一步的移动 int showState(_State state,string attachText,bool ifClear,bool ifInput); ``` ```cpp /**************** dosMain.cpp ***************/ // 下面是测试代码示例,不代表最终代码 int main(){ string path; MainProcess mainp(path); char movement; string attachText="please input by ‘WASD’"; while(1) { movement=showState(mainp.state,attachText,true,true); movement=mainp.MoveToward(movement); } return 0; } ``` ### 通过树搜索求解 这里求解采用多步的方法,把推箱子和移动的过程分离,从而大大减小树搜索的深度。 求解过程分以下几步: > 1. 读入场景,初始化全局变量和扩展表等 > 2. 通过树搜索去寻找一组箱子移动的动作 > 3. 通过箱子移动的动作,得到人先后要到达的几个位置 > 4. 以以上得到的位置为关键帧,中间用```Dijkstra```算法得到路径 > 5. 把得到的路径转化为WASD格式的动作 以上方式有两个主要模块,一个是树搜索寻找箱子移动过的顺序,另一个是```Dijkstra```算法导航。下面讲一下部分细节: #### 1.箱子移动动作搜索 每个节点是一个结构体: ``` cpp struct BoxNode{ int depth; // 节点的深度 int boxIndex; // 移动的箱子 Point2D movement; // 移动的方向矢量 long manPos; // 编码后的人的位置 long boxPosX; // 编码后的箱子的位置x long boxPosY; // 编码后的箱子的位置y BoxNode *prev; // 前一个节点 }; ``` 树搜索的过程分为以下几步: > 0. 把当前节点加入扩展表,并检查是否已经成功 > 1. 检查深度,如果已经到了但是未就位,直接返回失败 > 2. 漫水填充算法找出可达区域的mask > 3. 用DFS寻找每一个箱子的可执行操作 > 4. 记录其BoxNode加入节点列表,直到找到解 > 4. 如果需要就在找到解以后继续搜索 > 5. 用Dijkstra算法找到更优解,以去除冗余动作 > 6. 把箱子移动的节点翻译成人先后要到达的坐标  为了性能和开销考量,`地图`和`目标位置`作为全局变量,树搜索的节点只记录`箱子的位置`和`人的位置`。  为了防止陷入循环,这里以下几种节点不可取: >  a.移动的方向前面和后面有墙或者其他箱子;   b.移动后箱子没有就位,而且被挡在墙角(上下至少有一个墙,左右至少有一个墙);   c.移动箱子要达到的位置不可达;   d.移动后的状态曾经出现过,且已知它不能再指定步数内完成;   e.步骤数超过还未完成。步数上限为`箱子数 x 地图长 x 地图宽`;  以上`可达性`采用`漫水填充法`,每一个节点只要算一次就可以了。  以上"已经出现过"的判据为一个节点扩展表,每一个元素都是一个记录了箱子位置和人位置的结构体。  以上深度优先搜索时有箱子就位的节点优先扩展,上一步移动过的的箱子优先扩展,有箱子被移出位置的最后扩展。 ## 导航算法 把每个位置当作一个节点,存储为以下结构体: ```cpp struct DijkstraNode{ Point2D position; // 节点的位置 int distance; // 和出发点的距离 DijkstraNode *prev; // 到达它的最短路径的上一个节点 }; ``` 然后进行以下几步操作: > 0. 初始化所有节点,算出所有节点和出发点的距离,并升序排序; > 1. 初始化节点扩展表,把起点加进去; > 2. 添加一个和扩展表中的节点相邻、而且不在扩展表中的节点; > 3. 查看新节点到已有相邻节点的距离,从而算出它离起点的最小路径的距离,填写它的prev字段; > 4. 查看已有相邻节点和新节点的距离,从而更新相邻节点到起点的最小路径距离,更新已有相邻节点的prev字段; > 5. 如果扩展到了目标节点就退出,如果扩展完了所有节点且没有到目标就报错,否则回到 `2` > 6. 根据得到的扩展表得出路径表`vector`并退出 ## 图形界面可视化 - 用的是windoes GUI,也就是C语言的,然后把墙、人、箱子、目标点分别用黑色方块、蓝色圆、棕色方块和红色圆来表示画出来就可以了。 - 程序中提供了多种交互方案: - - 1. 键盘操作 WSAD 控制上下左右 - - 2. 鼠标左键点击要达到的位置,然后导航算法自动寻路走过去 - - 3. 鼠标右键点击要达到的位置,只不过这里不会把箱子视作障碍物 - - 4. 点击按钮 Solve ,程序全自动求解和执行。 - - 5. 点击按钮 Generate ,随机生成一个地图 - - 6. 点击按钮 Save ,保存当前状态 - - 7. 把地图文件拖到窗口上释放,程序会立马打开这个文件 - - 8. 在命令行把地图文件路径当作参数来输入来打开地图 - - 9. 把map文件的 ### 6.地图生成 考虑到确保地图有解比较麻烦,所以这里采用逆向的方式: > 1. 随机在设定范围内生成参数 > 2. 生成地图和障碍墙,检查是否为全通,如果不是就重新生成 > 3. 随机生成目标点 > 4. 把箱子放到目标点上,并把人放在随机一个不是箱子也不是墙的地方 > 5. 把箱子按照移动的相反方式向随机方向拉 > 6. 如果发现有箱子在移动后还在目标点上就重新生成