用Python写一个走迷宫的小程序（图形化：matplotlib,dfs,prim）

爱被打了一巴掌 2021-09-30 12:20 523阅读 0赞

不要脸的放到了Github上面，嘿嘿。

Github：[https://github.com/Radium1209/Maze][https_github.com_Radium1209_Maze]

先看一下动态效果图（慢放）：

![70][]

首先生成迷宫：

主要用了两个算法：Prim和dfs

总结：Prim生成的比较像真正的迷宫，所以默认用了Prim生成迷宫

具体参考：[https://blog.csdn.net/juzihongle1/article/details/73135920][https_blog.csdn.net_juzihongle1_article_details_73135920]

先输入n,m,会生成一个迷宫（prim生成），然后会动态的走完整个迷宫。

![70 1][]

![70 2][]

走迷宫用的是bfs算法，具体不多说了，关键难点在于记录路径：

我是用一个path二维数组来记录路径的，每一个位置存的是这个位置的上一个位置，在输出的时候倒着从最后一个点回溯到第一个点存入一个栈，最后正常出栈就是路径了。

画路径：有上，下，左，右，上左，上右，下左，下右，左下，左上，右上，右下12中情况分类讨论（实在是太麻烦了）。

![70 3][]

最后用pyinstaller生成exe

教程：[https://blog.csdn.net/Radium\_1209/article/details/82939368][https_blog.csdn.net_Radium_1209_article_details_82939368]

全部代码：

import random
    import numpy as np
    from matplotlib import pyplot as plt
    import matplotlib.cm as cm
    from collections import deque
    import tkinter
    
    
    //显示地图（图形化显示）
    def show_maze(Maze):
        plt.imshow(Maze, cmap=cm.Wistia_r, interpolation='none')
        # plt.ion()
        plt.show()
    
    
    //用bfs查找路径
    def find_path_bfs(image, M):
        path = np.zeros((num_rows, num_cols, 2))
        vis = np.zeros((num_rows, num_cols))
        vis[0][0] = 1
        Queue = deque()
        Queue.append((0, 0))
        while(Queue):
            temp = Queue.popleft()
            nr = temp[0]
            nc = temp[1]
    
            if (nc == num_cols - 1) and (nr == num_rows - 1):
                show_path(image, path)
                break
            if (nc > 0) and (not vis[nr][nc - 1]) and (M[nr][nc][0]):
                vis[nr][nc] = 1
                Queue.append((nr, nc - 1))
                path[nr][nc - 1][0] = nr
                path[nr][nc - 1][1] = nc
            if (nr > 0) and (not vis[nr - 1][nc]) and (M[nr][nc][1]):
                vis[nr][nc] = 1
                Queue.append((nr - 1, nc))
                path[nr - 1][nc][0] = nr
                path[nr - 1][nc][1] = nc
            if (nc < num_cols - 1) and (not vis[nr][nc + 1]) and (M[nr][nc][2]):
                vis[nr][nc] = 1
                Queue.append((nr, nc + 1))
                path[nr][nc + 1][0] = nr
                path[nr][nc + 1][1] = nc
            if (nr < num_rows - 1) and (not vis[nr + 1][nc]) and (M[nr][nc][3]):
                vis[nr][nc] = 1
                Queue.append((nr + 1, nc))
                path[nr + 1][nc][0] = nr
                path[nr + 1][nc][1] = nc
    
    
    //prim算法生成地图
    def Create_maze_prim():
        M = np.zeros((num_rows, num_cols, 5))
        image = np.zeros((num_rows * 10, num_cols * 10))
    
        r = 0
        c = 0
        history = [(r, c)]
    
        while history:
            M[r, c, 4] = 1
            check = []
            if c > 0 and M[r, c - 1, 4] == 0:
                check.append('L')
            if r > 0 and M[r - 1, c, 4] == 0:
                check.append('U')
            if c < num_cols - 1 and M[r, c + 1, 4] == 0:
                check.append('R')
            if r < num_rows - 1 and M[r + 1, c, 4] == 0:
                check.append('D')
    
            if len(check):
                history.append([r, c])
                move_direction = random.choice(check)
                if move_direction == 'L':
                    M[r, c, 0] = 1
                    c = c - 1
                    M[r, c, 2] = 1
                if move_direction == 'U':
                    M[r, c, 1] = 1
                    r = r - 1
                    M[r, c, 3] = 1
                if move_direction == 'R':
                    M[r, c, 2] = 1
                    c = c + 1
                    M[r, c, 0] = 1
                if move_direction == 'D':
                    M[r, c, 3] = 1
                    r = r + 1
                    M[r, c, 1] = 1
            else:
                r, c = history.pop()
    
        M[0, 0, 0] = 1
        M[num_rows - 1, num_cols - 1, 2] = 1
    
        for row in range(0, num_rows):
            for col in range(0, num_cols):
                cell_data = M[row, col]
                for i in range(10 * row + 2, 10 * row + 8):
                    image[i, range(10 * col + 2, 10 * col + 8)] = 255
                if cell_data[0] == 1:
                    image[range(10 * row + 2, 10 * row + 8), 10 * col] = 255
                    image[range(10 * row + 2, 10 * row + 8), 10 * col + 1] = 255
                if cell_data[1] == 1:
                    image[10 * row, range(10 * col + 2, 10 * col + 8)] = 255
                    image[10 * row + 1, range(10 * col + 2, 10 * col + 8)] = 255
                if cell_data[2] == 1:
                    image[range(10 * row + 2, 10 * row + 8), 10 * col + 9] = 255
                    image[range(10 * row + 2, 10 * row + 8), 10 * col + 8] = 255
                if cell_data[3] == 1:
                    image[10 * row + 9, range(10 * col + 2, 10 * col + 8)] = 255
                    image[10 * row + 8, range(10 * col + 2, 10 * col + 8)] = 255
        return M, image
    
    
    //dfs方法生成地图
    def Create_maze_dfs():
        M = np.zeros((num_rows, num_cols, 5))
        image = np.zeros((num_rows * 10, num_cols * 10))
    
        r = 0
        c = 0
        history = [(r, c)]
    
        while history:
            r, c = random.choice(history)
            M[r, c, 4] = 1
            history.remove((r, c))
            check = []
    
            if c > 0:
                if M[r, c - 1, 4] == 1:
                    check.append('L')
                elif M[r, c - 1, 4] == 0:
                    history.append((r, c - 1))
                    M[r, c - 1, 4] = 2
            if r > 0:
                if M[r - 1, c, 4] == 1:
                    check.append('U')
                elif M[r - 1, c, 4] == 0:
                    history.append((r - 1, c))
                    M[r - 1, c, 4] = 2
            if c < num_cols - 1:
                if M[r, c + 1, 4] == 1:
                    check.append('R')
                elif M[r, c + 1, 4] == 0:
                    history.append((r, c + 1))
                    M[r, c + 1, 4] = 2
            if r < num_rows - 1:
                if M[r + 1, c, 4] == 1:
                    check.append('D')
                elif M[r + 1, c, 4] == 0:
                    history.append((r + 1, c))
                    M[r + 1, c, 4] = 2
    
            if len(check):
                move_direction = random.choice(check)
                if move_direction == 'L':
                    M[r, c, 0] = 1
                    c = c - 1
                    M[r, c, 2] = 1
                if move_direction == 'U':
                    M[r, c, 1] = 1
                    r = r - 1
                    M[r, c, 3] = 1
                if move_direction == 'R':
                    M[r, c, 2] = 1
                    c = c + 1
                    M[r, c, 0] = 1
                if move_direction == 'D':
                    M[r, c, 3] = 1
                    r = r + 1
                    M[r, c, 1] = 1
    
        M[0, 0, 0] = 1
        M[num_rows - 1, num_cols - 1, 2] = 1
    
        for row in range(0, num_rows):
            for col in range(0, num_cols):
                cell_data = M[row, col]
                for i in range(10 * row + 2, 10 * row + 8):
                    image[i, range(10 * col + 2, 10 * col + 8)] = 255
                if cell_data[0] == 1:
                    image[range(10 * row + 2, 10 * row + 8), 10 * col] = 255
                    image[range(10 * row + 2, 10 * row + 8), 10 * col + 1] = 255
                if cell_data[1] == 1:
                    image[10 * row, range(10 * col + 2, 10 * col + 8)] = 255
                    image[10 * row + 1, range(10 * col + 2, 10 * col + 8)] = 255
                if cell_data[2] == 1:
                    image[range(10 * row + 2, 10 * row + 8), 10 * col + 9] = 255
                    image[range(10 * row + 2, 10 * row + 8), 10 * col + 8] = 255
                if cell_data[3] == 1:
                    image[10 * row + 9, range(10 * col + 2, 10 * col + 8)] = 255
                    image[10 * row + 8, range(10 * col + 2, 10 * col + 8)] = 255
        return M, image
    
    
    //显示路径（图形化）
    def show_path(image, path):
        plt.imshow(image, cmap=cm.Wistia_r, interpolation='none')
        plt.ion()
        plt.pause(2)
        str = ""
        stack = []
        nr = num_rows - 1
        nc = num_cols - 1
        stack.append((nr, nc + 1))
        stack.append((nr, nc))
        while nr or nc:
            tr = nr
            tc = nc
            nr = (int)(path[tr][tc][0])
            nc = (int)(path[tr][tc][1])
            stack.append((nr, nc))
        # stack.append((num_rows, num_cols))
        pr = 0
        pc = 0
        dir = 2
        color_num = 150
        while(stack):
            temp = stack.pop()
            nr = temp[0]
            nc = temp[1]
            if nr or nc:
                if (nr == pr):
                    if (nc > pc):
                        # print("R")
                        if (dir == 2):
                            image[10 * pr + 4,
                                  range(10 * pc + 0, 10 * pc + 10)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 0, 10 * pc + 10)] = color_num
                        elif (dir == 1):
                            image[10 * pr + 4,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 5] = color_num
                        elif (dir == 3):
                            image[10 * pr + 4,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 5] = color_num
                        dir = 2
                    else:
                        # print("L")
                        if (dir == 0):
                            image[10 * pr + 4,
                                  range(10 * pc + 0, 10 * pc + 10)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 0, 10 * pc + 10)] = color_num
                        elif (dir == 1):
                            image[10 * pr + 4,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 5] = color_num
                        elif (dir == 3):
                            image[10 * pr + 4,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 5] = color_num
                        dir = 0
                elif (nc == pc):
                    if (nr > pr):
                        # print("D")
                        if (dir == 3):
                            image[range(10 * pr + 0, 10 * pr + 10),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 0, 10 * pr + 10),
                                  10 * pc + 5] = color_num
                        elif (dir == 0):
                            image[10 * pr + 4,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 5] = color_num
                        elif (dir == 2):
                            image[10 * pr + 4,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 4, 10 * pr + 10),
                                  10 * pc + 5] = color_num
                        dir = 3
                    else:
                        # print("U")
                        if (dir == 1):
                            image[range(10 * pr + 0, 10 * pr + 10),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 0, 10 * pr + 10),
                                  10 * pc + 5] = color_num
                        elif (dir == 0):
                            image[10 * pr + 4,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 4, 10 * pc + 10)] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 5] = color_num
                        elif (dir == 2):
                            image[10 * pr + 4,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[10 * pr + 5,
                                  range(10 * pc + 0, 10 * pc + 6)] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 4] = color_num
                            image[range(10 * pr + 0, 10 * pr + 6),
                                  10 * pc + 5] = color_num
                        dir = 1
                pr = nr
                pc = nc
                plt.clf()
                plt.imshow(image, cmap=cm.Wistia_r, interpolation='none')
                # plt.ion()
                if (stack):
                    plt.ion()
                    plt.pause(0.03 / (num_cols * num_rows / 100))
                else:
                    plt.ioff()
                    plt.show()
                    # plt.pause(1000)
    
    
    //主函数
    if __name__ == '__main__':
        num_rows = int(input("Please input rows: "))
        num_cols = int(input("Please input columns: "))
    
        path = np.zeros((num_rows, num_cols, 2))
        M = np.zeros((num_rows, num_cols, 5))
        image = np.zeros((num_rows * 10, num_cols * 10))
        # row_image = np.zeros((num_rows * 10, num_cols * 10))
    
        M, image = Create_maze_prim()
    
        # show_maze(image)
        find_path_bfs(image, M)
    
        # show_path(image, path)

转载于:https://www.cnblogs.com/Radium1209/p/10415341.html

[https_github.com_Radium1209_Maze]: https://github.com/Radium1209/Maze
[70]: /images/20210724/e80b2fff48ac4e4a9a681d040779a244.png
[https_blog.csdn.net_juzihongle1_article_details_73135920]: https://blog.csdn.net/juzihongle1/article/details/73135920
[70 1]: /images/20210724/a838fccfc9dc4836b359d1480aac4785.png
[70 2]: /images/20210724/e6226851640546cc8e6f23c0846cb6fc.png
[70 3]: /images/20210724/618e7df49ba4494988e4f7342f250a5d.png
[https_blog.csdn.net_Radium_1209_article_details_82939368]: https://blog.csdn.net/Radium_1209/article/details/82939368