迷宫设计思路.doc

《迷宫设计思路.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.迷宫程序设计5.1主要功能：分析图象处理得到迷宫的01矩阵，找到迷宫出口和入口，并找出迷宫的路径。（路径为连接出口和入口的一条近似为道路中线的坐标点集合）5.2设计原理：最简单的，道路宽度为一个数据的迷宫采用回溯算法。在每个点P处最多有三个方向可以继续走（三个方向都走不通才回溯倒退），根据设定的优先级选定一方向（选定某方向后就将该方向设置标志，以免重复），如果该方向下一点Q为道路则将点P入堆栈，并把当前位置设置为Q（同时将该位置设置标志，防止优先倒退），否则选取余下方向中的一个检测能否走。当三个方向都走不通时，出栈回溯，当前

2、位置点变成P点的上一个坐标点O，然后对O的未被标志的方向进行探测。以此不断探测最终找出正确的路径。 实际处理得到的迷宫01矩阵，路的宽度有几十个数据。为了得到近似路中间的那条路径，对基本的回溯算法进行了很多改进。首先根据入口位置探测得到一半路宽对应的数据数量width，选取下一步前进方向首先选取当前前进的方向，当该方向上道路数据宽度小于width（实际编程时数据会适当放大）时说明路不通，要选取其它方向，并且该方向上路的数据宽度要大于width，所有方向都走不通则回溯。5.3算法框架：5.3注意问题：1）为了保证路径为路的中间，在

3、回溯出栈时要遇到转弯角要反复出栈，出栈次数为半路宽的数据点数量，以此避免在路边就转弯了。2）在实际运行中，01矩阵并不是理想的那样，而是存在燥点和一些缺口等。所以首先对01矩阵进行去燥点（将每个点与相邻部分点求算术和，由和值大小来判定该点是0还是1），在比较路宽等参数设置上根据实际环境情况会适当进行调整以获得最佳效果。