algorithm - 特殊的完美迷宫生成算法

标签 algorithm generator depth-first-search maze

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

我处理的不是具有房间和墙壁的标准情况，而是处理充满方 block 的单元格网格，我可以在其中从某些单元格中移除方 block :

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

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

正常情况从这里开始

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

到这里

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

在我的例子中，我试图将左上角的单元格连接到右下角的单元格:

##
##

到这里

.#
..

或在这里

..
#.

但不是在这里(因为右下角的单元格被屏蔽了)

..
.#

而不是这里(两个单元格没有连接)

.#
#.

而不是这里(迷宫并不完美，单元之间由不止一条路径连接)

..
..

这里还有两个 8x8 的例子:

好的(完美的迷宫，从左上角的单元格到右下角的单元格有一条路径):

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

错误的(完美迷宫，但没有从左上角单元格到右下角单元格的路径):

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

Some nice 1000x1000 solved generated maze

最佳答案

看起来使用两步过程生成符合您标准的迷宫实际上是相当合理的:

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

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

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

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

Do not convert a full cell to an empty cell if it's adjacent to more than one empty cell.

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

这是一个使用 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;
}

希望这对您有所帮助!

关于algorithm - 特殊的完美迷宫生成算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56688412/

上一篇：python - 交错集群的算法

下一篇：algorithm - 使用迭代器和堆栈的二进制搜索树按顺序遍历 - 空间复杂度 O(log N)？如何？

相关文章：

java - 是先学数据结构和算法还是先学Java？

java - 生成项目依赖结构图

javascript - 为什么 Javascript 生成器既是迭代器又是可迭代对象？

algorithm - 寻找二叉树中的最长路径

JavaScript 最长公共(public)子序列

algorithm - 随机快速排序 : probability of low partition size 1

python - 如何在循环中调用带有非类型函数的生成器类型函数？

java - MINIMAX算法如何从树底向上进行BFS？

algorithm - 我应该使用广度优先还是深度优先来搜索文件系统以查找预定数量的错误？

algorithm - 维持二维约束的调度算法

©2024 IT工具网  联系我们