さくらんぼのlambda日記

lambdaちっくなことからゲーム開発までいろいろ書きます。

Common Lispでゲーム用の状態遷移マシン 完成？

Lisp LispGameDev

やっと、コード書く時間がとれたので、記録用に書きます。

singletonクラス作成用のパッケージ

とりあえず、singletonをつくるためのパッケージを作成しました。
http://cadr.g.hatena.ne.jp/g000001/20081202/1228199756
この記事が超参考になりました。

closer-mopを使うことで、特定の実装に依存しないでsingletonが実現できますね。
素晴らしいです。

(defpackage :singleton
  (:use :cl )
  (:export #:define-singleton-class
	   ))

(in-package :singleton)
(defclass singleton-meta (standard-class)
  ((%the-singleton-instance :initform () )))

(defmethod make-instance ((class singleton-meta) &key)
  (with-slots (%the-singleton-instance) class
    (if %the-singleton-instance
        %the-singleton-instance
        (let ((ins (call-next-method)))
          (setf %the-singleton-instance ins)
          ins))))

(defmethod c2mop:validate-superclass ((class singleton-meta)
                                      (super standard-class))
  'T)
(defmethod c2mop:validate-superclass ((class singleton-meta)
                                (superclass standard-class))
  ;; it's OK for a standard class to be a superclass of a singleton
  ;; class
  'T)

(defmethod c2mop:validate-superclass ((class singleton-meta)
                                (superclass singleton-meta))
  ;; it's OK for a singleton class to be a subclass of a singleton class
  'T)

(defmethod c2mop:validate-superclass ((class standard-class)
                                (superclass singleton-meta))
  ;; but it is not OK for a standard class which is not a singleton class
  ;; to be a subclass of a singleton class
  nil)

(defmacro define-singleton-class (name supers &rest args)
  (and (assoc :metaclass args)
       (error "Metaclass already specified."))
  `(defclass ,name ,supers ,@args
     (:metaclass singleton-meta)))

状態遷移マシン自体のパッケージ

状態遷移マシンは、こんな感じで実装してみました。
state-machine:stateを継承しているクラスを使うことを想定しています。

(in-package :cl)
(defpackage :state-machine
  (:use :cl :singleton)
  (:export #:state
  	   #:state-machine
	   #:set-current-state
	   #:set-prev-state
	   #:set-global-state
	   #:change-state
	   #:enter
	   #:execute
	   #:exit
	   #:update
	   #:current-state ) )
(in-package :state-machine)
(singleton:define-singleton-class state ()
  ())
(defmethod enter ((state-instance state) &rest arg) )
(defmethod execute ((state-instance state) &rest arg) )
(defmethod exit ((state-instance state) &rest arg) )
(defclass state-machine ()
  ((owner :initarg :owner)
   (current-state :initform nil  :accessor current-state)
   (prev-state :initform nil :accessor prev-state)
   (global-state :initform nil :accessor global-state)))

(defmethod set-current-state ((obj state-machine) s)
  (setf (current-state obj) s))
(defmethod set-prev-state ((obj state-machine) s)
  (setf (prev-state obj) s))
(defmethod set-global-state ((obj state-machine) s)
  (setf (global-state obj) s))  
    
(defmethod update ((obj state-machine))
  (when (not (null (global-state obj)))
    (execute (make-instance (global-state obj))))
  (when (not (null (current-state obj)))
    (execute (make-instance (current-state obj)))))

(defmethod change-state ((obj state-machine) new-state)
  (setf (prev-state obj) (current-state obj))
  (exit (make-instance (current-state obj)))
  (setf (current-state obj) new-state)
  (enter (make-instance (current-state obj))))

実際の例

こんな感じで、状態遷移マシンを構成してみます。

(singleton:define-singleton-class getup (state-machine:state)  ())
(singleton:define-singleton-class goodnight (state-machine:state) ())

(defmethod state-machine:enter ((state-instance getup) &rest arg) 
  (declare (ignore arg))
  (format t "enter getup~%"))
(defmethod state-machine:execute ((state-instance getup) &rest arg) 
  (declare (ignore arg))
  (format t "exec getup~%"))
(defmethod state-machine:exit ((state-instance getup) &rest arg) 
  (declare (ignore arg))
  (format t "exit getup~%"))

(defmethod state-machine:enter ((state-instance goodnight) &rest arg) 
  (declare (ignore arg))
  (format t "enter goodnight~%"))
(defmethod state-machine:execute ((state-instance goodnight) &rest arg) 
  (declare (ignore arg))
  (format t "exec  goodnight~%"))
(defmethod state-machine:exit ((state-instance goodnight) &rest arg) 
  (declare (ignore arg))
  (format t "exit  goodnight~%"))

(setf fsm (make-instance 'state-machine:state-machine))
(state-machine:set-current-state fsm  'getup)
(state-machine:update fsm)

さて、実際に実行してみると

CL-USER> (state-machine:update fsm)
exec getup
NIL
CL-USER> (state-machine:update fsm)
exec getup
NIL
CL-USER> (state-machine:update fsm)
exec getup
NIL
CL-USER> (state-machine:change-state fsm 'goodnight)
exit getup
enter goodnight
NIL
CL-USER> (state-machine:update fsm)
exec  goodnight
NIL

いい感じですねー。

課題

  • 状態遷移のためのstateを継承したクラスの定義が面倒くさい。パッケージをわざわざ指定するのは面倒くさい。

解決方法をちょっと考えてみます...。

移植にあたっての課題とその解決方法

ここでは、FSM/State.hとStateMachine.hをCLOS上に移植する上での課題とその回避策について考えます。

移植上の2つの課題

簡単に移植できると思うのですが、CLOSで扱うのが面倒臭そうな技術上の課題がいくつかあります。
上記のコードでは、以下のテクニックが使われています。

  • テンプレート
  • singletonパターン

こんな手法を使っている理由を考えてみます

テンプレートは、いちいちStateMachineおよびStateを継承したマーカクラスを作成するのが面倒くさいというのが主たる目的でしょう。

singletonパターンは、StateMachineを愚直に実装すると、StateMachineごとにStateのインスタンスを生成する実装が考えられます。しかし、これはメモリの使用効率が良くないです。StateMachineは1万とかオーダーで生成されることを想定されます。このたびにStateを生成していては無駄となります。なので、静的に確保したいのでしょう。

余談

singletonは、最初はnamespaceでも良いのではと考えてしまいましたが、これではダメですね。statemachineクラスが現在の状態を管理するには、右辺値として扱えるクラスであって欲しいですね。statemachineクラスがenter,execute,exit関数を関数ポインタで保持して、管理する形式にすれば可能ですが、それはあまりにも煩雑でしょう。また、テンプレートを使っていることを考えるとトリッキーなコードになりそうですし...。

テンプレートについての解決方法

これは困った。CLOSにはテンプレートとかないです。Common Lispなので動的型付けだし、みなかったことにしたいですねw
ありえない型への遷移も許容してしまう実装になってしまいそうですねぇ...。
マクロにして型チェックをするコードを挿入するというのも手ですが、これでも動的チェックになってしまいますね。
静的チェックを実装する方法については、今後の課題にしておきます。

singletonパターンについての解決方法

これまた困りました。どうしてこんなに世の中生きていくのが辛いのでしょうか?

以下の2つが制御できるかどうかが課題ですね。

  • setf
  • make-instance

CLOSでsingletonクラスの実装をしている人はいるようで以下のような実装がありました。
http://www.tfeb.org/programs/lisp/singleton-class.lisp

make-instanceを制御しているようです

(make-instance 'foo)

で毎回同じオブジェクトが返ってくるようになりますね。

(setf (make-instance 'foo) nil)

とかしたらオワタなきがします。

やってみました。

The function (SETF MAKE-INSTANCE) is undefined.
   [Condition of type UNDEFINED-FUNCTION]

Restarts:
 0: [RETRY] Retry SLIME REPL evaluation request.
 1: [*ABORT] Return to SLIME's top level.
 2: [TERMINATE-THREAD] Terminate this thread (#<THREAD "repl-thread" RUNNING {AB97279}>)

なるほどー。エラーがかえってきました。この実装でそのまま使えそうですねー。
わーい。

というわけで、singletonは大丈夫そうですね!

C++の場合はどうなるか?

いきなりCommon Lispで挑戦するのでもよかったのですが、ここは先人の知恵を借りたいところです。
C++でゲーム用の状態遷移クラスを作っているサンプルや枯れているものはたくさんあるので参考にしようと思います。

ここでは、以下の本に載っている状態遷移クラスを参考にしようと考えています。

実例で学ぶゲームAIプログラミング

実例で学ぶゲームAIプログラミング

ソースコードは以下のSamples & Additional Resourcesから入手可能です。

http://www.jblearning.com/Catalog/9781556220784/student/

具体的なファイルはCommon/FSM/State.h,Common/FSM/StateMachine.hです。
これをCommon Lispへと移植することにします。

ゲームに使える状態遷移マシン

LispGameDev ゲーム Lisp

備忘録的に吸闘紀で採用している状態遷移マシンの設計と実装について書いておきます。

ゲームに必要な状態遷移マシン

ゲームに使える状態遷移マシン。そこまで複雑な状態遷移マシンは必要とはなりません。
簡単に要件をまとめておきます。

まず、各遷移する状態を表す状態は以下の要件があれば十分です

  • 各状態は特定のタイミングで指定した関数を実行する
  • 各状態が定めている関数の引数の数や意味はそれぞれに異なる可能性がある

次に、上記の状態を管理し、遷移を適切に処理する状態遷移マシンクラスの要件です。

  • 状態遷移マシンは状態を2種類もつ

各要件の詳細

各状態は特定のタイミングで関数を実行する

以下の3つのタイミングで、各状態ごとに定義されている関数を実行する必要があります。

  • 状態に遷移する時に実行する関数(enter)
  • 状態の更新関数(update)
  • 次状態に遷移する時に実行する関数(leave)

f:id:sakura-1:20110524171252p:image:w400

各状態が定めている関数の引数の数や意味はそれぞれに異なる可能性がある

上記の関数の引数は、各状態ごとに異なる可能性があります。
これは、敵の更新関数、プレイヤーの更新関数、シーンの更新関数では必要な情報が異なる場合が少なくないためです。

状態遷移マシンは状態を2種類もつ

ゲームでは基本的な状態に加えて、すべての状態に関係する常に気にしなければならない状態があります。

例えば、吸闘紀ですと基本的な状態としては、歩く、ジャンプするなどが有ります。これとは別に、物を吸い込んでいる状態とそうでない状態があります。この後者の物を吸い込んでいる状態などは全ての状態に影響を与えます。物を吸い込んでいる状態では、空は飛べないとか、吸い込んでいない状態では物をすこむことが出来る等...。
f:id:sakura-1:20110524171251p:image:w400

クラス分けをしてみる

というわけで、これらの要件を満たせるようなクラス構成を考えてみます。
こんな感じだとうまくいくはず。ざっくりUMLを書いてみました。

f:id:sakura-1:20110524134152p:image

使用上の注意

この設計では、各エンティティが自分の状態を管理する状態遷移マシンを持っています。また、状態遷移マシンは各エンティティへの参照を持っています。
このため、相互に所有している関係となっています。
エンティティが開放されると同時に状態遷移マシンも開放されるように、状態遷移マシンの参照はエンティティ内部に閉じるようにしておく必要があります。

実装

次回にまとめてソースは書きます。

Mac環境構築ガイド for 自分

Mac メモ 日常 Lisp

MacBookPro(15インチ)を購入しちゃいました!!

Apple MacBook Pro 2.2GHz 15.4インチ MC723J/A

Apple MacBook Pro 2.2GHz 15.4インチ MC723J/A

今後の備忘録もかねて環境構築ガイドを作成しようと思い記事にしてしまいます。

ブラウザ(Chrome)のインストール

しばらく前からFirefoxからChromeに乗り換えています。何をするにもブラウザがいる世の中なので最初にインストールします。

ランチャ(QuickSilver)のインストール

Macでは有名なキーボードで操作できるランチャです。
起動のキーバインドはCommand + Shit + Spaceを割り当てています。

マウスの設定

画面の四隅のショートカットをよく使うので設定します。

  • 画面左上でエクスポゼが実行されるように
  • 画面右下でデスクトップが表示されるように

Spotlightの設定

検索機能のspotlightの設定です。検索機能自体は便利なのですがバインドがEmacsとぶつかるので無効にします。

雑多なアプリケーションのインストール

AppStoreから以下のアプリをインストールします。

  • Keynote
  • shufftitexpander
  • twitterクライアント(YoruFukurou)のインストール
  • Evernoteのインストール

以下のアプリは適宜サイトからDLしインストール

XCodeのインストール

XCode4は有料なので、XCode3をインストールします。これはディスクからでも良いし、AppleのサイトからDLしてインストールしても問題ないです。
サイズが大きいので。お茶でも呑んで待ちます。

MacPortsのインストール

これも公式のサイトからインストールします。

ターミナルの設定

端末の色がデフォルトでは見づらいので、色を変更できるように以下の２つをインストールします。

端末で日本語が表示できるように以下の設定を行います。
内容は後日追記します。

  • inputrc
  • MacOS/environments.plist
  • zshrc

MacPortsで入れるもの

あとはMacPortsでほしい物をじゃんじゃんインストールしましょう。

  • git-core +svn

なぜかしょっぱなからコケました。db46のコンパイルにjava developperがいるみたいです。
全くわからなくて時間を浪費してしまいました。

Carbon Emacsはもう古いのでこちらのEmacsを利用しています。Cocoaを利用するようになっていて、フォントなどの設定が楽になっています。

開発用に以下のライブラリをインストールします。

  • libsdl
  • libsdl-framework
  • libsdl-image
  • libsdl-image-framework
  • libsdl-mixer
  • libsdl-mixer-framework
  • libsdl-ttf
  • libsdl-ttf-framework

もちろんCommon Lispの環境もインストールします

quicklisp

これは、quicklispのサイトからDLして来ます。
Lispの環境設定についてはまた別の記事にでもしようかと思ういます。

設定完了！

以上が、自分のMacの環境です。
主に、開発にしか使わないので素っ気ない環境ですが気に入ってます。

ガンダムUC読了

とりあえずガンダムUCを10巻全部読了しますた。

なかなか良い話だった気がします。文句があるとすると筆者がガンダム好きすぎ。そのせいで、セリフのほとんどがガンダムのオマージュになっててちょっともったいない。そんなことしなくても魅力的な話なのに。

機動戦士ガンダムUC 1 ユニコーンの日(上) (角川コミックス・エース 189-1)

機動戦士ガンダムUC 1 ユニコーンの日(上) (角川コミックス・エース 189-1)