基于python实现的迷宫游戏

快来打我* 2024-03-24 09:53 39阅读 0赞

目录  
一、项目概述与编译环境 1  
二、问题的数学建模 2  
三、算法实现 2  
1.迷宫的创建 2  
(1)对每一小格随机添加障碍物 2  
2.搜索算法描述 3  
(1)深度优先搜索 3  
(2)宽度优先搜索 3  
(3)一致代价搜索 3  
(4)A*搜索 4  
四、项目架构与GUI设计 4  
(1)项目架构 4  
(2)GUI设计 4  
五、搜索算法效率对比 6  
六、实验心得与体会 7  
七、参考文献 7  
(1)pygame official doc 7  
该项目在windows下编译通过，所需环境为python3，编写GUI所用的库为pygame，在运行作业前，需要配置依赖项，即在main.py的路径下打开cmd，并运行：  
pip install –r requirement.txt  
配置完依赖项后即可运行游戏：  
python main.py  
为了方便测试不同搜索算法的效率，编写了脚本test.py进行测试：  
python test.py --maze\_size 10 (设置为需要的迷宫大小，建议为5-25，否则可能超过递归上界)  
二、问题的数学建模  
由于迷宫的实质为一个由0,1构成的矩阵  
其中1代表可行走的区域，0代表障碍物  
由于穴居人生活区域中存在冰面，因此设置了随机道路中存在冰块，在冰块上穴居人会打滑，导致行走的代价*2。  
在本问题中，设置穴居人初始位置处的值为10，宝藏处的值为1，则迷宫求解转化为该矩阵中10处到1处的带权连通路径。

三、算法实现  
1.迷宫的创建  
事实上，本次大作业中的一大难点在于迷宫如何创建，在实现过程中进行了如下尝试：  
(1)对每一小格随机添加障碍物  
(2)限定障碍物的形状，并在地图中随机放置障碍物，如(L型，H型)  
但实际的创建结果均不理想(迷宫的样子不像迷宫：出现大量空白/障碍堆积现象)  
最后经过查阅资料，采取递归回溯的算法生成迷宫，算法如下：

①每次把新找到的未访问迷宫单元作为优先  
②寻找其相邻的未访问过的迷宫单元，直到所有的单元都被访问到

通俗的说，就是从起点开始随机走，走不通了就返回上一步，从下一个能走的地方再开始随机走。

在创建完迷宫后，再在迷宫中随机指定人物的初始位置与宝藏，以及随机冰面的位置。  
该迷宫创建算法可以创建不同长、宽、障碍物、初始\\终点位置，具体代码详见：maze.py

import maze
    import solution
    import argparse
    import time
    
    parser = argparse.ArgumentParser()
    parser.add_argument('--maze_size', type=int, default=10)
    
    if __name__ == '__main__':
        args = parser.parse_args()
        time_cost = [0,0,0,0]
        opennum = [0,0,0,0]
        closenum = [0,0,0,0]
        pathcost = [0,0,0,0]
    
        for i in range(1000):
            Maze = maze.createmaze(args.maze_size)
            while solution.solution_maze(Maze,'DFS') == False:
                Maze = maze.createmaze(args.maze_size)
            print('testing Maze  ' + str(i+1))
            time_start = time.time()
            a,open1,close1,pathcost1 = solution.solution_maze(Maze,'DFS')
            time_end = time.time()
            time_cost[0] += time_end - time_start
            opennum[0] += open1
            closenum[0] += close1
            pathcost[0] += pathcost1
    
            time_start = time.time()
            a,open1,close1,pathcost1 = solution.solution_maze(Maze,'BFS')
            time_end = time.time()
            time_cost[1] += time_end - time_start
            opennum[1] += open1
            closenum[1] += close1
            pathcost[1] += pathcost1
    
            time_start = time.time()
            a,open1,close1,pathcost1 = solution.solution_maze(Maze,'uniform')
            time_end = time.time()
            time_cost[2] += time_end - time_start
            opennum[2] += open1
            closenum[2] += close1
            pathcost[2] += pathcost1
    
            time_start = time.time()
            a,open1,close1,pathcost1 = solution.solution_maze(Maze,'A*')
            time_end = time.time()
            time_cost[3] += time_end - time_start
            opennum[3] += open1
            closenum[3] += close1
            pathcost[3] += pathcost1
    
    
    
            
        print('')
        print('Test Result')
        print('Maze_size = '+str(2*args.maze_size + 1))
        print('method:DFS   time_cost:' + str(round(time_cost[0], 2)) + '  Average openlist: '
         + str(opennum[0]/1000) + '  Average closelist: ' + str(closenum[0]/1000) + '  Average pathcost: ' + str(pathcost[0]/1000))
        print('method:BFS   time_cost:' + str(round(time_cost[1], 2)) + '  Average openlist: '
         + str(opennum[1]/1000) + '  Average closelist: ' + str(closenum[1]/1000) + '  Average pathcost: ' + str(pathcost[1]/1000))
        print('method:UCS   time_cost:' + str(round(time_cost[2], 2)) + '  Average openlist: '
         + str(opennum[2]/1000) + '  Average closelist: ' + str(closenum[3]/1000) + '  Average pathcost: ' + str(pathcost[2]/1000))
        print('method:Astar time_cost:' + str(round(time_cost[3], 2)) + '  Average openlist: '
         + str(opennum[3]/1000) + '  Average closelist: ' + str(closenum[3]/1000) + '  Average pathcost: ' + str(pathcost[3]/1000))

![在这里插入图片描述][7459e7c1373e4764b9c0bcaa5f803d0e.png_pic_center]  
![在这里插入图片描述][47db75ffd7c0440fbd3c1a151487d3e0.png_pic_center]  
![在这里插入图片描述][378ceba76ab9414594d4a268e23c60e7.png_pic_center]  
![在这里插入图片描述][83c32eb449c6491cac63bbc82e56ce63.png_pic_center]  
![在这里插入图片描述][3c88b3289b0047eab21183f874abdb81.png_pic_center]  
![在这里插入图片描述][7d361652770b4bffaf27cc5d9d25ed20.png_pic_center]  
![在这里插入图片描述][21fd1601984e49d0ae27b689e9a6bc00.png_pic_center]  
![在这里插入图片描述][bbb05fca32d44e2cb3d0d4413d3e269e.png_pic_center]  
![在这里插入图片描述][67f693ee8f834ad6aa5bf493991baf04.png_pic_center]  
![在这里插入图片描述][5f79d236f00c47028cd8e46ed3bda136.png_pic_center]

[7459e7c1373e4764b9c0bcaa5f803d0e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c49a71173eda4ddcb89c511abbfb2049.png
[47db75ffd7c0440fbd3c1a151487d3e0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/49fa11a349ec46dc8b9b84a75735cde4.png
[378ceba76ab9414594d4a268e23c60e7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4941573145904363921a7fd03d1077dc.png
[83c32eb449c6491cac63bbc82e56ce63.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9415184a6865406690c499d5e0baa4cf.png
[3c88b3289b0047eab21183f874abdb81.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/03dfe2125d9648a29e967bb45e4b083c.png
[7d361652770b4bffaf27cc5d9d25ed20.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/879cbc6b06d54e7f9ff759c844d01a52.png
[21fd1601984e49d0ae27b689e9a6bc00.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7e7a2c71560a4dc5b6840a2a1c8690fd.png
[bbb05fca32d44e2cb3d0d4413d3e269e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d1b673f570954fb68dc3bd882bf6f60f.png
[67f693ee8f834ad6aa5bf493991baf04.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3f7609e1e9044477b9847121c7916380.png
[5f79d236f00c47028cd8e46ed3bda136.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/40989c9f5d794d7f81b4bdb406f72724.png