迷宫(递归除法)算法设计 [英] Maze (recursive division) algorithm design
问题描述
我目前正在开发一个随机迷宫生成器，该迷宫生成器将迷宫存储在称为grid的二维数组中.然后，稍后将使用它来生成一个真实的3D迷宫，用户随后可以穿过它.
做完一些研究后，我尝试使用递归除法算法创建此迷宫生成器，但是由于迷宫格式的性质，这对我来说实际上并不起作用.
据我了解，递归划分方法不会将墙视为单元格.
例如，我的网格如下所示:
a b c d e f g h
1 - - - - - - - -
2 | | | | |
3 | | |
4 | - - | - |
5 | | | |
6 | - | - |
7 x |
8 - - - - - - - -
我要在这里介绍的要点是，我要创建的网格将被表示为以下内容:
w w w w w w w w
w w w w w
w w w
w w w w w w
w w w w
w w w w w
g w
w w w w w w w w
其中"w"是墙，"g"是入口/出口.因此，将墙壁放置在网格中，例如grid[1][2] == 'w'
递归除法算法的问题是墙不被视为单元的成员.所有的单元"本质上都将包含空格，并且墙壁将围绕它们放置.
因此，当我尝试在这种情况下实现此算法时，最终得到如下结果:(黑色正方形是墙壁，白色正方形是空的，红色正方形是入口)
我的JSFiddle位于此处.
基本上，用户将从红色方块开始，必须经过迷宫并找到可以打开门(即红色方块)以逃脱的钥匙，因此迷宫中的所有空白都必须是可访问的
有人对我如何重写此算法有任何想法，以确保始终有一条从红场到迷宫中其他任何空间的路径吗?理想情况下，路径的宽度不应超过一平方毫米.
代码:
var grid;
function generate(dimensions, numDoors) {
//numDoors is unused right now
grid = new Array();
for (var i = 0; i < dimensions; i++) {
grid[i] = new Array();
for (var j = 0; j < dimensions; j++) {
grid[i][j] = "";
}
}
addOuterWalls();
var ent = addEntrance();
addInnerWalls(true, 1, grid.length - 2, 1, grid.length - 2, ent);
}
function addOuterWalls() {
for (var i = 0; i < grid.length; i++) {
if (i == 0 || i == (grid.length - 1)) {
for (var j = 0; j < grid.length; j++) {
grid[i][j] = "w";
}
} else {
grid[i][0] = "w";
grid[i][grid.length - 1] = "w";
}
}
}
function addEntrance() {
var x = randomNumber(1, grid.length - 1);
grid[grid.length - 1][x] = "g";
return x;
}
function addInnerWalls(h, minX, maxX, minY, maxY, gate) {
if (h) {
if (maxX - minX < 2) {
return;
}
var y = randomNumber(minY, maxY);
addHWall(minX, maxX, y);
addInnerWalls(!h, minX, maxX, minY, y-1, gate);
addInnerWalls(!h, minX, maxX, y + 1, maxY, gate);
} else {
if (maxY - minY < 2) {
return;
}
var x = randomNumber(minX, maxX);
addVWall(minY, maxY, x);
addInnerWalls(!h, minX, x-1, minY, maxY, gate);
addInnerWalls(!h, x + 1, maxX, minY, maxY, gate);
}
}
function addHWall(minX, maxX, y) {
var hole = randomNumber(minX, maxX);
for (var i = minX; i <= maxX; i++) {
if (i == hole) grid[y][i] = "";
else grid[y][i] = "w";
}
}
function addVWall(minY, maxY, x) {
var hole = randomNumber(minY, maxY);
for (var i = minY; i <= maxY; i++) {
if (i == hole) grid[i][x] = "";
else grid[i][x] = "w";
}
}
function randomNumber(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
}
function display() {
document.getElementById("cnt").innerHTML = "";
for (var i = 0; i < grid.length; i++) {
var output = "<div>";
for (var j = 0; j < grid.length; j++) {
output += "<b " + grid[i][j] + "></b>";
}
output += "</div>";
document.getElementById("cnt").innerHTML += output;
}
}
generate(30, 1, 1);
display();
仅在偶数单元格中放置墙，在奇数单元格中放置门，并使尺寸"为奇数. http://jsfiddle.net/tPm3s/1/
Code:
var grid;
function generate(dimensions, numDoors) {
grid = new Array();
for (var i = 0; i < dimensions; i++) {
grid[i] = new Array();
for (var j = 0; j < dimensions; j++) {
grid[i][j] = "";
}
}
addOuterWalls();
var ent = addEntrance();
addInnerWalls(true, 1, grid.length - 2, 1, grid.length - 2, ent);
}
function addOuterWalls() {
for (var i = 0; i < grid.length; i++) {
if (i == 0 || i == (grid.length - 1)) {
for (var j = 0; j < grid.length; j++) {
grid[i][j] = "w";
}
} else {
grid[i][0] = "w";
grid[i][grid.length - 1] = "w";
}
}
}
function addEntrance() {
var x = randomNumber(1, grid.length - 1);
grid[grid.length - 1][x] = "g";
return x;
}
function addInnerWalls(h, minX, maxX, minY, maxY, gate) {
if (h) {
if (maxX - minX < 2) {
return;
}
var y = Math.floor(randomNumber(minY, maxY)/2)*2;
addHWall(minX, maxX, y);
addInnerWalls(!h, minX, maxX, minY, y-1, gate);
addInnerWalls(!h, minX, maxX, y + 1, maxY, gate);
} else {
if (maxY - minY < 2) {
return;
}
var x = Math.floor(randomNumber(minX, maxX)/2)*2;
addVWall(minY, maxY, x);
addInnerWalls(!h, minX, x-1, minY, maxY, gate);
addInnerWalls(!h, x + 1, maxX, minY, maxY, gate);
}
}
function addHWall(minX, maxX, y) {
var hole = Math.floor(randomNumber(minX, maxX)/2)*2+1;
for (var i = minX; i <= maxX; i++) {
if (i == hole) grid[y][i] = "";
else grid[y][i] = "w";
}
}
function addVWall(minY, maxY, x) {
var hole = Math.floor(randomNumber(minY, maxY)/2)*2+1;
for (var i = minY; i <= maxY; i++) {
if (i == hole) grid[i][x] = "";
else grid[i][x] = "w";
}
}
function randomNumber(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
}
function display() {
document.getElementById("cnt").innerHTML = "";
for (var i = 0; i < grid.length; i++) {
var output = "<div>";
for (var j = 0; j < grid.length; j++) {
output += "<b " + grid[i][j] + "></b>";
}
output += "</div>";
document.getElementById("cnt").innerHTML += output;
}
}
generate(31, 1, 1);
display();
I am currently developing a random maze generator that stores the maze in a 2-dimensional array called grid. This will then be used later on to generate a real 3D maze that the user can then walk through.
After doing some research, I attempted to create this maze generator using the recursive division algorithm, however due to the nature of the format of the maze, this isn't really working for me.
From what I understand, the recursive division method does not treat walls as cells.
For instance, my grid would look like this:
a b c d e f g h
1 - - - - - - - -
2 | | | | |
3 | | |
4 | - - | - |
5 | | | |
6 | - | - |
7 x |
8 - - - - - - - -
The point that I'm trying to get across here is that the grid I am trying to create will be represented something like this:
w w w w w w w w
w w w w w
w w w
w w w w w w
w w w w
w w w w w
g w
w w w w w w w w
Where 'w' is a wall and 'g' is the entrance/exit. So walls are placed into the grid, e.g. grid[1][2] == 'w'
The problem with the recursive division algorithm is that walls are not treated as members of the cell. All of the 'cells' would essentially contain whitespace and the walls would be placed around them.
So when I tried to implement this algorithm in my situation, I ended up with a result like this: (the black squares are walls, the white squares are empty, and the red square is the entrance)
My JSFiddle is located here.
Essentially the user will start at the red square and have to go through the maze and find keys that will open the door (which is the red square) to escape, so all of the whitespace in the maze would have to be accessible.
Does anyone have any ideas on how I can rewrite this algorithm to make sure that there is always a path from the red square to any other space in the maze? Ideally, the path would never be more than one square wide.
Code:
var grid;
function generate(dimensions, numDoors) {
//numDoors is unused right now
grid = new Array();
for (var i = 0; i < dimensions; i++) {
grid[i] = new Array();
for (var j = 0; j < dimensions; j++) {
grid[i][j] = "";
}
}
addOuterWalls();
var ent = addEntrance();
addInnerWalls(true, 1, grid.length - 2, 1, grid.length - 2, ent);
}
function addOuterWalls() {
for (var i = 0; i < grid.length; i++) {
if (i == 0 || i == (grid.length - 1)) {
for (var j = 0; j < grid.length; j++) {
grid[i][j] = "w";
}
} else {
grid[i][0] = "w";
grid[i][grid.length - 1] = "w";
}
}
}
function addEntrance() {
var x = randomNumber(1, grid.length - 1);
grid[grid.length - 1][x] = "g";
return x;
}
function addInnerWalls(h, minX, maxX, minY, maxY, gate) {
if (h) {
if (maxX - minX < 2) {
return;
}
var y = randomNumber(minY, maxY);
addHWall(minX, maxX, y);
addInnerWalls(!h, minX, maxX, minY, y-1, gate);
addInnerWalls(!h, minX, maxX, y + 1, maxY, gate);
} else {
if (maxY - minY < 2) {
return;
}
var x = randomNumber(minX, maxX);
addVWall(minY, maxY, x);
addInnerWalls(!h, minX, x-1, minY, maxY, gate);
addInnerWalls(!h, x + 1, maxX, minY, maxY, gate);
}
}
function addHWall(minX, maxX, y) {
var hole = randomNumber(minX, maxX);
for (var i = minX; i <= maxX; i++) {
if (i == hole) grid[y][i] = "";
else grid[y][i] = "w";
}
}
function addVWall(minY, maxY, x) {
var hole = randomNumber(minY, maxY);
for (var i = minY; i <= maxY; i++) {
if (i == hole) grid[i][x] = "";
else grid[i][x] = "w";
}
}
function randomNumber(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
}
function display() {
document.getElementById("cnt").innerHTML = "";
for (var i = 0; i < grid.length; i++) {
var output = "<div>";
for (var j = 0; j < grid.length; j++) {
output += "<b " + grid[i][j] + "></b>";
}
output += "</div>";
document.getElementById("cnt").innerHTML += output;
}
}
generate(30, 1, 1);
display();
Put walls only in even cells, and doors in odd cells, and make "dimensions" odd. http://jsfiddle.net/tPm3s/1/
Code:
var grid;
function generate(dimensions, numDoors) {
grid = new Array();
for (var i = 0; i < dimensions; i++) {
grid[i] = new Array();
for (var j = 0; j < dimensions; j++) {
grid[i][j] = "";
}
}
addOuterWalls();
var ent = addEntrance();
addInnerWalls(true, 1, grid.length - 2, 1, grid.length - 2, ent);
}
function addOuterWalls() {
for (var i = 0; i < grid.length; i++) {
if (i == 0 || i == (grid.length - 1)) {
for (var j = 0; j < grid.length; j++) {
grid[i][j] = "w";
}
} else {
grid[i][0] = "w";
grid[i][grid.length - 1] = "w";
}
}
}
function addEntrance() {
var x = randomNumber(1, grid.length - 1);
grid[grid.length - 1][x] = "g";
return x;
}
function addInnerWalls(h, minX, maxX, minY, maxY, gate) {
if (h) {
if (maxX - minX < 2) {
return;
}
var y = Math.floor(randomNumber(minY, maxY)/2)*2;
addHWall(minX, maxX, y);
addInnerWalls(!h, minX, maxX, minY, y-1, gate);
addInnerWalls(!h, minX, maxX, y + 1, maxY, gate);
} else {
if (maxY - minY < 2) {
return;
}
var x = Math.floor(randomNumber(minX, maxX)/2)*2;
addVWall(minY, maxY, x);
addInnerWalls(!h, minX, x-1, minY, maxY, gate);
addInnerWalls(!h, x + 1, maxX, minY, maxY, gate);
}
}
function addHWall(minX, maxX, y) {
var hole = Math.floor(randomNumber(minX, maxX)/2)*2+1;
for (var i = minX; i <= maxX; i++) {
if (i == hole) grid[y][i] = "";
else grid[y][i] = "w";
}
}
function addVWall(minY, maxY, x) {
var hole = Math.floor(randomNumber(minY, maxY)/2)*2+1;
for (var i = minY; i <= maxY; i++) {
if (i == hole) grid[i][x] = "";
else grid[i][x] = "w";
}
}
function randomNumber(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
}
function display() {
document.getElementById("cnt").innerHTML = "";
for (var i = 0; i < grid.length; i++) {
var output = "<div>";
for (var j = 0; j < grid.length; j++) {
output += "<b " + grid[i][j] + "></b>";
}
output += "</div>";
document.getElementById("cnt").innerHTML += output;
}
}
generate(31, 1, 1);
display();
这篇关于迷宫(递归除法)算法设计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
