読者です 読者をやめる 読者になる 読者になる

ありがちなパズルゲームのアルゴリズムを考えよう

ショートコーディング

f:id:carrot_boy:20170312084913p:plain

(画像をクリックするとデモページにとびます)

ありがちなパズルゲームを作ってみました。絵をそろえて、絵を消していくゲームですね。こうゆうゲームの醍醐味である絵が消えた後、新しい絵がスライドして落ちてくるアニメーションは作れませんでした。作り方がわからなかったので。ちゃんとしたゲームを作ることは置いておいて、こうゆうゲームって絵を消す時にどの絵を消すのか計算するアルゴリズムが必要だと思います。そのアルゴリズムを考えてみたいと思います。

まずはゲームのルールの説明から

  • たて、よこ、どちらかで3枚以上同じ絵が並んでいるものを消す。
  • 絵の種類は4種類。
  • 5×5で絵を並べる。

以上です。

こうやって考えてみよう

 4種類の絵を数字で表します。その数字を表に書いていきます。

f:id:carrot_boy:20170312103925p:plain

こんな感じで。

その次にある行を一つの文字列としてみてください。1行目なら「12223」ですね。種類「1」が消えるパターンは、

「11111」,「1111」,「111」

です。このパターンが対象の行に含まれていれば、その行に消える絵があります。 対象の行に消える絵があるかだけではなくて、消える場所も知りたいのでパターンをすべて書き出します。1行目の場合、

「12223」,「1222」,「2223」,「122」,「222」,「223」

このパターンに一致した場合、1つ目はすべて消える、2つ目は最初から4つ目まで消える、というように場所もわかります。ただこの場合、「222」しか該当しません。種類「1」だけでなく、種類「2」,「3」,「4」の場合も調べ、さらに1行目だけでなく5行すべて調べ、さらによこだけでなく、たてもありますので、列についても調べます。調べる回数は、

(1行あたりの比較) 6 × (4種類) 4 × (5行) 5 × (列の場合もあるので) 2 = 240 (回)

のようになります。このように計算して、消える対象の絵の場所は1、消えない絵の場所は0で表した表を作ります。

f:id:carrot_boy:20170312103938p:plain

プログラムを書いてみる

 

さっき説明した手順をjavascriptでプログラムにしてみると、こうなります。

感想

5 × 5のパズルの場合、簡単に計算できます。パターンもすぐにすべて書き出せますので。n × nのパズルになると、考えるのが大変そうですね。