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

MANA-DOT

PIXEL ART, PROGRAMING, ETC.

文字列置換により20行程度で実装する倉庫番ゲームのミニマム実装

文字列置換により20行程度で実装する倉庫番ゲームのミニマム実装

先日、Slack上でインタラクティブに倉庫番を遊べるhubot-slack-soukobanを作ったにてSlack上で遊べる倉庫番の紹介を行いました。 このhubotスクリプトでは文字列置換による実装を駆使して倉庫番のゲームロジック部分が20行程度で実装されており、今回はその実装について解説をします。

※このエントリは倉庫番というゲームのルールを知っている前提で書かれていますので、予めご了承ください。

コード全貌

hubot-slack-soukoban のうち、倉庫番の出力用の処理を抜いたロジック部分は以下のようになっています。

Util =
  strToMatrix: (str) -> str.split(/\n/).map((s) -> s.split(''))
  matrixToStr: (matrix) -> matrix.map((a) -> a.join('')).join('\n')
  translocateMatrix: (matrix) -> _.range(matrix[0].length).map((j) -> _.range(matrix.length).map((i) -> matrix[i][j]))
  translocateStr: (str) -> Util.matrixToStr Util.translocateMatrix Util.strToMatrix str
  flipStr: (str) -> Util.matrixToStr Util.strToMatrix(str).map(_.reverse)
  moveRight: (state) ->
    state
    .replace(/[PBg]/g, (s) -> {P: 'ap', B: 'ab', g: 'a.'}[s])
    .replace(/(a?)p(a?)b(a?)\./, '$1.$2p$3b')
    .replace(/(a?)p(a?)\./, '$1.$2p')
    .replace(/a[pb\.]/g, (s) -> {ap: 'P', ab: 'B', 'a.': 'g'}[s])

class SoukobanGame
  constructor: (@state) -> @work = 0
  isClear: -> !(/[gP]/.test @state)
  updateState: (newState) ->
    if newState isnt @state
      @state = newState
      @work = @work + 1
  right: -> @updateState Util.moveRight @state
  up: -> @updateState Util.translocateStr Util.flipStr Util.moveRight Util.flipStr Util.translocateStr @state
  down: -> @updateState Util.translocateStr Util.moveRight Util.translocateStr @state
  left: -> @updateState Util.flipStr Util.moveRight Util.flipStr @state

改行を抜かすと23行です。見やすさのための改行も消せば20行切る程度のコード量です。

解説

コードはユーティリティオブジェクトUtilと、SoukobanGameクラスからなっています。 SoukobanGameクラスは以下の様な文字列を初期状態としてコンストラクタで受け取ります。 そしてup、right、left、down、のメソッドを呼ぶと、フィールドに保持するこの文字列を置換します。

#########
#.......#
#.##b##.#
#.p...b.#
##bggg#.#
.#....#.#
.###..###
...####..

初期状態として与えるこの文字列は、見たまんま倉庫番のマップを表しています。 # は壁、 . は床です。 p はプレイヤー、 b は箱、 g は箱を運ぶべきゴールとなっています。 またこの文字列には出現していませんが、P はゴールに乗っている状態のプレイヤー、 B はゴールに乗っている状態の箱となっています。

rightメソッド(右方向への移動)

rightメソッドは、右に移動するメソッドです。このメソッドの実態は見ての通り Util.moveRight です。このメソッドは例えば、

#########
#.......#
#.##b##.#
#.p...b.#
##bggg#.#
.#....#.#
.###..###
...####..

という文字列を

#########
#.......#
#.##b##.#
#..p..b.#
##bggg#.#
.#....#.#
.###..###
...####..

に置換します。また、箱が右側にある場合は箱も右に移動させます。 つまりゴールとの重なりを考慮しなければ、 p. という部分文字列を .p に置換し、 pb. という部分文字列を .pb と置換します。プレイヤーや箱の右側に壁がある場合は 置換パターンにないため、特に当たり判定をしなくても、壁の方向に進むことはできません。

ゴールとの重なりを考慮しなければ、これを素直に置換すれば実装完了なのですが、ゴールとの重なりを考慮する必要があります。例えば、

#########
#.......#
#.##b##.#
#.b...b.#
##pggg#.#
.#....#.#
.###..###
...####..

という文字列は、

#########
#.......#
#.##b##.#
#.b...b.#
##.Pgg#.#
.#....#.#
.###..###
...####..

に置換されなければなりません。

このゴールとの重なりも考慮した結果が、 Util.moveRight の実装となります。

moveRight: (state) ->
  state
  .replace(/[PBg]/g, (s) -> {P: 'ap', B: 'ab', g: 'a.'}[s])
  .replace(/(a?)p(a?)b(a?)\./, '$1.$2p$3b')
  .replace(/(a?)p(a?)\./, '$1.$2p')
  .replace(/a[pb\.]/g, (s) -> {ap: 'P', ab: 'B', 'a.': 'g'}[s])

ゲームの状態を示す文字列に対して、4つの置換を行っています。

まず最初の置換

.replace(/[PBg]/g, (s) -> {P: 'ap', B: 'ab', g: 'a.'}[s])

はゴール上のプレイヤー Pap という文字列に、 ゴール上の箱 Bab に、 ゴール ga. に置換します。 察しがいい方は分かりそうですが、ゴールの有無を a という一時的な文字列に置換し、ゴールの有無+ p , b , . のどれかに統一しています。 つまり、この置換をしたあとaが直前にある文字はゴール上にあるというフラグです。

次の文字列

#########
#.......#
#.##b##.#
#.b...b.#
##.Pgg#.#
.#....#.#
.###..###
...####..

は、

#########
#.......#
#.##b##.#
#.b...b.#
##.apa.a.#.#
.#....#.#
.###..###
...####..

こう置換されます。

次とその次の置換

.replace(/(a?)p(a?)b(a?)\./, '$1.$2p$3b')
.replace(/(a?)p(a?)\./, '$1.$2p')

は、先ほど出てきた「p. という部分文字列を .p に置換し、pb. という部分文字列を .pb と置換する」ことを a の位置=マップ城のゴールの位置を維持したまま行う置換です。 例えば ap.a.p に、 paba..apab に置換されます。

#########
#.......#
#.##b##.#
#.b...b.#
##.apa.a.#.#
.#....#.#
.###..###
...####..

は、

#########
#.......#
#.##b##.#
#.b...b.#
##.a.apa.#.#
.#....#.#
.###..###
...####..

に置換されます。

最後の変換

.replace(/a[pb\.]/g, (s) -> {ap: 'P', ab: 'B', 'a.': 'g'}[s])

は、 a を元に戻す置換ですね。

#########
#.......#
#.##b##.#
#.b...b.#
##.a.apa.#.#
.#....#.#
.###..###
...####..

は、

#########
#.......#
#.##b##.#
#.b...b.#
##.gPg#.#
.#....#.#
.###..###
...####..

に置換されます。

以上の置換で、プレイヤーは無事右に移動することができました。

left, up, downメソッド

left, up, downメソッドはそれぞれ左、上、下に移動するメソッドですが、これらは右に移動させるメソッド Util.moveRight と2つのUtilメソッド flipStrtranslocateStr によって実装されています。

flipStr はマップ文字列を左右反転させるメソッドです。

#########
#.......#
#.##b##.#
#.b...b.#
##.gPg#.#
.#....#.#
.###..###
...####..

#########
#.......#
#.##b##.#
#.b...b.#
#.#gPg.##
#.#....#.
###..###.
..####...

に変換されます。

translocateStr はマップ文字列を転置させるメソッドです。

#########
#.......#
#.##b##.#
#.b...b.#
##.gPg#.#
.#....#.#
.###..###
...####..

#####...
#...###.
#.#b..#.
#.#.g.##
#.b.P..#
#.#.g..#
#.#b####
#.....#.
#######.

に変換されます。

これらの関数でマップを変形し、任意の方向を右に向けることで、どの方向への移動も右移動で実装しています。

左移動 left は左右反転してから右移動し、もう一度左右反転することで実装しています。 下移動 down は転地してから右移動し、もう一度転地することで実装しています。 そして上移動 up は、転地してから左右反転して右移動し、その後左右反転と転置をすることで実装しています。

これで四方向への移動が実装できました。

クリア判定isClear

ここまで実装すればクリア判定は簡単で、文字列にゴール g またはゴールを踏んでいるプレイヤー P が残ってないかを判定するだけです。

isClear: -> !(/[gP]/.test @state)

これで、倉庫番ゲームのメイン機能は完成です。

雑感

倉庫番の状態を文字列として表し、その文字列を置換して次の状態を作ることで倉庫番のゲームを実装する方法について紹介しました。 これは以前このブログで紹介した、 正規表現による置換の繰り返しだけでライフゲームを作る と似た話になっています。

この実装方法の楽ちんなのは、変化する部分にだけマッチさせてそこを次の状態に遷移させるという記述の組み合わせで、ゲーム全体を実装できるところです。 今回は「プレイヤーと床が隣接してる時、それらを入れ替える」と「プレイヤー→箱→床の順で並んでる時、床→プレイヤー→箱の順番に並べ替える」という2つのルールがありました。 この2つのルールを比較的素直に置換で記述してあげれば、それだけで倉庫番が作れてしまいます。

このアイデアは、うまくゲームルールにマッチする状態表現と、状態遷移の記述表現があればそのゲームが簡単に作れてしまうということだと思います。 倉庫番というゲームの表現として、普通の文字列が状態表現の記述としてうまく機能し、文字列置換が状態遷移の記述としてうまく機能していると考えられます。 文字列では限界が見えるものの、もっと多くのゲームの記述に適した表現を考え出せればすごく簡単にゲームが作れるのではないのかと思ったりします。 まあ夢なんですが。

また、上下左への移動の記述を、マップを変形させることで右移動だけで記述してサボるという技も使いました。 左はともかく、文字列でマップを表現した場合上下へのマッチングは比較的面倒です(ライフゲームの実装でも鬼門でした)。 転置して上下を左右に変えてしまうことで、ここはスマートに実装できました。

関連リンク