xyzzysims制作中

2009-07-18

構造的なデータ表現 03:04

lispにはハッシュ表、構造体、CLOSなど、さまざまなデータ表現がある。しかし、一番基礎となるものはリストである。任意個数のデータを列挙したり、データの並び替えや変更・追加をするにはリストが最も適している。というのはもっともらしい言い分で、実際のところ、現在のxyzzyは残念ながらCLOSに対応していないので、オブジェクト指向で組むには手間がかかる。生のリストに近い状態で操作できた方が楽である。


ということで、複雑なリストにアクセスするマクロを作ってみよう。マクロが必要な理由は、関数ではsetfによる代入が面倒(全く不可能ではないが)ということと、複雑なリストへアクセスする関数を直書きしていたら非常にややこしいからである。今回想定しているのは、普通のRPGに近いゲームらしいデータ構造なのだが、それでもかなり入り組んだ形を取る。

;キャラクターのデータ案
(type name domain class (hp phit pdod shit sdod &rest feats) conditions skills spells items blesses)

実際のところ()内が必要かどうかは考慮に値するが、feat(特徴)やskill(技能)などはさらにリストを作るため、この見た目より複雑になるだろう。こうしたデータへのアクセスはcar cdr系では間に合わず、eltの組合せで行う必要がある。


また、上の例ではspellsやitemsなどの長いリストになりそうなものが後ろに来ているため、初期にデータを確認する場合には便利かも知れないが、速度をわずかでも早くしたい場合は手前に移動したいかも知れない。その場合、直書きされていると修正が困難である。構造体なら順番が関係ないが、保存する際にスロット名がいちいちつくので、データが多いと結構無駄になってしまう。


そこで、各データへアクセスするマクロを作る。

(defmacro ^feats (obj)
  `(nthcdr 5 (elt ,obj 4)))

長くなるので1つだけ例に挙げる。こうしたマクロを作るには、スロット一つごとに位置を順番に数えなくてはならない。・・・としたら、修正が非常に面倒なので構造体を使った方が良いだろう。実際には次のようにする。

(defobj person (type name domain class (hp phit pdod shit sdod &rest feats) skills spells items blesses))

これを実行すれば、先に定義したようなアクセスマクロが全て作られ、初期化用のマクロも出来上がる。そうなっていれば、リストでも作りやすいだろう。

再帰処理をする関数

複雑なリストといっても、全て入れ子になっているので、順に処理していけば問題ない。次に、入れ子になったリストに対する操作関数を示す。

(defun mapcar-tree (fn tree &rest more-trees)
  (if (consp tree)
      (apply 'mapcar (lambda (x &rest y) (apply 'mapcar-tree fn x y)) tree more-trees)
    (apply fn tree more-trees)))

(defun rmapcan (fn tree &rest more-trees)
  (if (consp tree)
      (apply 'mapcan (lambda (x &rest y) (apply 'rmapcan fn x y)) tree more-trees)
    (apply fn tree more-trees)))

(defun mapcan-tree (fn tree &rest more-trees &aux sub)
  (setq sub (lambda (fn tree &rest more-trees)
              (if (consp tree)
                  (list (apply 'mapcan (lambda (x &rest y) (apply sub fn x y)) tree more-trees))
                (apply fn tree more-trees))))
    (apply 'identity (apply sub fn tree more-trees)))

(setq test (list (lambda (x y) (if (oddp x) (list (+ x y))))
                 '(1 2 (3 4) (5 5) (6 6) 7)
                 '(7 6 (5 4) (3 2) (1 0) 1)))
|
(#<lexical-closure: (anonymous)> (1 2 (3 4) (5 5) (6 6) 7) (7 6 (5 4) (3 2) (1 0) 1))

(apply 'mapcar-tree test)
|
((8) nil ((8) nil) ((8) (7)) (nil nil) (8))

(apply 'rmapcan test)
|
(8 8 8 7 8)

(apply 'mapcan-tree test)
|
(8 (8) (8 7) nil 8)

mapcar-treeはmapcarの再帰版である。rmapcanはmapcanの再帰版であるがmapcanはリストを順に繋げていくため、最終的には平坦なリストが出来上がる。mapcan-treeは元の構造を保った状態で止めるバージョンである。次のマクロではmapcan-treeのみ用いる。

再帰処理をするマクロ

アクセスマクロでは、eltで用いる順序が必要なので、mapcar-treeは使えない。mapcan-treeを初期化用に使うだけにして、実際は再帰処理を行う。まあ、見てもらった方が早い。

(defmacro defobj (objname args)
  (append
   (list 'progn)
   (mapcar 'defobj-slot (defobj-parse args))
   `((defmacro ,(intern (concat "new" (symbol-name objname))) ()
       '(copy-tree ',(mapcan-tree (lambda (x) (if (eq x &rest) nil (list nil))) args))))))

(defun defobj-slot (x)
  `(defmacro ,(intern (concat "^" (symbol-name (car x)))) (obj)
     ,(cdr x)))

(defun defobj-parse (&optional args res (accesser 'obj) (n 0))
  (cond
   ((null args) res)
   ((atom args) (list (cons args accesser)))
   ((eq (car args) &rest)
    (append res (list (cons (cadr args) `(list 'nthcdr ,n ,accesser)))))
   ((consp args)
    (defobj-parse (cdr args)
                  (append res (defobj-parse (car args) nil `(list 'elt ,accesser ,n) 0))
                  accesser (1+ n)))))

マクロの本体は、引数アクセス関数を生成する関数に引き渡したり、初期化マクロを作ったりするだけである。問題はアクセス関数を生成する関数で、これはちょっとややこしい。

(defobj-parse 'a)
|
((a . obj))

(defobj-parse '(a))
|
((a list 'elt obj 0))

(defobj-parse '((a)))
|
((a list #1='elt (list #1# obj 0) 0))

(defobj-parse '(a b))
|
((a list #1='elt obj 0) (b list #1# obj 1))

動作を見て追っていくしかないが、再帰する場所を掴めば読めるはずだ。再帰する方向は2つ、深さ方向と幅方向である。幅方向へは順序が増え、深さ方向へは要素を取り出す回数が増える。それらの情報を持ちながら再帰で掘り進めていく。また、キーワードは&restにのみ対応して、これが出たら残りの要素をまとめてリストにする。定義では対応する変数が1つしか現れないが、取り出し関数eltからnthcdrに変わる。


これだけ作れば、リストへアクセスする準備は十分だ。次のように、満足な動作をするだろう。

(defobj person (type name domain class (hp phit pdod shit sdod &rest feats) skills spells items blesses))
|
newperson

(setq x (newperson))
|
(nil nil nil nil (nil nil nil nil nil nil) nil nil nil nil)

;データ入力例(一部)
(progn
  (setf (^class x) 'warrior)
  (setf (^hp x) 100)
  (setf (^name x) "hoge")
  x)
|
(nil "hoge" nil warrior (100 nil nil nil nil nil) nil nil nil nil)

実際は、初期化キーワードで値を代入できる関数を作ったり、内部リストへ直接アクセスするマクロも必要だが、それらはあまり手間がかからない。使い方にあった方法で、必要に応じて順次書いていくことになる。

2009-05-23

道をつくる 15:28

道をつくる

やり直し - xyzzysims制作中 - 人工知能一般の続き。一度定義した関数は適当に過去を参照しよう。多くなってくると参照が大変になるのでコード管理用のサービスを使った方が良いかな。


現在の環境はこんな感じ。

(world (room east west)
       (person moon tues)
       (item 1st 2nd)
       (in (moon . east) (tues . east) (1st . moon) (2nd . west)))

今回は、部屋を増やして、部屋をつなぐ道を作ってみようと思う。どこへでも一瞬で移動できるというのは不自然で、ある場所から移動できる場所は限られている。

(treat (key 'room *world*)
  (pushd 'north key)
  (pushd 'south key))

(pushd '(path
         (east . north)
         (east . west)
         (north . east)
         (north . south)
         (west . east)
         (west . south)
         (south . west)
         (south . north))
       *world*)

ここで、pathはcarからcdrへ移動できることを表す。一つのデータで双方向への経路を表しても良いのだが、一方通行の道もあるので、とりあえず分けておこう。

(defun go-path (world actor to)
  (and (contain world 'person actor)
       (contain world 'room to)
       (member (treat (where 'in world)
                 (cons (findd actor where) to))
               (findd 'path world) :test 'equal)
       (move world actor to))
  world)

;移動できる例
(result (go-path *world* 'moon 'north))
|(in (moon . north) (tues . east) (1st . moon) (2nd . west))
;移動できない例
(result (go-path *world* 'moon 'west))
|(in (moon . north) (tues . east) (1st . moon) (2nd . west))

丁度safe-moveに経路条件が追加された形になる。これまでのmoveを使った関数はみな、前置条件を満たせばmoveを実行できるという形になっている。このように、シミュレータ上の動作は条件節と動作節を分けて考えることが出来る。後でこれを一般化することになると思うが、今はまだ一通りの動作が出ていないので行わない。


先ほど一方通行の話題を出したので、部屋をもう一つ作って一方通行を試そう。

(treat (key 'room *world*)
  (pushd 'central key))

(treat (key 'path *world*)
  (pushd '(east . central) key)
  (pushd '(central . west) key))

;東から中央へは行ける
(result (go-path *world* 'tues 'central))
|(in (moon . north) (tues . central) (1st . moon) (2nd . west))
;中央から東へは行けない
(result (go-path *world* 'tues 'east))
|(in (moon . north) (tues . central) (1st . moon) (2nd . west))

格子状の部屋

次に、この部屋から移動できる、格子状に配列した部屋群を製作する。最初の部屋はシミュレーションの選択肢風、その次はすごろく風の動作で、今度は普通のRPGのマップのような動作になる。

03 13 23 33
02 12 22 32
01 11 21 31
00 10 20 30

と部屋を配置して、それぞれの部屋から東西南北の部屋へ移動できる。普通のRPGではキャラごとに座標の配列を持って、座標のx,yを変更させて移動するが、今回は座標を用いずに、今まで通りの方法で移動を実現する。一般的なルールを使う方が、AIにとっては処理が楽になるだろう。


ということで、部屋群と経路群を登録しよう。もちろん直書きすれば済むのだが、同じような部屋を何回も用意する場合は面倒なので、この形式の部屋を生成する関数を作る。

(defun make-grid-sub (name x y)
  (let (row)
    (dotimes (yi y (reverse row))
      (let (column)
        (dotimes (xi x column)
          (push (list name xi yi) column))
        (push (reverse column) row)))))

(defun make-grid (name x y)
  (mapcar (lambda (row)
            (mapcar (lambda (x) (intern (format nil "~{~A~}" x))) row))
          (make-grid-sub name x y)))

(make-grid-sub 'm 2 2)
|(((m 0 0) (m 1 0)) ((m 0 1) (m 1 1)))

(format t "~{~A~%~}" (make-grid 'm 3 3))
|(m00 m10 m20)
|(m01 m11 m21)
|(m02 m12 m22)

部屋の名前は何でも良いのだが、動作が分かりやすいようにXYの番号で名前を付ける。数字だけだと登録できないし、同じような部屋をいくつも作ることを想定して適当にアルファベットをつけよう。ところで、make-gridの中身を見てもらえば分かるようにシンボルをinternしている。つまり、lisp環境にシンボルを撒き散らしているので、今のやり方は好ましくない。登録などが面倒になるが、もう少し作ったら名前を文字列として扱うようにしよう。


部屋の名前の座標の配置が想定と異なるが、上下を入れ替えて考えればいいので特に問題ない。

(defun make-grid-path (name &optional x y)
  (do ((lm (if (consp name) name (make-grid name x y))
           (mapcar 'cdr lm))
       (res))
      ((null (apply 'append lm)) (nreverse res))
    (do ((li lm (cdr li)))
        ((null li))
      (macrolet ((! (x y) `(push (cons (,x li) (,y li)) res)))
        (when (cadar li)
          (! caar cadar)
          (! cadar caar))
        (when (cdr li)
          (! caar caadr)
          (! caadr caar))))))

(format t "~{~A~%~}" (make-grid-path 'm 3 3))
|(m00 . m10)
|(m10 . m00)
|(m00 . m01)
|(m01 . m00)
|(m01 . m11)
|(m11 . m01)
|(m01 . m02)
|(m02 . m01)
|(m02 . m12)
|(m12 . m02)
|(m10 . m20)
|(m20 . m10)
|(m10 . m11)
|(m11 . m10)
|(m11 . m21)
|(m21 . m11)
|(m11 . m12)
|(m12 . m11)
|(m12 . m22)
|(m22 . m12)
|(m20 . m21)
|(m21 . m20)
|(m21 . m22)
|(m22 . m21)

doの入れ子になっていて煩雑だが、出力が合ってれば問題ない。各部屋から2~4つの行き先がある。これで、それぞれの部屋と経路、それに中央と部屋群への経路を登録する。

(treat (key 'room *world*)
  (dolist (arg (apply 'append (make-grid 'm 4 4)))
    (pushd arg key)))

(treat (key 'path *world*)
  (dolist (arg (make-grid-path (make-grid 'm 4 4)))
    (pushd arg key))
  (pushd '(central . m00) key)
  (pushd '(m33 . central) key))

;新天地へ
(result (go-path *world* 'tues 'm00))
|(in (moon . north) (tues . m00) (1st . moon) (2nd . west))

;進んでみる
(result (go-path *world* 'tues 'm01))
|(in (moon . north) (tues . m01) (1st . moon) (2nd . west))

;すぐには帰れない
(result (go-path *world* 'tues 'central))
|(in (moon . north) (tues . m01) (1st . moon) (2nd . west))

方角による移動

これだけだと、まだ通常のRPGのマップ移動と同じではない。部屋が整列して並んでいるなら、場所を指定して移動するのではなく、方角によって移動できるべきである。十字キーによる移動は基本的に方角による移動だ。


というわけで、経路情報だけでなく、方角の情報も作る。東西南北の項目を作り、それを参照して相対移動する。また、その情報を生成する関数も必要になる。とはいえ、それぞれちょっとずつ改造すればすぐに作れる。

ymbol

方角を指定して移動するが、道がなくては移動できないため、行き先を確認したら経路を用いて移動する関数に渡している。北に部屋があるのが分かっても、扉に鍵がかかっていたら入れない、といった状況が考えられる。

ここまで作れば、お使いイベントくらいは作れると思う。環境が大分広くなってきたので、次回は人を動かして、目的を達成するように行動させてみよう。

2009-05-21

やり直し 11:34

前回のやり直し。

(setq *world*
      '(world
        (room east west)
        (person moon tues)
        (item 1st 2nd)
        (in (moon . east) (tues . east)
            (1st . west) (2nd . west))))

最初の状態は簡単に直書きすることにした。ついでに、試しに入れるデータは4つずつもいらないので半分にした。まずは移動させる関数を作る。

(defun move (world actor to)
 (treat (where 'in world)
  (treat (it actor where)
    (rplacd it to)))
  world)

前回のtreatがそのまま使えて、前のより単純に書ける。これは良さそうだ。

(defun result (world)
  (find 'in (cdr world) :key 'car))

(result *world*)
|(in (moon . east) (tues . east) (1st . west) (2nd . west))

(result (move *world* 'moon 'hoge))
|(in (moon . hoge) (tues . east) (1st . west) (2nd . west))

オブジェクトの種類は変わらないので、inの中身だけ出力するようにして動作を確認する。存在しないオブジェクトも登録できちゃうので、まずは人間が部屋に移動するという関数を作る。

(defun contain (place group arg)
  (let ((grp (gensym)))
    (treat (grp group place)
      (find arg grp))))

(defun safe-move (world actor to)
  (and (contain world 'person actor)
       (contain world 'room to)
       (move world actor to))
  world)

(result (safe-move *world* 'moon 'fuga))
|(in (moon . hoge) (tues . east) (1st . west) (2nd . west))

(result (safe-move *world* 'moon 'west))
|(in (moon . west) (tues . east) (1st . west) (2nd . west))

(result (safe-move *world* '1st 'east))
|(in (moon . west) (tues . east) (1st . west) (2nd . west))

対象が正当かどうか確認すればいいので、適当に確認する関数を作ればOK。続けてアイテムを拾う関数

(defun pick (world actor target)
  (and (contain world 'person actor)
       (contain world 'item target)
       (treat (where 'in world)
         (eq (findd actor where)
             (findd target where )))
       (move world target actor))
  world)

(result (pick *world* 'tues '1st))
|(in (moon . west) (tues . east) (1st . west) (2nd . west))

(result (pick *world* 'moon '1st))
|(in (moon . west) (tues . east) (1st . moon) (2nd . west))

今度はお互いの場所も合ってないといけないので、それを確認する。特に難しいことはない。今度は置く関数moveと同じように、まずはオブジェクト一般に使えるように作っておく。

(defun findd (item place)
  (cdr (find item (cdr place) :key 'car)))

(defun exit (world target)
  (treat (where 'in world)
    (let ((outer (findd (findd target where) where)))
      (and outer (move world target outer))))
  world)

(result (exit *world* 'moon))
|(in (moon . west) (tues . east) (1st . moon) (2nd . west))

(result (safe-move *world* 'moon 'east))
|(in (moon . east) (tues . east) (1st . moon) (2nd . west))

(result (exit *world* '1st))
|(in (moon . east) (tues . east) (1st . east) (2nd . west))

まあ、人は出入りするところがまだないので、今は区別する必要はないだろう。次に、人が他の人に持ってるアイテムを渡す関数

(defun give (world actor taker target)
  (and (contain world 'person actor)
       (contain world 'person taker)
       (treat (where 'in world)
         (and (eq (findd actor where)
                  (findd taker where ))
              (eq (findd target where)
                  actor)))
       (move world target taker))
  world)

(result (pick *world* 'tues '1st))
|(in (moon . east) (tues . east) (1st . tues) (2nd . west))

(result (give *world* 'tues 'moon '1st))
|(in (moon . east) (tues . east) (1st . moon) (2nd . west))

「誰」が「誰」に「何」を渡すのか、また、渡す方がそれをちゃんと持ってるのか、同じ場所にいるのかを確認して、条件が全て揃っていれば相手に渡すことが出来る。条件は多いが、これも平易に書ける。

ということで、この方式で結構複雑なことが出来そうである。このようなことが記述できれば、NPCに目標を与えて、それを与えられた関数の組合せで実現させるようなことがプログラムを書く作業に入れるだろう。

2009-05-17

最初の一歩 02:37

なんにせよ、まずは世界を表現できないといけない。究極的には、シミュレーション空間の世界自体に、世界の変化の仕方を記述するようにしていきたいが、まずは外から世界を構成してみよう。


これから書くソースコードは、特に断りがなければ、xyzzy上で動作するlispである。手軽にlispを試すことが出来て便利だ。

(setq *world* (list 'world))

最初に入れ物を作る。データは(名前 中身)という形式にするとして、とりあえず全体の名前も付けておく。

(defmacro pushd (item place)
  `(rplacd ,place (cons ,item (cdr ,place))))

(dolist (a (mapcar (lambda (x) (list x)) (list 'east 'south 'west 'north)) *world*)
	(pushd a *world*))

中身を入れるにはpushだと都合が悪いので、適当にマクロpushdを作っておく。世界の中身として、東西南北の4つの部屋を入れる。

(defmacro treat ((it item place) &rest args)
  `(let ((,it (find ,item (cdr ,place) :key 'car)))
     (when ,it ,@args)))

(treat (at 'east *world*)
    (dolist (a (mapcar (lambda (x) (list x)) (list 'moon 'tues 'wednes 'thurs)) *world*)
      (pushd a at)))

今度は部屋の中に人を入れる必要があるので、中身から名前でオブジェクトを探すマクロtreatを作って、それを用いて月火水木の4人を入れる。とりあえず東の部屋に全員入れる。

|(world (north) (west) (south) (east (thurs) (wednes) (tues) (moon)))

全て実行して、現在の状況はこんな感じだ。これから、部屋から部屋へ人が移動できるようにする。

(defmacro chase ((it there) (item place) &rest args)
  (let ((a (gensym))
        (b (gensym)))
    `(multiple-value-bind (,it ,there)
         (dolist (,a (cdr ,place))
           (treat (,b ,item ,a)
             (return (values ,b ,a))))
       (when (and ,it ,there)
         ,@args))))

(defmacro exiled (item place)
  `(rplacd ,place (remove ,item (cdr ,place))))

(defun move (world actor to)
  (chase (item place) (actor world)
    (unless (equal (car place) to)
      (treat (new-place to world)
        (exiled item place)
        (pushd item new-place))))
  world)

人の名前を指定して、人オブジェクトとその人がいる部屋オブジェクトを見つけなくてはならないので、そんなマクロchaseを作る。人を動かすには、

  • 指名した人を見つける
  • 現在いる部屋からその人を消す
  • 指定した部屋へその人を移動する

のように行う。中身を消すマクロがなかったのでexiledとして作れば、移動関数move本体は動作の通り作ればいい。

(move *world* 'moon 'west)
|(world (north) (west (moon)) (south) (east (thurs) (wednes) (tues)))

(move *world* 'thurs 'south)
|(world (north) (west (moon)) (south (thurs)) (east (wednes) (tues)))

次の要素

人が移動できるようになったので、次は物を置いてみる。

(treat (at 'north *world*)
    (dolist (a (mapcar (lambda (x) (list x )) (list '1st '2nd '3rd '4th)) *world*)
      (pushd a at)))
|(world (north (4th) (3rd) (2nd) (1st)) (west (moon)) (south (thurs)) (east (wednes) (tues)))

人と同じように、一二三四の4つの物を置く。


さて、ここで人と物を区別する方法が必要だ。人は移動できるし、物を持つことができるが、物は自分で移動しないし、何も持つことができない。また、人は人を持つことはできない。こういったルールを決めるには、人と物が見分けられなくてはならない。もちろん、moveを評価する前に判断すればいいのだが、自動的にイベントを起こすためには、どこかでスクリプトが判断しなくてはならない。


そこで、主に2種類の案がある。

  • オブジェクトが中身として種別を持つ。 ex. (moon (is person))
  • 世界の外に種別に関するルールを書く。 ex. ((world ...) (is (person moon tues ...)))

分かれ道

1つ目の方法では、例えば人を探すとき、部屋を選んでからその中のオブジェクトの種類を見ることになる。名前から種別を得るときは、部屋を一つずつ当たってその名前のオブジェクトを探してからでないと出来ない。なんだか面倒そうだ。


2つ目の方法では、人を探したければ人の項目を当たればよい。名前から種別を得るのはやや面倒だが、欲しい種別の項目を探せば、その名前のオブジェクトがその種別かどうかすぐにわかる。


ということは、2つ目の方法が良さそうだ。ところで、オブジェクトの包含関係も、今までやったように直接表すのではなく、

(A-in-B (moon east) (tues south))

のように表した方が便利そうである。また、この形式で有ればオブジェクトオブジェクトらしい実体は必要なく、リストにせずに個別の要素として扱うことが出来そうだ。

世界データベース

オブジェクト自身が属性を持ったり、オブジェクト同士のデータ内での位置関係が意味を持ったりするのではなく、属性や関係性を個別に取り出して記述するというのは関係データベースのような方法である。ここまでマクロとか作ってみたが、今回のプログラムは止めて、次はデータベースっぽい感じで作り直してみよう。

2009-05-14

これからつくるもの 12:58

twitterbotはよく見かけるし、そーいうのも作ってみたいとは思う。でも、何か新規性のあるbotのアイデアがないので、それは後回しにして、今はローカルで動くものを作ってみたい。


どのようなものかというと、ルールとストーリーを渡すと、それにしたがってGMをしてくれるシステムだ。メッセージが表示されて、それに対してコマンドを返すとゲームが進行する。実際の動作はほぼZORKと同じようになると思う。


それだけならゲームブックのようなもので、作るのは簡単な部類に入るだろう。今回は、ゲーム内の世界の中でNPCが自由に動いているようなものを試したい。シムズストーリーみたいに、NPCが自立的に行動してる中を探索する感じである。どこまで作り込むかによるが、NPCの行動を決定するのにある程度のAIが必要である。


と、今回は前フリみたいなものだけ。しばらく色々考えてたのだが、なかなか大変そうなので、かなり単純化した問題から取り組まないと出来なそう。これからゆっくり進めていこう。

タイトル変更~ 13:05

こちらでは当分sims-likeなシステムの話題を扱うので日記の名前を変更した。


どうやって作るか見通しが立ってないけど、気楽に考えてみるのだ。

JasonvoitaJasonvoita2017/01/25 04:22изготовление открыток http://wkrolik.com.ua/products/konverty