この記事は，TeX & LaTeX Advent Calendar 2021の14日目の記事です。13日目はh-kitagawaさんでした。15日目はmod_poppoさんです。
はじめに
そろそろクリスマスです。つまりクリスマスプレゼントの準備が必要になります。というわけで本記事ではexpl3で迷路を自動生成してみます。これでクリスマスプレゼントには困りません！年賀状に迷路を描くのもいいですね。（皆さんは年賀状をもちろんTeXで書いてると思うので。）
作成したスタイルファイル等はここにあります。expl3初心者なんで，いろいろと微妙なところがあると思います。温かい目で見てください。
目標
\maze[seed]{width}{height}のように乱数のSeed値（未指定の場合はシステム時刻（？）），幅，高さを指定して下の画像のように迷路を生成するマクロを作成します。迷路生成のアルゴリズムには穴掘り法にします。アルゴリズムの実装にはもちろんexpl3を使います。迷路はTikZで描きます。下の画像は\maze[0][24][18]の出力です。
実装
このような構成でスタイルファイルを作ります。
1
2
3
4
5
6
7
8
|
\RequirePackage{expl3, xparse, tikz}
\ProvidesExplPackage {auto-maze} {...} {...} {...}
% 変数宣言
\NewDocumentCommand \maze { o m m }
{
% 迷路データの生成
% 迷路の出力
}
|
定数/変数宣言
迷路データの生成に使う定数と変数について簡単に説明します。
迷路の壁（\c__atmz_wall_int）と道（\c__atmz_road_int）をそれぞれ定数で宣言します。
\l__atmz_arg_width_intと\l__atmz_arg_height_intはマクロの引数（#2，#3）に対応するもので，迷路の壁の厚さを0，道の幅を1とした迷路のサイズの値です。
\l__atmz_maze_propに迷路の情報を格納します。keyには迷路のセル番号とし値を\c__atmz_wall_intか\c__atmz_road_intとします。セル番号とは，左からx列目，迷路の上からy行目のセルの場合にy * \l__atmz_maze_width_int + xとなる値のことです。\l__atmz_maze_width_intは\l__atmz_arg_width_int * 2 + 1 + 2（heightも同様）となる値です。迷路データの生成の画像を見るとわかりやすいです。
他の変数については後で説明します。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
\int_const:Nn \c__atmz_wall_int { \c_one_int }
\int_const:Nn \c__atmz_road_int { \c_zero_int }
\int_new:N \l__atmz_arg_width_int
\int_new:N \l__atmz_arg_height_int
\int_new:N \l__atmz_maze_width_int
\int_new:N \l__atmz_maze_height_int
\prop_new:N \l__atmz_maze_prop
\int_new:N \l__atmz_loop_i_int
\int_new:N \l__atmz_loop_j_int
\int_new:N \l__atmz_x_int
\int_new:N \l__atmz_y_int
\int_new:N \l__atmz_tmp_int
\int_new:N \l__atmz_key_int
\int_new:N \l__atmz_rand_int
\seq_new:N \l__atmz_rand_box_seq
\bool_new:N \l__atmz_loop_i_bool
\int_new:N \l__atmz_now_int
\int_new:N \l__atmz_count_tblr_int
|
Seed値の指定
オプションでSeed値が指定されたら\sys_gset_rand_seed:nでSeed値を設定します。
1
|
\IfNoValueF { #1 } { \sys_gset_rand_seed:n { #1 } }
|
迷路データの生成
ここでは\l__atmz_maze_propを下の画像のようにすることを目的とします。穴掘り法による迷路生成がわかっていることを前提に簡単に説明します。
初期化
まずは外周を道，その内部を壁とします。最初のループでは全てを壁にしています。次のループでは左側と右側を，最後のループでは上側と下側を道にしています。
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
|
\int_set:Nn \l__atmz_loop_i_int { 1 }
\int_do_while:nn { \l__atmz_loop_i_int < \l__atmz_maze_height_int - 1 }
{
\int_set:Nn \l__atmz_loop_j_int { 1 }
\int_do_while:nn { \l__atmz_loop_j_int < \l__atmz_maze_width_int - 1 }
{
\int_set:Nn \l__atmz_key_int { \l__atmz_loop_i_int * \l__atmz_maze_width_int + \l__atmz_loop_j_int }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_key_int \c__atmz_wall_int
\int_incr:N \l__atmz_loop_j_int
}
\int_incr:N \l__atmz_loop_i_int
}
\int_set:Nn \l__atmz_loop_i_int { 0 }
\int_do_while:nn { \l__atmz_loop_i_int < \l__atmz_maze_height_int }
{
\int_set:Nn \l__atmz_key_int { \l__atmz_loop_i_int * \l__atmz_maze_width_int }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_key_int \c__atmz_road_int
\int_set:Nn \l__atmz_key_int { \l__atmz_loop_i_int * \l__atmz_maze_width_int + \l__atmz_maze_width_int - 1 }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_key_int \c__atmz_road_int
\int_incr:N \l__atmz_loop_i_int
}
\int_set:Nn \l__atmz_loop_j_int { 0 }
\int_do_while:nn { \l__atmz_loop_j_int < \l__atmz_maze_width_int }
{
\int_set:Nn \l__atmz_key_int { \l__atmz_loop_j_int }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_key_int \c__atmz_road_int
\int_set:Nn \l__atmz_key_int { ( \l__atmz_maze_height_int - 1 ) * \l__atmz_maze_width_int + \l__atmz_loop_j_int }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_key_int \c__atmz_road_int
\int_incr:N \l__atmz_loop_j_int
}
|
穴掘り地点を決める
\l__atmz_now_intが現在の穴掘り地点です。この値は下の画像のような値です。\l__atmz_maze_propとは違う管理方法になっています。\fp_eval:n { randint(...) } で乱数で \l__atmz_now_intを決めます。そして\l__atmz_key_intを求め，\l__atmz_maze_propの\l__atmz_key_intを道（\c__atmz_road_int）とします。
1
2
3
4
5
|
\int_set:Nn \l__atmz_now_int { \fp_eval:n { randint( 0, \l__atmz_arg_width_int * \l__atmz_arg_height_int - 1 ) } }
\int_set:Nn \l__atmz_x_int { ( \int_mod:nn { \l__atmz_now_int } { \l__atmz_arg_width_int } ) * 2 + 2 }
\int_set:Nn \l__atmz_y_int { \fp_eval:n { floor( \l__atmz_now_int / \l__atmz_arg_width_int ) } * 2 + 2 }
\int_set:Nn \l__atmz_key_int { \l__atmz_y_int * \l__atmz_maze_width_int + \l__atmz_x_int }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_key_int \c__atmz_road_int
|
掘り進める
穴掘り地点を決めるで決めた\l__atmz_now_intから穴を掘り進めます。もし掘り進めることができない場合は，新たな地点に飛びそこから掘り進めます。迷路が完成したら\l__atmz_loop_i_boolをfalseにしてループを終了します。
1
2
3
4
5
6
|
\bool_set_true:N \l__atmz_loop_i_bool
\bool_do_while:Nn \l__atmz_loop_i_bool
{
% 2つのセルを掘る
% 掘り進めることができない場合，新しい地点を決める
}
|
2つのセルを掘る
まず\l__atmz_now_intから\l__atmz_key_intを求めます。
1
2
3
|
\int_set:Nn \l__atmz_x_int { ( \int_mod:nn { \l__atmz_now_int } { \l__atmz_arg_width_int } ) * 2 + 2 }
\int_set:Nn \l__atmz_y_int { \fp_eval:n { floor( \l__atmz_now_int / \l__atmz_arg_width_int ) } * 2 + 2 }
\int_set:Nn \l__atmz_key_int { \l__atmz_y_int * \l__atmz_maze_width_int + \l__atmz_x_int }
|
現在のセルから移動できる方向の数を数えます。2マス先が壁である場合掘れるので，4方向で掘れる場合は\l__atmz_count_tblr_intをインクリメントしてます。綺麗なコードではないですが，単純ですね。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
\int_set:Nn \l__atmz_count_tblr_int { 0 }
\int_set:Nn \l__atmz_tmp_int { \l__atmz_key_int - \l__atmz_maze_width_int * 2 }
\prop_get:NVN \l__atmz_maze_prop \l__atmz_tmp_int \l__atmz_maze_value_tl
\int_compare:nNnT { \l__atmz_maze_value_tl } = { \c__atmz_wall_int }
{ \int_incr:N \l__atmz_count_tblr_int }
\int_set:Nn \l__atmz_tmp_int { \l__atmz_key_int + \l__atmz_maze_width_int * 2 }
\prop_get:NVN \l__atmz_maze_prop \l__atmz_tmp_int \l__atmz_maze_value_tl
\int_compare:nNnT { \l__atmz_maze_value_tl } = { \c__atmz_wall_int }
{ \int_incr:N \l__atmz_count_tblr_int }
\int_set:Nn \l__atmz_tmp_int { \l__atmz_key_int - 2 }
\prop_get:NVN \l__atmz_maze_prop \l__atmz_tmp_int \l__atmz_maze_value_tl
\int_compare:nNnT { \l__atmz_maze_value_tl } = { \c__atmz_wall_int }
{ \int_incr:N \l__atmz_count_tblr_int }
\int_set:Nn \l__atmz_tmp_int { \l__atmz_key_int + 2 }
\prop_get:NVN \l__atmz_maze_prop \l__atmz_tmp_int \l__atmz_maze_value_tl
\int_compare:nNnT { \l__atmz_maze_value_tl } = { \c__atmz_wall_int }
{ \int_incr:N \l__atmz_count_tblr_int }
|
\l__atmz_count_tblr_intが0の場合には掘り進めることができません。\l__atmz_count_tblr_intが0でない場合を考えます。1から\l__atmz_count_tblr_intの乱数（\l__atmz_rand_int）を取得し，それに対応した方向に掘り進めればいいです。
\l__atmz_rand_intに対応した向きの2マス先の状態を取得し，壁でないなら（道ならば）\l__atmz_rand_intをインクリメントします。この処理にすることで，\l__atmz_rand_intが移動できない場合は次の向きに任せることができるからです。また，\l__atmz_rand_intの最大値は\l__atmz_count_tblr_intとなっているため，4までにからなず掘り進めることができます。
掘り進めることができる場合には，1マス先と2マス先のセルを道にします。そして\l__atmz_now_intを更新します。また，\l__atmz_rand_box_seqに\fp_eval:n { randint( 0, 262143 ) } * 4096 + \l__atmz_now_intとなる値を追加します。これは掘り進めることができなくなった場合のためのメモになります。具体的には新しい地点を決めるで説明します。
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
|
\int_compare:nNnF { \l__atmz_count_tblr_int } = { 0 }
{
\int_set:Nn \l__atmz_rand_int { \fp_eval:n { randint( 1, \l__atmz_count_tblr_int ) } }
\int_compare:nNnT { \l__atmz_rand_int } = { 1 }
{
\int_set:Nn \l__atmz_tmp_int { \l__atmz_key_int - \l__atmz_maze_width_int * 2 }
\prop_get:NVN \l__atmz_maze_prop \l__atmz_tmp_int \l__atmz_maze_value_tl
\int_compare:nNnTF { \l__atmz_maze_value_tl } = { \c__atmz_wall_int }
{
\int_set:Nn \l__atmz_now_int { \l__atmz_now_int - \l__atmz_arg_width_int }
\int_set:Nn \l__atmz_rand_int { \fp_eval:n { randint( 0, 262143 ) } * 4096 + \l__atmz_now_int }
\seq_put_right:Nx \l__atmz_rand_box_seq { \int_use:N \l__atmz_rand_int }
\int_set:Nn \l__atmz_tmp_int { \l__atmz_key_int - \l__atmz_maze_width_int }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_tmp_int \c__atmz_road_int
\int_set:Nn \l__atmz_tmp_int { \l__atmz_key_int - \l__atmz_maze_width_int * 2 }
\prop_put:NVV \l__atmz_maze_prop \l__atmz_tmp_int \c__atmz_road_int
}
{ \int_incr:N \l__atmz_rand_int }
}
\int_compare:nNnT { \l__atmz_rand_int } = { 2 }
{
% ...
}
\int_compare:nNnT { \l__atmz_rand_int } = { 3 }
{
% ...
}
\int_compare:nNnT { \l__atmz_rand_int } = { 4 }
{
% ...
}
}
|
新しい地点を決める
掘り進めることができない（\l__atmz_count_tblr_intが0の）場合に新しく掘り進める地点を決めます。新しい地点の条件は，これまで掘り進めた道上であることです。これまで作成した道を\l__atmz_rand_box_seqでメモしているため，これを使います。
\l__atmz_rand_box_seqが空の場合掘り進めることができないので，ループを終了します。\l__atmz_rand_box_seqが空で無い場合を考えます。\l__atmz_rand_box_seqの値は乱数 * 4096 + 地点となっています。この乱数 * 4096は新しい地点の優先順位を表しています。seqをソートする\seq_sort:Nnがl3sortによって提供されているので，ソートして先頭からpopします。popした値の4096で割ったあまりが新しい地点なので，\l__atmz_now_intを更新します。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
\int_compare:nNnT { \l__atmz_count_tblr_int } = { 0 }
{
\seq_if_empty:NTF \l__atmz_rand_box_seq
{
\bool_set_false:N \l__atmz_loop_i_bool
}
{
\seq_sort:Nn \l__atmz_rand_box_seq
{
\int_compare:nNnTF { ##1 } < { ##2 }
{ \sort_return_swapped: }
{ \sort_return_same: }
}
\seq_pop_left:NN \l__atmz_rand_box_seq \l__atmz_rand_box_left_tl
\int_set:Nn \l__atmz_now_int { \int_mod:nn { \l__atmz_rand_box_left_tl } { 4096 } }
}
}
|
出力
冒頭でも説明したとおり迷路はTikZで描きます。\begin{tikzpicture}...\end{tikzpicture}のようなトークンを出力するようにします。
\l__atmz_maze_tlにトークンを加えていき，最後に\tl_use:N \l__atmz_maze_tlします。
まずループでは，迷路の内側を描きます。偶数行目と奇数行目で縦線か横線かを描くかが異なるので，分岐して処理してます。最後に，外枠にスタートとゴールが1マス開くように線を引きます。
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
|
\tl_set:Nn \l__atmz_maze_tl { }
\tl_put_right:Nn \l__atmz_maze_tl { \begin{tikzpicture}[x=8pt, y=8pt, line~width=1pt, line~cap=round] }
\int_set:Nn \l__atmz_loop_i_int { 2 }
\int_do_while:nn { \l__atmz_loop_i_int < \l__atmz_maze_height_int - 2 }
{
\int_compare:nNnTF { \int_mod:nn { \l__atmz_loop_i_int } { 2 } } = { 0 }
{
\int_set:Nn \l__atmz_loop_j_int { 3 }
\int_do_while:nn { \l__atmz_loop_j_int < \l__atmz_maze_width_int - 2 }
{
\int_set:Nn \l__atmz_x_int { \l__atmz_loop_j_int / 2 }
\int_set:Nn \l__atmz_y_int { \l__atmz_loop_i_int / 2 }
\int_set:Nn \l__atmz_key_int { \l__atmz_loop_i_int * \l__atmz_maze_width_int + \l__atmz_loop_j_int }
\prop_get:NVN \l__atmz_maze_prop \l__atmz_key_int \l__atmz_maze_value_tl
\int_compare:nNnT { \l__atmz_maze_value_tl } = { \c__atmz_wall_int }
{
\tl_put_right:Nx \l__atmz_maze_tl
{
\exp_not:N \draw (\int_use:N \l__atmz_x_int, \int_use:N \l__atmz_y_int)--++(0, 1);
}
}
\int_set:Nn \l__atmz_loop_j_int { \l__atmz_loop_j_int + 2 }
}
}
{
\int_set:Nn \l__atmz_loop_j_int { 0 }
\int_do_while:nn { \l__atmz_loop_j_int < \l__atmz_maze_width_int - 2 }
{
\int_set:Nn \l__atmz_x_int { \l__atmz_loop_j_int / 2 }
\int_set:Nn \l__atmz_y_int { \l__atmz_loop_i_int / 2 }
\int_set:Nn \l__atmz_key_int { \l__atmz_loop_i_int * \l__atmz_maze_width_int + \l__atmz_loop_j_int }
\prop_get:NVN \l__atmz_maze_prop \l__atmz_key_int \l__atmz_maze_value_tl
\int_compare:nNnT { \l__atmz_maze_value_tl } = { \c__atmz_wall_int }
{
\tl_put_right:Nx \l__atmz_maze_tl
{
\exp_not:N \draw (\int_use:N \l__atmz_x_int, \int_use:N \l__atmz_y_int)--++(1, 0);
}
}
\int_set:Nn \l__atmz_loop_j_int { \l__atmz_loop_j_int + 2 }
}
}
\int_incr:N \l__atmz_loop_i_int
}
\int_set:Nn \l__atmz_x_int { ( \l__atmz_maze_width_int - 4 ) / 2 }
\int_set:Nn \l__atmz_y_int { ( \l__atmz_maze_height_int - 4 ) / 2 }
\tl_put_right:Nx \l__atmz_maze_tl
{
\exp_not:N \draw (1, \int_use:N \l__atmz_y_int + 1)--++(\int_use:N \l__atmz_x_int, 0);
\exp_not:N \draw (1, 1)--++(\int_use:N \l__atmz_x_int, 0);
\exp_not:N \draw (1, 1)--++(0, \int_use:N \l__atmz_y_int - 1);
\exp_not:N \draw (\int_use:N \l__atmz_x_int + 1, 2)--++(0, \int_use:N \l__atmz_y_int - 1);
}
\tl_put_right:Nn \l__atmz_maze_tl { \end{tikzpicture} }
\tl_use:N \l__atmz_maze_tl
|
次のように実行すると，下の迷路が生成されます。
さいごに
これは\maze[0][64][64]の出力です。生成に時間がかかります。遠くから見ると気持ち悪いですね。
謝辞
これを作るにあたって，@zr_tex8rさんと@wtsnjpさんからTwitterでたくさんの助言を頂いました。ありがとうございました。
文献
- TeX言語者のためのexpl3入門
- 迷路生成（穴掘り法）
- auto-maze (GitHub)
