Featured image of post 迷路型アルゴリズムを追加する - Perlダンジョン生成の拡張【第2回】
Tech

迷路型アルゴリズムを追加する - Perlダンジョン生成の拡張【第2回】

ダンジョン生成アルゴリズムを拡張し、迷路型ダンジョンを追加。コードの重複問題に直面しながら、複数アルゴリズムへの対応課題を体験します。Perlクラス設計の改善点を学習。

PerlとMooで「ランダムダンジョンジェネレーター」を作る連載の第2回です。

https://www.nqou.net/2026/01/26/002040/
設計パターンを疑え

前回はランダムに床を配置するシンプルなダンジョンを作りました。 今回は、もっとダンジョンらしい見た目にするために「迷路型」のアルゴリズムを追加します。

ランダムから迷路へ進化

前回のおさらい

前回作成したDungeon.pmは、ランダムに床を配置するシンプルな生成方法でした。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# ランダムに床を配置
sub generate ($self) {
    my $map = $self->map;

    for my $y ( 1 .. $self->height - 2 ) {
        for my $x ( 1 .. $self->width - 2 ) {
            if ( rand() < 0.7 ) {
                $map->[$y][$x] = '.';
            }
        }
    }
}

この方法だと、床がランダムに散らばるだけで「通路」や「部屋」の構造がありません。 もっとダンジョンらしくするために、迷路型のアルゴリズムを追加してみましょう。

迷路型アルゴリズムとは

迷路型アルゴリズムでは、壁で埋められた空間に通路を掘り進めていきます。 今回は「再帰的バックトラック法（Recursive Backtracking）」という手法を使います。

再帰的バックトラック法は、以下のステップで迷路を生成します。

  1. スタート地点（座標 1,1）から始める
  2. 4方向（上下左右）のいずれかをランダムに選ぶ
  3. 選んだ方向に2マス進んで通路を掘る（間の壁も掘る）
  4. 進めなくなったら、来た道を戻って別の方向を試す（これが「バックトラック」）
  5. すべてのマスを訪問するまで繰り返す

なぜ「2マス」進むのでしょうか？ それは、壁と通路を交互に配置するためです。 1マスずつ進むと、すべてが通路になってしまいます。

MazeDungeon.pmを作成する

新しいモジュールMazeDungeon.pmを作成します。

サイズが41×11と奇数になっていることに注目してください。 迷路生成では、壁と通路を交互に配置するため、奇数サイズにする必要があります。 偶数だと、最外周の壁がずれてしまいます。

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

# MazeDungeon.pm - 迷路型ダンジョン
package MazeDungeon;
use v5.36;
use Moo;

# ダンジョンのサイズ（奇数にする必要あり）
has width  => ( is => 'ro', default => 41 );
has height => ( is => 'ro', default => 11 );

# マップデータ
has map => (
    is      => 'rw',
    lazy    => 1,
    builder => '_build_map',
);

# 訪問済みマス
has visited => (
    is      => 'rw',
    lazy    => 1,
    default => sub { {} },
);

# 初期状態：すべて壁で埋める
sub _build_map ($self) {
    my @map;
    for my $y ( 0 .. $self->height - 1 ) {
        my @row;
        for my $x ( 0 .. $self->width - 1 ) {
            push @row, '#';
        }
        push @map, \@row;
    }
    return \@map;
}

# 迷路型アルゴリズム（再帰的バックトラック法）
sub generate ($self) {
    my $map = $self->map;

    # 開始地点（奇数座標）
    my $start_x = 1;
    my $start_y = 1;

    $self->_carve( $start_x, $start_y );
}

# 通路を掘る（再帰）
sub _carve ( $self, $x, $y ) {
    my $map     = $self->map;
    my $visited = $self->visited;

    # 現在地を床にして訪問済みにする
    $map->[$y][$x] = '.';
    $visited->{"$x,$y"} = 1;

    # 4方向をシャッフル
    my @directions = ( [ 0, -2 ], [ 0, 2 ], [ -2, 0 ], [ 2, 0 ] );
    @directions = sort { rand() <=> rand() } @directions;

    for my $dir (@directions) {
        my ( $dx, $dy ) = $dir->@*;
        my $nx = $x + $dx;
        my $ny = $y + $dy;

        # 範囲内かつ未訪問なら掘り進む
        if (   $nx > 0
            && $nx < $self->width - 1
            && $ny > 0
            && $ny < $self->height - 1
            && !$visited->{"$nx,$ny"} )
        {
            # 間の壁も掘る
            $map->[ $y + $dy / 2 ][ $x + $dx / 2 ] = '.';

            # 再帰
            $self->_carve( $nx, $ny );
        }
    }
}

# ASCII artで表示
sub render ($self) {
    my $map    = $self->map;
    my $output = '';

    for my $row ( $map->@* ) {
        $output .= join( '', $row->@* ) . "\n";
    }

    return $output;
}

1;

コードの中で特に注目すべき部分を解説します。

@directions = sort { rand() <=> rand() } @directions は配列をシャッフル（ランダムに並び替え）するテクニックです。 sortの比較関数が毎回ランダムな値を返すので、結果が予測不可能になります。

$map->[ $y + $dy / 2 ][ $x + $dx / 2 ] は、現在地と次の地点の「間」の壁を掘る処理です。 例えば、(1,1)から(1,3)に移動する場合、間の(1,2)も床にします。 これにより、通路が繋がった迷路になります。

迷路型ダンジョンを実行する

実行スクリプトを作成して、迷路型ダンジョンを生成してみましょう。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#!/usr/bin/env perl
# maze_demo.pl - 迷路型ダンジョン生成デモ
use v5.36;
use lib '.';
use MazeDungeon;

my $dungeon = MazeDungeon->new(
    width  => 41,
    height => 11,
);

$dungeon->generate;

print $dungeon->render;

実行結果は以下のようになります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

$ perl maze_demo.pl
#########################################
#.#.....#.....#.......#.#.....#.........#
#.#.###.#.###.#.#####.#.#.###.#.#######.#
#.#...#.#...#.#.#...#.#.#.#...#.......#.#
#.###.#.###.#.#.#.#.#.#.#.#.#########.#.#
#.....#.....#...#.#...#...#...........#.#
#####.#####.#####.#.###############.###.#
#...#.....#.....#.#.#.............#...#.#
#.#.#####.#####.#.#.#.###########.###.#.#
#.#.............#...#...............#...#
#########################################

通路が繋がった迷路構造になりました。 ランダム配置よりもずっとダンジョンらしい見た目です。

コードの重複に気づく

ここで、Dungeon.pmとMazeDungeon.pmを見比べてみましょう。

以下のコードが重複しています。

  • width/height 属性の定義
  • map 属性と _build_map メソッド
  • render メソッド
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# Dungeon.pm にも MazeDungeon.pm にも同じコードがある
has width  => ( is => 'ro', default => 40 );
has height => ( is => 'ro', default => 10 );

sub _build_map ($self) {
    # 同じ処理...
}

sub render ($self) {
    # 同じ処理...
}

異なるのはgenerateメソッドだけです。 生成アルゴリズムが違うだけなのに、モジュール全体をコピーしてしまいました。

問題点の整理

現時点での問題点は以下の通りです。

  • 共通コードが重複している
  • アルゴリズムを追加するたびにモジュール全体をコピーする必要がある
  • renderメソッドを修正したら、すべてのモジュールを修正しなければならない

まだ2つのアルゴリズムしかないので、なんとか管理できています。 しかし、アルゴリズムがもっと増えたらどうなるでしょうか？

次回は、さらに「テーマ」という軸を追加しようとして、本格的な問題に直面します。

完成コード

今回作成したMazeDungeon.pmの完成コードです。

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

# MazeDungeon.pm - 迷路型ダンジョン（完成版）
package MazeDungeon;
use v5.36;
use Moo;

# ダンジョンのサイズ（奇数にする必要あり）
has width  => ( is => 'ro', default => 41 );
has height => ( is => 'ro', default => 11 );

# マップデータ
has map => (
    is      => 'rw',
    lazy    => 1,
    builder => '_build_map',
);

# 訪問済みマス
has visited => (
    is      => 'rw',
    lazy    => 1,
    default => sub { {} },
);

# 初期状態：すべて壁で埋める
sub _build_map ($self) {
    my @map;
    for my $y ( 0 .. $self->height - 1 ) {
        my @row;
        for my $x ( 0 .. $self->width - 1 ) {
            push @row, '#';
        }
        push @map, \@row;
    }
    return \@map;
}

# 迷路型アルゴリズム（再帰的バックトラック法）
sub generate ($self) {
    my $map = $self->map;

    # 開始地点（奇数座標）
    my $start_x = 1;
    my $start_y = 1;

    $self->_carve( $start_x, $start_y );
}

# 通路を掘る（再帰）
sub _carve ( $self, $x, $y ) {
    my $map     = $self->map;
    my $visited = $self->visited;

    # 現在地を床にして訪問済みにする
    $map->[$y][$x] = '.';
    $visited->{"$x,$y"} = 1;

    # 4方向をシャッフル
    my @directions = ( [ 0, -2 ], [ 0, 2 ], [ -2, 0 ], [ 2, 0 ] );
    @directions = sort { rand() <=> rand() } @directions;

    for my $dir (@directions) {
        my ( $dx, $dy ) = $dir->@*;
        my $nx = $x + $dx;
        my $ny = $y + $dy;

        # 範囲内かつ未訪問なら掘り進む
        if (   $nx > 0
            && $nx < $self->width - 1
            && $ny > 0
            && $ny < $self->height - 1
            && !$visited->{"$nx,$ny"} )
        {
            # 間の壁も掘る
            $map->[ $y + $dy / 2 ][ $x + $dx / 2 ] = '.';

            # 再帰
            $self->_carve( $nx, $ny );
        }
    }
}

# ASCII artで表示
sub render ($self) {
    my $map    = $self->map;
    my $output = '';

    for my $row ( $map->@* ) {
        $output .= join( '', $row->@* ) . "\n";
    }

    return $output;
}

1;

今回のまとめ

第2回では、迷路型アルゴリズムを追加しました。

  • 再帰的バックトラック法による迷路生成
  • MazeDungeon.pmとして新しいモジュールを作成
  • コードの重複問題に気づいた

現時点では2つのアルゴリズム（ランダム配置、迷路型）があります。 でも、コードの重複が気になりませんか？

次回は、「テーマ」（洞窟、城、遺跡）という新しい軸を追加しようとします。 すると、クラスの数が爆発的に増えてしまう問題に直面します。 これが今後の連載で解決する「クラス爆発問題」です！

https://www.nqou.net/2026/01/26/002114/
設計パターンを疑え
comments powered by Disqus
© 2000 - 2026 設計パターンを疑え
Hugo で構築されています。
テーマ Stack は Jimmy によって設計されています。