迷路画像の自動生成に挑戦しよう

前回、Rustを使ってビットマップ画像を出力するプログラムを作りました。今回は迷路を自動的に作成し、PNG画像に描画して保存するプログラムを作ってみましょう。今回は迷路の自動生成に挑戦してみます。

迷路の自動生成について

まずは、迷路の自動生成の方法を考えてみましょう。既にいろいろな研究がなされており、代表的なアルゴリズムだけでも「棒倒し法」「穴掘り法」「クラスタリング法」などがあります。このうち「棒倒し法」については、こちらの姉妹連載にて解説しています。

上記で既に「穴掘り法」については紹介していますので、今回は、Rustで穴掘り法のプログラムを作ってみましょう。

穴掘り法では、次のような手順で迷路を自動生成します。

• (1) 迷路全体を壁で初期化する
• (2) 起点から穴掘りを開始する
• (3) 上下左右の4方向をシャッフルして、順に以下の処理を行う
• (4) 2マス先を調べて通路であれば、(3)に戻って別の方向を処理する
• (5) 2マス先が通路であれば、(3)に戻って別の方向を処理する
• (6) 1マス先と2マス先を通路にする
• (7) 2マス先を起点にして、再帰的に(3)以降の処理を行う

ポイントは、上記(3)以降の再帰処理を使って、迷路の通路を掘り進んでいく点にあります。

• 穴掘り法で迷路を自動生成する方法

迷路を自動生成するプログラム

具体的なアルゴリズムが分かったところで、迷路を自動生成するプログラムの作成に取りかかりましょう。 今回、Rustのパッケージ管理ツールツールのCargoを使ってプロジェクトを管理してみましょう。ターミナルを起動して、次のコマンドを実行してプロジェクトを初期化しましょう。ターミナルとは、WindowsならPowerShell、macOSならターミナル.appのことです。

cargo init

そして、さらに乱数を手軽に使えるlazyrandと、画像を保存するimageクレートをプロジェクトに追加します。以下のコマンドを実行しましょう。

cargo add lazyrand
cargo add image

今回のプログラムは、モジュールの仕組みを学ぶために、機能ごとにプログラムファイルを分割してみようと思います。メインプログラム(main.rs)と、迷路生成プログラム(genarator.rs)と、迷路を画像に描画して保存するプログラム(drawer.rs)の3つのファイルに分割してみましょう。

それで、srcディレクトリ以下に、次の3つのファイルを作成します。

src
├── drawer.rs  --- 迷路を画像に描画して保存するプログラム
├── generator.rs --- 迷路を自動生成するプログラム
└── main.rs --- メインプログラム

なお、分かりやすくファイル3つに分けたものの、全部のプログラムを合計しても70行未満なので処理を確認するのは容易でしょう。

メインプログラムを記述しよう

まずは「main.rs」を記述しましょう。

// 利用するモジュールの記述 --- (*1)
mod drawer;
mod generator;

fn main() {
    let (w, h) = (81, 81); // 迷路の幅と高さを指定 --- (*2)
    let data = generator::make_maze(w, h); // 迷路を生成
    drawer::save(&data, w, h, "maze.png"); // ファイルへ保存
}

プログラムを確認しましょう。(＊1)では、利用するモジュールを宣言します。Rustでプログラムファイルを分割する場合、ファイル名がモジュール名となります。それで、今回記述したプログラム「drawer.rs」と「generator.rs」を利用するために、このように記述します。

(＊2)以降の部分では、迷路を生成してファイルへ保存するプログラムを記述します。

迷路を自動生成するプログラム

次に迷路を生成する「generator.rs」を記述しましょう。このプログラムでは、穴掘り法で迷路を生成します。

// 定数宣言 --- (*1)
pub const ROAD: u8 = 0; // 道を表す値 
pub const WALL: u8 = 1; // 壁を表す値

// 迷路自動生成する関数 --- (*2)
pub fn make_maze(width: usize, height: usize) -> Vec<u8> {
    // 迷路データを壁で初期化 --- (*3)
    let mut maze = vec![];
    for _ in 0..(width * height) {
        maze.push(WALL);
    }
    // (1, 1)から掘り始める --- (*4)
    dig_maze(&mut maze, width, height, 1, 1);
    maze
}
// 壁があるところを掘って道にする --- (*5)
fn dig_maze(maze: &mut Vec<u8>, width: usize, height: usize, x: isize, y: isize) {
    maze[(y * width as isize + x) as usize] = ROAD; // 道を掘る
    let mut dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]; // 上下左右 --- (*6)
    lazyrand::shuffle(&mut dirs);
    for dir in dirs {
        let (dx, dy) = dir;
        // 1マス先と2マス先の座標を確認 --- (*7)
        let (x1, y1) = (x + dx, y + dy);
        let (x2, y2) = (x + dx * 2, y + dy * 2);
        // 2マス先が範囲外か確認 --- (*8)
        if x2 < 1 || x2 >= (width - 1) as isize { continue; }
        if y2 < 1 || y2 >= (height - 1) as isize { continue; }
        // 2マス先が道なら掘らない
        if maze[(y2 * width as isize + x2) as usize] == ROAD { continue; }
        // 道を掘る --- (*9)
        maze[(y1 * width as isize + x1) as usize] = ROAD;
        maze[(y2 * width as isize + x2) as usize] = ROAD;
        // 再帰的に道を掘る --- (*10)
        dig_maze(maze, width, height, x2, y2);
    }
}

プログラムを確認しましょう。(＊1)では定数を宣言します。ROADは迷路データの道を表す値、WALLは壁を表す値として定義します。

(＊2)では迷路を自動生成する関数make_mazeを定義します。(＊3)で迷路データを全部壁として初期化します。(＊4)では座標(1, 1)を起点として迷路を掘り始めます。

(＊5)では壁があるところを掘って道にする関数dig_mazeを定義します。(＊6)では起点(x, y)から上下左右方向に対して順に穴を掘ります。ただし、毎回上下左右の順番に掘るのではなく、掘る順番をシャッフルして掘ります。

(＊7)では1マス先と2マス先の座標を確認し、(＊8)では迷路の範囲外になったら掘りません。また、2マス先が既に道となっている場合も掘らないようにします。そして、(＊9)では実際に道を掘り、(*10)で再帰的にdig_mazeを呼び出します。

迷路を画像に描画して保存するプログラム

最後に作成した迷路データを、画像に描画してファイルに保存するプログラム「drawer.rs」を記述しましょう。

use crate::generator::{ROAD, WALL};
use image::{imageops, ImageBuffer};

// 画像に迷路を描画 --- (*1)
pub fn save(maze: &Vec<u8>, width: usize, height: usize, filename: &str) {
    // 指定サイズで画像バッファを用意 --- (*2)
    let mut imbuf = ImageBuffer::new(width as u32, height as u32);
    for i in 0..maze.len() { // 繰り返し描画 --- (*3)
        let color = match maze[i] {
            WALL => image::Rgb([200, 80, 100]),
            ROAD => image::Rgb([255, 255, 255]),
            _ => image::Rgb([0, 0, 0]),
        };
        let (y, x) = ((i / width) as u32, (i % width) as u32);
        imbuf.put_pixel(x, y, color); // 座標に色を配置
    }
    // 画像を拡大して保存 --- (*4)
    let (w, h) = (12 * width as u32, 12 * height as u32);
    let imbuf = imageops::resize(&imbuf, w, h, imageops::FilterType::Nearest);
    image::save_buffer(filename, &imbuf, w, h, image::ColorType::Rgb8).unwrap();
}

プログラムを確認しましょう。(＊1)では迷路を画像ファイルに保存する関数saveを宣言します。(＊2)ではimageクレートに用意されている画像バッファを作成するメソッドImageBuffer::newを使ってメモリに画像バッファを作成します。(＊3)では迷路データに基づいて繰り返し各ピクセルを描画します。そして、(＊4)で画像を保存します。ただし、そのまま保存するととても小さな画像になってしまうので、12倍にして保存します。