ダブル配列のゲーム作った

本記事は「データ構造とアルゴリズム Advent Calendar 2020」の22日目の記事です。

突然ですけど、Typescript+PIXI.jsでダブル配列のゲームを作りました。
https://kampersanda.github.io/xchecker/app/

ゲーム名はXChecker¹っていいます。与えられたトライ木から隙間なく要素を配置してダブル配列を構築する（たぶんパズル）ゲームです。²

ちょっとフロントエンドな何かを作って遊んでみたくなったのが動機で、なぜダブル配列？と聞かれると宗教上の理由です。

ところで、トライ木やダブル配列に関しては素晴らしい解説がたくさん存在してます。今年のアドカレでも10日目に@Naughieさんが非常に詳しい解説を書いてくださってます。他にも調べたら出てくると思います。

ということで、本記事ではトライ木やダブル配列について改めて解説したりはせず、ゲームの説明に終始します。このアドカレの趣旨に沿わなかったらごめんなさい。

でもゲームのルール自体がダブル配列のデータ構造なので、ゲームがクリアできた人はダブル配列を完全に理解したと自称してもいいんじゃないんでしょうか（自己責任）

以降では、トライ木やダブル配列は知っていただいているものとして、ゲームを簡単に説明します。ただゲーム自体はものすごくシンプルなので、読まなくてもダブル配列を知らなくても遊べると思います。

ゲーム説明

「与えられたトライ木からダブル配列を構築すること」は、すなわち「ノードを BASE & CHECK 配列に配置すること」です。XCheckerはランダムに生成されたトライ木を幅優先で辿り、衝突しないようにノードを配置していくゲームです。ただし、最終的に空き要素がないことがクリア条件です。³

下の図を見てください。ゲームは BASE & CHECK の先頭の要素に根ノードが配置されているところから始まり、その子ノードが配置できる要素を探します。このとき、枝ラベルの有無を表す配列が与えられます。図では文字 {a,b} をラベルに持つので、a と b に ✔︎ が入った配列が与えられます。そして ✔︎ が入った要素が衝突しないような BASE & CHECK の位置を探します。⁴

とりあえず、枝ラベル配列の先頭が要素 1 にくるように右に一つズラすことで ✔︎ が衝突しなくなるので、そこで下キーを押すと下図のようにノードを配置できます。a の子は要素 1 に、b の子は要素 2 に配置されているのが分かります。ただし、枝ラベル配列は BASE & CHECK 配列の内側しか移動できないので注意してください。

続いて a の子に移動し、同じように空き要素を探してノードを配置していきます。

うまく全てを配置できれば、以下のような結果になります（この一通りではないです）。

空き要素を生まないように配置できなければゲームオーバーです。また、時間に応じてスコアがでます。上は時間がかかりすぎてるので「まるで二乗時間」です。

3秒以内に配置できれば「まるで定数時間」です。定数時間出せたらすごいです。

あとHardモードも用意してます。これの定数時間は多分無理です。

感想

何か新しい言語やツールに入門するのはやっぱり楽しいです。

ただこのゲームについては、結局いい感じのトライ木が与えられるのを待つ運ゲーになってしまった感じです。でもダブル配列ってそういうものなのかもしれません。⁵

あとキーの操作性があまりよくないです。深く押し込むタイプのキーボードではちょっとストレスです。ソースもすごく汚いので、いつか整理したい（しない）

参考にしたサイト

• Learning Pixi: https://github.com/kittykatattack/learningPixi
• 初心者による超初心者のためのPixiJS入門: https://qiita.com/chiisanwo/items/f22caabc89ed8a6c41de

1. 論文内で、配列の空いた要素を探す関数がXCHECKと名付けられていることに由来します。 ↩

2. 2020/12/21現在、ChromeとSafariでしか動作確認していません。 ↩

3. ダブル配列というデータ構造が空き要素を許容しないというわけではなく、あくまでこのゲーム内での条件です。また、少なくとも一通りはそういう配置ができるトライ木が与えられます。 ↩

4. この辺りのお気持ちは、情報系修士にもわかるダブル配列がとても詳しいです。 ↩

5. 実際には優れた素晴らしいデータ構造だと言う意味です。 ↩