こんにちは、きうちです。
すっかり暑くなりましたね！いかがお過ごしでしょうか。
無理をせずエアコンを付けたり、屋外では日傘や帽子で対策していきたいですね。
★ ★ ★
今回は迷路を作るプログラムをお届けしようかと思います。
Webで探したり、あるいは生成AIに頼めば一発だとは思うんですが、あえて中学高校時代にやったおぼろげな記憶をたよりに作ってみたいと思います。
★ ★ ★
迷路って、ただ単に壁をランダムに作るだけだと入口から出口の間が壁でふさがれて解けない迷路ができあがってしまいますが…
次のような手順・ルールで作るとそうならなくて済みます（たしか）。
- 地面から幹を生やす
- 幹から枝を伸ばす
- 幹や枝は先端が触れないようにする
私もこの話をプログラミングの本で見かけたときは「？？？」となりましたが、図を見てなんとなく納得した記憶があります。
こんな感じのやつです・・・。(図がへたっぴですみません)
うーん、ホントかな。
まあ、作ってみましょう。
★ ★ ★
言語は例によってC#にします。Windowsフォームアプリとして作成します。
迷路は横64×縦48で作ろうと思います。
それぞれのマス(セル)に、壁があるかないかに従って画面に描画します。
1マスは8×8ピクセルでいきます。
そこで、フォームのサイズは 544×440 にします。64*8, 48*8 のそれぞれにフォームのフチの分を足した値です。
今回はフォームに直接描画しようと思いますので、PictureBoxは無し。
まずは大地を作って、それを画面に表示させてみましょう。
(とりあえず先にご説明した、地面とか幹とか枝とか、そういった表現に沿っていきます。)
迷路のデータを保持するための2次元配列 ─ ここでは「セル」と呼ぶことにします ─ をフィールド変数として宣言・初期化し、ゼロでクリアします。
そのあと、上端と下端、左端と右端に壁を並べていきます。
namespace Maze
{
public partial class Form1 : Form
{
private static readonly Brush[] CELL_COLORS = { Brushes.Black }; // 壁の色
private const int CELL_EMPTY = 0; // セルの値 0:何もない
private const int CELL_GROUND = 1; // セルの値 1:地面
private readonly int[,] cells = new int[64, 48]; // セル情報
public Form1()
{
InitializeComponent();
Make(); // 迷路を作る
Refresh(); // 画面を再描画させる
}
private void Make() // 迷路を作る
{
// セルをクリアする
ClearCells();
// 大地を作る
MakeGround();
}
private void ClearCells() // セルをクリアする
{
for (int x = 0; x < cells.GetLength(0); x++)
{
for (int y = 0; y < cells.GetLength(1); y++)
{
cells[x, y] = CELL_EMPTY;
}
}
}
private void MakeGround() // 大地を作る
{
for (int x = 0; x < cells.GetLength(0); x++)
{
cells[x, 0] = CELL_GROUND; // 上端
cells[x, cells.GetLength(1) - 1] = CELL_GROUND; // 下端
}
for (int y = 0; y < cells.GetLength(1); y++)
{
cells[0, y] = CELL_GROUND; // 左端
cells[cells.GetLength(0) - 1, y] = CELL_GROUND; // 右端
}
}
}
}
画面に描画するために、Form1のPaintイベントメソッドを設定します。
private void Form1_Paint(object sender, PaintEventArgs e) // 画面描画
{
for (int x = 0; x < cells.GetLength(0); x++)
{
for (int y = 0; y < cells.GetLength(1); y++)
{
if (cells[x, y] > 0) // 点(壁)を示す値なら壁描画
{
Brush brs = CELL_COLORS[0];
e.Graphics.FillRectangle(brs, x * 8 + 8, y * 8 + 8, 8, 8);
}
}
}
}
実行してみます。
シンプルな枠みたいなものが描かれました！
★ ★ ★
次は、この「大地」から「幹」を伸ばします。
セルに入れる値の定義を追加します。ついでなので、この後登場する「枝」の分も追加しちゃいます。
あと、乱数が使いたいので Random の変数もフィールド宣言します。
進行方向(4方向)ごとの座標増分も定義します(VXVY)。各要素の第一要素がX方向増分(vx)、第二要素がY方向増分(vy)です。
private const int CELL_STEM = 2; // セルの値 2:幹
private const int CELL_BRANCH = 3; // セルの値 3:枝
private readonly Random random = new(); // 乱数発生用
private static readonly int[,] VXVY = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // 座標増分(右方向、下方向、左方向、上方向)
Makeメソッドに幹を作るメソッドの呼び出しとそのメソッドを追加します。とりえあず幹は300個くらい作ることにします(迷路のサイズによって適切な数は変わります)。
private void Make() // 迷路を作る
{
// セルをクリアする
ClearCells();
// 大地を作る
MakeGround();
// 幹を作る
MakeStem();
}
private void MakeStem() // 幹を作る
{
int direction = -1;
for (int i = 0; i < 300; i++)
{
int sx = 0;
int sy = 0;
if (MakeStemStartPosition(ref sx, ref sy, ref direction))
{
Grow(sx, sy, direction, GetGrowLength(50, 10), 11, CELL_STEM);
}
}
}
幹を作るときにやることは
- 大地の上下左右、どこかの点をランダムに抽出し開始地点とする
- 進行方向に進めるか確認しながら壁を置いていく(＝幹を伸ばしていく)
です。なお、開始地点の上下左右のいずれかに応じ、進行方向(座標増分)が決まります。
まっすぐ伸ばせるだけ伸ばしてしまうと壁の長いつまらない迷路ができてしまうので、適当な長さ進んだら進行方向が変わるようにします。
開始地点を求めるメソッドは以下。
private bool MakeStemStartPosition(ref int sx, ref int sy, ref int direction) // 幹の開始位置と伸ばす方向を決める
{
int ct = 0;
while (ct++ < 100) // 100回試行する(100回やってもいい開始地点が見つからなければあきらめる)
{
direction = random.Next(4);
switch (direction)
{
case 0: // 左端から右方向
sx = 1;
sy = random.Next(1, cells.GetLength(1) - 2);
break;
case 1: // 上端から下方向
sx = random.Next(1, cells.GetLength(1) - 2);
sy = 1;
break;
case 2: // 右端から左方向
sx = cells.GetLength(0) - 2;
sy = random.Next(1, cells.GetLength(1) - 2);
break;
case 3: // 下端から上方向
sx = random.Next(1, cells.GetLength(1) - 2);
sy = cells.GetLength(1) - 2;
break;
}
if (CountNeighbor(sx, sy) <= 3)
{
break;
}
}
return ct < 100;
}
何かもう少しすっきりした書き方ができそうな気もしますが、わかりやすさを重視しました。
なお、CountNeighborというメソッドが登場しますが、これは近傍の壁の数を調べるためのものです。後述します。
続いて、「どのくらい伸ばすか」を決めるメソッド。
private int GetGrowLength(int max, int min) // 幹・枝を伸ばす長さをランダムに決める
{
return random.Next(max - min) + min;
}
単純に最小値と最大値を基に乱数で決定しているだけです。
あとで「枝」にも使いたいので、簡単な内容ですがあえてメソッドに。
続いて、「幹を伸ばす」部分。
private void Grow(int x, int y, int direction, int glowLength, int maxStraightLen, int p) // 幹や枝を伸ばす
{
int vx = VXVY[direction, 0];
int vy = VXVY[direction, 1];
int length = 0;
for (int i = 0; i < glowLength; i++) // ランダムな長さ、幹を伸ばす
{
if (cells[x, y] == 0) cells[x, y] = p;
int x1 = x + vx; // 次に壁を置く座標を計算する
int y1 = y + vy;
if (CountNeighbor(x1, y1) > 1 || length > maxStraightLen) // 他の幹や枝にくっつきそうなら"方向転換"
{
direction = MakeNextDirection(x, y, direction);
if (direction == -1) break; // 方向転換できない場合は幹を伸ばすのをあきらめる
vx = VXVY[direction, 0];
vy = VXVY[direction, 1];
x += vx; // 増分を足しこむ
y += vy;
length = 0;
}
else
{
x = x1; // 現在座標を次の座標に置き替える
y = y1;
}
length++;
}
}
private int CountNeighbor(int x, int y) // 近傍の点(壁)の数を数える
{
int ct = 0;
for (int xx = -1; xx <= 1; xx++) // 増分-1～1
{
for (int yy = -1; yy <= 1; yy++) // 増分 -1～1
{
if (xx == 0 && yy == 0) continue; // 対象点の位置についてはカウント対象としない
int x1 = x + xx; // 近傍の座標を計算する
int y1 = y + yy;
if (x1 < 0 || y1 < 0 || x1 >= cells.GetLength(0) || y1 >= cells.GetLength(1)) ct++; // フィールド外の座標であれば壁とみなす
else if (cells[x1, y1] > 0) ct++; // フィールド内の座標であればフィールドの対応する要素の値が0より大きければ壁とみなす
}
}
return ct;
}
private int MakeNextDirection(int x, int y, int direction) // 次に進む方向を決める
{
int delta = random.Next(2) * 2 - 1; // 向きを変える方向を -1 か 1 か乱数で決める
int nextDirection = GetDirection(direction, delta);
int ct = CountNeighbor(x + VXVY[nextDirection, 0], y + VXVY[nextDirection, 1]);
if (ct > 2) // 行こうとする位置の、周辺にある壁が「今いる位置のもの」と「1つ前の位置のもの」の2つを超える場合はNGなのでもう片方の方向を確認する
{
delta = -delta; // -1 => 1, 1 => -1
nextDirection = GetDirection(direction, delta);
ct = CountNeighbor(x + VXVY[nextDirection, 0], y + VXVY[nextDirection, 1]);
if (ct > 2) // 行こうとする位置の、周辺にある壁が「今いる位置のもの」と「1つ前の位置のもの」の2つを超える場合はNGなので方向転換できないことを呼び元に伝える
{
nextDirection = -1;
}
}
return nextDirection;
}
private int GetDirection(int currentDirection, int delta) // 進む向きを変える
{
int nextDirection = currentDirection + delta;
if (nextDirection < 0) nextDirection = 3;
else if (nextDirection > 3) nextDirection = 0;
return nextDirection;
}
ちょっと長くなってしまいましたが、やっていることは前述のとおり「進行方向に進めるか確認しながら壁を置いていく(＝幹を伸ばしていく)」です。
曲がりたくなったときは、進行方向に対しての右方向か左方向に行こうとするわけですが、＋１または－１で表現(変数delta)しています。
フィールド VXVY では各要素が
0: 右 (1, 0) 1: 下 (0, 1) 2: 左 (-1, 0) 3: 上 (0, -1)
を表現していますが、この順番になっているのはこれをするためです。
ここまでで実行してみます。
迷路っぽくなりましたね！
あ、幹がどこなのかわかるように色分けしましょう。
CELL_COLORSに色を足します。ついでなので「枝」の分も足しちゃいましょう。
private static readonly Brush[] CELL_COLORS = { Brushes.Black, Brushes.Blue, Brushes.Red }; // 壁の色
そして、Paintイベントを次のように変更します。
private void Form1_Paint(object sender, PaintEventArgs e)
{
for (int x = 0; x < cells.GetLength(0); x++)
{
for (int y = 0; y < cells.GetLength(1); y++)
{
if (cells[x, y] > 0) // 点(壁)を示す値なら壁描画
{
Brush brs = CELL_COLORS[cells[x, y] - 1]; // 変更
e.Graphics.FillRectangle(brs, x * 8 + 8, y * 8 + 8, 8, 8);
}
}
}
}
実行すると…
「幹」が青で表示されましたね！
★ ★ ★
というところで、今日はここまでにしたいと思います。
次回は枝も伸ばして、あと伸ばし切れていないところをなんとか埋めて、迷路として完成させたいと思います！
ではまた！