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

迷路の自動生成について

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

上記で既に「穴掘り法」については紹介していますので、今回は、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倍にして保存します。

プログラムを実行しよう

ターミナルで以下のコマンドを入力してプログラムを実行してみましょう。

cargo run

すると、迷路を自動生成し、画像に描画して「maze.png」という名前で画像ファイルを作成します。

• 

  プログラムを実行して作成した画像を確認したところ

まとめ

以上、今回は迷路を自動生成し画像ファイルとして保存するプログラムを作ってみました。今回は、主に迷路を自動生成するアルゴリズムを紹介しましたが、画像ファイルを動的に作成する方法や、プログラムを機能ごとに3つのファイルに分割する方法も確認しました。少し大きなプログラムを作るときに参考になるでしょう。

自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。技術書も多く執筆している。直近では、「シゴトがはかどる Python自動処理の教科書(マイナビ出版)」「すぐに使える!業務で実践できる! PythonによるAI・機械学習・深層学習アプリのつくり方 TensorFlow2対応(ソシム)」「マンガでざっくり学ぶPython(マイナビ出版)」など。