「ホームメイロ」的脱出（迷路）ゲーム【TIC-80】 #ゲーム制作

はじめに

「VOICEゲームジャム3」に「HOMEMAZE」というゲームを「TIC-80」で制作して参加しました。

知りたいこと

今回作成した迷路（グラフ？）に一般的な呼称、名称はあるか？
作成の仕方にセオリーはあるか？

以前に「オートタイル」「シーン遷移」という言葉を知らなかったために効率的な調査ができず、有用な情報にたどり着くのに苦労したため、今回のものも何かちゃんとした呼び方があるものと思っています。

「ホームメイロ」とは

ドラえもんのひみつ道具の一つ。
回転すると家が迷路のようになる。
（外から見た）広さは変わらないが接続がむちゃくちゃになり、実質的な部屋数増加？
（「どこでもドア」や「タケコプター」ほどメジャーではないですが、
　それなりに有名、と自分では思っていますが知名度はどの程度なんでしょうか？）

ホームメイロ的迷路の特徴（制約?、ルール?）

ランダムで自動生成
生成後の接続は固定
ペアとなる接続要素は固定（右 ⇔ 左、上 ⇔ 下など）
接続は双方向（逆にたどれば元の場所に戻る）
（露骨な）行き止まりはない（スタートとゴール以外は2以上の接続が存在）
空間的整合性はない（右→下、下→右、で同じ部屋に行くとは限らない）

元ネタの「ホームメイロ」の仕様を再現しているとは言えませんが、エッセンスをなんとなくは取り入れたつもりです。
一般的な迷路より制約は小さいけど、「正しい道でなければスタートに戻る（1対多、一方通行の接続）」なども含む「迷いの森」的な迷路よりは制約がきびしいものでしょうか？

（今回のゲームでの）作成手順

知識不足と検索力不足で同様の迷路の制作方法が分からなかったため以下我流です。

基本

上記を基本として、スタート[0]とゴール['G']以外の部屋をコピーして増やして、ランダムに接続します。

接続を抽出

ランダムで接続の組を選択

選択された組に応じて部屋の接続を設定する

例えば上のように上３、下５が選ばれた場合、部屋番号3の上の接続先を5、部屋5の下接続先を3に設定します。

すべての組を処理すると以下のような迷路ができます。

ダメなパターン

このような生成方法でいいかというとそうではなく、ダメなパターンが存在します。
基本のレベル1でも以下のようなものがあります。

スタート直ゴール

スタート-ゴールの接続を禁止したとしても

こんな感じに。4部屋ではまあ妥当とも言えますが、極端に短い場合はあるでしょう。

ゴールできない

ゴール不可能なことをプレイヤーに判断させる、というのもアリかも知れませんが、なるべくなら避けたい。自分自身に接続しているのが良くないということでこれを禁止したとして‥‥

うーん、やっぱりゴールできない場合はあります。

とりあえず、ゴールには到達できるように作成手順を考える？
すべての部屋に到達するようにするべきか？（クラスタリング？）
手順を途中まで戻す？差し替える？

‥‥‥

よく分からないし面倒くさい！

とりあえず、できた迷路をチェックするのはそれほど難しいものではないらしい。（検索できた！）
「全探索アルゴリズム入門」を参考に迷路をチェックする処理を書く。
日本語で手順がまとめられていてわかりやすかったです。（筆者はLuaしか知りません）

というわけで方針が決まりました。

適当（ランダム）に作らせる
解いてみる（チェックする）
ゴール不可だったり、ゴール手順がある程度以上でなければ最初から作り直させる

適切な手順や方針をあたえずに気に入らなければ最初から。
リアルではちょっと人にさせるには躊躇するようなこともコンピュータ相手ならできてしまう
（ごめんよ「TIC-80」）
富豪プログラミングというよりブラック企業プログラミングですね、これは‥‥

以下、実際のコードです。

homemaze.lua

LV=2
U,D,L,R=1,2,3,4 -- direct num
TYPE={ -- room type
    [0]={false,false,false,true},
    {false,true,true,true},
    {false,true,true,false},
    {true,false,false,true},
    {true,false,true,true},
    ['G']={false,false,true,false}
    }
ran=math.random
ins,rem=table.insert,table.remove

function makemaze(lv,seed)
    lv=lv or LV
    if seed then math.randomseed(seed) end
    local connect={[U]={},[D]={},[L]={},[R]={}}
    local rooms={[0]={tn=0},['G']={tn='G'}}

    for rn=1,lv*#TYPE do
        rooms[rn]={tn=(rn-1)%#TYPE+1}
    end
    for rn,t in pairs(rooms) do
        for dir=1,4 do
            if TYPE[t.tn][dir] then
                ins(connect[dir],rn) end
        end
    end

    -- conncet U and D, L and R
    for i=1,3,2 do
        for cn=1,#connect[i] do
            local rn=connect[i][cn]
            local pn=rem(connect[i+1],ran(#connect[i+1]))
            rooms[rn][i]=pn
            rooms[pn][i+1]=rn
        end
    end
    return rooms
end

function chkmaze(rms)
    local visit={}
    local chk={}
    local now,num=0,0
    ins(chk,0)
    while(#chk>0)do
        now=rem(chk,1)
        if now=='G' then return num end
        for d=1,4 do
            local nx=rms[now][d]
            if nx and not visit[nx] then
                    ins(chk,nx)
            end
        end
        visit[now]=true
        num=num+1
    end
    return false
end

function init(lv)
    nlv=lv or LV
    repeat
        rooms=makemaze(nlv)
        cnt=chkmaze(rooms)
    until(cnt and cnt>nlv*2)
end

このような感じで最適化とはほど遠いですが、LV=1000（4000部屋+start+goal）の迷路だと一瞬。
LV=10000（4万部屋+2）だとnativeで7～8秒、html(javascript）版で20数秒（途中で重くなってるよ的な警告）。
グローバル変数をローカル変数に、テーブルの識別子を整数に限定したりするともう少し速くなるでしょうか。
部屋タイル指定を考慮に入れて、ゴールの部屋番号は'G'ではなく'-1'の方が良かったです。
（5番目に配置してしまい、気軽に部屋のタイプを増やせなくなってしまった）
seedも結局使ってないし‥。

部屋の表示は当初は以下のように「迷いのずんだ森」のような感じでした。

まあこれではあまりに味気ない（というかずんだ味しかしない）ため、冒頭のように東北家としました。

まとめ

そういう迷路は一般的には○○と呼ぶよ
効率的な作成方法は～～辺りを調べればわかるんじゃないかな

といったものがありましたら、教えて下さい！

反省点、改良、発展

いきあたりばったりで効率、拡張性ともに乏しいコーディングになってしまった
東西南北昇降、など接続の種類ペアを増やす
部屋のタイプももう少し増やす（4つはやはり少なかった）
対応する接続のペアさえ同数ならいいので、その中でタイプの偏りを指定可能に
Unityで3D？VR？（そもそも使えない上、面白くなるかは不明、絶望感は上がるかも）