[C言語] 迷路生成アルゴリズムまとめ(壁のランダム削除/棒倒し法/穴掘り法/Growing Tree Algorithm/Prim/Kruskal)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 10
#define HEIGHT 10
void initializeMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x] = '#'; // 壁で初期化
        }
    }
}
void printMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            printf("%c", maze[y][x]);
        }
        printf("\n");
    }
}
void randomRemoveWalls(char maze[HEIGHT][WIDTH]) {
    for (int i = 0; i < (WIDTH * HEIGHT) / 4; i++) { // 壁を削除する回数
        int x = rand() % WIDTH;
        int y = rand() % HEIGHT;
        maze[y][x] = ' '; // 壁を削除して通路を作成
    }
}
int main() {
    srand(time(NULL)); // 乱数の初期化
    char maze[HEIGHT][WIDTH];
    
    initializeMaze(maze); // 迷路の初期化
    randomRemoveWalls(maze); // 壁のランダム削除
    printMaze(maze); // 迷路の表示
    
    return 0;
}

 #########
 ######## 
#### # #  
######## #
# ########
## ###  ##
# #####  #
 ## ##### 
##  ######

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 10
#define HEIGHT 10
void initializeMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x] = '#'; // 壁で初期化
        }
    }
}
void printMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            printf("%c", maze[y][x]);
        }
        printf("\n");
    }
}
void knockDown(char maze[HEIGHT][WIDTH], int x, int y) {
    // 通路を作成
    maze[y][x] = ' ';
    
    // 隣接セルの配列
    int directions[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    
    // 隣接セルに棒を倒す
    for (int i = 0; i < 4; i++) {
        int dir = rand() % 4; // ランダムな方向を選択
        int nx = x + directions[dir][0] * 2; // 2セル先のX座標
        int ny = y + directions[dir][1] * 2; // 2セル先のY座標
        
        // 範囲内かつ壁の場合
        if (nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT && maze[ny][nx] == '#') {
            maze[y + directions[dir][1]][x + directions[dir][0]] = ' '; // 壁を削除
            knockDown(maze, nx, ny); // 再帰的に棒を倒す
        }
    }
}
int main() {
    srand(time(NULL)); // 乱数の初期化
    char maze[HEIGHT][WIDTH];
    
    initializeMaze(maze); // 迷路の初期化
    knockDown(maze, 1, 1); // スタート地点から棒を倒す
    printMaze(maze); // 迷路の表示
    
    return 0;
}

##########
#     #   
##### # # 
#     # # 
# ##### ##
#     # # 
# ### # # 
# ###   # 
##### # # 
##### #   

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 10
#define HEIGHT 10
void initializeMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x] = '#'; // 壁で初期化
        }
    }
}
void printMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            printf("%c", maze[y][x]);
        }
        printf("\n");
    }
}
void digTunnel(char maze[HEIGHT][WIDTH], int x, int y) {
    // 通路を作成
    maze[y][x] = ' ';
    
    // 隣接セルの配列
    int directions[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    
    // 隣接セルに向かって掘り進める
    for (int i = 0; i < 4; i++) {
        int dir = rand() % 4; // ランダムな方向を選択
        int nx = x + directions[dir][0]; // 隣接セルのX座標
        int ny = y + directions[dir][1]; // 隣接セルのY座標
        
        // 範囲内かつ壁の場合
        if (nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT && maze[ny][nx] == '#') {
            maze[nx][ny] = ' '; // 壁を削除して通路を作成
            digTunnel(maze, nx, ny); // 再帰的に掘り進める
        }
    }
}
int main() {
    srand(time(NULL)); // 乱数の初期化
    char maze[HEIGHT][WIDTH];
    
    initializeMaze(maze); // 迷路の初期化
    digTunnel(maze, 1, 1); // スタート地点から通路を掘る
    printMaze(maze); // 迷路の表示
    
    return 0;
}

##########
# #       
# # ##### 
# #   #   
# # # ### 
# # #   # 
# ##### # 
# #     # 
# # ##### 
#   #    

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 10
#define HEIGHT 10
void initializeMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x] = '#'; // 壁で初期化
        }
    }
}
void printMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            printf("%c", maze[y][x]);
        }
        printf("\n");
    }
}
void growTree(char maze[HEIGHT][WIDTH], int x, int y) {
    maze[y][x] = ' '; // 通路を作成
    
    // 隣接セルの配列
    int directions[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    
    // 隣接する壁のリストを作成
    for (int i = 0; i < 4; i++) {
        int dir = rand() % 4; // ランダムな方向を選択
        int nx = x + directions[dir][0] * 2; // 2セル先のX座標
        int ny = y + directions[dir][1] * 2; // 2セル先のY座標
        
        // 範囲内かつ壁の場合
        if (nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT && maze[ny][nx] == '#') {
            maze[y + directions[dir][1]][x + directions[dir][0]] = ' '; // 壁を削除
            growTree(maze, nx, ny); // 再帰的に成長
        }
    }
}
int main() {
    srand(time(NULL)); // 乱数の初期化
    char maze[HEIGHT][WIDTH];
    
    initializeMaze(maze); // 迷路の初期化
    growTree(maze, 1, 1); // スタート地点から成長を開始
    printMaze(maze); // 迷路の表示
    
    return 0;
}

##########
#   # #   
### # # # 
# #     # 
# # ##### 
#   # ### 
# ### ####
# #       
# # ### # 
#   ### # 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define WIDTH 10
#define HEIGHT 10

void initializeMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x] = '#'; // 壁で初期化
        }
    }
}

void printMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            printf("%c", maze[y][x]);
        }
        printf("\n");
    }
}

void addWall(int x, int y, int walls[][2], int *wallCount) {
    walls[*wallCount][0] = x; // 壁のX座標を保存
    walls[*wallCount][1] = y; // 壁のY座標を保存
    (*wallCount)++;           // 壁のカウントを増やす
}

int isValidWall(char maze[HEIGHT][WIDTH], int x, int y) {
    if (x <= 0 || x >= WIDTH - 1 || y <= 0 || y >= HEIGHT - 1) {
        return 0;
    }
    if (maze[y][x] == '#') {
        int count = 0;
        if (maze[y + 1][x] == ' ') count++;
        if (maze[y - 1][x] == ' ') count++;
        if (maze[y][x + 1] == ' ') count++;
        if (maze[y][x - 1] == ' ') count++;
        return count == 1;
    }
    return 0;
}

void primMaze(char maze[HEIGHT][WIDTH], int startX, int startY) {
    maze[startY][startX] = ' '; // スタート地点を通路としてマーク
    int walls[WIDTH * HEIGHT][2]; // 壁のリスト
    int wallCount = 0;            // 壁のカウント

    // 隣接する壁をリストに追加
    if (isValidWall(maze, startX + 1, startY)) addWall(startX + 1, startY, walls, &wallCount);
    if (isValidWall(maze, startX - 1, startY)) addWall(startX - 1, startY, walls, &wallCount);
    if (isValidWall(maze, startX, startY + 1)) addWall(startX, startY + 1, walls, &wallCount);
    if (isValidWall(maze, startX, startY - 1)) addWall(startX, startY - 1, walls, &wallCount);

    while (wallCount > 0) {
        int randIndex = rand() % wallCount; // ランダムに壁を選択
        int x = walls[randIndex][0];
        int y = walls[randIndex][1];

        if (isValidWall(maze, x, y)) {
            maze[y][x] = ' '; // 通路を作成

            // 隣接する壁をリストに追加
            if (isValidWall(maze, x + 1, y)) addWall(x + 1, y, walls, &wallCount);
            if (isValidWall(maze, x - 1, y)) addWall(x - 1, y, walls, &wallCount);
            if (isValidWall(maze, x, y + 1)) addWall(x, y + 1, walls, &wallCount);
            if (isValidWall(maze, x, y - 1)) addWall(x, y - 1, walls, &wallCount);
        }

        // 選択した壁をリストから削除
        walls[randIndex][0] = walls[wallCount - 1][0];
        walls[randIndex][1] = walls[wallCount - 1][1];
        wallCount--; // 壁のカウントを減らす
    }
}

int main() {
    srand(time(NULL)); // 乱数の初期化
    char maze[HEIGHT][WIDTH];

    initializeMaze(maze); // 迷路の初期化
    primMaze(maze, 1, 1); // Prim法による迷路生成
    printMaze(maze);      // 迷路の表示

    return 0;
}

##########
#        #
## # # # #
#  ## #  #
##    ## #
#  # # # #
# #    # #
## # #  ##
#     #  #
##########

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define WIDTH 10
#define HEIGHT 10

typedef struct {
    int x1, y1; // 1つ目のセルの座標
    int x2, y2; // 2つ目のセルの座標
} Edge;

void initializeMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x] = '#'; // 壁で初期化
        }
    }
}

void printMaze(char maze[HEIGHT][WIDTH]) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            printf("%c", maze[y][x]);
        }
        printf("\n");
    }
}

int find(int parent[], int i) {
    if (parent[i] == -1) {
        return i;
    }
    return find(parent, parent[i]);
}

void unionSets(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

void shuffleEdges(Edge edges[], int edgeCount) {
    for (int i = edgeCount - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        Edge temp = edges[i];
        edges[i] = edges[j];
        edges[j] = temp;
    }
}

void kruskalMaze(char maze[HEIGHT][WIDTH]) {
    Edge edges[2 * WIDTH * HEIGHT]; // 辺のリスト
    int edgeCount = 0;
    int parent[WIDTH * HEIGHT]; // 親の配列

    // 初期化
    for (int i = 0; i < WIDTH * HEIGHT; i++) {
        parent[i] = -1; // 親を初期化
    }

    // 辺のリスト作成
    for (int y = 1; y < HEIGHT; y += 2) {
        for (int x = 1; x < WIDTH; x += 2) {
            if (x < WIDTH - 2) { // 右の壁
                edges[edgeCount++] = (Edge){x, y, x + 2, y};
            }
            if (y < HEIGHT - 2) { // 下の壁
                edges[edgeCount++] = (Edge){x, y, x, y + 2};
            }
        }
    }

    // 辺をシャッフル
    shuffleEdges(edges, edgeCount);

    // 辺の選択
    for (int i = 0; i < edgeCount; i++) {
        Edge edge = edges[i];
        int cell1 = edge.y1 * WIDTH + edge.x1; // 1つ目のセルのインデックス
        int cell2 = edge.y2 * WIDTH + edge.x2; // 2つ目のセルのインデックス

        if (find(parent, cell1) != find(parent, cell2)) {
            // 2つのセルの間の壁を壊す
            maze[edge.y1][edge.x1] = ' '; // 1つ目のセル
            maze[edge.y2][edge.x2] = ' '; // 2つ目のセル
            maze[(edge.y1 + edge.y2) / 2][(edge.x1 + edge.x2) / 2] = ' '; // 間の壁

            unionSets(parent, cell1, cell2); // セットを統合
        }
    }
}

int main() {
    srand(time(NULL)); // 乱数の初期化
    char maze[HEIGHT][WIDTH];

    initializeMaze(maze); // 迷路の初期化
    kruskalMaze(maze); // Kruskal法による迷路生成

    // 出入口を作成
    maze[1][0] = ' '; // スタート地点
    maze[HEIGHT - 2][WIDTH - 1] = ' '; // ゴール地点

    printMaze(maze); // 迷路の表示

    return 0;
}

##########
      #   
### # # # 
#   #   # 
# ### # # 
# #   # # 
##### ####
#
# # ### # 
# #   # #