dfs bfs - HimxhMC/HimDSL GitHub Wiki

int W = 41;   // 建议为奇数
int H = 31;   // 建议为奇数

char grid[64][64];      // '#' = 墙, '.' = 地板, 'S' = 起点, 'E' = 终点
bool visited[64][64];   // 房间格是否访问过

struct Pos {
    int x;
    int y;
};

Pos stack[64 * 64];
int top = 0;

// BFS 找最远点用的全局货架
int dist[64][64];
Pos bfsq[64 * 64];
int qhead = 0;
int qtail = 0;

void push1(Pos p) {
    stack[top] = p;
    top = top + 1;
}

Pos pop1() {
    top = top - 1;
    return stack[top];
}

bool is_empty() {
    return top == 0;
}

void generate() {
    // 四个方向，每次跨 2 格（房间格都在奇数坐标上）
    int dirs[4][2];
    dirs[0][0] =  2; dirs[0][1] =  0;
    dirs[1][0] = -2; dirs[1][1] =  0;
    dirs[2][0] =  0; dirs[2][1] =  2;
    dirs[3][0] =  0; dirs[3][1] = -2;

    // 初始化
    for (int y = 0; y < H; y = y + 1) {
        for (int x = 0; x < W; x = x + 1) {
            grid[y][x] = '#';
            visited[y][x] = false;
        }
    }

    // 起点
    Pos start;
    start.x = 1;
    start.y = 1;
    grid[1][1] = '.';
    visited[1][1] = true;
    push1(start);

    // 迭代式 DFS
    while (!is_empty()) {
        Pos cur = stack[top - 1];   // 偷看栈顶，不弹出

        // 收集所有未访问的邻居
        Pos cand[4];
        int n = 0;
        for (int i = 0; i < 4; i = i + 1) {
            int nx = cur.x + dirs[i][0];
            int ny = cur.y + dirs[i][1];
            if (nx > 0 && nx < W - 1 && ny > 0 && ny < H - 1 && !visited[ny][nx]) {
                cand[n].x = nx;
                cand[n].y = ny;
                n = n + 1;
            }
        }

        if (n == 0) {
            // 死路，回溯
            pop1();
            continue;
        }

        // 随机挑一个邻居前进
        int pick = rand(0, n - 1);
        Pos nxt = cand[pick];

        // 打通中间的墙
        int mx = (cur.x + nxt.x) / 2;
        int my = (cur.y + nxt.y) / 2;
        grid[my][mx] = '.';
        grid[nxt.y][nxt.x] = '.';
        visited[nxt.y][nxt.x] = true;

        push1(nxt);
    }
}

void mark_exit() {
    // 初始化距离
    for (int y = 0; y < H; y = y + 1) {
        for (int x = 0; x < W; x = x + 1) {
            dist[y][x] = -1;
        }
    }

    qhead = 0;
    qtail = 0;

    Pos start;
    start.x = 1;
    start.y = 1;
    bfsq[qtail] = start;
    qtail = qtail + 1;
    dist[1][1] = 0;

    int bestX = 1;
    int bestY = 1;
    int bestD = 0;

    int bdirs[4][2];
    bdirs[0][0] =  1; bdirs[0][1] =  0;
    bdirs[1][0] = -1; bdirs[1][1] =  0;
    bdirs[2][0] =  0; bdirs[2][1] =  1;
    bdirs[3][0] =  0; bdirs[3][1] = -1;

    while (qhead < qtail) {
        Pos cur = bfsq[qhead];
        qhead = qhead + 1;
        int d = dist[cur.y][cur.x];

        if (d > bestD) {
            bestD = d;
            bestX = cur.x;
            bestY = cur.y;
        }

        for (int i = 0; i < 4; i = i + 1) {
            int nx = cur.x + bdirs[i][0];
            int ny = cur.y + bdirs[i][1];

            if (nx >= 0 && nx < W && ny >= 0 && ny < H) {
                if (grid[ny][nx] == '.' && dist[ny][nx] == -1) {
                    dist[ny][nx] = d + 1;
                    Pos nxt;
                    nxt.x = nx;
                    nxt.y = ny;
                    bfsq[qtail] = nxt;
                    qtail = qtail + 1;
                }
            }
        }
    }

    // 起点和终点插旗
    grid[1][1] = 'S';
    grid[bestY][bestX] = 'E';
}

void print() {
    for (int y = 0; y < H; y = y + 1) {
        string line = "";
        for (int x = 0; x < W; x = x + 1) {
            line = line + grid[y][x];
        }
        Bukkit.getServer().getLogger().info(line);
    }
}

int main() {
    generate();
    mark_exit();
    print();
    return 0;
}