迷宫(递归除法)算法设计

Question

我目前正在开发一个随机迷宫生成器,将迷宫存储在一个名为的二维数组中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();

Answer 1

仅在偶数单元格中放置墙壁，在奇数单元格中放置门，并使“尺寸”为奇数。 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();