Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
27
Help us understand the problem. What is going on with this article?

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

突然ですけど、Typescript+PIXI.jsでダブル配列のゲームを作りました。
https://kampersanda.github.io/xchecker/app/
Playing.gif
ゲーム名はXChecker1っていいます。与えられたトライ木から隙間なく要素を配置してダブル配列を構築する(たぶんパズル)ゲームです。2

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

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

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

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

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

ゲーム説明

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

下の図を見てください。ゲームは BASE & CHECK の先頭の要素に根ノードが配置されているところから始まり、その子ノードが配置できる要素を探します。このとき、枝ラベルの有無を表す配列が与えられます。図では文字 {a,b} をラベルに持つので、a と b に ✔︎ が入った配列が与えられます。そして ✔︎ が入った要素が衝突しないような BASE & CHECK の位置を探します。4
スクリーンショット 2020-12-20 23.48.53.png
とりあえず、枝ラベル配列の先頭が要素 1 にくるように右に一つズラすことで ✔︎ が衝突しなくなるので、そこで下キーを押すと下図のようにノードを配置できます。a の子は要素 1 に、b の子は要素 2 に配置されているのが分かります。ただし、枝ラベル配列は BASE & CHECK 配列の内側しか移動できないので注意してください。

続いて a の子に移動し、同じように空き要素を探してノードを配置していきます。
スクリーンショット 2020-12-20 23.52.58.png
うまく全てを配置できれば、以下のような結果になります(この一通りではないです)。
Screen Shot 2020-12-21 at 21.24.28.png
空き要素を生まないように配置できなければゲームオーバーです。また、時間に応じてスコアがでます。上は時間がかかりすぎてるので「まるで二乗時間」です。

3秒以内に配置できれば「まるで定数時間」です。定数時間出せたらすごいです。
Screen Shot 2020-12-14 at 22.31.01.png
あとHardモードも用意してます。これの定数時間は多分無理です。

感想

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

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

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

参考にしたサイト


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

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

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

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

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

27
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
kampersanda
printf("Hello, Tokushima!\n");

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
27
Help us understand the problem. What is going on with this article?