特殊完美迷宫生成算法

Question

我正在尝试创建一个特殊的完美迷宫生成器。

而不是有房间和墙壁的标准案例，我正在处理一个充满块的单元格网格，在那里我可以从一些单元格中删除块：

• 连接两个给定的单元格（例如，将左上角的单元格连接到左下角的单元格）
• 为了有一个最大的块删除
• 每个移除的块单元必须使用一种方式相互连接

我使用 DFS 算法来挖掘路径迷宫，但我找不到确保两个给定单元格连接的方法。

正常情况从这里开始

+-+-+
| | |
+-+-+
| | |
+-+-+

到这里

+-+-+
| | |
+ + +
|   |
+-+-+

就我而言，我试图将左上角的单元格连接到右下角的单元格：

##
##

到这里

.#
..

或在这里

..
#.

但不是在这里（因为右下角的单元格被挡住了）

..
.#

而不是在这里（两个单元格没有连接）

.#
#.

而不是在这里（迷宫并不完美，细胞由不止一条路径连接）

..
..

这里还有两个 8x8 示例：

好一个（完美的迷宫，从左上角的单元格到右下角的单元格有一条路径）：

..#.....
.#.#.##.
.......#
.#.#.##.
.##...#.
..#.#...
.##.#.#.
...###..

坏的（完美的迷宫，但没有从左上角单元格到右下角单元格的路径）：

...#....
.##..#.#
....##..
#.#...##
#..##...
..#..#.#
#...#...
##.###.#

Answer 1

看起来使用两步过程生成满足您标准的迷宫实际上是非常合理的：

1. 生成一个随机迷宫而不考虑是否有可能从左上角到达右下角。

2. 重复步骤 (1)，直到有一条通往右下角的路径。

我已经使用两种策略对此进行了编码，一种基于随机深度优先搜索，另一种基于随机广度优先搜索。随机深度优先搜索在 100 × 100 大小的网格上生成迷宫，其中 82% 的时间可以从左上角到达右下角。使用随机广度优先搜索，100 × 100 网格的成功率约为 70%。所以这个策略似乎确实是可行的。平均而言，您需要使用 DFS 生成大约 1.2 个迷宫，使用 BFS 生成大约 1.4 个迷宫，然后才能找到一个有效的迷宫。

我用来生成没有循环的迷宫的机制是基于对常规 BFS 和 DFS 思想的概括。在这两种算法中，我们选择一些位置 (1) 我们尚未访问过但 (2) 与我们拥有的某个位置相邻，然后将新位置添加到前一个位置作为其父位置。也就是说，新添加的位置最终恰好与先前访问过的单元格之一相邻。我通过使用这个规则调整了这个想法：

如果一个完整的单元格与多个空单元格相邻，则不要将其转换为空单元格。

此规则确保我们永远不会得到任何循环（如果某物与两个或更多空位置相邻并且我们将其清空，我们通过到达第一个位置，然后移动到新清空的方格，然后移动到第二个位置）。

这是使用 DFS 方法生成的 30 × 30 迷宫示例：

.#.........#...#.#....#.#..##.
.#.#.#.#.#.#.#.....##....#....
..#...#..#.#.##.#.#.####.#.#.#
#..#.##.##.#...#..#......#.#..
.#..#...#..####..#.#.####..##.
...#..##..#.....#..#....##..#.
.##.#.#.#...####..#.###...#.#.
..#.#.#.###.#....#..#.#.#..##.
#.#...#....#..#.###....###....
...#.###.#.#.#...#..##..#..#.#
.#....#..#.#.#.#.#.#..#..#.#..
..####..#..###.#.#...###..#.#.
.#.....#.#.....#.########...#.
#..#.##..#######.....#####.##.
..##...#........####..###..#..
.#..##..####.#.#...##..#..#..#
..#.#.#.#....#.###...#...#..#.
.#....#.#.####....#.##.#.#.#..
.#.#.#..#.#...#.#...#..#.#...#
.#..##.#..#.#..#.##..##..###..
.#.#...##....#....#.#...#...#.
...#.##...##.####..#..##..##..
#.#..#.#.#.......#..#...#..#.#
..#.#.....#.####..#...##..##..
##..###.#..#....#.#.#....#..#.
...#...#..##.#.#...#####...#..
.###.#.#.#...#.#.#..#...#.#..#
.#...#.##..##..###.##.#.#.#.##
.#.###..#.##.#....#...#.##...#
......#.......#.#...#.#....#..

这是使用 BFS 生成的 30 × 30 迷宫示例：

.#..#..#...#......#..##.#.....
..#.#.#.#.#..#.##...#....#.#.#
#...#.......###.####..##...#.#
.#.#..#.#.##.#.......#.#.#..#.
.....#..#......#.#.#.#..#..##.
#.#.#.###.#.##..#.#....#.#....
..##.....##..#.##...##.#...#.#
#....#.#...#..##.##...#.#.##..
.#.#..##.##..##...#.#...##...#
....#...#..#....#.#.#.##..##..
#.##..#.##.##.##...#..#..##..#
....#.##.#..#...#.####.#...#..
.#.##......#..##.#.#.....#..#.
#....#.#.#..#........#.#.#.##.
.#.###..#..#.#.##.#.#...####..
.#.#...#.#...#..#..###.#.#...#
....##.#.##.#..#.####.....#.#.
.#.#.......###.#.#.#.##.##....
#..#.#.#.##.#.#........###.#.#
.#..#..#........##.#.####..#..
...#.#.#.#.#.##.#.###..#.##..#
#.#..#.##..#.#.#...#.#.....#..
....#...##.#.....#.....##.#..#
#.#.#.##...#.#.#.#.#.##..#.##.
...#..#..##..#..#...#..#.#....
#.#.#.##...#.##..##...#....#.#
..#..#...##....##...#...#.##..
#...#..#...#.#..#.#.#.#..#...#
..#..##..##..#.#..#..#.##.##..
#.#.#...#...#...#..#........#.

而且，为了好玩，这是我用来生成这些数字和这些迷宫的代码。一、DFS代码：

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <random>
using namespace std;

/* World Dimensions */
const size_t kNumRows = 30;
const size_t kNumCols = 30;

/* Location. */
using Location = pair<size_t, size_t>; // (row, col)

/* Adds the given point to the frontier, assuming it's legal to do so. */
void updateFrontier(const Location& loc, vector<string>& maze, vector<Location>& frontier,
                    set<Location>& usedFrontier) {
  /* Make sure we're in bounds. */
  if (loc.first >= maze.size() || loc.second >= maze[0].size()) return;

  /* Make sure this is still a wall. */
  if (maze[loc.first][loc.second] != '#') return;

  /* Make sure we haven't added this before. */
  if (usedFrontier.count(loc)) return;

  /* All good! Add it in. */
  frontier.push_back(loc);
  usedFrontier.insert(loc);
}

/* Given a location, adds that location to the maze and expands the frontier. */
void expandAt(const Location& loc, vector<string>& maze, vector<Location>& frontier,
              set<Location>& usedFrontier) {
  /* Mark the location as in use. */
  maze[loc.first][loc.second] = '.';

  /* Handle each neighbor. */
  updateFrontier(Location(loc.first, loc.second + 1), maze, frontier, usedFrontier);
  updateFrontier(Location(loc.first, loc.second - 1), maze, frontier, usedFrontier);
  updateFrontier(Location(loc.first + 1, loc.second), maze, frontier, usedFrontier);
  updateFrontier(Location(loc.first - 1, loc.second), maze, frontier, usedFrontier);
}

/* Chooses and removes a random element of the frontier. */
Location sampleFrom(vector<Location>& frontier, mt19937& generator) {
  uniform_int_distribution<size_t> dist(0, frontier.size() - 1);

  /* Pick our spot. */
  size_t index = dist(generator);

  /* Move it to the end and remove it. */
  swap(frontier[index], frontier.back());

  auto result = frontier.back();
  frontier.pop_back();
  return result;
}

/* Returns whether a location is empty. */
bool isEmpty(const Location& loc, const vector<string>& maze) {
  return loc.first < maze.size() && loc.second < maze[0].size() && maze[loc.first][loc.second] == '.';
}

/* Counts the number of empty neighbors of a given location. */
size_t neighborsOf(const Location& loc, const vector<string>& maze) {
  return !!isEmpty(Location(loc.first - 1, loc.second), maze) +
         !!isEmpty(Location(loc.first + 1, loc.second), maze) +
         !!isEmpty(Location(loc.first, loc.second - 1), maze) +
         !!isEmpty(Location(loc.first, loc.second + 1), maze);
}

/* Returns whether a location is in bounds. */
bool inBounds(const Location& loc, const vector<string>& world) {
  return loc.first < world.size() && loc.second < world[0].size();
}

/* Runs a recursive DFS to fill in the maze. */
void dfsFrom(const Location& loc, vector<string>& world, mt19937& generator) {
  /* Base cases: out of bounds? Been here before? Adjacent to too many existing cells? */
  if (!inBounds(loc, world) || world[loc.first][loc.second] == '.' ||
      neighborsOf(loc, world) > 1) return;

  /* All next places. */
  vector<Location> next = {
    { loc.first - 1, loc.second },
    { loc.first + 1, loc.second },
    { loc.first, loc.second - 1 },
    { loc.first, loc.second + 1 }
  };
  shuffle(next.begin(), next.end(), generator);

  /* Mark us as filled. */
  world[loc.first][loc.second] = '.';

  /* Explore! */
  for (const Location& nextStep: next) {
    dfsFrom(nextStep, world, generator);
  }
}

/* Generates a random maze. */
vector<string> generateMaze(size_t numRows, size_t numCols, mt19937& generator) {
  /* Create the maze. */
  vector<string> result(numRows, string(numCols, '#'));

  /* Build the maze! */
  dfsFrom(Location(0, 0), result, generator);

  return result;
}

int main() {
  random_device rd;
  mt19937 generator(rd());

  /* Run some trials. */
  size_t numTrials = 0;
  size_t numSuccesses = 0;

  for (size_t i = 0; i < 10000; i++) {
    numTrials++;

    auto world = generateMaze(kNumRows, kNumCols, generator);

    /* Can we get to the bottom? */
    if (world[kNumRows - 1][kNumCols - 1] == '.') {
      numSuccesses++;

      /* Print the first maze that works. */
      if (numSuccesses == 1) {
        for (const auto& row: world) {
          cout << row << endl;
        }
        cout << endl;
      }
    }
  }

  cout << "Trials:    " << numTrials << endl;
  cout << "Successes: " << numSuccesses << endl;
  cout << "Percent:   " << (100.0 * numSuccesses) / numTrials << "%" << endl;


  cout << endl;
  return 0;
}

接下来是BFS代码：

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <random>
using namespace std;

/* World Dimensions */
const size_t kNumRows = 30;
const size_t kNumCols = 30;

/* Location. */
using Location = pair<size_t, size_t>; // (row, col)

/* Adds the given point to the frontier, assuming it's legal to do so. */
void updateFrontier(const Location& loc, vector<string>& maze, vector<Location>& frontier,
                    set<Location>& usedFrontier) {
  /* Make sure we're in bounds. */
  if (loc.first >= maze.size() || loc.second >= maze[0].size()) return;

  /* Make sure this is still a wall. */
  if (maze[loc.first][loc.second] != '#') return;

  /* Make sure we haven't added this before. */
  if (usedFrontier.count(loc)) return;

  /* All good! Add it in. */
  frontier.push_back(loc);
  usedFrontier.insert(loc);
}

/* Given a location, adds that location to the maze and expands the frontier. */
void expandAt(const Location& loc, vector<string>& maze, vector<Location>& frontier,
              set<Location>& usedFrontier) {
  /* Mark the location as in use. */
  maze[loc.first][loc.second] = '.';

  /* Handle each neighbor. */
  updateFrontier(Location(loc.first, loc.second + 1), maze, frontier, usedFrontier);
  updateFrontier(Location(loc.first, loc.second - 1), maze, frontier, usedFrontier);
  updateFrontier(Location(loc.first + 1, loc.second), maze, frontier, usedFrontier);
  updateFrontier(Location(loc.first - 1, loc.second), maze, frontier, usedFrontier);
}

/* Chooses and removes a random element of the frontier. */
Location sampleFrom(vector<Location>& frontier, mt19937& generator) {
  uniform_int_distribution<size_t> dist(0, frontier.size() - 1);

  /* Pick our spot. */
  size_t index = dist(generator);

  /* Move it to the end and remove it. */
  swap(frontier[index], frontier.back());

  auto result = frontier.back();
  frontier.pop_back();
  return result;
}

/* Returns whether a location is empty. */
bool isEmpty(const Location& loc, const vector<string>& maze) {
  return loc.first < maze.size() && loc.second < maze[0].size() && maze[loc.first][loc.second] == '.';
}

/* Counts the number of empty neighbors of a given location. */
size_t neighborsOf(const Location& loc, const vector<string>& maze) {
  return !!isEmpty(Location(loc.first - 1, loc.second), maze) +
         !!isEmpty(Location(loc.first + 1, loc.second), maze) +
         !!isEmpty(Location(loc.first, loc.second - 1), maze) +
         !!isEmpty(Location(loc.first, loc.second + 1), maze);
}

/* Generates a random maze. */
vector<string> generateMaze(size_t numRows, size_t numCols, mt19937& generator) {
  /* Create the maze. */
  vector<string> result(numRows, string(numCols, '#'));

  /* Worklist of free locations. */
  vector<Location> frontier;

  /* Set of used frontier sites. */
  set<Location> usedFrontier;

  /* Seed the starting location. */
  expandAt(Location(0, 0), result, frontier, usedFrontier);

  /* Loop until there's nothing left to expand. */
  while (!frontier.empty()) {
    /* Select a random frontier location to expand at. */
    Location next = sampleFrom(frontier, generator);

    /* If this spot has exactly one used neighbor, add it. */
    if (neighborsOf(next, result) == 1) {   
      expandAt(next, result, frontier, usedFrontier);
    }
  }

  return result;
}

int main() {
  random_device rd;
  mt19937 generator(rd());

  /* Run some trials. */
  size_t numTrials = 0;
  size_t numSuccesses = 0;

  for (size_t i = 0; i < 10000; i++) {
    numTrials++;

    auto world = generateMaze(kNumRows, kNumCols, generator);

    /* Can we get to the bottom? */
    if (world[kNumRows - 1][kNumCols - 1] == '.') {
      numSuccesses++;

      /* Print the first maze that works. */
      if (numSuccesses == 1) {
        for (const auto& row: world) {
          cout << row << endl;
        }
        cout << endl;
      }
    }
  }

  cout << "Trials:    " << numTrials << endl;
  cout << "Successes: " << numSuccesses << endl;
  cout << "Percent:   " << (100.0 * numSuccesses) / numTrials << "%" << endl;


  cout << endl;
  return 0;
}

希望这可以帮助！