AIに任せたMAZE MAZEの実装を、自分で読み解く

MAZE MAZEという、2人で同じ迷路を同時に解くブラウザゲームを公開した。

ただ、実装はほとんどAIに任せた。動くものはできたけれど、自分で仕組みを説明できるかと聞かれると怪しい。それでは作ったと言い切りにくいので、この記事では実際のコードを読みながら、MAZE MAZEがどう動いているのかを自分なりに整理する。

まず全体像

登場するものは大きく4つある。

プレイヤーAのブラウザ ─┐
                       ├─ WebSocket ─ MatchRoom Durable Object
プレイヤーBのブラウザ ─┘                    │
                                            ├─ 対戦状態を保存
                                            ├─ 軌跡を中継
                                            └─ ゴール経路を検証

ランダム対戦を選んだブラウザ
        └─ WebSocket ─ Matchmaker Durable Object
                              └─ 2人へ同じmatch IDを渡す

画面はReact、迷路の描画と入力はCanvas 2D、通信はWebSocketで実装されている。サーバーはCloudflare Workersで動き、対戦ルームとランダムマッチングにはDurable Objectsを使っている。

Durable Objectは、特定のIDに対する処理を1か所へ集められる仕組みだ。 MAZE MAZEではmatch IDから1つのMatchRoomを決めるため、同じ対戦へ参加した2人の接続と勝敗判定が同じ場所に集まる。

同じ迷路をどうやって2人へ渡すのか

最初は、サーバーが迷路全体をJSONで送っているのだと思っていた。実際には、サーバーが送るのは主にseedと迷路の縦横サイズだけだった。

迷路生成関数は、同じseedを渡すと必ず同じ迷路を返す。

const maze = generateMaze(seed, width, height)

ブラウザとWorkerは同じgenerateMazeを共有している。ブラウザは受け取ったseedから表示用の迷路を作り、Workerもゴール判定をするときに同じseedから検証用の迷路を作る。

つまり、通信しているのは完成した迷路ではなく「同じ迷路を作るためのレシピ」だ。

seedは1人目が待っている間は公開されない。 2人の接続が揃って対戦状態がrunningになったとき、初めて両方へ送られる。先に接続した人だけが迷路を見て考える時間を持たないための処理になっている。

迷路はどう作られるのか

各マスは、上下左右のどこへ移動できるかを4bitの数値で持っている。

NORTH = 1 // 0001
EAST  = 2 // 0010
SOUTH = 4 // 0100
WEST  = 8 // 1000

例えば東と南が開いているマスは2 | 4で6になる。移動するときは、現在のマスに目的の方向のbitが立っているかをcanMoveで確認する。

生成にはランダム化Prim法が使われている。通路がまだつながっていないマスを候補へ追加し、その中からseed付き乱数で1つずつ選んで接続していく。すべてのマスがつながり、途中で輪ができないため、スタートからゴールまでの経路は1つになる。

ゴールは適当に置くのではなく、スタートから幅優先探索して最も遠いマスが選ばれる。さらに、1つのseedにつき12種類の候補を生成し、次のような要素から難易度を計算して、一番スコアが高い迷路を採用している。

正解経路の長さ
分岐を選ぶ地点の数
間違った枝道の数
曲がる回数
行き止まりの数

ランダム生成した結果をそのまま使うのではなく、遊びごたえがある候補を選び直していた。

指やマウスの線をどうやって経路にするのか

Canvas上では滑らかな線を描いているが、ゲームの判定に使うのはピクセル座標ではなく、通過したマスの配列だ。

[
  { x: 0, y: 3 },
  { x: 1, y: 3 },
  { x: 1, y: 4 },
]

Pointer Eventの座標をCanvasの大きさで割り、迷路上の座標へ変換する。イベントは必ずしも細かく発生するとは限らないので、前回の点と今回の点の間を補間しながら、壁を飛び越えていないか確認している。

次のマスへ移動したときはcanMoveで通路があるかを調べる。壁へ少し触れただけなら160msの猶予があり、通路へ戻せば続行できる。指を離した場合も、それまでの経路は消えず、線の先端付近から再開できる。

タッチ操作では指で進行方向が隠れるため、現在位置を拡大するルーペも別のCanvasで描画している。さらに、どちらかのプレイヤーがタッチ端末なら、通常の21×15ではなく13×9の迷路をサーバー側で選ぶ。 2人が別のサイズの迷路を見ることがないように、端末ごとではなく対戦単位で決めている。

リアルタイムで何を送っているのか

相手の線をリアルタイム表示するために、ポインターの座標を毎フレーム送っているわけではない。送るメッセージは、マスへ入ったときのstart、moveと、やり直したときのresetだけだ。

{ v: 1, type: "trace", action: "move", cell: { x: 4, y: 7 } }

Workerは受け取った移動が直前のマスと本当につながっているかを確認してから、もう一方のプレイヤーへ中継する。そのため、通信量はマウスの細かな動きではなく「何マス進んだか」に近くなる。

v: 1は通信プロトコルのバージョンだ。クライアントとサーバーのメッセージはTypeScriptの型として定義されているが、ネットワークから来るデータは信用できないので、受信時にはJSONの形も検証している。

なぜDurable Objectsなのか

通常のWorkerは、リクエストごとに同じ実行場所へ届くとは限らない。一方、対戦ゲームでは「今は何人いるか」「もう勝者が決まったか」という状態を2人で共有する必要がある。

MAZE MAZEでは、match IDから次のように対戦専用のDurable Objectを取得している。

const room = env.MATCHES.get(env.MATCHES.idFromName(matchId))

同じmatch IDは同じMatchRoomへ届く。そこでWebSocket、参加者、seed、開始時刻、勝者などをまとめて管理する。

対戦状態は次のように変わる。

waiting ── 2人接続 ──> running ── 有効な経路を受信 ──> finished

Durable Object内では同じルームの処理が順番に行われるため、ほぼ同時に2人がゴールしても、先に有効な経路を処理した側だけが勝者になる。

ゴール判定をクライアント任せにしない

ゴールへ着くと、ブラウザは通過した全マスをfinishメッセージとして送る。

Workerはseedから迷路を再生成し、受け取った経路について次を確認する。

最初のマスがスタートである
最後のマスがゴールである
すべての移動が隣り合うマスへの移動である
各マスの間に通路が存在する

検証を通った最初のプレイヤーが勝者になる。画面側で「ゴールした」と表示するだけではなく、最終結果はサーバー側で決めている。

ただし、これは完全な不正対策ではない。対戦開始後はseedがブラウザへ渡るので、改造したクライアントなら迷路を自動で解いて、正しい経路をすぐ送ることもできる。現在のサーバーが保証しているのは「壁を越えていない正しい経路であること」であって、「人間が実際に線を引いたこと」ではない。

身内や気軽なオンライン対戦には十分だが、ランキングや賞品を付けるなら、入力時間の検証など別の対策が必要になる。

ランダムマッチングは対戦ルームと分かれている

ランダム対戦には、全員が接続するMatchmakerという別のDurable Objectを使う。

1人目にはqueuedを返して待機させる。 2人目が接続するとランダムなmatch IDを作り、両方へmatchedとして送る。ブラウザは受け取ったIDのURLへ切り替え、その後は通常のMatchRoomへ接続する。

Matchmakerは「2人を組み合わせるところ」までしか担当しない。実際のゲーム状態はmatch IDごとに分かれたMatchRoomが担当するため、役割が混ざらない。

Hibernation APIと有効期限

WebSocketはDurable ObjectsのHibernation APIで受け付けている。接続情報はWebSocketのattachmentへ保存されるため、Durable Objectがメモリ上で休止しても、次のメッセージで接続状態を復元できる。

使われなくなった部屋を残し続けないように、alarmで有効期限も設定されている。

マッチング待機: 2分
対戦相手待ち: 1時間
対戦中: 2時間
対戦終了後: 24時間

期限になると接続を閉じ、保存した状態を削除する。

テストで何を保証しているのか

迷路単体のテストでは、同じseedから同じ迷路ができること、必ず解けること、壁を越えた経路を拒否することを確認している。

Workerのテストでは、実際に2つのWebSocketを接続して、次の流れを通している。

2人が同じ迷路で開始する
待機中はseedが見えない
3人目は参加できない
不正な軌跡は中継しない
正しい経路を最初に送った人が勝つ
2人が希望すると別のseedで再戦する
タッチ端末がいる場合は迷路を小さくする
ランダム待機中の2人へ同じmatch IDを渡す

見た目だけでは分からないサーバー側の約束を、テストで固定している。

読み解いて分かったこと

最初は「WebSocketで座標を送り合うゲーム」くらいに考えていた。コードを読むと、重要なのは座標のリアルタイム送信より、次の3点だった。

seedを共有し、同じデータを両側で再現する
リアルタイム通信では必要最小限の通過セルだけを送る
最終的な勝敗はサーバーが同じ迷路を再生成して検証する

Durable Objectsも、単にCloudflareの機能を使っているのではなく、「1つの対戦を1つの状態管理単位にする」ために合っている。

AIに実装を任せると、完成までの速度はかなり上がる。一方で、動いたことと理解したことは別だった。今回のように、データがどこで作られ、何が通信され、どこを信用しているのかを順番に追うと、ようやく自分の中でも仕組みがつながった。

ソースコードは現在、非公開のGitHubリポジトリで管理している。ゲーム本体はこちらから遊べる。