使用 Prim 算法在迷宫中放置房间

Question

我试图在 ASCII 屏幕上放置房间，然后使用 Prim's algorithm 到 "fill" 房间之间的 space 迷宫，但实际上并没有闯入房间。我已经修修补补了几个小时，但我想不出阻止我的算法闯入我的房间的方法。

谁能帮帮我？我很迷路。我正在练习地图生成技术，这是我的第 5 个。不，我不想用另一种方式来做，我只是想用这种方式来做 - 但是对。

下面是我当前带房间输出的照片，我当前不带房间的输出照片，以及相关源代码（又名 Prim 的算法部分）的 link。如果你真的能帮助我，再次感谢！

注意：所有相反的方法都是找出 "parent" 单元格是哪个单元格，并根据它确定方向。因此，如果父单元格的 x 值为 7，而子单元格的 x 值为 6，则它知道这是新的子单元格。

start = new Point(x,y, null);
map[start.x][start.y] = Tile.STAIRS_DOWN;

for(int nx = -1; nx <= 1; nx++){
    for(int ny = -1; ny <= 1; ny++){
        if((nx == 0 && ny == 0) || (nx != 0 && ny != 0)){
            continue;
        }
        try{
            if(map[start.x + nx][start.y + ny] == Tile.FLOOR){
                continue;
            }
            frontier.add(new Point(start.x+nx, start.y + ny, start));
        }
        catch(Exception e){
            continue;
        }
    }
}

Point last = null;
while(!frontier.isEmpty()){
    Point cu = frontier.remove(RandomGen.rand(0, frontier.size() - 1));
    Point op = cu.opposite();
    try{
        if((map[cu.x][cu.y] == Tile.WALL) && (map[op.x][op.y] == Tile.WALL)){
            for (int bx = -1; bx <= 1; bx++)
                for (int by = -1; by <= 1; by++) {
                    boolean failed = false;
                    if (bx == 0 && by == 0 || bx != 0 && by != 0)
                        continue;
                    try {
                        if(map[op.x + bx][op.y + by] == Tile.FLOOR){
                            break;
                        }
                        last = op;
                        if(!failed){
                        map[cu.x][cu.y] = Tile.FLOOR;
                        map[op.x][op.y] = Tile.FLOOR;
                        frontier.add(new Point(op.x + bx, op.y + by, op));
                        }
                    }
                    catch(Exception e){
                        continue;
                    }
                }
        }
    }
    catch(Exception e){}
}

Without Rooms

With Rooms

Answer 1

已解决：我需要检查我的前向角落是否有开放空间。所以如果我要去 "east" 那么我还需要检查东北和东南方块，否则我可能会钻进房间。

使用 Prim 算法在迷宫中放置房间

Room placement in a maze using Prim's algorithm

java

maze

graph-theory

minimum-spanning-tree

roguelike