Maze Generation: Algorithm Recap

迷宫生成

Make the initial cell the current cell and mark it as visited While there are unvisited cells   If the current cell has any neighbours which have not been visited     Choose randomly one of the unvisited neighbours     Push the current cell to the stack     Remove the wall between the current cell and the chosen cell     Make the chosen cell the current cell and mark it as visited   Else if stack is not empty     Pop a cell from the stack     Make it the current cell

后来还看到一个followup，要求生成的迷宫只有一条通路可以到目的地。

我当时的思路是：从入口到出口生成一个不自相交path，这是唯一的一条可以到目的地的path。这条path把整个的四方地区分割成两个部分。因为要求只能有一条路，所以给一个门可以从path进入上下任意的部分，那么必然不能再给你一个门可以回到path。否则就有多条路了以到目的地了。所以从path的两边的wall里，各开一个门。然后分别进入门内用DFS来生成两部分的maze。并且不能打破path的墙。不知我对于“只有一条通路可以到目的地”的理解对否。

对于m * n的maze:

1/ 生成m * n个cell

2/ 对每个cell建立与其neighbors的connection

3/ run kruskal, count = m * n - 1，每次列举一个cell，检查其任何neighbor是否在同一个set中(union find), 如果不在则knockdown wall，count--

4/ 这样生成的maze任意两点之间必有通路且唯一

我在youtube上看了几个总结, 大致有三种方法.

只记得两个了. 

1) 和 kruskal 差不多, 对着每个当前选定的元素四边再选下一个, 如果已经选过了就不能选, 然后开这个.

2) 每次在空间内横竖各一条线分割成4份, 然后连接其中三个. 

补充内容 (2019-3-7 13:49):
是prim

顶楼没有放PRIM是因为虽然PRIM的效果更自然，但是感觉面试时如果没有特殊要求，我感觉只记一个递归的就可以。followup难在特别的requirement上。这几种哪一种更灵活呢？

?

Start with a grid full of walls. Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list. While there are walls in the list:   Pick a random wall from the list. If only one of the two cells that the wall divides is visited, then:     Make the wall a passage and mark the unvisited cell as part of the maze.     Add the neighboring walls of the cell to the wall list.   Remove the wall from the list.

假这长宽都是长度至少为3的奇数, 因为这样才好保证墙壁的厚度为1, 先把所有的数组设为墙壁，从最左上角开始，每次可以随机往四个方向走两步把墙打通，假如所有可以打的墙都打通了，数组会变成这样

    ０００００００００００００
    ０１０１０１０１０１０１０
    ０００００００００００００
    ０１０１０１０１０１０１０
    ０００００００００００００
    ０１０１０１０１０１０１０
    ０００００００００００００

    零是路，一是牆
    
为求确保只有一条路线，必须避免

    000
    010
    000

的情况. 也就是說，離當前座標距離為二位置如果已經是零了，就不能打通開路線, 最终所有x, y 皆为偶数的座标全部都会被打通，都是奇数的座标必定为墙, 一奇一偶的可能被打通可能不被打通, 但一定不会出现一个环的路径



Maze Generation: Algorithm Recap

Maze Generation: Recursive Backtracking
Choose a starting point in the field.
Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell.
If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat.
The algorithm ends when the process has backed all the way up to the starting point.

Java Implementation:
http://rosettacode.org/wiki/Maze_generation#Java

 private void generateMaze(int cx, int cy) {
  DIR[] dirs = DIR.values();
  Collections.shuffle(Arrays.asList(dirs));
  for (DIR dir : dirs) {
   int nx = cx + dir.dx;
   int ny = cy + dir.dy;
   if (between(nx, x) && between(ny, y)
     && (maze[nx][ny] == 0)) {
    maze[cx][cy] |= dir.bit;
    maze[nx][ny] |= dir.opposite.bit;
    generateMaze(nx, ny);
   }
  }
 }

Maze Generation: Prim's Algorithm
frontier set
Choose an arbitrary vertex from G (the graph), and add it to some (initially empty) set V.
Choose the edge with the smallest weight from G, that connects a vertex in V with another vertex not in V.
Add that edge to the minimal spanning tree, and the edge’s other vertex to V.
Repeat steps 2 and 3 until V includes every vertex in G.

Now, we choose one of these frontier cells at random and carve a passage from that frontier cell to whichever adjacent cell is already part of the maze. Then we’ll mark the neighbors of the formerly frontier cell, as “frontier” cells themselves.

Now, here’s an interesting bit. Look what happens if we (ahem, “randomly”) choose the cell at (1,0) (the top middle). It is adjacent to two cells that are already “in” the maze. The algorithm resolves this by simply choosing one of the “in” neighbors at random. Prim’s doesn’t care which neighbor is picked, only that each frontier cell eventually be connected to a cell already within the maze.

The algorithm terminates when there are no more frontier cells to choose from, giving us the anticipated perfect maze.
mark a cell as “in” (which then marks the “out” neighbors as frontier cells), and one that returns all the “in” neighbors of a given frontier cell.
http://jonathanzong.com/blog/2012/11/06/maze-generation-with-prims-algorithm
https://java.net/nonav/projects/trackbot-greenfoot/sources/svn/content/trunk/Version1/TrackBot/maze/PrimMazeGenerator.java?rev=142

mark(rand(width), rand(height), grid, frontier)


until frontier.empty?


x, y = frontier.delete_at(rand(frontier.length))


n = neighbors(x, y, grid)


nx, ny = n[rand(n.length)]


 


dir = direction(x, y, nx, ny)


grid[y][x] |= dir


grid[ny][nx] |= OPPOSITE[dir]


 


mark(x, y, grid, frontier)


 


display_maze(grid)


sleep 0.01


end

def add_frontier(x, y, grid, frontier)


if x >= 0 && y >= 0 && y < grid.length && x < grid[y].length && grid[y][x] == 0


grid[y][x] |= FRONTIER


frontier << [x,y]


end


end

def mark(x, y, grid, frontier)


grid[y][x] |= IN


add_frontier(x-1, y, grid, frontier)


add_frontier(x+1, y, grid, frontier)


add_frontier(x, y-1, grid, frontier)


add_frontier(x, y+1, grid, frontier)


end

def neighbors(x, y, grid)


n = []


 


n << [x-1, y] if x > 0 && grid[y][x-1] & IN != 0


n << [x+1, y] if x+1 < grid[y].length && grid[y][x+1] & IN != 0


n << [x, y-1] if y > 0 && grid[y-1][x] & IN != 0


n << [x, y+1] if y+1 < grid.length && grid[y+1][x] & IN != 0

n


end

def direction(fx, fy, tx, ty)


return E if fx < tx


return W if fx > tx


return S if fy < ty


return N if fy > ty


end

Maze Generation: Kruskal's Algorithm
Kruskal’s algorithm is a method for producing a minimal spanning tree from a weighted graph. The algorithm I’ll cover here is actually a randomized version of Kruskal’s; the original works something like this:

Throw all of the edges in the graph into a big burlap sack. (Or, you know, a set or something.)
Pull out the edge with the lowest weight. If the edge connects two disjoint trees, join the trees. Otherwise, throw that edge away.
Repeat until there are no more edges left.

The randomized algorithm just changes the second step, so that instead of pulling out the edge with the lowest weight, you remove an edge from the bag at random. Making that change, the algorithm now produces a fairly convincing maze.

sets = Array.new(height) { Array.new(width) { Tree.new } }

# build the list of edges


edges = []


height.times do |y|


width.times do |x|


edges << [x, y, N] if y > 0


edges << [x, y, W] if x > 0


end


end


 


edges = edges.sort_by{rand}

until edges.empty?


x, y, direction = edges.pop


nx, ny = x + DX[direction], y + DY[direction]


 


set1, set2 = sets[y][x], sets[ny][nx]


 


unless set1.connected?(set2)


display_maze(grid)


sleep(delay)


 


set1.connect(set2)


grid[y][x] |= direction


grid[ny][nx] |= OPPOSITE[direction]


end


end

Java code:
https://github.com/psholtz/Puzzles/blob/master/mazes/maze-04/java/Kruskal.java
Maze Generation: Growing Tree algorithm

https://segmentfault.com/a/1190000009178060

对于迷宫生成,其实更上面朋友圈有点类似.生成步骤如下

1. 首先,先创建一个n*m的二维密室.每个单元格四方都是墙.
2. 随机选择密室中的一个单元格.之后在随机选择一面要打通的墙壁.
3. 判断要打通的墙壁是否为边界.是则返回步骤3,不是则继续
4. 判断步骤的单元个和要打通的墙壁的对面是否联通(用find算法)
5. 如果两个单元格不联通,则把步骤2选中的墙壁打通(用union算法).否则返回步骤2.
6. 判断迷宫起点和终点是否已经联通,是则迷宫生成结束,否则返回步骤2.

public enum Wall {
    /**
     * 墙壁
     */
    BLOCK,
    /**
     * 通道
     */
    ACCESS
}

墙壁,是一个枚举变量,用于判断当前的墙壁是否可以通行.

public class Box {
    private Wall[] walls;

    public Box(){
        walls = new Wall[4];
        for (int i = 0; i < walls.length; i ++){
            walls[i] = Wall.BLOCK;
        }
    }

    public void set(Position position, Wall wall){
        walls[position.getIndex()] = wall;
    }

    public Wall get(Position position){
        return walls[position.getIndex()];
    }
}

一个单元格(小房间)是有四面墙组成的,刚开始四面墙都是墙壁.

public enum Position {
    TOP(0), RIGHT(1), DOWN(2), LEFT(3);

    public int index;

    Position(int index) {
        this.index = index;
    }

    public static Position indexOf(int index){
        int pos = index % Position.values().length;
        switch (pos){
            case 0:
                return TOP;
            case 1:
                return RIGHT;
            case 2:
                return DOWN;
            case 3:
            default:
                return LEFT;
        }
    }

    public Position anotherSide(){
        switch (this){
            case TOP:
                return DOWN;
            case RIGHT:
                return LEFT;
            case DOWN:
                return TOP;
            case LEFT:
            default:
                return RIGHT;
        }
    }

    public int getIndex() {
        return index;
    }
}

方向,枚举类,用于判断单元格的那一面墙壁需要打通.

这里我使用find-union的两种实现方式实现,

1. 一种是用数组的方式MazeArrayBuilder
2. 一种使用map的方式实现MazeMapBuilder
   所以我把迷宫生成的一些共同方法和属性抽取出现,编写了一个抽象类AbstractMazeBuilder.然后再在MazeArrayBuilder或MazeMapBuilder做具体的实现.

现在我们来看看AbstractMazeBuilder这个类

public abstract class AbstractMazeBuilder {
    /**
     * 迷宫行列最大值
     */
    public static final int MAX_ROW_LINE = 200;
    /**
     * 行
     */
    protected int row;
    /**
     * 列
     */
    protected int line;
    /**
     * 迷宫格子集合,每个格子有四面墙
     */
    protected Box[][] boxes;
    /**
     * 求解迷宫中间变量
     */
    protected int[][] solverPath;
    /**
     * 迷宫时候已经算出最佳路径
     */
    protected boolean isSolver;
    /**
     * 使用贪婪算法,算出最佳路径集合
     */
    protected List<MazePoint> bestPath;
    protected Random random;

    public AbstractMazeBuilder(int row, int line){
        if (row < 3 || row > MAX_ROW_LINE || line < 3 || line > MAX_ROW_LINE){
            throw new IllegalArgumentException("row/line 必须大于3,小于" + MAX_ROW_LINE);
        }
        this.row = row;
        this.line = line;

        isSolver = false;
        boxes = new Box[row][line];
        solverPath = new int[row][line];
        bestPath = new ArrayList<MazePoint>();
        random = new Random();

        for (int i = 0; i < row; i ++){
            for (int j = 0; j < line; j ++){
                boxes[i][j] = new Box();
                solverPath[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    /**
     * 查询与point点联通的最大格子的值
     * @param point point
     * @return 查询与point点联通的最大格子的值
     */
    protected abstract int find(MazePoint point);

    /**
     * 联通point1和point2点
     * @param point1 point1
     * @param point2 point2
     */
    protected abstract void union(MazePoint point1, MazePoint point2);

    /**
     * 判断时候已经生成迷宫路径
     * @return 判断时候已经生成迷宫路径
     */
    protected abstract boolean hasPath();

    /**
     * 生成迷宫
     */
    public void makeMaze(){

        while (hasPath()){
            // 生成 当前点, 当前点联通的方向, 当前点联通的方向对应的点
            ThreeTuple<MazePoint, Position, MazePoint> tuple = findNextPoint();
            if (tuple == null){
                continue;
            }
            union(tuple.one, tuple.three);
            breakWall(tuple.one, tuple.two);
            breakWall(tuple.three, tuple.two.anotherSide());
        }
        breakWall(new MazePoint(0,0), Position.LEFT);
        breakWall(new MazePoint(row - 1, line - 1), Position.RIGHT);
    }

    /**
     * 生成 当前点, 当前点联通的方向, 当前点联通的方向对应的点
     * @return
     * ThreeTuple.one 当前点
     * ThreeTuple.two 当前点联通的方向
     * ThreeTuple.three 当前点联通的方向对应的点
     */
    private ThreeTuple<MazePoint, Position, MazePoint> findNextPoint() {
        MazePoint currentPoint = new MazePoint(random.nextInt(row), random.nextInt(line));
        Position position = Position.indexOf(random.nextInt(Position.values().length));
        MazePoint nextPoint = findNext(currentPoint, position);
        if (nextPoint == null || find(currentPoint) == find(nextPoint)){
            return null;
        }
        return new ThreeTuple<MazePoint, Position, MazePoint>(currentPoint, position, nextPoint);
    }

    /**
     * 打通墙
     * @param point   当前点
     * @param position 当前点的方向
     */
    private void breakWall(MazePoint point, Position position) {
        boxes[point.x][point.y].set(position, Wall.ACCESS);
    }

    /**
     * 通过当前点以及对应当前点的方向找到下一个点
     * @param currentPoint 当前点
     * @param position 方向
     * @return 下个点,若该点在迷宫内,这返回,否则返回null
     */
    private MazePoint findNext(MazePoint currentPoint, Position position) {
        MazePoint nextPoint;
        switch (position){
            case TOP:
                nextPoint = new MazePoint(currentPoint.x - 1, currentPoint.y);
                break;
            case RIGHT:
                nextPoint = new MazePoint(currentPoint.x, currentPoint.y + 1);
                break;
            case DOWN:
                nextPoint = new MazePoint(currentPoint.x + 1, currentPoint.y);
                break;
            case LEFT:
            default:
                nextPoint = new MazePoint(currentPoint.x, currentPoint.y - 1);
                break;
        }
        if (nextPoint.x < 0 || nextPoint.x >= row || nextPoint.y < 0 || nextPoint.y >= line){
            return null;
        }
        return nextPoint;
    }

    public Box getBoxes(int x, int y) {
        return boxes[x][y];
    }

    public int getRow() {
        return row;
    }

    public int getLine() {
        return line;
    }

    /**
     * 求解迷宫路径
     * @return 迷宫路径
     */
    public List<MazePoint> solvePath(){
        // 1 迷宫时候已经求解完成,是的话,则直接返回,不必再次计算
        if (isSolver){
            return bestPath;
        }
        // 2 否则计算迷宫最佳路径
        bestPath = new ArrayList<MazePoint>();
        solverPath(new MazePoint(0, 0), 0);
        addPath(new MazePoint(row - 1, line - 1));
        Collections.reverse(bestPath);
        isSolver = true;
        return bestPath;
    }

    /**
     * 从终点逆推,添加最佳路径
     * @param point 当前点
     */
    private void addPath(MazePoint point) {
        bestPath.add(point);
        // 遍历当前点的每个方向,如果该方向能联通,这步数跟当前点的步数相差1步,这添加改点,递归计算下去
        for (Position position :Position.values()){
            MazePoint next = findNext(point, position);
            if (next == null || getBoxes(point.x, point.y).get(position) == Wall.BLOCK){
                continue;
            }
            if (solverPath[point.x][point.y] - 1 == solverPath[next.x][next.y]){
                addPath(next);
                return;
            }
        }
    }

    /**
     * 递归求解迷宫最佳路径
     * @param point 当前点
     * @param count 从开始走到当前点所需要的步数
     */
    private void solverPath(MazePoint point, int count) {
        // 判断当前点的步数时候小于现在走到这个点的步数,
        // 如果当前点的步数比较小,则直接返回
        if (solverPath[point.x][point.y] <= count){
            return;
        }
        // 否则表示当前点,有更短的路径
        solverPath[point.x][point.y] = count;
        // 再遍历当前点的每个方向
        for (Position position : Position.values()){
            MazePoint next = findNext(point, position);
            // 如果下一个点不在迷宫内,或当前点对应的方向是一面墙壁,则跳过继续编写下一个方向
            if (next == null || getBoxes(point.x, point.y).get(position) == Wall.BLOCK){
                continue;
            }
            // 否则,步数加1, 递归计算
            solverPath(next, count + 1);
        }
    }

    public static class MazePoint{
        public final int x;
        public final int y;

        public MazePoint(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "MazePoint{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}

迷宫的求解,一般我会使用以下两种方法

1. 右手规则,从起点出发,遇到墙壁,则向右手边转,按照这个规则.一般是可以找到出口的.不过如果迷宫有闭环,则无法求解,而且解出来的路径也不是最短路径.
2. 迷宫最短路径算法.
   1. 从起点出发,计数count=0
   2. 遍历该点的任意方向,如果是墙壁,则忽略,不然count++,进入下一个联通的格子
   3. 判断当前格子的的count(默认值一般是比较大的数)是否比传入的参数大,是说明该格子是一条捷径,将当前各自的count=入参,继续第2步;否则,说明该点已经被探索过且不是一条捷径,忽略
   4. 如果反复,暴力遍历所有单元格,即可以求出最短路径
   5. 遍历完之后,从出口开始找,此时出口的数字,表示从入口走到出口需要的最小步数.依次减1,找到下一个格子,直到找打入口.则最短路径就生成了.

https://github.com/kco1989/maventest/blob/master/src/main/java/com/kco/game/maze/MazeArrayBuilder.java

https://github.com/kco1989/maventest/blob/master/src/main/java/com/kco/game/maze/MazeMapBuilder.java