Похоже, что на самом деле вполне разумно создавать лабиринты, отвечающие вашим критериям, используя двухэтапный процесс:
Создайте случайный лабиринт независимо от того, возможно ли попасть в правый нижний угол из верхнего левого угла.
Повторяйте шаг (1), пока не появится путь к правому нижнему углу.
Я закодировал это, используя две стратегии, одну на основе рандомизированного поиска в глубину и одну на основе рандомизированного поиска в ширину. Рандомизированный поиск в глубину по сеткам размером 100 & times; 100, генерирует лабиринты, где нижний правый угол доступен из верхнего левого угла 82% времени. При рандомизированном поиске в ширину вероятность успеха в 100 раз больше; 100 сеток - это около 70%. Таким образом, эта стратегия действительно представляется жизнеспособной; в среднем вам понадобится создать около 1,2 лабиринта с DFS и около 1,4 лабиринта с BFS, прежде чем вы найдете тот, который работает.
Механизм, который я использовал для создания лабиринтов без петель, основан на обобщении идеи из обычных BFS и DFS. В обоих этих алгоритмах мы выбираем какое-то местоположение, которое (1) мы еще не посещали, но (2) находится рядом с тем местом, которое у нас есть, затем добавляем новое местоположение с предыдущим местоположением в качестве его родителя. Таким образом, вновь добавленное местоположение заканчивается тем, что оно является смежным точно с одной из ранее посещенных ячеек. Я адаптировал эту идею, используя это правило:
Не преобразовывайте полную ячейку в пустую, если она соседствует с несколькими пустыми ячейками.
Это правило гарантирует, что мы никогда не получим никаких циклов (если что-то смежно с двумя или более пустыми местоположениями, и мы очищаем это, мы создаем цикл, добираясь до первого местоположения, затем перемещаясь к недавно освобожденному квадрату, затем переезд во второе место).
Вот пример 30 раз; 30 лабиринтов, созданных с использованием подхода DFS:
.#.........#...#.#....#.#..##.
.#.#.#.#.#.#.#.....##....#....
..#...#..#.#.##.#.#.####.#.#.#
#..#.##.##.#...#..#......#.#..
.#..#...#..####..#.#.####..##.
...#..##..#.....#..#....##..#.
.##.#.#.#...####..#.###...#.#.
..#.#.#.###.#....#..#.#.#..##.
#.#...#....#..#.###....###....
...#.###.#.#.#...#..##..#..#.#
.#....#..#.#.#.#.#.#..#..#.#..
..####..#..###.#.#...###..#.#.
.#.....#.#.....#.########...#.
#..#.##..#######.....#####.##.
..##...#........####..###..#..
.#..##..####.#.#...##..#..#..#
..#.#.#.#....#.###...#...#..#.
.#....#.#.####....#.##.#.#.#..
.#.#.#..#.#...#.#...#..#.#...#
.#..##.#..#.#..#.##..##..###..
.#.#...##....#....#.#...#...#.
...#.##...##.####..#..##..##..
#.#..#.#.#.......#..#...#..#.#
..#.#.....#.####..#...##..##..
##..###.#..#....#.#.#....#..#.
...#...#..##.#.#...#####...#..
.###.#.#.#...#.#.#..#...#.#..#
.#...#.##..##..###.##.#.#.#.##
.#.###..#.##.#....#...#.##...#
......#.......#.#...#.#....#..
Вот пример 30 раз; 30 лабиринтов, созданных с использованием BFS:
.#..#..#...#......#..##.#.....
..#.#.#.#.#..#.##...#....#.#.#
#...#.......###.####..##...#.#
.#.#..#.#.##.#.......#.#.#..#.
.....#..#......#.#.#.#..#..##.
#.#.#.###.#.##..#.#....#.#....
..##.....##..#.##...##.#...#.#
#....#.#...#..##.##...#.#.##..
.#.#..##.##..##...#.#...##...#
....#...#..#....#.#.#.##..##..
#.##..#.##.##.##...#..#..##..#
....#.##.#..#...#.####.#...#..
.#.##......#..##.#.#.....#..#.
#....#.#.#..#........#.#.#.##.
.#.###..#..#.#.##.#.#...####..
.#.#...#.#...#..#..###.#.#...#
....##.#.##.#..#.####.....#.#.
.#.#.......###.#.#.#.##.##....
#..#.#.#.##.#.#........###.#.#
.#..#..#........##.#.####..#..
...#.#.#.#.#.##.#.###..#.##..#
#.#..#.##..#.#.#...#.#.....#..
....#...##.#.....#.....##.#..#
#.#.#.##...#.#.#.#.#.##..#.##.
...#..#..##..#..#...#..#.#....
#.#.#.##...#.##..##...#....#.#
..#..#...##....##...#...#.##..
#...#..#...#.#..#.#.#.#..#...#
..#..##..##..#.#..#..#.##.##..
#.#.#...#...#...#..#........#.
И, для забавы, вот код, который я использовал для генерации этих чисел и лабиринтов. Сначала код 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;
}
Надеюсь, это поможет!