はじめに
迷路を生成するツールを作りました。
迷路が完成するまでの過程を見ることができます。
#が壁で.が道であり、スタートとゴールは設定されていません。
以下を引数で指定することができます。
- 高さ ※5以上の奇数
- 幅 ※5以上の奇数
- 生成アルゴリズム ※以下のいずれかを指定
- laying (棒倒し法)
- digging (穴掘り法)
- extending (壁伸ばし法)
生成アルゴリズム
今回実装した3つのアルゴリズムを解説します。
また、生成された迷路は必ず以下の条件を満たします。
- 迷路の幅と高さは外周を含めて5以上の奇数
- 通路がループしない
- 閉じた領域が存在しない
棒倒し法
比較的シンプルな方法です。
-
外周に壁が配置された二次元配列を用意します。
-
x座標、y座標ともに偶数の座標に壁を配置します。
-
2.で配置した壁の隣接した座標のいずれかに壁を配置します。
y座標が2の壁は上下左右いずれかの方向に、それ以外の壁は下左右いずれかの方向に配置します。
すでに壁が配置されている場所に再び配置することはできません。
穴掘り法
道を掘り進めていくことで迷路を生成する方法です。
- 壁で満たされた2次元配列を用意します。
- x座標、y座標ともに奇数の座標をランダムに選び開始地点とします。
- 上下左右のいずれかから進める方向をランダムに選び2マス先まで進んで道にします。
既に道となっている方向へ進むことはできません。 - 3.を掘り進められなくなるまで進めます。
- 掘り進められなくなったら、今まで進んで来た経路を戻り
新たに掘り進められる方向を探します。 - 全ての奇数座標が道になったら終了です。
壁伸ばし法
穴掘り法と似ていますが、こちらは壁を伸ばしていくことで迷路を生成します。
- 外周に壁が配置された二次元配列を用意します。
- x座標、y座標ともに偶数の座標をランダムに選び開始地点として壁伸ばしを開始します。
- 上下左右のいずれかから進める方向をランダムに選び2マス先まで進んで壁にします。
自身の壁伸ばしで生成した壁には進むことはできません。 - いずれの方向も自身が生成した壁の場合は、今まで進んで来た経路を戻り
新たに壁を伸ばせる方向を探します。 - 3.~4.を自身が生成してない壁にぶつかるまで進めます。
- 自身が生成してない壁にぶつかった場合は一旦そこで壁伸ばしは終了です。
壁ではないx座標、y座標ともに偶数の座標をランダムに選び、新たに壁伸ばしを開始します。 - 全ての偶数座標が壁になったら終了です。
コード
今回実装したコードの一部を載せます。
棒倒し法
迷路は2次元のboolベクタで表します。(true: 壁、 false: 道)
左から右へ順番に偶数座標の壁の周辺に壁を配置していきます。
pub struct LayingStick {
field_len: Vector2,
pos: Vector2,
field: Vec<Vec<bool>>,
}
...
impl Generator for LayingStick {
fn in_process(&self) -> bool {
self.pos.y <= self.field_len.y - 3
}
fn proceed(&mut self) {
for dir in get_random_dirs() {
// y座標が2より大きい場合、上方向に壁を生成できない
if self.pos.y > 2 && dir == UP {
continue;
}
// 道である座標に壁を配置する
let pos = self.pos + dir;
if !self.field[pos.y as usize][pos.x as usize] {
self.field[pos.y as usize][pos.x as usize] = true;
break;
}
}
self.pos = if self.pos.x < self.field_len.x - 3 {
self.pos + RIGHT * 2
} else {
Vector2::new(self.pos.y + 2, 2)
};
}
fn get_field(&self) -> &Vec<Vec<bool>> {
&self.field
}
}
穴掘り法
2次元配列内を移動するWalker構造体を実装します。
この構造体は移動した座標をstackに保存しています。
次の座標に移動するwalk関数はSome((現在の座標、次の座標))を返します。
全ての座標に移動した場合はNoneを返します。
Walker構造体は壁伸ばし法でも使います。
pub struct Walker {
field_len: Vector2,
stack: Vec<(Vector2, Vec<Vector2>)>,
get_dirs: Box<dyn Fn() -> Vec<Vector2>>,
}
impl Walker {
pub fn new(field_len: Vector2, pos: Vector2, get_dirs: Box<dyn Fn() -> Vec<Vector2>>) -> Self {
let stack = vec![(pos, get_dirs())];
Walker {
field_len,
stack,
get_dirs,
}
}
pub fn is_empty(&self) -> bool {
self.stack.is_empty()
}
pub fn walk(&mut self, is_valid: impl Fn(Vector2) -> bool) -> Option<(Vector2, Vector2)> {
while let Some((pos, mut dirs)) = self.stack.pop() {
// 次の進行方向を決める
let next_dir = dirs.iter().position(|d| {
let new_pos = pos + *d * 2;
// 範囲内か
let is_inside = (0 <= new_pos.y && new_pos.y < self.field_len.y)
&& (0 <= new_pos.x && new_pos.x < self.field_len.x);
// まだ通っていない場所か
let is_new_pos = self.stack.iter().all(|(p, _)| new_pos != *p);
is_inside && is_new_pos && is_valid(new_pos)
});
if let Some(idx) = next_dir {
// 現在の座標を保存
let dir = dirs.remove(idx);
self.stack.push((pos, dirs));
// 次の座標を保存する
let new_pos = pos + dir * 2;
self.stack.push((new_pos, (self.get_dirs)()));
return Some((pos, new_pos));
}
}
None
}
pub fn clear(&mut self) {
self.stack.clear();
}
}
以下が穴掘り法の実装です。
walkerは2歩ずつ移動しているので、途中の座標も道にします。
pub struct DiggingHole {
walker: Walker,
field: Vec<Vec<bool>>,
}
...
impl Generator for DiggingHole {
fn in_process(&self) -> bool {
!self.walker.is_empty()
}
fn proceed(&mut self) {
// 範囲内の壁を探す
let result = self
.walker
.walk(|next_pos| self.field[next_pos.y as usize][next_pos.x as usize]);
if let Some((pos, new_pos)) = result {
// 進行方向へ道を進める
let inter_pos = (pos + new_pos) / 2;
self.field[inter_pos.y as usize][inter_pos.x as usize] = false;
self.field[new_pos.y as usize][new_pos.x as usize] = false;
}
}
fn get_field(&self) -> &Vec<Vec<bool>> {
&self.field
}
}
壁伸ばし法
予め全ての偶数座標をwallsに格納しておき、wallsが空になるまで壁伸ばしを続けます。
新しく壁伸ばしを始める際は、Walker構造体のインスタンスを再度生成します。
impl Generator for ExtendingWall {
fn in_process(&self) -> bool {
!self.walker.is_empty() || !self.walls.is_empty()
}
fn proceed(&mut self) {
// 新しい座標から壁伸ばしを開始
if self.walker.is_empty() {
while let Some(pos) = self.walls.pop() {
// すでに壁ならスキップ
if self.field[pos.y as usize][pos.x as usize] {
continue;
}
self.field[pos.y as usize][pos.x as usize] = true;
// 新しい座標を設定
let field_len = Vector2::new(self.field.len() as i32, self.field[0].len() as i32);
self.walker = Walker::new(field_len, pos, Box::new(get_random_dirs));
break;
}
return;
}
// 壁を伸ばしを続ける
while !self.walker.is_empty() {
let result = self.walker.walk(|_| true);
if let Some((pos, new_pos)) = result {
// 次の座標が壁なら壁伸ばし終了
if self.field[new_pos.y as usize][new_pos.x as usize] {
self.walker.clear();
}
// 進行方向へ道を進める
let inter_pos = (pos + new_pos) / 2;
self.field[inter_pos.y as usize][inter_pos.x as usize] = true;
self.field[new_pos.y as usize][new_pos.x as usize] = true;
break;
}
}
}
fn get_field(&self) -> &Vec<Vec<bool>> {
&self.field
}
}
おわりに
迷路を生成するコードは以前書いたことがあったので、今回は完成するまでの過程も出力するようにしました。
生成アルゴリズムにも色々あり、完成するまでの過程もそれぞれ異なっているのが面白いです。