- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试创建一个特殊的完美迷宫生成器。
我处理的不是具有房间和墙壁的标准情况,而是处理充满方 block 的单元格网格,我可以在其中从某些单元格中移除方 block :
我使用 DFS 算法来挖掘路径迷宫,但我找不到一种方法来确保给定的两个单元格是相连的。
正常情况从这里开始
+-+-+
| | |
+-+-+
| | |
+-+-+
到这里
+-+-+
| | |
+ + +
| |
+-+-+
在我的例子中,我试图将左上角的单元格连接到右下角的单元格:
##
##
到这里
.#
..
或在这里
..
#.
但不是在这里(因为右下角的单元格被屏蔽了)
..
.#
而不是这里(两个单元格没有连接)
.#
#.
而不是这里(迷宫并不完美,单元之间由不止一条路径连接)
..
..
这里还有两个 8x8 的例子:
好的(完美的迷宫,从左上角的单元格到右下角的单元格有一条路径):
..#.....
.#.#.##.
.......#
.#.#.##.
.##...#.
..#.#...
.##.#.#.
...###..
错误的(完美迷宫,但没有从左上角单元格到右下角单元格的路径):
...#....
.##..#.#
....##..
#.#...##
#..##...
..#..#.#
#...#...
##.###.#
最佳答案
看起来使用两步过程生成符合您标准的迷宫实际上是相当合理的:
生成一个随机迷宫,而不考虑是否可以从左上角到达右下角。
重复步骤 (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/
我正在尝试使用以下 keytool 命令为我的应用程序生成 keystore : keytool -genkey -alias tomcat -keystore tomcat.keystore -ke
编辑:在西里尔正确解决问题后,我注意到只需将生成轴的函数放在用于生成标签的函数下面就可以解决问题。 我几乎读完了 O'Reilly 书中关于 D3.js 的教程,并在倒数第二页上制作了散点图,但是当添
虽然使用 GraphiQL 效果很好,但我的老板要求我实现一个用户界面,用户可以在其中通过 UI 元素(例如复选框、映射关系)检查呈现给他们的元素并获取数据,这样做将为该人生成 graphql 输入,
我尝试在 Netbean 6.8 中使用 ws-import 生成 Java 类。我想重新生成 jax-ws,因为在 ebay.api.paypalapi 包中发现了一个错误(我认为该错误是由于 Pa
我有一个 perl 脚本,它获取系统日期并将该日期写入文件名。 系统日期被分配给 TRH1 变量,然后它被设置为一个文件名。 $TRH1 =`date + %Y%m%d%H%M`; print "TR
我是 Haskell 的新手,需要帮助。我正在尝试构建一种必须具有某种唯一性的新数据类型,因此我决定使用 UUID 作为唯一标识符: data MyType = MyType { uuid ::
我制作了一个脚本,它可以根据 Mysql 数据库中的一些表生成 XML。 该脚本在 PHP 中运行。 public function getRawMaterials($apiKey, $format
所以这是我的项目中的一个问题。 In this task, we will use OpenSSL to generate digital signatures. Please prepare a f
我在 SAS LIFEREG 中有一个加速故障时间模型,我想绘制它。因为 SAS 在绘图方面非常糟糕,我想实际重新生成 R 中曲线的数据并将它们绘制在那里。 SAS 提出了一个尺度(在指数分布固定为
我正在为 Django 后端制作一个样板,并且我需要能够使它到达下一个下载它的人显然无法访问我的 secret key 的地方,或者拥有不同的 key 。我一直在研究一些选项,并在这个过程中进行了实验
我正在创建一个生成采购订单的应用程序。我可以根据用户输入的详细信息创建文本文件。我想生成一个看起来比普通文本文件好得多的 Excel。有没有可以在我的应用程序中使用的开源库? 最佳答案 目前还没有任何
我正在尝试使用 ScalaCheck 为 BST 创建一个 Gen,但是当我调用 .sample 方法时,它给了我 java.lang.NullPointerException。我哪里错了? seal
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我尝试编写一些代码,例如(在verilog中): parameter N = 128; if (encoder_in[0] == 1) begin 23 binary_out = 1;
我正忙于在 Grails 项目中进行从 MySQL 到 Postgres 的相当复杂的数据迁移。 我正在使用 GORM 在 PostGres 中生成模式,然后执行 MySQL -> mysqldump
如何使用纯 XSLT 生成 UUID?基本上是寻找一种使用 XSLT 创建独特序列的方法。该序列可以是任意长度。 我正在使用 XSLT 2.0。 最佳答案 这是一个good example 。基本上,
我尝试安装.app文件,但是当我安装并单击“同步”(在iTunes中)时,我开始在设备上开始安装,然后停止,这是一个问题,我不知道在哪里,但我看到了我无法解决的奇怪的事情: 最佳答案 似乎您没有在Xc
自从我生成 JavaDocs 以来已经有一段时间了,我确信这些选项在过去 10 年左右的时间里已经得到了改进。 我能否得到一些有关生成器的建议,该生成器将输出类似于 .Net 文档结构的 JavaDo
我想学习如何生成 PDF,我不想使用任何第三方工具,我想自己用代码创建它。到目前为止,我所看到的唯一示例是我通过在第 3 方 dll 上打开反射器查看的代码,以查看发生了什么。不幸的是,到目前为止我看
我正在从 Epplus 库生成 excel 条形图。 这是我成功生成的。 我的 table 是这样的 Mumbai Delhi Financial D
我是一名优秀的程序员,十分优秀!