C#で迷路をつくります。
考え方は
等間隔に点をつくる。
出発点から別の点に移動する。すでに通過した点には移動できないとする。
移動できる点がない場合は一つ前に戻って移動できる点があるか探す。
移動できる点が見つからない場合は見つかるまで遡って探す。
すべての点を通過したら終了。
ではさっそくこのようなクラスを作成してみましょう。
以下は移動できる方向を示す列挙体です。
|
1 2 3 4 5 6 7 |
public enum MoveDirect { Left, Up, Right, Down, } |
分岐点を管理するBranchPointクラスの作成
分岐点を管理するBranchPointクラスを作成します。
コンストラクタではその分岐点は左から何列目か（0からはじまる）、上から何行目か（0からはじまる）、分岐点と分岐点の間隔、描画するときに左と上にどれだけマージンをとるかを指定します。
Usedプロパティはその分岐点は使用されているかどうかを示します。すべてが使用されているのであれば迷路は完成していることになります。Pointプロパティは分岐点が存在する座標、MoveDirectsプロパティはその分岐点から移動できる方向を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
public class BranchPoint { public BranchPoint(int colum, int row, int spacing, int leftMargin, int topMargin) { Colum = colum; Row = row; Spacing = spacing; Used = false; _point = new Point(leftMargin + colum * spacing, topMargin + row * spacing); } public int Colum { get; } public int Row { get; } public int Spacing { get; } public bool Used { set; get; } Point _point; public Point Point { get { return _point; } } List<MoveDirect> _moveDirects = new List<MoveDirect>(); public List<MoveDirect> MoveDirects { get { return _moveDirects; } } } |
分岐点と分岐点をつなぐ線分を描画するためのLineクラス
次に分岐点と分岐点をつなぐ線分を描画するために必要な座標を管理するLineクラスを示します。
コンストラクタはふたつの点の座標です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Line { public Line(Point start, Point end) { Start = start; End = end; } public Point Start { get; } public Point End { get; } } |
迷路を生成するMaseGeneratorクラス
次に迷路を生成するMaseGeneratorクラスを示します。
コンストラクタは分岐点が全部で何列存在するか、何行存在するか、それぞれの間隔、左側のマージン、上側のマージンを指定します。
最初にcolumMax列でrowMax行の分岐点を生成します。そして最初の現在位置を中心にある分岐点にします。現在位置はすでに使用されているのでBranchPoint.Usedプロパティをtrueにします。そしてConnectedPointsのなかに格納します。これは中心から繋がっている分岐点のリストです。最後にCreateMazeメソッドを呼び出して迷路をつくっていきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class MaseGenerator { Random Random = new Random(); List<BranchPoint> _branchPoints = new List<BranchPoint>(); BranchPoint CurPoint = null; List<BranchPoint> ConnectedPoints = new List<BranchPoint>(); public List<Line> _lines = new List<Line>(); int _numberOfRecursion = 0; public MaseGenerator(int columMax, int rowMax, int spacing, int leftMargin, int topMargin) { RowMax = rowMax; ColumMax = columMax; // 分岐点をつくる for (int y = 0; y < RowMax; y++) { for (int x = 0; x < ColumMax; x++) _branchPoints.Add(new BranchPoint(x, y, spacing, leftMargin, topMargin)); } // 最初は中心から CurPoint = _branchPoints.FirstOrDefault(x => x.Colum == ColumMax / 2 && x.Row == RowMax / 2); CurPoint.Used = true; ConnectedPoints.Add(CurPoint); // 迷路をつくる CreateMaze(); } } |
ColumMaxプロパティとRowMaxプロパティは迷路を構成する分岐点が何列、何行存在するかを示します。BranchPointsプロパティはすべての分岐点のリスト、Linesは分岐点の座標のペアを示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public class MaseGenerator { public int ColumMax { get; } public int RowMax { get; } public List<BranchPoint> BranchPoints { get { return _branchPoints.ToList(); } } public List<Line> Lines { get { return _lines.ToList(); } } } |
CreateMazeメソッドは迷路をつくります。まずConnectedPointsの最後にある要素を調べて移動できる方向がいくつあるか調べます。これが0の場合は移動できないということなので、ConnectedPointsの最後にある要素は取り除いて過去に通過した分岐点に遡って移動できる分岐点が存在するところまで戻ります。
現在位置が移動できる方向が存在する分岐点である場合は移動する方向を乱数で求めてその方向に移動します。
NumberOfRecursionプロパティはCreateMazeメソッドを再帰呼び出しした回数です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
public class MaseGenerator { public int NumberOfRecursion { get{ return _numberOfRecursion; } } void CreateMaze() { _numberOfRecursion++; while (true) { // ConnectedPointsの最後の要素を取得する BranchPoint point = ConnectedPoints.Last(); // ConnectedPointsの最後の要素が移動できる点が存在する点である場合は // そこを新しい現在位置にしてループをぬける if (GetMoveDirect(point).Count > 0) { CurPoint = point; break; } // 現在位置から移動できる点が見つからない場合は現在位置をConnectedPointsから取り除く // もし出発点まで戻ってしまった場合は終了 ConnectedPoints.Remove(point); if (ConnectedPoints.Count == 0) return; } while (true) { // 現在位置から移動できる分岐点を探して移動する // これを移動先が見つからなくなるまで繰り返す bool ret = MovePoint(); // 移動先が見つからない場合 // すでにすべての分岐点が使用されているのであれば終了 if (!_branchPoints.Any(x => !x.Used)) return; // 移動先が見つからない場合は自身を再帰呼び出しする if (!ret) CreateMaze(); } } } |
MovePointメソッドは現在位置から移動できる点があるかどうか探し、存在する場合は移動してtrueを返します。存在しない場合はfalseを返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public class MaseGenerator { bool MovePoint() { List<MoveDirect> moveDirects = GetMoveDirect(CurPoint); if (moveDirects.Count == 0) return false; int r = Random.Next(moveDirects.Count); MoveDirect direct = moveDirects[r]; if (direct == MoveDirect.Left) MoveLeft(); if (direct == MoveDirect.Up) MoveUp(); if (direct == MoveDirect.Right) MoveRight(); if (direct == MoveDirect.Down) MoveDown(); return true; } } |
GetMoveDirectメソッドは引数として渡された分岐点から移動できる方向のリストを返します。このリストが空ならここから移動できる点は存在しないということになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class MaseGenerator { List<MoveDirect> GetMoveDirect(BranchPoint curPoint) { List<MoveDirect> ret = new List<MoveDirect>(); if (CanMoveLeft(curPoint)) ret.Add(MoveDirect.Left); if (CanMoveUp(curPoint)) ret.Add(MoveDirect.Up); if (CanMoveRight(curPoint)) ret.Add(MoveDirect.Right); if (CanMoveDown(curPoint)) ret.Add(MoveDirect.Down); return ret; } } |
CanMoveLeftメソッドは引数として渡された分岐点から左に移動できるかどうかを返します。引数として渡された分岐点のColumプロパティが0であればここが左端なので移動できないということになります。_branchPointsからColumプロパティが1小さい分岐点を探して、そこが使用されていないのであれば移動可能であるといえます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class MaseGenerator { bool CanMoveLeft(BranchPoint curPoint) { if (curPoint.Colum == 0) return false; BranchPoint point = _branchPoints.FirstOrDefault(x => x.Colum == curPoint.Colum - 1 && x.Row == curPoint.Row); if (!point.Used) return true; else return false; } } |
MoveLeftメソッドは実際に現在位置を左に移動します。まずここから左に移動可能であるという情報を現在位置の分岐点に追加します。また移動先の分岐点にもここから右、すなわち移動元に移動できるという情報を追加します。
そして現在位置のUsedプロパティをtrueにします。そして現在位置をConnectedPointsに格納します。最後に分岐点同士を線分でつなぐことができるように両分岐点の座標のペアを_linesに格納します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public class MaseGenerator { void MoveLeft() { Point oldPoint = CurPoint.Point; CurPoint.MoveDirects.Add(MoveDirect.Left); CurPoint = _branchPoints.FirstOrDefault(x => x.Colum == CurPoint.Colum - 1 && x.Row == CurPoint.Row); CurPoint.MoveDirects.Add(MoveDirect.Right); Point newPoint = CurPoint.Point; CurPoint.Used = true; ConnectedPoints.Add(CurPoint); _lines.Add(new Line(oldPoint, newPoint)); } } |
上に移動できるかを調べる処理と実際に上に移動する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class MaseGenerator { bool CanMoveUp(BranchPoint curPoint) { if (curPoint.Row == 0) return false; BranchPoint point = _branchPoints.FirstOrDefault(x => x.Colum == curPoint.Colum && x.Row == curPoint.Row - 1); if (!point.Used) return true; else return false; } void MoveUp() { Point oldPoint = CurPoint.Point; CurPoint.MoveDirects.Add(MoveDirect.Up); CurPoint = _branchPoints.FirstOrDefault(x => x.Colum == CurPoint.Colum && x.Row == CurPoint.Row - 1); CurPoint.MoveDirects.Add(MoveDirect.Down); Point newPoint = CurPoint.Point; CurPoint.Used = true; ConnectedPoints.Add(CurPoint); _lines.Add(new Line(oldPoint, newPoint)); } } |
右に移動できるかを調べる処理と実際に右に移動する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class MaseGenerator { bool CanMoveRight(BranchPoint curPoint) { if (curPoint.Colum + 1 >= ColumMax) return false; BranchPoint point = _branchPoints.FirstOrDefault(x => x.Colum == curPoint.Colum + 1 && x.Row == curPoint.Row); if (!point.Used) return true; else return false; } void MoveRight() { Point oldPoint = CurPoint.Point; CurPoint.MoveDirects.Add(MoveDirect.Right); CurPoint = _branchPoints.FirstOrDefault(x => x.Colum == CurPoint.Colum + 1 && x.Row == CurPoint.Row); CurPoint.MoveDirects.Add(MoveDirect.Left); Point newPoint = CurPoint.Point; CurPoint.Used = true; ConnectedPoints.Add(CurPoint); _lines.Add(new Line(oldPoint, newPoint)); } } |
下に移動できるかを調べる処理と実際に下に移動する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class MaseGenerator { bool CanMoveDown(BranchPoint curPoint) { if (curPoint.Row + 1 >= RowMax) return false; BranchPoint point = _branchPoints.FirstOrDefault(x => x.Colum == curPoint.Colum && x.Row == curPoint.Row + 1); if (!point.Used) return true; else return false; } void MoveDown() { Point oldPoint = CurPoint.Point; CurPoint.MoveDirects.Add(MoveDirect.Down); CurPoint = _branchPoints.FirstOrDefault(x => x.Colum == CurPoint.Colum && x.Row == CurPoint.Row + 1); CurPoint.MoveDirects.Add(MoveDirect.Up); Point newPoint = CurPoint.Point; CurPoint.Used = true; ConnectedPoints.Add(CurPoint); _lines.Add(new Line(oldPoint, newPoint)); } } |
仕上げ
Form1クラスはどのようにすればいいのでしょうか？
MaseGenerateメソッドでMaseGeneratorのインスタンスを生成します。何度でも生成できるようにメニューも追加します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
public partial class Form1 : Form { int RowMax = 28; int ColumMax = 32; int LeftMargin = 30; int TopMargin = 35; int Spacing = 15; MaseGenerator MaseGenerator = null; public Form1() { InitializeComponent(); this.DoubleBuffered = true; this.BackColor = Color.Black; // 次回との関係で背景を黒にする CreateMenu(); MaseGenerate(); } void MaseGenerate() { MaseGenerator = new MaseGenerator(ColumMax, RowMax, Spacing, LeftMargin, TopMargin); } void CreateMenu() { ToolStripMenuItem menuItemGenerate = new ToolStripMenuItem("生成"); menuItemGenerate.Click += MenuItemGenerate_Click; MenuStrip menuStrip = new MenuStrip(); this.Controls.Add(menuStrip); menuStrip.Items.Add(menuItemGenerate); } private void MenuItemGenerate_Click(object sender, EventArgs e) { MaseGenerate(); Invalidate(); } } |
描画するときは以下のようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public partial class Form1 : Form { protected override void OnPaint(PaintEventArgs e) { DrawMaze(e.Graphics); base.OnPaint(e); } void DrawMaze(Graphics graphics) { int lineWidth = 3; Pen pen = new Pen(Color.White, lineWidth); SolidBrush brush = new SolidBrush(Color.White); foreach (Line line in MaseGenerator.Lines) { // 取得した2点を結ぶ Point start = new Point(line.Start.X - lineWidth / 2, line.Start.Y - lineWidth / 2); Point end = new Point(line.End.X - lineWidth / 2, line.End.Y - lineWidth / 2); // 線を太くすると角が丸く描画されるので正方形を描画する Size size = new Size(lineWidth, lineWidth); graphics.FillRectangle(brush, new Rectangle(start, size)); graphics.FillRectangle(brush, new Rectangle(end, size)); graphics.DrawLine(pen, line.Start, line.End); } pen.Dispose(); brush.Dispose(); } } |
これで迷路を生成して描画することができました。
