迷宫生成方案

常见的迷宫生成算法有：prim算法，递归回溯，递归分割。

Prim算法

普里姆算法（Prim’s algorithm），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

描述

从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；
2. 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
3. 重复下列操作，直到Vnew = V：
   1. 在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将v加入集合Vnew中，将（u, v）加入集合Enew中；
4. 输出：使用集合Vnew和Enew来描述所得到的最小生成树。

使用prim算法生成迷宫

1. 让迷宫全是墙.
2. 选一个单元格作为迷宫的通路，然后把它的邻墙放入列表
3. 当列表里还有墙时，从列表里随机选一个墙
   1. 如果这面墙分隔的两个单元格只有一个单元格被访问过。从列表里移除这面墙，墙标记为通，让未访问的单元格成为迷宫的通路，把这个格子的墙加入列表
   2. 如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙

实现代码

• 格子：

  package pres.fei.algorithm.maze;
  
  import lombok.Getter;
  import lombok.Setter;
  
  /**
   * 迷宫格子
   *
   * @author fei
   */
  @Getter
  @Setter
  public class MazeGrid {
  
      private int x;
  
      private int y;
  
      private MazeWall up;
  
      private MazeWall right;
  
      private MazeWall down;
  
      private MazeWall left;
  
      public MazeGrid(int x, int y) {
          this.x = x;
          this.y = y;
      }
  
      @Override
      public boolean equals(Object o) {
          if (this == o) {
              return true;
          }
          if (o == null || getClass() != o.getClass()) {
              return false;
          }
  
          MazeGrid mazeGrid = (MazeGrid) o;
  
          if (x != mazeGrid.x) {
              return false;
          }
          return y == mazeGrid.y;
      }
  
      @Override
      public int hashCode() {
          int result = x;
          result = 31 * result + y;
          return result;
      }
  }

• 墙

  package pres.fei.algorithm.maze;
  
  import lombok.Getter;
  import lombok.Setter;
  
  /**
   * 迷宫墙
   *
   * @author fei
   */
  @Getter
  @Setter
  public class MazeWall {
  
      private String id;
  
      private boolean open;
      /**
       * 墙一侧的格子
       */
      private MazeGrid g1;
      /**
       * 墙另一侧的格子
       */
      private MazeGrid g2;
  
      public MazeWall(String id, MazeGrid g1, MazeGrid g2) {
          this.id = id;
          this.g1 = g1;
          this.g2 = g2;
      }
  
      public boolean isClose() {
          return !open;
      }
  
      @Override
      public String toString() {
          return id + " " + open;
      }
  
      @Override
      public boolean equals(Object o) {
          if (this == o) {
              return true;
          }
          if (o == null || getClass() != o.getClass()) {
              return false;
          }
  
          MazeWall mazeWall = (MazeWall) o;
  
          return id.equals(mazeWall.id);
      }
  
      @Override
      public int hashCode() {
          return id.hashCode();
      }
  }

• prim算法

  package pres.fei.algorithm.maze;
  
  import java.util.ArrayList;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  import java.util.concurrent.ThreadLocalRandom;
  
  /**
   * prim算法处理迷宫格子
   *
   * @author fei
   */
  public class Prim {
  
      /**
       * 构建迷宫
       */
      public static void buildMazeGrids(int width, int high, List<MazeGrid> grids) {
          Set<MazeGrid> openGrids = new HashSet<>(grids.size(), 1);
          List<MazeWall> closeWalls = new ArrayList<>();
          MazeGrid startGrid = grids.get(ThreadLocalRandom.current().nextInt(grids.size()));
          openGrids.add(startGrid);
          if (startGrid.getUp() != null) {
              closeWalls.add(startGrid.getUp());
          }
          if (startGrid.getDown() != null) {
              closeWalls.add(startGrid.getDown());
          }
          if (startGrid.getLeft() != null) {
              closeWalls.add(startGrid.getLeft());
          }
          if (startGrid.getRight() != null) {
              closeWalls.add(startGrid.getRight());
          }
          while (!closeWalls.isEmpty()) {
              MazeWall wall = closeWalls.get(ThreadLocalRandom.current().nextInt(closeWalls.size()));
              closeWalls.remove(wall);
              MazeGrid g1 = wall.getG1();
              MazeGrid g2 = wall.getG2();
              if (openGrids.contains(g1) && openGrids.contains(g2)) {
                  continue;
              }
              MazeGrid closeGrid;
              if (openGrids.contains(g1)) {
                  closeGrid = g2;
              } else {
                  closeGrid = g1;
              }
              wall.setOpen(true);
              openGrids.add(closeGrid);
              MazeWall up = closeGrid.getUp();
              if (up != null && up.isClose()) {
                  closeWalls.add(up);
              }
              MazeWall down = closeGrid.getDown();
              if (down != null && down.isClose()) {
                  closeWalls.add(down);
              }
              MazeWall right = closeGrid.getRight();
              if (right != null && right.isClose()) {
                  closeWalls.add(right);
              }
              MazeWall left = closeGrid.getLeft();
              if (left != null && left.isClose()) {
                  closeWalls.add(left);
              }
          }
      }
  
  }

• 构建迷宫

  package pres.fei.algorithm.maze;
  
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  /**
   * 迷宫构建器
   *
   * @author fei
   */
  public class MazeMapBuilder {
  
  
      /**
       * 构建迷宫
       */
      public static List<MazeGrid> buildMazeGrids(int width, int high) {
          List<MazeGrid> grids = buildGrids(width, high);
          Prim.buildMazeGrids(width, high, grids);
          return grids;
      }
  
      /**
       * 构建格子即墙
       */
      private static List<MazeGrid> buildGrids(int width, int high) {
          MazeGrid[][] gridArray = new MazeGrid[width][high];
          List<MazeGrid> grids = new ArrayList<>(width * high);
          for (int i = 0; i < width; i++) {
              for (int j = 0; j < high; j++) {
                  gridArray[i][j] = new MazeGrid(i, j);
              }
          }
          Map<String, MazeWall> wallMap = new HashMap<>(width * high * 2, 1);
          for (int y = 0; y < high; y++) {
              for (int x = 0; x < width; x++) {
                  MazeGrid grid = gridArray[x][y];
                  grids.add(grid);
                  if (y != 0) {
                      String wallId = buildWallId(x, y - 1, x, y);
                      if (!wallMap.containsKey(wallId)) {
                          MazeWall up = new MazeWall(wallId, grid, gridArray[x][y - 1]);
                          wallMap.put(wallId, up);
                      }
                      grid.setUp(wallMap.get(wallId));
                  }
                  if (x != 0) {
                      String wallId = buildWallId(x - 1, y, x, y);
                      if (!wallMap.containsKey(wallId)) {
                          MazeWall left = new MazeWall(wallId, grid, gridArray[x - 1][y]);
                          wallMap.put(wallId, left);
                      }
                      grid.setLeft(wallMap.get(wallId));
                  }
                  if (x < width - 1) {
                      String wallId = buildWallId(x, y, x + 1, y);
                      if (!wallMap.containsKey(wallId)) {
                          MazeWall right = new MazeWall(wallId, grid, gridArray[x + 1][y]);
                          wallMap.put(wallId, right);
                      }
                      grid.setRight(wallMap.get(wallId));
                  }
                  if (y < high - 1) {
                      String wallId = buildWallId(x, y, x, y + 1);
                      if (!wallMap.containsKey(wallId)) {
                          MazeWall down = new MazeWall(wallId, grid, gridArray[x][y + 1]);
                          wallMap.put(wallId, down);
                      }
                      grid.setDown(wallMap.get(wallId));
                  }
              }
          }
          return grids;
      }
  
      private static String buildWallId(int x, int y, int x2, int y2) {
          return x + ":" + y + ":" + x2 + ":" + y2;
      }
  }

• 展示迷宫

  package pres.fei.algorithm.maze;
  
  import java.awt.BasicStroke;
  import java.awt.Color;
  import java.awt.Graphics;
  import java.awt.Graphics2D;
  import java.awt.RenderingHints;
  import java.util.List;
  import javax.swing.JFrame;
  import javax.swing.JPanel;
  
  /**
   * 迷宫展示
   *
   * @author fei
   */
  public class MazeShower extends JFrame {
  
      private static final long serialVersionUID = 1L;
  
  
      MazeShower(int size, int gridLen) {
          int h = size * (gridLen + 5);
          setSize(h, h + 40);
          MyPanel panel = new MyPanel(size, size, gridLen);
          setContentPane(panel);
          setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
          setVisible(true);
      }
  
      public static void main(String[] args) {
          new MazeShower(6, 50);
      }
  
      public static class MyPanel extends JPanel {
  
          private int width;
          private int high;
          private int gridLen;
  
          /**
           * Creates a new <code>JPanel</code> with a double buffer and a flow layout.
           */
          public MyPanel(int width, int high, int gridLen) {
              this.width = width;
              this.high = high;
              this.gridLen = gridLen + 5;
          }
  
          /**
           * 绘制面板的内容: 创建 JPanel 后会调用一次该方法绘制内容, 之后如果数据改变需要重新绘制, 可调用 updateUI() 方法触发 系统再次调用该方法绘制更新
           * JPanel 的内容。
           */
          @Override
          protected void paintComponent(Graphics g) {
              super.paintComponent(g);
              List<MazeGrid> grids = MazeMapBuilder.buildMazeGrids(width, high);
              for (MazeGrid grid : grids) {
                  int x = grid.getX();
                  int y = grid.getY();
                  MazeWall down = grid.getDown();
                  if (down != null && down.isClose()) {
                      int x1 = x * gridLen;
                      int x2 = x1 + gridLen;
                      int y1 = (y + 1) * gridLen;
                      int y2 = y1;
                      drawLine(g, x1, y1, x2, y2, true);
                  } else {
                      int x1 = x * gridLen;
                      int x2 = x1 + gridLen;
                      int y1 = (y + 1) * gridLen;
                      int y2 = y1;
                      drawLine1(g, x1, y1, x2, y2);
                  }
                  MazeWall right = grid.getRight();
                  if (right != null && right.isClose()) {
                      int x1 = (x + 1) * gridLen;
                      int x2 = x1;
                      int y1 = y * gridLen;
                      int y2 = y1 + gridLen;
                      drawLine(g, x1, y1, x2, y2, true);
                  } else {
                      int x1 = (x + 1) * gridLen;
                      int x2 = x1;
                      int y1 = y * gridLen;
                      int y2 = y1 + gridLen;
                      drawLine1(g, x1, y1, x2, y2);
                  }
              }
          }
  
          /**
           * 线段
           */
          private void drawLine(Graphics g, int x1, int y1, int x2, int y2, boolean close) {
  
              // 创建 Graphics 的副本, 需要改变 Graphics 的参数,
              // 这里必须使用副本, 避免影响到 Graphics 原有的设置
              Graphics2D g2d = (Graphics2D) g.create();
  
              // 抗锯齿
              g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                  RenderingHints.VALUE_ANTIALIAS_ON);
              // 设置画笔颜色
              if (close) {
                  g2d.setColor(Color.BLACK);
              } else {
                  g2d.setColor(Color.RED);
              }
  
              // 3. 两点绘制线段（设置线宽为5px）: 点(50, 150), 点(200, 150)
              BasicStroke bs1 = new BasicStroke(5);       // 笔画的轮廓（画笔宽度/线宽为5px）
              g2d.setStroke(bs1);
              g2d.drawLine(x1, y1, x2, y2);
  
              // 自己创建的副本用完要销毁掉
              g2d.dispose();
          }
  
          /**
           * 虚线
           */
          private void drawLine1(Graphics g, int x1, int y1, int x2, int y2) {
  
              // 创建 Graphics 的副本, 需要改变 Graphics 的参数,
              // 这里必须使用副本, 避免影响到 Graphics 原有的设置
              Graphics2D g2d = (Graphics2D) g.create();
  
              // 抗锯齿
              g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                  RenderingHints.VALUE_ANTIALIAS_ON);
              // 设置画笔颜色
              g2d.setColor(Color.RED);
  
              float[] dash = new float[]{5, 10};
              BasicStroke bs2 = new BasicStroke(
                  1,                      // 画笔宽度/线宽
                  BasicStroke.CAP_SQUARE,
                  BasicStroke.JOIN_MITER,
                  10.0f,
                  dash,                   // 虚线模式数组
                  0.0f
              );
              g2d.setStroke(bs2);
              g2d.drawLine(x1, y1, x2, y2);
              // 自己创建的副本用完要销毁掉
              g2d.dispose();
          }
      }
  }

深度优先-递归回溯

1. 将起点作为当前迷宫单元并标记为已访问
2. 当还存在未标记的迷宫单元，进行循环
   1. 如果当前迷宫单元有未被访问过的的相邻的迷宫单元
      1. 随机选择一个未访问的相邻迷宫单元
      2. 将当前迷宫单元入栈
      3. 移除当前迷宫单元与相邻迷宫单元的墙
      4. 标记相邻迷宫单元并用它作为当前迷宫单元
   2. 如果当前迷宫单元不存在未访问的相邻迷宫单元，并且栈不空
      1. 栈顶的迷宫单元出栈

• 与prim算法的区别：
  深度优先 每次在一个单元格的周围随机找一个未被访问的格子，而prim算法则是当前已遍历过的所有格子中随机一个未访问的格子。所以，深度有限生成的迷宫会有一条明显的主路，而prim算法生成的迷宫则更随机。

递归分割

1. 把空间用十字分成四个子空间，选择三面墙上连通
2. 持续1步骤，直到所有空间都不能再分割

• 递归分割迷宫特点
  地图比较方正