【C#】穴掘り法で迷路を生成する

迷路の幅と高さをそれぞれ width, height として設定し、
その数値にしたがって穴掘り法で迷路を生成する。
※迷路の幅と高さは5以上の奇数とする。

using System;
using System.Collections.Generic;
using System.Linq;

public class Maze {
    public const int PATH = 0;
    public const int WALL = 1;
    public int width;
    public int height;
    public int[,] maze;
    public int[] start;
    private Random random;
    
    public Maze(int width, int height, int seed = 0) {
        this.width = width;
        this.height = height;
        if (this.width < 5 || this.height < 5) {
            Environment.Exit(0);
        }
        if (this.width % 2 == 0) {
            this.width++;
        }
        if (this.height % 2 == 0) {
            this.height++;
        }
        this.maze = new int[this.height,this.width];
        for (int y = 0; y < this.height; ++y) {
            for (int x = 0; x < this.width; ++x) {
                this.maze[y,x] = Maze.PATH;
            }
        }
        this.start = new int[] {1, 1};
        this.random = new Random(seed);
    }

    public int[,] set_all_wall() {
        for (int y = 0; y < this.height; ++y) {
            for (int x = 0; x < this.width; ++x) {
                this.maze[y,x] = Maze.WALL;
            }
        }
        return this.maze;
    }

    public int[,] set_outer_path() {
        for (int y = 0; y < this.height; ++y) {
            for (int x = 0; x < this.width; ++x) {
                if (x == 0 || y == 0 || x == this.width-1 || y == this.height-1) {
                    this.maze[y,x] = Maze.PATH;
                }
            }
        }
        return this.maze;
    }

    public int[,] set_outer_wall() {
        for (int y = 0; y < this.height; ++y) {
            for (int x = 0; x < this.width; ++x) {
                if (x == 0 || y == 0 || x == this.width-1 || y == this.height-1) {
                    this.maze[y,x] = Maze.WALL;
                }
            }
        }
        return this.maze;
    }

    public int[,] set_maze_anahori() {
        this.set_all_wall();
        this.set_outer_path();
        int[] point;
        Stack<int[]> stack = new Stack<int[]>();
        point = this.start;
        stack.Push(point);
        this.maze[point[1],point[0]] = Maze.PATH;
        while (true) {
            if (stack.Count == 0) {
                break;
            }
            stack = new Stack<int[]>(stack.OrderBy(i => random.Next(stack.Count)).ToArray());
            point = stack.Pop();
            while (true) {
                List<int> directions = new List<int>();
                if (this.maze[point[1]-1,point[0]] == Maze.WALL && this.maze[point[1]-2,point[0]] == Maze.WALL) {
                    directions.Add(0);
                }
                if (this.maze[point[1],point[0]+1] == Maze.WALL && this.maze[point[1],point[0]+2] == Maze.WALL) {
                    directions.Add(1);
                }
                if (this.maze[point[1]+1,point[0]] == Maze.WALL && this.maze[point[1]+2,point[0]] == Maze.WALL) {
                    directions.Add(2);
                }
                if (this.maze[point[1],point[0]-1] == Maze.WALL && this.maze[point[1],point[0]-2] == Maze.WALL) {
                    directions.Add(3);
                }
                if (directions.Count == 0) {
                    break;
                }
                int direction = directions[random.Next(directions.Count)];
                switch (direction) {
                    case 0:
                        this.maze[point[1]-1,point[0]] = Maze.PATH;
                        this.maze[point[1]-2,point[0]] = Maze.PATH;
                        stack.Push(new int[] {point[0],point[1]});
                        point = new int[] {point[0],point[1]-2};
                        break;
                    case 1:
                        this.maze[point[1],point[0]+1] = Maze.PATH;
                        this.maze[point[1],point[0]+2] = Maze.PATH;
                        stack.Push(new int[] {point[0],point[1]});
                        point = new int[] {point[0]+2,point[1]};
                        break;
                    case 2:
                        this.maze[point[1]+1,point[0]] = Maze.PATH;
                        this.maze[point[1]+2,point[0]] = Maze.PATH;
                        stack.Push(new int[] {point[0],point[1]});
                        point = new int[] {point[0],point[1]+2};
                        break;
                    case 3:
                        this.maze[point[1],point[0]-1] = Maze.PATH;
                        this.maze[point[1],point[0]-2] = Maze.PATH;
                        stack.Push(new int[] {point[0],point[1]});
                        point = new int[] {point[0]-2,point[1]};
                        break;
                }
            }
        }
        this.set_outer_wall();
        return this.maze;
    }

    public void print_maze() {
        for (int y = 0; y < this.maze.GetLength(0); ++y) {
            for (int x = 0; x < this.maze.GetLength(1); ++x) {
                if (this.maze[y,x] == Maze.WALL) {
                    Console.Write('#');
                } else if (this.maze[y,x] == Maze.PATH) {
                    Console.Write(' ');
                }
            }
            Console.WriteLine();
        }
    }

    public static void Main() {
        Maze maze1 = new Maze(15, 15);
        maze1.set_maze_anahori();
        maze1.print_maze();
    }
}

 今回は、以下のように出力される。

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

参考

迷路生成(穴掘り法) - Algoful
穴掘り法は迷路生成アルゴリズムの一種です。全面壁の状態から穴を掘り進めながら迷路を作ります。シミュレーション機能で生成される過程を確認できます。複雑な迷路が生成できるためおすすめです。C#の実装サンプルを用意しているのでUnityでのゲーム...
[Python] 穴掘り法による迷路生成
迷路生成のアルゴリズム 迷路生成のアルゴリズムは数多くあります。 Maze Classification -M…
自動生成迷路
タイトルとURLをコピーしました