2

我目前正在开发一个迷宫生成程序，使用深度优先搜索。我有以下代码，但我无法弄清楚我做错了什么。我试图让 X 介于两者之间来说明哪些是墙。但它会覆盖它们，并将路径彼此相邻。任何帮助都会很棒。下面是输出。

. . . # # # # # # # 
. . . . # . . . . . 
. . . . # . # # # . 
. . # . # . . . # . 
. . # # # # # . # # 
. . . . # . . . # # 
. # # . # . # # # # 
. # # . . . # # # # 
. . . . . # # # # # 
# # # # # # # # # # 

import java.util.Random;

public class DepthFirstSearch {

    private Stack stack;
    public DepthFirstSearch() {}
    public char[][] DFS (int size, char[][] maze) {

        Random myRand = new Random();
        stack = new Stack(size);
        int x = myRand.nextInt(size);
        while (x % 2 == 0)
            x = myRand.nextInt(size);
        int y = myRand.nextInt(size);
        while (y % 2 == 0)
            y = myRand.nextInt(size);

        maze[x][y] = ' ';
        int total = (size * size) / 4;
        int visited = 1;
        int random[] = new int[4];
        int totalrand;

        while (visited < total) {
            totalrand = 0;
            if (x > 1 && maze[x - 2][y] == 'X')
                random[totalrand++] = 1;
            if (x < size - 2 && maze[x + 2][y] == 'X')
                random[totalrand++] = 2;
            if (y > 1 && maze[x][y - 2] == 'X')
                random[totalrand++] = 3;
            if (y < size - 2 && maze[x][y + 2] == 'X')
                random[totalrand++] = 4;

            if (totalrand > 0) {
                switch(random[myRand.nextInt(totalrand)]) {
                    case 1: maze[x-2][y] = maze[x-1][y] = ' ';
                            x -= 2;
                            stack.push(x * size + y);
                            visited++;
                            break;
                    case 2: maze[x+2][y] = maze[x+1][y] = ' ';
                            x += 2;
                            stack.push(x * size + y);
                            visited++;
                            break;
                    case 3: maze[x][y-2] = maze[x][y-1] = ' ';
                            y -= 2;
                            stack.push(x * size + y);
                            visited++;
                            break;
                    case 4: maze[x][y+2] = maze[x][y+1] = ' ';
                            y += 2;
                            stack.push(x * size + y);
                            visited++;
                            break;
                }
            }
            else {
                int vert = stack.pop();
                x = vert / size;
                y = vert % size;
            }
        }
        return maze;
    }

}
4

1 回答 1

1

事实证明，这非常有效。我试图提高我的堆栈效率，但把它搞砸了。因此，使用工作堆栈，它可以完美运行。

于 2012-11-02T16:08:16.340 回答