迷路のはなし

11文字のコードひとつで、どうやって同じ迷路をもう一度作れるのでしょう？

このページの目次

迷路は短いコードからブラウザの中で作り直されます。壁や通路をブラウザが生成するので、保存済みの迷路図をダウンロードしなくても、友だちと同じ迷路で遊べます。グローバルランキングに記録を送信すると、迷路コードもその記録と一緒に保存されます。

このページでは、そのひみつであるシード、迷路コード、生成アルゴリズムを紹介します。少しだけ数学が出てきますが、気軽に読めるように書きました。

シード — 迷路のたね

迷路は乱数（ランダムな数）から作られますが、このゲームの乱数は本当のランダムではなく、シードという数から出発する疑似乱数です。同じシードから始めれば、乱数の並びはいつでもまったく同じに再現されます。

だからシードと難易度さえあれば、迷路の全体 — 壁の配置、スタート地点、ゴール地点 — がそのまま作り直せます。どの国のどんな端末で開いても、結果はビット単位で同じ。小数の誤差が入り込まないように、生成器は整数の計算だけを使っています。

迷路コードはM1-7-03NQK8N5のような形をしています。ハイフンを除くとちょうど11文字 — 先頭のM、フォーマットのバージョン1文字、難易度1文字、シード7文字、そして最後にチェック用の1文字、という構成です。

文字にはCrockford Base32という文字セットを使います。数字の0〜9と、アルファベットからI、L、O、Uを除いた大文字です。紛らわしい文字を最初から外してあるので、手で書き写したり読み上げたりしやすく、うっかりOと書いても0として解釈してくれます。小文字・ハイフン・空白も自由です。

最後の文字は、それより前の文字から決まったルールで計算したチェックサムです。よくある入力ミスを見つけるのに役立ちますが、すべての誤りを検出できるわけではありません。手で書き写す代わりに、共有リンクやQRコードを使うこともできます。

生成アルゴリズムはGrowing Tree（育つ木）です。1つのマスから出発して隣のマスへ通路を掘りながら、木のように伸びていきます。いちばん新しいマスから伸ばし続けると長く曲がりくねった通路に、どのマスからでも伸ばすと分かれ道の多い迷路になります。難易度に応じて、この2つの性質をブレンドします。

一部の難易度では、行き止まりから追加の通路を開き、輪になった道や別のルートを作ります。レベル5〜7では追加の通路を作らず、木の枝のように分かれる構造を保ちます。ループは道の選び方を変えますが、その割合がレベルごとに増え続けるわけではありません。

スタートとゴールは、経路の距離を調べて迷路の外周で互いに遠くなるように選びます。正解の道がそのレベルの目標より短ければ、最大8回作り直し、目標に届いた時点で止めます。届かなければ最後の結果を使います。どの迷路にもゴールまでの道があり、決まったルールで生成するので同じコードは同じ迷路になります。

共有リンクや印刷物のQRコードには、壁の配置全体ではなく、ページのアドレスと迷路コードが入っています。受け取った側のブラウザがコードから迷路を作り直すので、最大の60×60の迷路でも同じ11文字のコード形式で表せます。