POSTD PRODUCED BY NIJIBOX

POSTD PRODUCED BY NIJIBOX

ニジボックスが運営する
エンジニアに向けた
キュレーションメディア

本記事は、原著者の許諾のもとに翻訳・掲載しております。

High Score

恐竜は十分古いですが、Lispもかなり古いので、気が合うのではないかと思います。ここで話している恐竜とは、Google Chromeに隠れている、”There is no Internet connection”(インターネットに接続されていません)のメッセージと一緒に現れる恐竜のことです。

何について話しているのか

この記事は、Chromeの恐竜ゲームをできるようなコードをCommon Lispで書く話です( ディープラーニング は必要ありません)。

何が手元にあるのか

Common Lispでプログラミングするために、Linuxをインストールしたコンピュータの前に座っていますが、もちろんモニタも接続しています。Common Lispの環境設定は簡単で、次のものがあればできます。

  • Linuxマシン(恐竜のジャンプを見るためにスクリーンを接続)
  • SBCL (私は現在1.3.4を使っていますが、より新しいバージョンのほうが良いでしょう)
  • Chromium あるいは Google Chrome (私が今使用しているのはChromium 52.0.2743.116です)

さらに、Lispをいじれるように、私は EmacsSLIME と一緒にインストールしましたが、他のエディタでも大丈夫です。

準備はできたので始めましょう。

Lispの目

短い2本足でスクリーン上を動くかわいいものを人が見れば、恐竜と分かりますが、Lispには分かりようがありません。人はスクリーンを目で見ることができますが、それはLispにはできません。そのため、スクリーンを読むようプログラミングし、恐竜を見つけられるようにします。

スクリーンを読む

Webで検索をすると、Common Lispにはスクリーンという概念がないことを知りました。実は次の記述を見つけたのです。

……文字列を操作する基本的なライブラリしかなく、OSと対話するライブラリは ほとんどない 。歴史的な理由から、Common Lispはあたかも OSが存在しない かのように振る舞う。

「OSは存在しない」とは……。Common Lispを選ぶなんて、自分でもおかしくなってしまったのかもしれないと思ってしまいました。

しかし、上の記事が書かれた2001年5月からは15年以上も経っているので、多くのことが変わったはずです。再びいろいろと調べてみると、便利なものを見つけることができました。

  • CFFI (Common Foreign Function Interface)はCommon Lisp用のFFIです。これを使えばどんなCライブラリ(その他の外部ライブラリ)でもCommon Lispで呼び出すことができます。
  • CLX はCommon Lisp用のX Window Systemプロトコルのクライアント向けライブラリです。これを使えばX Window Systemの制御が可能になり、スクリーンを読むことができます(もし、 OS X あるいは Windows を使用している場合は、少し難しいかもしれません)。
  • burgled-batteries はPythonとLispを連携させてくれます。これを使えばPythonの関数をCommon Lispでシームレスに呼び出すことができます。

実際には たくさんのライブラリ が存在していますので、基本的にはCommon Lispでやりたいことは何でもできるのです。 OSは存在するのです 。喜んでください。

恐竜を見つける

CLXマニュアル を読んだ後、 get-raw-image 関数を使用して直接 特定の領域からイメージデータを取得 できることを知りました。次にすることは。どうすれば恐竜を見つけられるのか考えてみましょう。

  • まず、すぐに頭に浮かぶのは、恐竜がどんどん走る画像です。スクリーンを読み、恐竜のポジションを特定する必要があります。やってみましょう。
  • 私は毎0.1秒ごとにスクリーンを読んでいます。では、恐竜の形状パターンと一致するコードを書く必要があります。
  • 形状マッチング、面白そうです。今までやったことがありません。さらに検索をして次の文書を見つけました。

  • 文書を読み始めたのですが、この論文は難しく、うーん……数学の話をしていますが……うーん……こんな数式は見たことがありませんし……
  • 一息入れようと思い、恐竜ゲームをしました。
  • なんと、恐竜は全く動いていませんでした。同じ場所で小さな足をバタつかせ、「走っている」振りをしているだけでした。
  • これは私の特別な人としての知性に対する究極の屈辱的な出来事でした。

でもすぐにショックからは立ち直りました。これ以上分かりにくい文書を読む必要がなくなったのです。よかった。

では、何をすればいいのでしょうか。

恐竜に関しては状態を確認するだけでいいんです。 立って いるのか、 ジャンプして いるのか、 前かがみになって いるのか(そう、Downキーで前かがみにすることができるんです)。

Three State of Dinosaur

実際には恐竜は前後に動くわけではないので、異なる姿勢の恐竜のスクリーンショットを撮り、それを GIMP で開き、姿勢に対応する位置決め点を取得ですることができます。これをコードにすると次のようになります。

(defvar *dino-standing-points* '((207 238) (242 223)))
(defvar *dino-bending-points* '((209 240) (262 243)))

これらの点を得た後は、現在のスクリーンのイメージデータをキャプチャし、特定のドットの色を取得し、そのドットの色が恐竜の色と同じかを判別します。もし、全ての *dino-standing-points* が一致すれば、恐竜は立っている状態です。もし、全ての *dino-bending-points* が一致すればかがんでいる状態で、そのどちらでもなければ恐竜はジャンプしている状態です。

ところが、少し遊んでみた後に、恐竜の色が昼と夜では異なることに気が付きました。そのため、恐竜の色を変える関数が必要です。恐竜はジャンプしたり屈んだりするため、色を抽出する点は背景にした方が簡単です。そうすると、恐竜の状態を背景の色を使用して判定することができます。もし、全ての *dino-standing-points* の色と背景の色が 一致しない のであれば、恐竜は立っていることになります。

恐竜を見つけられるようになりました。

サボテンと鳥

前方のサボテンと鳥によって、恐竜は死んでしまいます。そのため、サボテンと鳥に遭遇したら、 ジャンプする前かがみに なる、あるいはただ 立っている だけのいずれかの動作を取る必要があります(動作のタイミングも重要になります)。恐竜の前方の画像データを取得し、サボテンや鳥がいるかどうか確認することができます。

Search Squre

サボテンと鳥を探す領域を500×35の四角形の範囲に絞り、この四角形の位置を固定し、画面全体のスクリーンショットから GIMP を用いて取得します。次のようなコードになります。

;; the block search squre (x y weight height)
(defvar *block-search-squre* '(265 220 500 35))

この領域のイメージデータと背景の色を画素ごとに比較してみてください。もし一致しなければ、サボテンと鳥を見つけたことになります。

画素を比較する時、左上から右下の方向にイメージをスキャンすると、最初に特定できるのは、サボテンあるいは鳥の左上の位置になります。

サボテンと鳥をまとめてみました(全てのサボテンを集められていないかもしれません)。

Cactuses and Birds

実際、サボテンのサイズが異なっても何も変わらず、高くても低くても、太くても細くても適切なタイミングでジャンプすればやり過ごすことができます。しかし、鳥の場合は、飛んでいる高さを 低・中・高 に分けて特定する必要があり、 の位置にいる鳥に対してはジャンプし、 の位置にいる鳥に対しては前かがみになり、 の位置にいる鳥に対しては何もしないようにします。

上の画像からも分かるように、異なる高さで現れる鳥やサボテンはそれぞれ固有のy座標を持ち、鳥がどの高さにいるのかをy座標の値から特定することができます。

の位置にいる鳥はサボテンと同じ扱いにし、 の位置にいる鳥は存在しないもの(実際に無視します)とすればいいので、実際には の位置にいる鳥の固有のy座標だけあればいいのです。そのため、必要なのは次のコードだけなのです。

;; the y of middle flying bird
(defvar *middle-bird-y* 220)

サボテンと鳥を避けることもできるようになりました。

次のことが分かっています。

  • 恐竜の状態。 立って いる、 前かがみになって いる、 ジャンプして いる。
  • 恐竜の前のサボテンと鳥の位置。
  • サボテンや鳥に遭遇した時に取るべきアクション。 ジャンプ前かがみ何もしない

他にやるべきことは何か。

どのようにどのタイミングジャンプ前かがみ のアクションを取るようにするのかを考えなければなりません。どのように前かがみになるアクションを取るのか、そして、そのアクションを取るタイミングはいつなのかです。次で説明します。

恐竜の操作

どのように

恐竜をジャンプさせるか前かがみにさせるためには、 SPACE キー(あるいは UP キー)と DOWN キーの入力イベントをシミュレーションする必要があります。

キー入力イベントをシミュレーションする方法が必ずX Window Systemにあるはずです。さらに、 CLX はCommon Lisp用のX Window Systemプロトコルなので、こちらもキー入力イベントのシミュレーションする方法があるはずなのです。シミュレーションする方法が分かれば、恐竜を制御することができます。

CLXマニュアル を読むと イベントと入力 というセクションを見つけました。このセクションで書かれていたのは、使うことのできるイベントの操作方法でした。しかし、IRCのすばらしい方々の話を聞いて、 XTEST というX Window Systemの拡張機能の存在を知りました。これは「ユーザ介入なしにX11サーバを完全に試験するために必要な最低限のクライアントとサーバ拡張機能のセット」で、キーやマウスでの入力を疑似する XTestFakeInput という名のとおりの操作ができます。

幸運なことに、この機能はすでに CLXに実装されています ので、その関数を呼び出すことができます。 fake-key-event あるいは fake-button-event で、できるはずです。順調です。 REPL でも同じようなことができます。

(xtest:fake-key-event display *space-keycode* t) ; key down
(xtest:fake-key-event display *space-keycode* nil) ; key up

そして、恐竜はジャンプしました。

どのタイミングで

サボテンや鳥に近づいたらジャンプできるようにしなければなりません。しかし、どれくらい近づけばいいのでしょうか。100画素なのでしょうか。それとも200画素なのでしょうか。それとも全ての値を試してみて最適な値を特定するべきなのでしょうか。いいえ、最適な値を1つだけ特定することはできません。「サボテンとの距離が100画素以下になったらジャンプ」と恐竜に指示することはできません。それは、速度が上がっていくからです。おそらく速度が遅い場合には100画素でいいかもしれませんが、速度が上がれば100画素以上の値でなければタイミングは合いません。

速度に関係するのです。もし、恐竜の前のサボテンの座標が分かれば、x座標の変化を時間で割って速度を算出することができます。スクリーンを読み込むたびに全ての速度の値を集め、平均を算出することができます。次のようになります。

(defun jump? (distance speed)
    (<= (/ distance speed) 0.15))

jump? 関数が取るパラメータは2つあり、1つはサボテンと恐竜の距離を表す distance 、もう1つはサボテンの速度を表す speed です。すると、 (/ distance speed) はサボテンが恐竜に当たってしまうまでの残り時間となります。また、 0.15 は、恐竜の足が地面から離れるのに確保しておく時間です。つまり、この関数は、「0.15秒後にサボテンが恐竜に当たることが分かっていればジャンプするので、サボテンが接近した時には恐竜は空中にいることになり、無事サボテンをやり過ごすことができる」ということになります。

Jumping Dinosaur

毎秒60回スクリーンを読み込み、それぞれのスクリーンで jump? 関数を呼び出してアクションを読み込めば、ジャンプするタイミングが確認できます。

最後に

SLIME-REPLのコードスニペットをいじってみると、全てのシステムは次のように納まります。

  • get-raw-image が備わったスクリーンリーダ

    • 恐竜の状態確認(立っているか、前かがみになっているか、空中にいるのか)
    • ゲームの状態確認(ゲームオーバーなのか継続中なのか)
    • サボテンと鳥の検知
  • fake-key-eventfake-button-event が備わったキーボード・マウスシミュレータ

    • 恐竜の制御( SPACE キーと DOWN キー)
    • ゲームの起動(ゲームウィンドウをクリックして起動)

もう少しきれいにすれば、Common Lispで操作できるスーパー恐竜ゲームの出来上がりです。

ここでは、実装コードの詳細については説明しませんが、この記事の最後にコード公開先のリンクを貼っていますので、そちらを見てください。

最後にもう一言。Lispは決して古くて使えない机上の言語ではありませんし、強大な未知の力でもありません。正しく使えば、思いどおりのことが実現できる言語です。

YouTubeの動画

https://youtu.be/PkzlJcKR4TI

WOW! SUCH DINO!

GitHubのコード

https://github.com/VitoVan/cl-dino

私はCommon Lisp初級者なので、整理されたコードではないかもしれません(でも、きれいにしようと心がけています)。コードを見てエレガントではない部分がありましたら、ご指摘ください。


License: GNU GPL v2.0