1回答

liuyubobobo

2022-10-26

已采纳

如何更“随机”本身是一个非常大的话题了。我可以提供一些思路：

首先，你需要分析一下，为什么会产生这种情况？（自己试试看？有必要的话，实际跟踪一下现在的程序，看一看到底为什么会产生这种“锯齿状”的形状？）

==========

其核心原因是，我们的算法本质还是广度优先遍历，只不过广度优先遍历的顺序随机了而已。广度优先遍历就会导致，在一个节点的时候，会优先把这个节点周围没有遍历的节点都“占住”，回忆一下，如果我们使用纯粹的广度优先遍历生成的迷宫，本质是不是就是一个“大号的锯齿”？

怎么解决？一个显然的思路是，广度优先遍历应该和深度优先遍历结合起来。也就是，我们在一个节点，去根据广度优先遍历“占住”他的四个方向的节点以后，应该有一定的概率基于某一个方向做深度优先遍历。

以下的代码是我尝试的基于这个思路修改的 run 函数。其中我把从一个节点向外扩展四个方向封装成了一个 expand 函数，这样方便调用。你可以看到，在 expand 函数中，有一定的概率（我设置的是 90%）基于扩展的一个方向的节点继续扩展（即深度优先遍历）。

注意，为了进一步引入随机性，expand 中对四个方向的遍历顺序每次也是随机的。具体参考以下代码：

    private void run(){
        setRoadData(-1, -1);
        
        RandomQueue<Position> queue = new RandomQueue<Position>();
        Position first = new Position(data.getEntranceX(), data.getEntranceY()+1);
        queue.add(first);
        data.visited[first.getX()][first.getY()] = true;
        data.openMist(first.getX(), first.getY());
        
        while(queue.size() != 0){
            Position curPos = queue.remove();
            expand(curPos, queue);
        }
        
        setRoadData(-1, -1);
    }
    
    void expand(Position cur, RandomQueue<Position> q){
        
        // 进一步随机，每次遍历四个方向的顺序是随机的，而非固定的
        ArrayList<Integer> dirs = new ArrayList<>();
        for(int i = 0; i < 4; i ++) dirs.add(i);
        Collections.shuffle(dirs);
        
        for(int i = 0 ; i < 4 ; i ++){
            int newX = cur.getX() + d[dirs.get(i)][0]*2;
            int newY = cur.getY() + d[dirs.get(i)][1]*2;
            if(data.inArea(newX, newY) && !data.visited[newX][newY]){
                Position newPosition = new Position(newX, newY);
                q.add(newPosition);
                data.visited[newX][newY] = true;
                data.openMist(newX, newY);
                setRoadData(cur.getX() + d[dirs.get(i)][0], cur.getY() + d[dirs.get(i)][1]);
                
                //90% 的概率基于这个方向再往深度走一层
                if(Math.random() < 0.9) expand(newPosition, q);
            }
        }
    }

加入这一机制之后，这一情况就好转很多。在我的环境下的一次运行结果如下：

如果你对此还不满意，还可以思考更多随机的策略，比如：

1）锯齿本质就是长度为 1 就到思路的通路。我们是否可能在可能的情况下，让每条通路的长度至少为 2?（更进一步，至少为 3？至少为 4）

2）即使如此，锯齿还是无法避免的，因为当空间过于“拥挤”的时候，通路没地儿可去，只能走一步就退回来了。那么在这种情况下，我们是否能直接就把这个锯齿的通路扔掉？（整个迷宫的通路不在占据 board 上每一个间隔的格子了。）

3）我们现在深度拓展的概率是 90%，这个概率是个定值，我们是否可能让这个值也是随机的（或者变化的）？（注意，因为你不需要产生锯齿，所以这个概率值在初始应该比较高，以多走一层防止锯齿的出现，所以让这个概率值完全的随机也不是好主意。一个简单的方式是让这个概率值递减，这有点儿类似模拟退火的思想。）

等等等等。

这个程序可供拓展的地方非常多，印象里，这一章的最后，我也会介绍更多和迷宫生成相关的拓展内容。整体，当来到更加“真实世界”的程序中的时候，很多问题是 open 的。没有一定的对或者一定的不对。但是，当你尝试解决一个问题的时候，你需要做的是：

1）用更加数学（或者形式化的方式）定义问题本身。（比如你的描述，“锯齿形”的迷宫，就不是形式化的。我将其定义成“长度为 1 的通路”，就是更形式画的。）

2）一旦问题定义清晰了，很多时候可能得解决方案也就出现了。（一但能定义清楚了我们其实不希望有那么多“长度为 1 的通路”，我们就可以尽量让通路的长度至少为 2。）

继续加油！：）

1

1

tobeabee

非常感谢！

2022-10-26

共1条回复