はじめに
単一SQLクエリで迷路を作ります。以下Oracleで説明していますが、PostgreSQL版も記載しています。
追記：MySQL版は、LATERALが8.0.14でサポートされた後別記事に記載しました。
LATERALが実装されたのでMySQLでもSQLクエリで迷路を作ってみる
迷路を作るアルゴリズム
迷路を作るアルゴリズムはたくさんあるようですが、一般的なのはこの３つでしょう。以下のサイトで詳しく説明されており、ここでは簡単に説明します。クエリを作る難易度からいうと、あきらかに「（易）壁倒し法 >>> 穴掘り法 >>> 壁伸ばし法（難）」ですね。
壁倒し法
奇数x奇数の位置にある壁を上下左右に倒していくだけです。壁を順に倒していくだけなので非常に簡単で高速ですが、迷路の解答が非常に単調になります。見た目は迷路ですが迷路としてはあまり使えないレベルです。壁を倒す条件は、倒せる方向が一番上のラインは上下左右、その後は下左右のみで、前に倒した壁に重ならないことです。
穴掘り法
偶数x偶数の位置にあるセルから上下左右ランダムに穴を掘りながら一度に2セルづつ進んでいきます。掘り進む条件はこれまでに掘った穴に一切ぶつかってはいけないこと。上下左右どこにも進めなくなったらラウンドを終了し、これまでに掘ってきた穴のどこか一つ(偶数x偶数)をランダムに選び、そこから分岐してまた穴掘りを繰り返します。分岐する場所がなくなれば終了です。
壁伸ばし法
奇数x奇数の位置にある未接続の壁セルから上下左右ランダムに壁を伸ばしながら2セルづつ進んでいきます。伸ばす条件は現在のラウンドで伸ばした壁（ランダムに選んだスタート地点から続く壁）にぶつかってはいけないこと。これを外周や既存の壁にぶつかるまで続けます。ただし、現在のラウンドで伸ばした壁の袋小路にはいって進めなくなった場合は、ラウンドを最初からやり直します。未接続の壁がすべて接続されれば終了です。
壁倒し法
壁倒し法は、行間参照して倒す壁が重ならないようにするだけでいいので、モデル句を使用すれば簡単にできます。まず以下のような奇数x奇数の位置に倒す壁のある迷路の土台をつくります。
次に、モデルのルール句の一行目で左上から右下に向かって順番に壁をランダム方向に倒していき、二行目で倒した方向の通路に壁を追加します。最後にLISTAGGで整形して終了です。この方法であれば大きな迷路も非常に高速に作成できますが、いかんせん迷路自体がなんちゃってなのでやはり、他の方法でちゃんとした迷路を目指します。
壁倒し法(Oracle)
WITH
cells (x, y, c) -- 迷路の土台セル作成
AS (SELECT MOD(LEVEL, px) + 1,
CEIL(LEVEL / px),
CASE WHEN MOD(LEVEL, px) + 1 in (1, px) OR
CEIL(LEVEL / px) in (1, py)
THEN '#'
WHEN MOD(MOD(LEVEL, px) + 1, 2) = 1 AND
MOD(CEIL(LEVEL / px), 2) = 1
THEN 'X'
ELSE ' '
END
FROM (SELECT 101 px, 101 py FROM DUAL) -- 迷路のサイズ 101*101
CONNECT BY LEVEL <= px * py
)
SELECT LISTAGG(DECODE(c, 'X', '#', c)) WITHIN GROUP (ORDER BY x) -- 整形
FROM (SELECT x, y, dr, c
FROM cells
MODEL
DIMENSION BY (x, y)
MEASURES (c, 0 dr)
RULES (dr[FOR (x, y) IN (SELECT x, y FROM cells WHERE c = 'X')] ORDER BY y, x -- 壁のあるセルのみ
= TRUNC(DBMS_RANDOM.VALUE(2 - DECODE(cv(y), 3, 1, 0), -- 一番上だけ上方向も含める
5 - DECODE(dr[CV() - 2, CV()], 2, 1, 0))), -- 左隣に壁があれば重ねない
c[FOR (x, y) IN (SELECT x, y FROM cells WHERE c= ' ')] ORDER BY y, x -- 壁のないセルのみ
= CASE WHEN dr[CV(), CV() + 1] = 1 OR dr[CV() - 1, CV()] = 2 OR -- 壁倒し方向
dr[CV(), CV() - 1] = 3 OR dr[CV() + 1, CV()] = 4 -- 1/上 2/右 3/下 4/左
THEN '#' ELSE ' '
END
)
)
GROUP BY y
ORDER BY y;
穴掘り法
穴掘り法のイメージとしては以下の感じですね。ランダムに選ばれたA1から出発し掘り進み、B1で袋小路にはいったので、これまで掘った道からランダムに新規セルA2を選択肢し、そこから分岐して進みB2の袋小路に到達。これを繰り返して進んだり分岐できるセルがなくなれば完成になります。
PL/SQL版（参考）
まずは、動きの理解しやすいPL/SQLで見てみます。穴を掘り進める部分の内側のループと袋小路に入って場合に分岐の新規セルを選択する外側のループの二重ループになっています。これをそのまま再帰クエリに置き換えます。
PL/SQL穴掘り法 (開く)
コレクションの作成
CREATE OR REPLACE TYPE maze_cell_typ AS OBJECT (
x NUMBER, -- X座標
y NUMBER, -- Y座標
c VARCHAR2(1), -- セルの文字
id NUMBER); -- 通し番号
/
CREATE OR REPLACE TYPE maze_typ AS TABLE OF maze_cell_typ;
/
穴掘り法（PL/SQL）
SET SERVEROUT ON
DECLARE
p_size_x number := 41; -- 横サイズ
p_size_y number := 21; -- 縦サイズ
cells maze_typ := maze_typ(); -- 迷路セル
roadcells maze_typ := maze_typ(); -- 分岐可能セル保持用
scell maze_cell_typ; -- 現在セル
ncell maze_cell_typ; -- 次に移動するセル
bcell maze_cell_typ; -- 現在と次の間のセル
BEGIN
-- 迷路のサイズ条件 5x5以上で奇数
IF p_size_x < 5 OR mod(p_size_x, 2) = 0 OR
p_size_y < 5 OR mod(p_size_y, 2) = 0
THEN
RAISE_APPLICATION_ERROR(-20000, 'The length and width must be odd numbers of 5 or larger.');
RETURN;
END IF;
-- すべて壁'#'である迷路のベースを作ってcellsコレクションに保持
SELECT maze_cell_typ(MOD(LEVEL, p_size_x) + 1, CEIL(LEVEL / p_size_x), '#', LEVEL)
BULK COLLECT INTO cells
FROM DUAL CONNECT BY LEVEL <= p_size_x * p_size_y;
-- 最初の開始点を(偶数x偶数)セルの中からランダムに選ぶ
SELECT v INTO scell
FROM (SELECT VALUE(t) v,
ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
FROM TABLE(cells) t
WHERE MOD(x, 2) = 0 and MOD(y, 2) = 0)
WHERE rn = 1;
roadcells.EXTEND(cells.count); -- 分岐可能セルを保持するための迷路と同じ大きさに拡張
roadcells(scell.id) := scell; -- 開始点セルを分岐可能セルリストに追加
cells(scell.id).c := ' '; -- 開始点セルを道として確定
LOOP
-- 分岐可能セルリストの中から開始点セルとしてランダムに一つ選ぶ
-- 選ぶセルがなければ迷路は完成なのでループを抜ける
BEGIN
SELECT v INTO scell
FROM (SELECT VALUE(t) v,
ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
FROM TABLE(roadcells) t
WHERE id IS NOT NULL)
WHERE rn = 1;
EXCEPTION WHEN NO_DATA_FOUND THEN EXIT; -- 迷路完成
END;
LOOP
-- 現在のセルの上下左右２つとなりでかつ"#"であるセルを進めるセルとして取得し、
-- そのうちの一つをランダムで選ぶ(ncell)。同時に隣のセルも取得しておく(bcell)。
-- 進めなければ、分岐可能セルリストから現在セルを削除し今回のラウンドを終了する
BEGIN
SELECT v, value(p) INTO ncell, bcell
FROM (SELECT value(t) v,
ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE(1, 1000)) rn
FROM TABLE(cells) t
WHERE t.c = '#' AND
(t.x, t.y) IN ((scell.x + 2, scell.y), (scell.x - 2, scell.y), -- 二つ隣のセル
(scell.x, scell.y + 2), (scell.x, scell.y - 2))
) n,
TABLE(cells) p
WHERE rn = 1 AND
p.x = scell.x + (n.v.x - scell.x)/2 AND -- 移動する方向の一つ隣のセル
p.y = scell.y + (n.v.y - scell.y)/2;
EXCEPTION WHEN NO_DATA_FOUND THEN
roadcells.delete(scell.id); -- 分岐可能セルリストから削除
EXIT;
END;
cells(ncell.id).c := ' '; -- 二つ隣のセルを道に確定
cells(bcell.id).c := ' '; -- 一つ隣のセルを道に確定
roadcells(ncell.id) := ncell; -- 次の探査対象セルを分岐可能セルリストに追加
scell := ncell; -- 次の探査対象セルをセット
END LOOP;
END LOOP;
-- 行ごとにまとめて迷路図を出力
FOR i IN (SELECT y, LISTAGG (c) WITHIN GROUP (ORDER BY x) l
FROM TABLE(cells)
GROUP BY y
ORDER BY y)
LOOP
DBMS_OUTPUT.PUT_LINE(i.l);
END LOOP;
END;
/
単一クエリ(Oracle)版
二重ループ部分は、ラテラル句内でユニオンを使って分岐させることで実現可能です。またラテラル内のサブクエリが深くなっても「副問合せの多重飛び参照」によって直接再帰クエリのカラムを参照できるので全く問題になりません。ともにOracle 12cからの機能であり再帰クエリはそれらのおかげで自由度が上がっています。PostgreSQLも同様のことができるようです。
ここで必要となる再帰は本来の再帰ではなくただのループです。再帰内では現在位置とこれまで通ったセルのカンマ区切り文字列を受け取り、その上下左右セルの中からこれまで通った道にぶつからないように次に進むセルをランダムに決定します。進むセルがあればカンマ区切り文字列を追加して次のレベルへ、進めるセルがなければフラグをセットして(action=1)そのまま次のレベル進み次レベルではフラグに従い新規の分岐セルをランダムに選択します。プログラムでフラグを使用して二重ループを単一ループに書き換えることをイメージすれば理解しやすいのではないかと思います。
穴掘り法(Oracle12c)
WITH
msize(size_x, size_y) AS (SELECT 51, 21 FROM DUAL), -- 迷路のサイズ定義
moves(move_x, move_y) AS (SELECT +2, 0 FROM DUAL UNION ALL SELECT 0, +2 FROM DUAL UNION ALL
SELECT -2, 0 FROM DUAL UNION ALL SELECT 0, -2 FROM DUAL),
cells (x, y) -- 迷路サイズのセル作成
AS (SELECT MOD(LEVEL, size_x) + 1, CEIL(LEVEL / size_x)
FROM msize CONNECT BY LEVEL <= size_x * size_y
),
mazedig (n, x, y, cx, cy, action, path)
AS (-- セルの中から開始点(偶数x偶数)をランダムで一つ選ぶ
SELECT 1, x, y, x, y, 0, ',' || x || '/' || y || ','
FROM (SELECT x, y,
ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
FROM cells
WHERE MOD(x, 2) = 0 and MOD(y, 2) = 0)
WHERE rn = 1
UNION ALL
-- パフォーマンスのために、ACTIONフラグで必要なときだけ分岐の道の計算を行う
-- 継続して伸ばすセルが袋小路に入った場合にNULLが選択されACTIONがセットされる
SELECT n + 1, s.x, s.y, s.cx, s.cy,
DECODE(s.flg, 1, 1, 0),
path || DECODE(s.flg, 1, '', s.str || ',')
FROM mazedig r,
msize m,
LATERAL (SELECT i.x, i.y, i.x || '/' || i.y str, i.flg,
i.x - (i.x - i.nx)/2 cx,
i.y - (i.y - i.ny)/2 cy,
ROW_NUMBER() OVER (ORDER BY flg, DBMS_RANDOM.VALUE) rn
FROM (-- 既存の道からの分岐計算（前レベルで袋小路に入った場合のみ）
SELECT 2 flg, b.x + move_x x, b.y + move_y y, b.x nx, b.y ny
FROM moves,
(SELECT TO_NUMBER(SUBSTR(r.path,
INSTR(r.path, ',', 1, level) + 1,
INSTR(r.path, '/', 1, level)
- INSTR(r.path, ',', 1, level) - 1)) x,
TO_NUMBER(SUBSTR(r.path,
INSTR(r.path, '/', 1, level) + 1,
INSTR(r.path, ',', 1, level + 1)
- INSTR(r.path, '/', 1, level) - 1)) y
FROM dual
CONNECT BY LEVEL <= LENGTH(r.path)
- LENGTH(REPLACE(r.path, ',', '')) - 1
) b
WHERE b.x IS NOT NULL AND b.y IS NOT NULL AND
r.action > 0 -- パフォーマンスのため必要なときのみ計算
UNION ALL
-- 継続して伸ばす穴掘り先
SELECT 0, r.x + move_x, r.y + move_y, r.x, r.y
FROM moves WHERE r.action = 0
UNION ALL
-- 袋小路に入った場合に取得される
SELECT 1, NULL, NULL, NULL, NULL
FROM DUAL WHERE r.action = 0
) i
WHERE i.flg = 1 OR
(r.path NOT LIKE '%,' || i.x || '/' || i.y || ',%' AND
i.x > 1 AND i.y > 1 AND i.x < size_x AND i.y < size_y)
) s
WHERE s.rn = 1
)
CYCLE n SET cycle TO 1 DEFAULT 0
SELECT LISTAGG (c) WITHIN GROUP (ORDER BY x) maze
FROM (SELECT c.x, c.y, NVL2(p.x, ' ', '#') c
FROM cells c,
(SELECT x, y FROM mazedig UNION
SELECT cx, cy FROM mazedig) p
WHERE c.x = p.x (+) AND c.y = p.y (+)
)
GROUP BY y
ORDER BY y;
MAZE
---------------------------------------------------------
###################################################
# # # # # # # # #
# # ##### ##### # ####### # # ####### # # # ### # #
# # # # # # # # # # # # # # #
##### ### # # # ##### # ##### ##### # ### # # ### #
# # # # # # # # # # # #
# # ### ####### # # ##### # ### # # ########### ###
# # # # # # # # # # # # # # #
### # ### # # ### # # ####### ##### # # # # # ### #
# # # # # # # # # # # # # # #
# ############# ##### # ####### # # # ######### # #
# # # # # # # # # # # # # #
# # ### ########### # ##### # # ### # ### ### # # #
# # # # # # # # # # # # #
##### ### # ##### ####### # # ### ##### ### ##### #
# # # # # # # # # # # #
# ##### ####### # # ### ##### ####### ### ### # # #
# # # # # # # # # # # # # # #
# # # ### # ### ### # # # ##### # ### ##### # # # #
# # # # # # # # # # #
###################################################
21 rows selected.
Elapsed: 00:00:01.64
カンマ区切り文字列の展開があるので冗長になっていますが、カンマ区切り文字列ではなくコレクションを使えばもっとシンプルになりかつVARCHAR2の文字列制限がなくなります。
PostgreSQL版
穴掘り法のPostgreSQL版です。PostgreSQL 11.0で確認しました。ARRAYが使えるのでかなりスッキリしますね。
穴掘り法(PostgreSQL)
WITH RECURSIVE
msize(size_x, size_y) AS (SELECT 51, 21),
moves(move_x, move_y) AS (SELECT +2, 0 UNION ALL SELECT 0, +2 UNION ALL
SELECT -2, 0 UNION ALL SELECT 0, -2),
cells (n, x, y)
AS (SELECT 1, 1, 1
UNION ALL
SELECT n + 1, MOD(n, size_x) + 1, CAST((n / size_x) + 1 AS INTEGER)
FROM cells, msize
WHERE n < size_x * size_y
),
mazedig (n, x, y, cx, cy, action, path)
AS (SELECT 1, x, y, x, y, 0, ARRAY[str]
FROM (SELECT x, y, CONCAT(x, '/', y) str,
ROW_NUMBER() OVER (ORDER BY RANDOM()) rn
FROM cells
WHERE MOD(x, 2) = 0 AND MOD(y, 2) = 0) c
WHERE rn = 1
UNION ALL
SELECT r.n + 1, s.x, s.y, s.cx, s.cy,
CASE WHEN s.flg = 1 THEN 1 ELSE 0 END,
CASE WHEN s.flg = 1 THEN path ELSE path || s.str END
FROM msize m,
mazedig r
CROSS JOIN LATERAL (
SELECT i.x, i.y, CONCAT(i.x, '/', i.y) str, i.flg,
i.x - (i.x - i.nx)/2 cx,
i.y - (i.y - i.ny)/2 cy,
ROW_NUMBER() OVER (ORDER BY flg, random()) rn
FROM (SELECT 2 flg, b.x + move_x x, b.y + move_y y, b.x nx, b.y ny
FROM moves,
(SELECT CAST(SUBSTRING(p FROM '^\d+') AS INTEGER) x,
CAST(REGEXP_REPLACE(p, '^\d+/', '') AS INTEGER) y
FROM (SELECT UNNEST(r.path) p) pb) b
WHERE r.action > 0
UNION ALL
SELECT 0 flg, 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 1, NULL, NULL, NULL, NULL
WHERE r.action = 0
) i
WHERE i.flg = 1 OR
(NOT CONCAT(i.x, '/', i.y) = ANY(r.path) AND
i.x > 1 AND i.y > 1 AND i.x < size_x AND i.y < size_y)
) s
WHERE s.rn = 1
)
SELECT STRING_AGG (c, '' ORDER BY x) maze
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
ORDER BY y;
壁伸ばし法
壁伸ばし法のイメージ図です。ランダムに選ばれた未接続の壁A1から進んでいきB1で外周に衝突して終了、次にまたランダムに選ばれた未接続の壁A2から出発しB2で既存の壁に到達して終了しています。進む条件としては、ループを回避するため現ラウンドで継続して伸ばしている壁に接続することはできません。そのため袋小路に入った場合は、ラウンドを捨ててやり直します。これを繰り返し未接続の壁(X)がなくなると迷路が完成します。
PL/SQL版（参考）
まずは、PL/SQL版です。穴掘り法と同じ二重ループなので同じようにクエリに置換します。
PL/SQL壁伸ばし法 (開く)
壁伸ばし法と同じコレクションタイプを使用します。
壁伸ばし法（PL/SQL）
SET SERVEROUT ON
DECLARE
p_size_x number := 41; -- 横サイズ
p_size_y number := 21; -- 縦サイズ
cells maze_typ; -- 迷路セル
wallpath maze_typ; -- 壁セル保持用
scell maze_cell_typ := NULL;
pcell maze_cell_typ;
BEGIN
-- 迷路のサイズ条件 5x5以上で奇数
IF p_size_x < 5 OR mod(p_size_x, 2) = 0 OR
p_size_y < 5 OR mod(p_size_y, 2) = 0
THEN
RAISE_APPLICATION_ERROR(-20000, 'The length and width must be odd numbers of 5 or larger.');
RETURN;
END IF;
-- 奇数x奇数が壁(X)の迷路のベースを作成し、セルに展開してコレクションに格納
SELECT maze_cell_typ(
MOD(LEVEL, p_size_x) + 1,
CEIL(LEVEL / p_size_x),
CASE WHEN MOD(LEVEL, p_size_x) + 1 in (1, p_size_x) OR
CEIL(LEVEL / p_size_x) in (1, p_size_y)
THEN '#'
WHEN MOD(MOD(LEVEL, p_size_x) + 1, 2) = 1 AND
MOD(CEIL(LEVEL / p_size_x), 2) = 1
THEN 'X'
ELSE ' '
END,
LEVEL)
BULK COLLECT INTO cells
FROM DUAL CONNECT BY LEVEL <= p_size_x * p_size_y;
LOOP
-- 未接続の壁(X)のセルの内一つを開始点としてランダムに選択
-- scellがNULL以外のときはラウンドのやり直しなのでそのまま使用
IF scell.id IS NULL
THEN
BEGIN
SELECT v INTO scell
FROM (SELECT VALUE(t) v,
ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
FROM TABLE(cells) t
WHERE c = 'X')
WHERE rn = 1;
EXCEPTION WHEN NO_DATA_FOUND THEN EXIT;
END;
END IF;
wallpath := maze_typ(scell); -- 伸ばした壁に開始点をセットしてリセット
LOOP
-- 今回のラウンドで倒した壁のセル以外で上下左右のいずれかのセルにランダムに選択
BEGIN
SELECT v, value(p) INTO scell, pcell
FROM (SELECT value(t) v,
ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
FROM TABLE(cells) t
WHERE
NOT value(t) MEMBER OF wallpath AND -- 伸ばし中の壁への到達は禁止
(t.x, t.y) IN ((scell.x + 2, scell.y), (scell.x - 2, scell.y), -- 二つ隣のセル
(scell.x, scell.y + 2), (scell.x, scell.y - 2))
) n,
TABLE(cells) p
WHERE rn = 1 AND
p.x = scell.x + (n.v.x - scell.x)/2 AND -- 移動する方向の一つ隣のセル
p.y = scell.y + (n.v.y - scell.y)/2;
EXCEPTION WHEN NO_DATA_FOUND THEN -- 袋小路にはいったため進めず
scell := wallpath(1); -- スタート地点に戻る
wallpath := maze_typ(); -- 伸ばした壁を削除してEMPTYに
EXIT; -- やり直すためにラウンドを終了
END;
-- 伸ばした壁を一時的に保存
wallpath.EXTEND(1);
wallpath(wallpath.LAST) := pcell;
wallpath.EXTEND(1);
wallpath(wallpath.LAST) := scell;
EXIT WHEN scell.c <> 'X'; -- 既存の壁に到達
END LOOP;
-- wallpathがEMPTYならやり直し
-- 伸ばした壁が確定なら迷路(cells)を更新
IF wallpath IS NOT EMPTY
THEN
FOR i IN 1 .. wallpath.count
LOOP
cells(wallpath(i).id).c := '#';
END LOOP;
scell := null; -- 新規スタート
END IF;
END LOOP;
-- 行ごとにまとめて迷路図を出力
FOR i IN (SELECT y, LISTAGG (c) WITHIN GROUP (ORDER BY x) l
FROM TABLE(cells)
GROUP BY y
ORDER BY y)
LOOP
DBMS_OUTPUT.PUT_LINE(i.l);
END LOOP;
END;
/
単一クエリ(Oracle)版
壁伸ばし法でクエリを作る時問題となるポイントはなんといっても袋小路に入ったときのロールバックでしょう。これは、確定した壁のカンマ区切り文字列(path)と未確定の壁のカンマ区切り文字列(turn)を別に保持し、壁が確定した時に未確定壁を確定壁に追加することで実現します。袋小路に入った場合は、未確定壁を捨ててやり直します。
壁伸ばし法(Oracle12c）
WITH
-- 外壁が'#'、未接続壁が'X'の迷路の土台
cells (x, y, c)
AS (SELECT MOD(LEVEL, size_x) + 1,
CEIL(LEVEL / size_x),
CASE WHEN MOD(LEVEL, size_x) + 1 in (1, size_x) OR
CEIL(LEVEL / size_x) in (1, size_y)
THEN '#'
WHEN MOD(MOD(LEVEL, size_x) + 1, 2) = 1 AND
MOD(CEIL(LEVEL / size_x), 2) = 1
THEN 'X'
ELSE ' '
END
FROM (SELECT 51 size_x, 21 size_y FROM DUAL) -- 迷路サイズ
CONNECT BY LEVEL <= size_x * size_y
),
-- 次に進むセルが外壁または既存壁であれば、Action = 1をセットし、次レベルで未接続のスタートセルを取得
-- 袋小路に入った場合は、そのまま未接続のスタートセルを取得し、現ラウンドの壁を捨てる
-- path 確定壁、turn 未確定（現ラウンド）壁、path2 確定接続壁、tunr2 未確定接続壁
mazewall (n, x, y, action, path, turn, path2, turn2)
AS (SELECT 1, TO_NUMBER(NULL), TO_NUMBER(NULL), 1, -- 一行目はダミー
CAST(',' AS VARCHAR2(4000)), CAST(',' AS VARCHAR2(4000)),
CAST(',' AS VARCHAR2(4000)), CAST(',' AS VARCHAR2(4000))
FROM DUAL
UNION ALL
SELECT n + 1, s.x, s.y,
s.wallhit, -- 壁接続でActionフラグをセット
DECODE(s.wallhit, 0, r.path, r.path || substr(r.turn, 2)), -- 壁接続で壁を確定
CASE WHEN s.wallhit > 0 THEN '' -- 壁接続でラウンドを終了
WHEN s.flg > 0 THEN ',' || s.x || '/' || s.y || ',' -- ラウンドスタート
ELSE r.turn || s.x || '/' || s.y || ',' -- 壁を現ラウンドに追加
END,
DECODE(s.wallhit, 0, r.path2, r.path2 || substr(r.turn2, 2) || s.cx || '/' || s.cy || ','),
DECODE(s.flg, 0, r.turn2 || s.cx || '/' || s.cy || ',', ',')
FROM mazewall r,
LATERAL (SELECT x, y, -- 進む先のセル
x - (x - px)/2 cx, -- 進む方向の接続セル
y - (y - py)/2 cy,
flg, -- 継続/0、新規/1
wallhit, -- 進む先が壁でない0、壁/1
ROW_NUMBER() OVER (ORDER BY flg, DBMS_RANDOM.VALUE) rn -- 継続壁伸ばしを優先
FROM (
-- 現在位置からの継続壁伸ばし(flg=0)
-- 外壁や既存壁に接続した場合は、wallhitをセット
SELECT c.x, c.y, r.x px, r.y py, 0 flg,
CASE WHEN c.c = '#' OR -- 外壁
r.path LIKE '%,' || c.x || '/' || c.y || ',%' -- 既存壁
THEN 1 ELSE 0
END wallhit
FROM cells c
WHERE r.action = 0 AND -- 前レベルで既存の壁に接続していない（継続伸ばし）
r.turn NOT LIKE '%,' || c.x || '/' || c.y || ',%' AND -- 現ラウンドの壁に接続不可
(c.x, c.y) IN ((r.x + 2, r.y), (r.x - 2, r.y), (r.x, r.y + 2), (r.x, r.y - 2)) -- 現在位置からの上下左右
UNION ALL
-- 新規の未接続の壁の選択(flg=1)
SELECT c.x, c.y, c.x, c.y, 1, 0
FROM cells c
WHERE c.c = 'X' AND
r.path NOT LIKE '%,' || c.x || '/' || c.y || ',%' -- 既存の壁は選択から除外
)
) s
WHERE s.rn = 1
)
CYCLE n SET cycle TO 1 DEFAULT 0,
pcells -- カンマ区切り壁リストの展開
AS (SELECT REGEXP_SUBSTR(path, ',(\d+)/(\d+)', 1, LEVEL, '', 1) x,
REGEXP_SUBSTR(path, ',(\d+)/(\d+)', 1, LEVEL, '', 2) y,
REGEXP_SUBSTR(path2, ',(\d+)/(\d+)', 1, LEVEL, '', 1) cx,
REGEXP_SUBSTR(path2, ',(\d+)/(\d+)', 1, LEVEL, '', 2) cy
FROM (SELECT path, path2
FROM (SELECT ROW_NUMBER() OVER (ORDER BY n DESC) rn, path, path2
FROM mazewall
)
WHERE rn = 1
)
CONNECT BY LEVEL <= REGEXP_COUNT(path, ',') - 1
)
SELECT LISTAGG (c) WITHIN GROUP (ORDER BY x) maze
FROM (SELECT c.x, c.y, NVL2(p.x, '#', c.c) c
FROM cells c,
(SELECT x, y FROM pcells UNION SELECT cx, cy FROM pcells) p
WHERE c.x = p.x (+) AND c.y = p.y (+)
)
GROUP BY y
ORDER BY y;
MAZE
----------------------------------------------------------
###################################################
# # # # # #
# # ##### # ### ### # ### # # ######### # # ##### #
# # # # # # # # # # # # # # #
# ####### ##### ### ##### # ##### ####### # ##### #
# # # # # # # # # # # # # #
# ####### ##### # # ### ### ### ### # # ####### # #
# # # # # # # # # # # # #
### # ##### ### ### ##### # ####### ### # ### # # #
# # # # # # # # # # # #
### ######### ### # ####### ####### ##### ####### #
# # # # # # # # # # #
# ##### ### ##### ### ### ### # # # ### # ##### ###
# # # # # # # # # # # # # #
# ### ##### # # ### # ##### # ### ######### # ### #
# # # # # # # # # # # # #
### # ####### ########### # ### ### ### ### # # # #
# # # # # # # # # # # #
# ### # ### ### ####### # ##### ### # ### ### # # #
# # # # # # # # # # #
###################################################
21 rows selected.
Elapsed: 00:00:02.82
PostgreSQL版
壁伸ばし法(PostgreSQL)
WITH RECURSIVE
cells (n, x, y, c)
AS (SELECT 1, 1, 1, '#'
UNION all
SELECT n + 1, MOD(n, size_x) + 1, CAST((n / size_x) + 1 AS INTEGER),
CASE WHEN MOD(n, size_x) + 1 in (1, size_x) OR
(n / size_x) + 1 in (1, size_y)
THEN '#'
WHEN MOD(MOD(n, size_x) + 1, 2) = 1 AND
MOD((n / size_x) + 1, 2) = 1
THEN 'X'
ELSE ' '
END
FROM (SELECT 51 size_x, 21 size_y) msize, cells
WHERE n < size_x * size_y
),
mazewall (n, x, y, action, path, turn, path2, turn2)
AS (SELECT 1, cast(NULL as integer), cast(NULL as integer), 1,
'{}'::text[], '{}'::text[], '{}'::text[], '{}'::text[]
UNION ALL
SELECT n + 1, s.x, s.y,
s.wallhit,
CASE WHEN s.wallhit = 0 THEN r.path
ELSE r.path || r.turn
END,
CASE WHEN s.wallhit > 0 THEN NULL
WHEN s.flg > 0 THEN ARRAY[CONCAT(s.x, '/', s.y)]
ELSE r.turn || CONCAT(s.x, '/', s.y)
END,
CASE WHEN s.wallhit = 0 THEN r.path2
ELSE r.path2 || r.turn2 || CONCAT(s.cx, '/', s.cy)
END,
CASE WHEN s.flg = 0 THEN r.turn2 || CONCAT(s.cx, '/', s.cy)
ELSE NULL
END
FROM mazewall r
CROSS JOIN LATERAL (
SELECT i.x, i.y, i.x - (i.x - i.px)/2 cx, i.y - (i.y - i.py)/2 cy,
flg, wallhit,
ROW_NUMBER() OVER (ORDER BY flg, RANDOM()) rn
FROM (
SELECT c.x, c.y, r.x px, r.y py, 0 flg,
CASE WHEN c.c = '#' OR
CONCAT(c.x, '/', c.y) = ANY(r.path)
THEN 1 ELSE 0
END wallhit
FROM cells c
WHERE r.action = 0 AND
NOT CONCAT(c.x, '/', c.y) = ANY(r.turn) AND
(c.x, c.y) IN ((r.x + 2, r.y), (r.x - 2, r.y),
(r.x, r.y + 2), (r.x, r.y - 2))
UNION ALL
SELECT c.x, c.y, c.x, c.y, 1, 0
FROM cells c
WHERE c.c = 'X' AND
NOT CONCAT(c.x, '/', c.y) = ANY(r.path)
) i
) s
WHERE s.rn = 1
),
pcells
AS (SELECT CAST(SUBSTRING(p FROM '^\d+') AS INTEGER) x,
CAST(REGEXP_REPLACE(p, '^\d+/', '') AS INTEGER) y,
CAST(SUBSTRING(p2 FROM '^\d+') AS INTEGER) cx,
CAST(REGEXP_REPLACE(p2, '^\d+/', '') AS INTEGER) cy
FROM (SELECT UNNEST(path) p, UNNEST(path2) p2
FROM (SELECT path, path2
FROM (SELECT ROW_NUMBER() OVER (ORDER BY n DESC) rn, path, path2
FROM mazewall
) a
WHERE rn = 1
) b
) c
)
SELECT STRING_AGG (c, '' ORDER BY x) maze
FROM (SELECT c.x, c.y, CASE WHEN p.x IS NOT NULL THEN '#' ELSE c.c END c
FROM cells c
LEFT JOIN (SELECT x, y FROM pcells
UNION
SELECT cx, cy FROM pcells) p
ON c.x = p.x AND c.y = p.y
) g
GROUP BY y
ORDER BY y;
おわりに
ラテラル句や副問合せの多段飛び参照という比較的新しい機能を再帰内で使用すると再帰のルールである「再帰自身を再帰内のサブクエリから呼んではいけない」（PostgreSQLにはない？）や「再帰自身が再帰内で二度以上現れてはいけない」等によるクエリの行動制限をかなり回避できるようになります。またラテラル句の中でUNIONを使用して処理を意図的に分岐させることも可能であり再帰クエリが利用できる幅が大きく広がりました。これまでPL/SQLやアプリでないと制御できなかった動きがクエリ一発で済む可能性もありますね。ということで、これからもいろいろ試して行きたいと思います。
以上です。