はじめに
一年前に投稿した単一SQLで迷路を作ってみるのMySQL版です。投稿時点ではMySQLはLATERALをサポートしてなかったので除外したんですが、いつの間にかMySQLでも利用できるようになってたんですね（普段Oracleしか使ってないので、、、）。ということで、MySQLでもLATERALを活用してSQLクエリで迷路をつくってみます。
迷路作成の動作
穴掘り法での迷路作成の動きですが、まず指定された大きさの迷路となる盤面作成します。次にランダムにスタートポイントを選び、そこから上下左右にランダムに掘り進んでいきます。ただし自分の掘った穴にぶつかってはいけません。袋小路に入り上下左右どこにも進めなくなった場合はそこで一旦終了し、これまでに掘ってきた経路の内からランダムに選びそこを分岐開始ポイントとして再スタートします。どこからも再スタートできなくなったら迷路の完成です。
最終的にこんな感じで迷路を出力します。
迷路作成のクエリ
いきなりですが、以下完成版SQLクエリです。MySQL 8.0.14以降で動作するはずです(8.0.16で確認しました)。読み進めやすいようにコメントを多めに入れています。またMySQLではデフォルトで再帰クエリの深さが1000に制限されているため、最初にcte_max_recursion_depthを設定して制限を緩和しておきます。
set session cte_max_recursion_depth = 2000;
/* MySQL 8.0.14 or higher */
WITH RECURSIVE
/* 迷路のサイズ定義(縦横共に奇数であること) */
msize(size_x, size_y)
AS (SELECT 61, 25),
/* 迷路のセルを移動する４方向の定義 (2セルづつの移動) */
moves(move_x, move_y)
AS (SELECT +2, 0 UNION ALL
SELECT 0, +2 UNION ALL
SELECT -2, 0 UNION ALL
SELECT 0, -2 UNION ALL
SELECT NULL, NULL), /* 袋小路判定用NULL */
/* 迷路を構成する各セルの作成 */
cells (id, x, y)
AS (SELECT 1, MOD(1, size_x) + 1, CEIL(1 / size_x)
FROM msize
UNION ALL
SELECT id + 1, MOD(id + 1, size_x) + 1, CEIL((id + 1) / size_x)
FROM cells, msize
WHERE id + 1 <= size_x * size_y
),
/* 穴掘り法による迷路作成
x, y 現在地
cx, cy 現在地と以前の位置の間のブリッジセル(2セル毎の移動のため)
action アクションフラグ 0 - 通常移動, 1 - 袋小路時の新規セル
path カンマ区切りによる移動経路 */
mazedig (x, y, cx, cy, action, path)
AS (SELECT x, y, x, y, 0, cast(concat(x, '/', y) as char(4000))
FROM (SELECT x, y,
/* ランダムで開始セルを一つ選ぶ (rn=1) */
ROW_NUMBER() OVER (ORDER BY RAND()) rn
FROM cells
WHERE MOD(x, 2) = 0 and MOD(y, 2) = 0) c
WHERE rn = 1
UNION ALL
SELECT s.x, s.y, s.cx, s.cy,
/* 通常移動で移動先がない場合はACTIONフラグを立てて留まる */
CASE WHEN s.x is null THEN 1 ELSE 0 END,
CASE WHEN s.x is null THEN path ELSE CONCAT(path, ',', s.x, '/', s.y) END
FROM msize m, /* 迷路サイズ情報 */
mazedig r, /* 現在位置および経路(再帰) */
LATERAL ( /* 移動先のセルの選択 */
SELECT i.x, i.y,
i.x - (i.x - i.nx) / 2 cx,
i.y - (i.y - i.ny) / 2 cy,
/* 移動候補セルからランダムで移動先を一つ選ぶ (rn=1)
移動先がない場合は袋小路のフラグ行が選択される
袋小路から新規移動セルがない場合は終了 */
ROW_NUMBER() OVER (ORDER BY SIGN(x) desc, RAND()) rn
FROM (/* 移動候補セル */
/* 4方向の通常移動先候補 + NULL行 */
SELECT r.x + move_x x, r.y + move_y y, r.x nx, r.y ny
FROM moves
WHERE r.action = 0
UNION ALL
/* 袋小路に入ったときこれまでの移動経路から移動候補を作る */
SELECT b.x + move_x x, b.y + move_y y, b.x nx, b.y ny
FROM moves m, /* 4方向の移動 (NULL除外) */
(SELECT /* これまでのカンマ区切り経路を行に転換する */
CAST(REPLACE(REGEXP_SUBSTR(r.path, '[0-9]+[/]', 1, id), '/', '') AS SIGNED) x,
CAST(REPLACE(REGEXP_SUBSTR(r.path, '[/][0-9]+', 1, id), '/', '') AS SIGNED) y
FROM cells /* カンマ区切りリスト分解の補助テーブルとして使用 */
WHERE id <= (LENGTH(r.path) - LENGTH(REPLACE(r.path, ',', ''))) + 1 /* アイテム数 */
) b
WHERE m.move_x IS NOT NULL AND
r.action > 0
) i
WHERE /* 移動先がすでに到達した経路に含まれていないことおよび迷路の範囲内であること */
(NOT FIND_IN_SET(CONCAT(i.x, '/', i.y), r.path) AND
i.x > 1 AND i.y > 1 AND i.x < size_x AND i.y < size_y)
OR i.x IS NULL
) s
WHERE s.rn = 1
)
/* 迷路の表示 */
SELECT MAZE FROM (
SELECT GROUP_CONCAT(c ORDER BY x SEPARATOR '') maze, y
FROM (SELECT c.x, c.y,
/* 穴掘り経路はスペース、壁は#で表現 */
CASE WHEN p.x IS NOT NULL THEN ' ' ELSE '#' END c
FROM cells c
LEFT JOIN (SELECT x, y FROM mazedig UNION
SELECT cx, cy FROM mazedig) p
ON c.x = p.x AND c.y = p.y
) g
GROUP BY y
UNION ALL /* タイトル(迷路サイズ)*/
SELECT CONCAT('SIZE: ', size_x , 'x', size_y), 0 from msize) m
ORDER BY y
;
クエリの説明
このクエリのポイントはもちろん再帰内のLATERALですね。承知の通り再帰クエリの文法にはいくつか制限があり、その一つに自クエリ(ここではmazedig)は常にトップレベルクエリのFROM句に置かなければならならない（つまりサブクエリ内で直接使用できない）というのがあります。しかし再帰途中のデータを使って複雑な処理をしようとすると、サブクエリでの処理がどうしても必要となってきます。これを解決するのがLATERALです。LATERALは同列に並べられたテーブルのデータを相関で用いたインラインビューを構成できます。つまり再帰中のデータを利用したサブクエリが再帰内で実現できるのです。
ここではLATERAL内で次に移動するセルを算出しており、大きく分けて２つの動きがあります。
１つ目は上下左右への通常移動。以下の部分ですね。movesテーブル(CTE)には4つの移動方向とNULLが格納されています。NULL行は袋小路判断のためのものです。移動可能セル候補から移動不可セル除外した後にこれだけ残っていたらどこにも進めない袋小路に陥っていると判断できます。
/* 4方向の通常移動先候補作成 + NULL行 */
SELECT r.x + move_x x, r.y + move_y y, r.x nx, r.y ny
FROM moves
WHERE r.action = 0 /* 通常移動時のフラグ */
もう一つの動きは、袋小路に入った後に分岐点から再スタートするための分岐開始セルの算出ですね。分岐開始セルはこれまで進んできたセルの中から選ばれます。このためカンマ区切りで保持しているこれまでの経路を行に転換し、それぞれの行から４方向の移動候補を作成しています。このクエリで現れるcellsテーブル(CTE)は展開用の補助として使われているだけでここではデータに意味はありません。
ここで作成された移動候補が移動不可セル除外ですべて却下されてた場合は、迷路の作成が終了となります。従ってmovesからNULL行を除外しています。
/* 袋小路に入ったときこれまでの移動経路から移動候補を作る */
SELECT b.x + move_x x, b.y + move_y y, b.x nx, b.y ny
FROM moves m, /* 4方向の移動 (NULL除外) */
(SELECT /* これまでのカンマ区切り経路を行に転換する */
CAST(REPLACE(REGEXP_SUBSTR(r.path, '[0-9]+[/]', 1, id), '/', '') AS SIGNED) x,
CAST(REPLACE(REGEXP_SUBSTR(r.path, '[/][0-9]+', 1, id), '/', '') AS SIGNED) y
FROM cells /* 補助テーブル */
WHERE id <= (LENGTH(r.path) - LENGTH(REPLACE(r.path, ',', ''))) + 1 /* アイテム数 */
) b
WHERE m.move_x IS NOT NULL AND
r.action > 0 /* 袋小路状態のフラグ */
次に上記で算出された移動先候補セルから移動不可のセルを除外します。移動可能条件はこれまでの移動経路に含まれていないことおよび、迷路サイズの枠内にあることです。ただしNULL行は袋小路判定のために残しておきます。
WHERE (/* これまでの移動経路に含まれていないこと */
NOT FIND_IN_SET(CONCAT(i.x, '/', i.y), r.path) AND
/* 迷路サイズの枠内にあること */
i.x > 1 AND i.y > 1 AND i.x < size_x AND i.y < size_y
)
OR i.x IS NULL /* 袋小路判定用 */
その後、移動可能セルから一つをランダムで選びます (rn = 1)。ここではSIGN(x)を優先してソートすることで、移動可能セルがない場合のみに袋小路フラグであるNULL行が選択されるようにしています。
ROW_NUMBER() OVER (ORDER BY SIGN(x) desc, RAND()) rn
主要なところは以上ですかね。再帰自体は単にループしてるだけなので。
LATERALを使わない迷路作成クエリ
実のところこのクエリはLATERALを使わずにスカラークエリで書き換えることも可能です。ただし相関サブクエリの多段飛び参照が可能なMySQLのバージョンに限られます。以下のSQLがエラーにならないという条件ですね。手元では確認できないのですがおそらくLATERAL実装と同じバージョンだとおもわれます(Oracleも12cでLATERALと多段飛び参照が同時にサポートされました)。ちなみに8.0.13では不可、8.0.16では可でした。つまり少なくともLATERALがサポートされたバージョン以降ということになるので、ぶっちゃけLATERALを使ったほうが何倍も良いですけどね。
SELECT (SELECT n FROM (SELECT t.n) s) FROM (SELECT 1 n) t;
ともかくSELECT句のスカラークエリの制限として「返り値カラムが一つであること」、「返り行が一つまたは無いこと」があります。従って、スカラークエリ内で再帰の分岐計算はできませんし、再帰カラムが複数ある場合は結合して単一文字列カラムとして扱いかつクエリ内で分割することになります。以下LATERAL不使用版でが、いろいろ制約があるのですこし煩雑になっています。参考までに。
LATERALを使わない迷路作成SQLクエリ(開く)
WITH RECURSIVE
msize(size_x, size_y)
AS (SELECT 61, 25),
moves(move_x, move_y)
AS (SELECT +2, 0 UNION ALL
SELECT 0, +2 UNION ALL
SELECT -2, 0 UNION ALL
SELECT 0, -2 UNION ALL
SELECT NULL, NULL),
cells (id, x, y)
AS (SELECT 1, MOD(1, size_x) + 1, CEIL(1 / size_x)
FROM msize
UNION ALL
SELECT id + 1, MOD(id + 1, size_x) + 1, CEIL((id + 1) / size_x)
FROM cells, msize
WHERE id + 1 <= size_x * size_y
),
/* 穴掘り法による迷路作成 param = <x>:<y>:<cx>:<cy>:<action>:<path> */
mazedig (param)
AS (
SELECT /* 再帰で用いる値をすべて結合して単一パラメータとする */
CAST(CONCAT(x, ':', y, ':', x, ':', y, ':', 0, ':', x, '/', y) AS CHAR(4000))
FROM (SELECT x, y,
ROW_NUMBER() OVER (ORDER BY RAND()) rn
FROM cells
WHERE MOD(x, 2) = 0 and MOD(y, 2) = 0) c
WHERE rn = 1
UNION ALL
SELECT (SELECT CASE WHEN s.x IS NULL
THEN CONCAT('0:0:0:0:1:', REGEXP_SUBSTR(r.param, '[^:]+$'))
ELSE CONCAT(s.x, ':', s.y, ':', s.cx, ':', s.cy, ':0:',
REGEXP_SUBSTR(r.param, '[^:]+$'), ',', s.x, '/', s.y)
END
FROM (SELECT i.x, i.y,
truncate(i.x - (i.x - i.nx) / 2, 0) cx,
truncate(i.y - (i.y - i.ny) / 2, 0) cy,
ROW_NUMBER() OVER (ORDER BY SIGN(x) desc, RAND()) rn
FROM (
SELECT f.x + move_x x, f.y + move_y y, f.x nx, f.y ny
FROM moves,
(SELECT /* 再帰文字パラメータから必要な値の取り出し */
CAST(REPLACE(REGEXP_SUBSTR(r.param, '[0-9]+:', 1, 1), ':', '') AS SIGNED) x,
CAST(REPLACE(REGEXP_SUBSTR(r.param, '[0-9]+:', 1, 2), ':', '') AS SIGNED) y,
CAST(REPLACE(REGEXP_SUBSTR(r.param, '[0-9]+:', 1, 5), ':', '') AS SIGNED) action
) f
WHERE f.action = 0
UNION ALL
SELECT b.x + move_x x, b.y + move_y y, b.x nx, b.y ny
FROM moves m,
(SELECT CAST(REPLACE(REGEXP_SUBSTR(f.path, '[0-9]+[/]', 1, id), '/', '') AS SIGNED) x,
CAST(REPLACE(REGEXP_SUBSTR(f.path, '[/][0-9]+', 1, id), '/', '') AS SIGNED) y
FROM cells,
/* 再帰文字パラーメータから経由路の取り出し
REGEXP_SUBSTRを使うとLENGTHの返り値が何故か正しくない。
代替として、SUBSTRINGとREGEXP_INSTRを使用する。 */
(SELECT SUBSTRING(r.param, REGEXP_INSTR(r.param, '[^:]+$')) path) f
WHERE id <= (LENGTH(f.path) - LENGTH(REPLACE(f.path, ',', ''))) + 1
) b
WHERE m.move_x IS NOT NULL AND
CAST(REPLACE(REGEXP_SUBSTR(r.param, '[0-9]+:', 1, 5), ':', '') AS SIGNED) > 0 /* action */
) i
WHERE
(NOT FIND_IN_SET(CONCAT(i.x, '/', i.y), REGEXP_SUBSTR(r.param, '[^:]+$')) AND
i.x > 1 AND i.y > 1 AND i.x < size_x AND i.y < size_y)
OR i.x IS NULL
) s
WHERE s.rn = 1
)
FROM msize m, /* 迷路サイズ情報 */
mazedig r /* 現在位置および経路(再帰) */
WHERE r.param IS NOT NULL /* paramがNULLで終了 */
),
/* 穴掘りルートの取り出し */
route
AS (SELECT CAST(REPLACE(REGEXP_SUBSTR(param, '[0-9]+:', 1, 1), ':', '') AS SIGNED) x,
CAST(REPLACE(REGEXP_SUBSTR(param, '[0-9]+:', 1, 2), ':', '') AS SIGNED) y,
CAST(REPLACE(REGEXP_SUBSTR(param, '[0-9]+:', 1, 3), ':', '') AS SIGNED) cx,
CAST(REPLACE(REGEXP_SUBSTR(param, '[0-9]+:', 1, 4), ':', '') AS SIGNED) cy
FROM mazedig
WHERE param IS NOT NULL)
/* 迷路の表示 */
SELECT MAZE FROM (
SELECT GROUP_CONCAT(c ORDER BY x SEPARATOR '') maze, y
FROM (SELECT c.x, c.y,
CASE WHEN p.x IS NOT NULL THEN ' ' ELSE '#' END c
FROM cells c
LEFT JOIN (SELECT x, y FROM route UNION
SELECT cx, cy FROM route) p
ON c.x = p.x AND c.y = p.y
) g
GROUP BY y
UNION ALL
SELECT CONCAT('SIZE: ', size_x , 'x', size_y), 0 from msize) m
ORDER BY y
;
おわりに
SQLでも再帰、LATERAL、UNIONを組み合わせることで、ループに分岐という動きがある程度簡単にできるようになりました。といってもそこはSQLの得意とするところではないし、他の言語を使ったほうが適切であるというのはそのとおりなのですが、まぁそこはひとつ、SQLの幅が広がるということで (^^)。
ともかく、MySQLでもウィンドウ関数、CTE、再帰、LATERALと他のDBではすでに実装済みとなっている機能をこれまでの遅れを取り戻すかのように積極的にサポートし始めました。今後がとても楽しみです。
以上です。