AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Python可视化优先算法：走迷宫

2022-10-30 146
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Python可视化优先算法：走迷宫

简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。

走迷宫

显示迷宫

迷宫生成等等再提，先看一下迷宫的读取和显示。

image.png

第一行是行数和列数，代表有101行101列，这个迷宫后面可以使用最小生成树生成。读进一个迷宫：

public class MazeData {
    private char[][] maze;
    private int N, M;
    public static final char ROAD = '#';
    public static final char WALL = ' ';
    public MazeData(String fileName) {
        if (fileName == null) {
            throw new IllegalArgumentException("filename can't be null!");
        }
        Scanner scanner = null;
        try {
            File file = new File(fileName);
            if (!file.exists()) {
                throw new IllegalArgumentException("File is not exist!");
            }
            FileInputStream fileInputStream = new FileInputStream(file);
            scanner = new Scanner(new BufferedInputStream(fileInputStream), "UTF-8");
            String nm = scanner.nextLine();
            String[] nmC = nm.trim().split("\\s+");
            N = Integer.parseInt(nmC[0]);
            M = Integer.parseInt(nmC[1]);
            maze = new char[N][M];
            for (int i = 0; i < N; i++) {
                String line = scanner.nextLine();
                if (line.length() != M) {
                    throw new IllegalArgumentException("Message of file is not completed!");
                }
                for (int j = 0; j < M; j++) {
                    maze[i][j] = line.charAt(j);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (scanner != null) {
                scanner.close();
            }
        }
    }
    public char getMaze(int i, int j) {
        if (!inArea(i, j)) {
            throw new IllegalArgumentException("out of range!");
        }
        return maze[i][j];
    }
    public boolean inArea(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
    public int N() {
        return N;
    }
    public int M() {
        return M;
    }
}

使用File来获得当前文件，如果没有就要抛出异常。scanner获得输入流之后可以通过读取下一行获得每一行的内容，列数在前面已经提到了，所以要检查每一行是不是M列，不是就没得读了。#就是墙，空格是路，可以设置两个静态变量表示。同时还需要各种辅助函数，比如是否是在整区域里面的，返回当前区域的值等等。然后就是显示函数了：

         

int w = canvasWidth / data.M();
            int h = canvasHeight / data.N();
            for (int i = 0; i < data.N(); i++) {
                for (int j = 0; j < data.M(); j++) {
                    if (data.getMaze(i, j) == MazeData.ROAD){
                        AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
                    }else {
                        AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.White);
                    }
                    AlgorithmHelper.fillRectangle(graphics2D, j * w, i * h, w, h);
                }
            }

墙的宽度自适应，这样整个屏幕刚刚够。#号画浅蓝色，其余的白色。之后就是再控制器里面调用repaint即可。

image.png

迷宫问题

白色方块是可以走的路径，红色的就是墙。迷宫的本质就是一个图结构。可以把整个迷宫当成是一个图，而走迷宫的过程就可以等价成是图的遍历。从起始点开始遍历，直到遍历到了某一个终止点即可。如果遍历了所有点都没有得到结果，那么就可以确认无解了。
图的遍历可以分成两种遍历。深度优先遍历和广度优先遍历，一种遍历是按照深度，先往一个方向深了走，没有路了再回头，而广度是先广度走一遍再一层一层下去。首先固定了每一个迷宫的出口和入口位置，从一开始，就需要从相邻的四个方向走迷宫，如果可以就继续，不能就回头，其实就是递归实现。

深度优先

首先还是递归实现，递归比较方便，首先要准备递归函数，和上述的一样，走四个方向，一个一个尝试，如果下一个格子是在这个图里面，是一条路，而且还没有被访问过，那么久可以继续走，否则就需要返回。

  

private boolean go(int x, int y) {
        if (!data.inArea(x, y)) {
            throw new IllegalArgumentException("Paramenter is illgel!");
        }
        data.visited[x][y] = true;
        setData(x, y, true);
        if (x == data.getExitX() && y == data.getExitY()) {
            return true;
        } else {
            for (int i = 0; i < 4; i++) {
                int nexX = x + direction[i][0];
                int nexY = y + direction[i][1];
                if (data.inArea(nexX, nexY) &&
                        data.getMaze(nexX, nexY) == MazeData.ROAD &&
                        !data.visited[nexX][nexY]) {
                    if (go(nexX, nexY)) {
                        return true;
                    }
                }
            }
            setData(x, y, false);
            return false;
        }
    }

如果四个点都尝试过了，都是走不了的，那么还需要消除画的格子。相对来说还是比较简单的。再消除格子上这个步骤对于递归来说是相对方便，因为再回溯的过程中是有保留之前的点的信息的，所以相对简单。

image.png

这就是生成的结果了。
如果是非递归，用栈就可以模拟，因为递归本身就是用栈实现的。对于删除无用路径的情况，其实有点难，因为无用的路径是直接丢弃的，先前的递归可以是因为递归的栈保留了更加多的内容，而这里只是保留了点而已。

 

private boolean go_iteration() {
        Stack<Position> stack = new Stack<>();
        Position entrance = new Position(data.getEntanceX(), data.getEntanceY());
        stack.push(entrance);
        data.visited[entrance.getX()][entrance.getY()] = true;
        while (!stack.isEmpty()) {
            Position position = stack.pop();
            setData(position.getX(), position.getY(), true);
            for (int i = 0; i < 4; i++) {
                int newX = position.getX() + direction[i][0];
                int newY = position.getY() + direction[i][1];
                if (newX == data.getExitX() && newY == data.getExitY()) {
                    setData(newX, newY, true);
                    return true;
                }
                Position newPosition = new Position(newX, newY, position);
                if (data.inArea(newPosition.getX(), newPosition.getY()) &&
                        data.getMaze(newPosition.getX(), newPosition.getY()) == MazeData.ROAD
                        && !data.visited[newPosition.getX()][newPosition.getY()]) {
                    stack.push(newPosition);
                    data.visited[newPosition.getX()][newPosition.getY()] = true;
                }
            }
        }
        return false;
    }

image.png

广度优先

广度和深度在搜索策略上是不同的。深度是走到死路才回头，广度是对于每一次都是齐头并进。和遍历的深度优先的区别就是在于他们的数据结构不一样，一个是队列，一个是栈，其他的基本差不多。

 

private boolean go_level() {
        Queue<Position> queue = new LinkedList<>();
        Position position = new Position(data.getEntanceX(), data.getEntanceY());
        queue.add(position);
        data.visited[position.getX()][position.getY()] = true;
        while (!queue.isEmpty()) {
            Position position1 = queue.poll();
            setData(position1.getX(), position1.getY(), true);
            for (int i = 0; i < 4; i++) {
                int newX = position1.getX() + direction[i][0];
                int newY = position1.getY() + direction[i][1];
                if (newX == data.getExitX() && newY == data.getExitY()) {
                    findPath(position1);
                    setData(newX, newY, true);
                    return true;
                }
                Position newPosition = new Position(newX, newY, position1);
                if (data.inArea(newPosition.getX(), newPosition.getY()) &&
                        data.getMaze(newPosition.getX(), newPosition.getY()) == MazeData.ROAD
                        && !data.visited[newPosition.getX()][newPosition.getY()]) {
                    queue.add(newPosition);
                    data.visited[newPosition.getX()][newPosition.getY()] = true;
                }
            }
        }
        return false;
    }

image.png


如果迷宫有很多个解，深度优先遍历那么久只会搜索到第一个碰到的解，搜索到的解那么就是一个随缘排序出来，广度优先就是会查找最短的路径。广度优先可以找到无全图的最短路径。深度和广度的非递归差不多，只是使用的数据结构不同而已。

生成迷宫

刚刚是走迷宫，刚刚生成的那个用例其实就是生成的迷宫。对于一个迷宫，只有一个入口一个出口，为了简单化，入口就是第二行的第一个口，出口是倒数第二行的第一个口。而且只有一个解，并且路径是连续的，有些游戏里面的迷宫是有传送点的，改变起来也很简单。
首先迷宫其实就是一棵树，每一个点都会有分支，任何一个叶子或者是节点都可以作为是一个入口，生成一个迷宫其实就是一个生成树的过程。之前在数据结构有提到过一个最小生成树，但是由于是一个随机的迷宫，所以应该是随机生成树。无论是什么树，都是基于树的。而图的遍历结果就是一颗树，每一个节点只是访问一次，且没有环，深度优先遍历的结果是一颗深度优先树，广度优先的结果是广度优先树。可以先把一张画布分成很多很多小格子，然后每隔一个格子就挖空一个点，没有挖空点的都是墙，用一种遍历方法来遍历这些点所生成的树就是一个迷宫了。但是这样的迷宫其实带有偏见的，随机性不高，所以可以在选择点的进行遍历的时候进行随机选择。
@@@@@
@ @  @
@@@@@
@  _ @    _@
@@@@@
可以看的出无论怎么看，行和列一定要是基数，限制还是蛮多的。深度优先生成迷宫其实和之前的差不多，没有上面打的差别。首先是要得到一个格子布。然后通过深度遍历把格子全部连接起来。递归实现：

 

private void run() {
        setData(-1, -1);
        go(data.getEntranceX(), data.getEntranceY() + 1);
        setData(-1, -1);
    }
    private void go(int x, int y) {
        if (!data.inArea(x, y)) {
            throw new IllegalArgumentException("x or y is illegal!");
        }
        data.visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int newX = x + direction[i][0] * 2;
            int newY = y + direction[i][1] * 2;
            if (data.inArea(newX, newY) &&
                    !data.visited[newX][newY]) {
                setData(x + direction[i][0], y + direction[i][1]);
                go(newX, newY);
            }
        }
    }

这里要注意每两个格子之间的差距是2，因为中间都隔着一堵墙。go的参数是开始的参数，开始不能直接从入口开始，因为入口是我们新加的，不符合迷宫节点的规矩，比如每一个格子相差两个点，但是出口和第一个点差一个而已。

           int newX = x + direction[i][0] * 2;
           int newY = y + direction[i][1] * 2;

乘上2的原因就是因为两个格子之间相差了2。而渲染都放在了setData里面处理。渲染的点就不是我们newX和newY了，因为那两个点本来就是road，渲染的应该是两个点之间的墙，所以是加1的。和前面深度搜索对比区别就是，这里没有终止点，不是到了exit就退出，事实上是不一定有解的。因为我们这里是要全部生成而不是生成到了终点就停止，所以是无终止条件的。但是for循环里面是隐含了的。还有一个就是条件确认是不是一条路，这个决策是不必要的，因为就要生成路的。但是这样导致的迷宫很无随机性：

image.png

因为方向都是一样的，从左上右下这样。
这是递归方法，非递归方法：

 

private void go_iterator(){
        Stack<Position> stack = new Stack<>();
        Position firstPosition = new Position(data.getEntranceX(), data.getEntranceY() + 1);
        stack.push(firstPosition);
        data.visited[firstPosition.getX()][firstPosition.getY()] = true;
        while (!stack.isEmpty()){
            Position position = stack.pop();
            for (int i = 0; i < 4; i++) {
                int newX = position.getX() + direction[i][0] * 2;
                int newY = position.getY() + direction[i][1] * 2;
                if (data.inArea(newX, newY) &&
                        !data.visited[newX][newY]) {
                    setData(position.getX() + direction[i][0], position.getY() + direction[i][1]);
                    stack.push(new Position(newX, newY));
                    data.visited[newX][newY] = true;
                }
            }
        }
    }

image.png

不一样的原因就是因为在加入栈的时候就已经上下左右看了，看看能不能走，走就直接把墙消去了，所以会出现锯齿型。至于大体的trend的不一样的因为两个方向是相反的。
广度遍历：之前提到过了和深度遍历差不多：

 

private void go_level(){
        LinkedList<Position> stack = new LinkedList<>();
        Position firstPosition = new Position(data.getEntranceX(), data.getEntranceY() + 1);
        stack.addLast(firstPosition);
        data.visited[firstPosition.getX()][firstPosition.getY()] = true;
        while (stack.size() != 0){
            Position position = stack.removeFirst();
            for (int i = 0; i < 4; i++) {
                int newX = position.getX() + direction[i][0] * 2;
                int newY = position.getY() + direction[i][1] * 2;
                if (data.inArea(newX, newY) &&
                        !data.visited[newX][newY]) {
                    setData(position.getX() + direction[i][0], position.getY() + direction[i][1]);
                    stack.addLast(new Position(newX, newY));
                    data.visited[newX][newY] = true;
                }
            }
        }
    }

image.png


生成的图像都很规则。 一个很重要的原因的因为我们在数据结构的选择过程中都是栈和队列，可预期性太强了。我们只需要在数据结构中加上随机性就好了。出队或者是删除都是随机队列。

public class RandomQueue<E> {
    private ArrayList<E> queue;
    public RandomQueue() {
        queue = new ArrayList<>();
    }
    public void add(E e) {
        queue.add(e);
    }
    public E remove() {
        if (queue.size() == 0) {
            throw new IllegalArgumentException("no elements!");
        }
        int randomIndex = (int) (Math.random() * queue.size());
        E Ele = queue.get(randomIndex);
        queue.set(randomIndex, queue.get(queue.size() - 1));
        queue.remove(queue.size() - 1);
        return Ele;
    }
    public boolean isEmpty(){
        return queue.isEmpty();
    }
}

在广度优先里面把队列改一下：

image.png

这样就有一定的随机性了。可以看到在很多空白的小格子很容易让别人猜到我们是怎么生成的。所以可以加上如果没有遍历到的格子全部变黑色。

  

private void go_level(){
        RandomQueue<Position> stack = new RandomQueue<>();
        Position firstPosition = new Position(data.getEntranceX(), data.getEntranceY() + 1);
        stack.add(firstPosition);
        data.openMinst(firstPosition.getX(), firstPosition.getY());
        data.visited[firstPosition.getX()][firstPosition.getY()] = true;
        while (!stack.isEmpty()){
            Position position = stack.remove();
            for (int i = 0; i < 4; i++) {
                int newX = position.getX() + direction[i][0] * 2;
                int newY = position.getY() + direction[i][1] * 2;
                if (data.inArea(newX, newY) &&
                        !data.visited[newX][newY]) {
                    data.openMinst(newX, newY);
                    setData(position.getX() + direction[i][0], position.getY() + direction[i][1]);
                    stack.add(new Position(newX, newY));
                    data.visited[newX][newY] = true;
                }
            }
        }
    }private void go_level(){
        RandomQueue<Position> stack = new RandomQueue<>();
        Position firstPosition = new Position(data.getEntranceX(), data.getEntranceY() + 1);
        stack.add(firstPosition);
        data.openMinst(firstPosition.getX(), firstPosition.getY());
        data.visited[firstPosition.getX()][firstPosition.getY()] = true;
        while (!stack.isEmpty()){
            Position position = stack.remove();
            for (int i = 0; i < 4; i++) {
                int newX = position.getX() + direction[i][0] * 2;
                int newY = position.getY() + direction[i][1] * 2;
                if (data.inArea(newX, newY) &&
                        !data.visited[newX][newY]) {
                    data.openMinst(newX, newY);
                    setData(position.getX() + direction[i][0], position.getY() + direction[i][1]);
                    stack.add(new Position(newX, newY));
                    data.visited[newX][newY] = true;
                }
            }
        }
    }

image.png


但是其实还有一个问题，很多时候这个迷宫的路径顺序是都是斜向下的趋势，所以有时候是可以猜到怎么走的。可以通过改进随机队列：

   

public void add(E e) {
        if (Math.random() < 0.5){
            queue.addFirst(e);
        }else {
            queue.addLast(e);
        }
    }
    public E remove() {
        if (queue.size() == 0) {
            throw new IllegalArgumentException("no elements!");
        }
//        int randomIndex = (int) (Math.random() * queue.size());
//        E Ele = queue.get(randomIndex);
//        queue.set(randomIndex, queue.get(queue.size() - 1));
//        queue.remove(queue.size() - 1);
//        return Ele;
        if (Math.random() < 0.5){
            return queue.removeFirst();
        }else {
            return queue.removeLast();
        }
    }

这个时候随机性就更强了：

image.png


文章标签：
Python
Go
测试技术
数据挖掘
数据可视化
SQL
算法
关键词：
Python算法
算法python
Python可视化
Python优先
可视化算法
老表Python123
目录
相关文章
子午s
|
2天前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络，基于37种常见猫狗数据集训练高精度模型，并保存为h5格式。通过Django框架搭建Web平台，用户上传宠物图片即可识别其名称，提供便捷的宠物识别服务。
子午s
91 55
德国都芳最好
|
18天前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中，`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环，外层循环控制排序的轮数，内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素，就将它们交换位置。
德国都芳最好
123 67
德国都芳最好
|
18天前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$，空间复杂度为$O(logn)$。它在大多数情况下表现良好，但在某些特殊情况下可能会退化为最坏情况，时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改，或者尝试使用其他优化策略来提高快速排序的性能
德国都芳最好
114 61
子午s
|
12天前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统，本系统使用Python作为主要开发语言，基于TensorFlow搭建卷积神经网络算法，并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫（Abyssinian）', '孟加拉猫（Bengal）', '暹罗猫（Birman）', '孟买猫（Bombay）', '英国短毛猫（British Shorthair）', '埃及猫（Egyptian Mau）', '缅因猫（Maine Coon）', '波斯猫（Persian）', '布偶猫（Ragdoll）', '俄罗斯蓝猫（Russian Blue）', '暹罗猫（Siamese）', '斯芬克斯猫（Sphynx）', '美国斗牛犬
子午s
82 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
光明顶阳顶天
|
18天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体，算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心，对于提高程序的质量和性能具有至关重要的作用
光明顶阳顶天
52 24
德国都芳最好
|
18天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化？
德国都芳最好
48 19
AIweker
|
10天前
|
数据可视化 编译器 Python
Manim：数学可视化的强大工具 | python小知识
Manim（Manim Community Edition）是由3Blue1Brown的Grant Sanderson开发的数学动画引擎，专为数学和科学可视化设计。它结合了Python的灵活性与LaTeX的精确性，支持多领域的内容展示，能生成清晰、精确的数学动画，广泛应用于教育视频制作。安装简单，入门容易，适合教育工作者和编程爱好者使用。
AIweker
65 7
天下无贼001
|
24天前
|
存储 数据可视化 数据挖掘
使用Python进行数据分析和可视化
本文将引导你理解如何使用Python进行数据分析和可视化。我们将从基础的数据结构开始，逐步深入到数据处理和分析的方法，最后通过实际的代码示例来展示如何创建直观的数据可视化。无论你是初学者还是有经验的开发者，这篇文章都将为你提供有价值的见解和技巧。让我们一起探索数据的世界，发现隐藏在数字背后的故事！
天下无贼001
51 5
游客qf4jmczx4xu2y
|
27天前
|
机器学习/深度学习 数据可视化 数据挖掘
使用Python进行数据分析和可视化
【10月更文挑战第42天】本文将介绍如何使用Python进行数据分析和可视化。我们将从数据导入、清洗、探索性分析、建模预测，以及结果的可视化展示等方面展开讲解。通过这篇文章，你将了解到Python在数据处理和分析中的强大功能，以及如何利用这些工具来提升你的工作效率。
游客qf4jmczx4xu2y
35 1
小白学大数据
|
28天前
|
数据可视化 搜索推荐 Shell
Python与Plotly：B站每周必看榜单的可视化解决方案
Python与Plotly：B站每周必看榜单的可视化解决方案
小白学大数据
44 3

热门文章

最新文章

  • 1
    简单学习一下AES算法：GCM、ECB、CFB、OFB等
  • 2
    希尔排序(shellsort)算法实现
  • 3
    openssl中算法的组织方式
  • 4
    平滑过渡的战争迷雾(一) 原理：Warcraft3地形拼接算法
  • 5
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 6
    Kmeans聚类算法详解
  • 7
    算法精解:最小二乘法C实现
  • 8
    指针难，算法难，难住了谁
  • 9
    我在STM32单片机上跑神经网络算法—CUBE-AI
  • 10
    iOS 算法之排序、查找、递归
  • 1
    Python 密码学实用指南（全）（2）
    36
  • 2
    【python】习题 6-10周（下）
    57
  • 3
    【python】习题 6-10周（中）
    65
  • 4
    Python 入门指南（七）（4）
    48
  • 5
    【python】习题 1-5周（中）
    83
  • 6
    【python】习题 1-5周（上）
    50
  • 7
    Python 入门指南（七）（2）
    55
  • 8
    Python 入门指南（七）（1）
    41
  • 9
    Python 入门指南（六）（4）
    28
  • 10
    Python 入门指南（六）（3）
    41

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 用Python画圣诞树
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • Python选择及循环结构
  • 云端Python及基本操作

    • 推荐镜像

    更多
  • python-release
  • nodejs-release
  • debian-cd
    • 下一篇
    fs.oss.accessKeyId和fs.oss.accessKeySecret。