プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(23)

まさかの2度めの更新です。やる気が溢れているのです。

エッジリストを完成させる

ここまでで作ったエッジリストをalistにします。
そしてランダムに通ったらゲームオーバーになるエッジを設定します。

CL-USER> (defun make-city-edges ()
           (let* ((nodes (loop for i from 1 to *node-num*
                              collect i))
                  (edge-list (connect-all-islands nodes (make-edge-list)))
                  (cops (remove-if-not (lambda (x)
                                         (zerop (random *cop-odds*)))
                                       edge-list)))
             (add-cops (edges-to-alist edge-list) cops)))
MAKE-CITY-EDGES
CL-USER>

もういちいちめげずに一つづつ理解していきます。
とはいえ、add-copsとedges-to-alistはまだ定義していないので、
変数の定義部分しか見れません。自分の小さな脳味噌にはちょうどいいです。
まず、nodesは簡単ですね。1から*node-num*まで刻む数値のリストです。
(1 2 3 ... 29 30)ってリストがnodesに格納されるはずです。
edge-listは…ここだ!前半で悩んだ部分がここで解消されました。
ここでエッジのリストを作って、全ての島を確実に繋ぐんですね!
さてcopsは…zeropってなんだ。…どうやら引数が0ならtですね。
ああ、通ったらゲームオーバーになる道の数は固定なわけではなく、
それぞれの道が15分の1の確率でゲームオーバーの道になるのか。
(random *cop-odds*)も15分の1の確率でtになり、
そしたらそこがcopsのリストに入る(ゲームオーバー箇所として
記録される)ということですね。

よし、続きを書いていきます

CL-USER> (defun edges-to-alist (edge-list)
           (mapcar (lambda (node1)
                     (cons node1
                           (mapcar (lambda (edge)
                                     (list (cdr edge)))
                                   (remove-duplicates (direct-edges node1 edge-list)
                                                      :test #'equal))))
                   (remove-duplicates (mapcar #'car edge-list))))
EDGES-TO-ALIST
CL-USER>

remove-duplicatesは、重複を取り除くそうです。
デフォルトではeqlを使って比較しているけども、今回はコンスを比較するので
testキーワードで#'equalを使うように設定しているとのこと。

まずはmapcarでedge-listからそれぞれの要素のcar部分を抜いて、
そこにremove-duplicatesで重複のないリストを作ってます。
そのリストにそのそれぞれの要素に適用する無名関数の中身は…
受け取った引数をnode1としてcons、繋ぐ対象は…
node1をcar部分に含んでいるものをdirect-edgesで出したリストを
remove-duplicatesで重複削除したリストの各要素をcdrで抜いたものを
リストにしたものですね!うわわわ、頭がパンクしそうです。
…具体例を与えて考えます。

CL-USER> (edges-to-alist '((1 . 2) (2 . 1) (2 . 3) (3 . 2)))
((1 (2)) (2 (1) (3)) (3 (2)))
CL-USER>

一番外側のmapcarではそれぞれのエッジの起点となるノードの
リストを作っています。上の例では(1 2 3)が作られます。
内側のmapcarでは与えられた起点ノードから行けるノードの
組み合わせのリストをedge-listから重複削除して作っています。
その抜いたリストのcdr部分をリストに入れて、
起点として最初のmapcarで出す要素とconsしている…。
自分の理解と言語化の限界です…。次行きます。

CL-USER> (defun add-cops (edge-alist edges-with-cops)
           (mapcar (lambda (x)
                     (let ((node1 (car x))
                           (node1-edges (cdr x)))
                       (cons node1
                             (mapcar (lambda (edge)
                                       (let ((node2 (car edge)))
                                         (if (intersection (edge-pair node1 node2)
                                                           edges-with-cops
                                                           :test #'equal)
                                             (list node2 'cops)
                                             edge)))
                                     node1-edges))))
                   edge-alist))
ADD-COPS
CL-USER>

また難解な…。いや、ちゃんと読めばわかるかも。頑張ります。
まず、引数として渡されるのは、先程の関数で作られたalistと
ゲームオーバーになるエッジのリストです。
外側のmapcarでedge-alistの要素を一つづつ処理します。
そこでは、node1にalistのキー、エッジの起点を
node1-edgesにnode1から伸びる場所のリストを格納します。
内側のmapcarは、node1から伸びる場所のリストを一つづつ処理します。
その処理の中に放り込まれるedgeは(1)←こんな形のはずなので
carを使ってリストを取っ払います。
intersectionは、2つのリストで共通の要素を求める関数だそうです。
ifでは、ここまでやってやっと作れたnode1とnode2のペアが
ゲームオーバーの道として設定されているかどうかを調べていますね。
もしedges-with-copsにあるなら、node2にcopsというシンボルを
くっつけたリストにしています。
そうでなけりゃただedge(括弧を取っ払う前の要素)を返します。
で、それを最初のmapcarで出したnode1とくっつけるワケすね。
つまり、'(1 (2))か'(1 (2 cops))が返ってくるわけで、
最終的には'( (1 (2)) (2 (3 cops)))みたいなリストになるはず。

ふう、解説によるとこれはネストされたalistですと。
エッジをこの形式にしておけば、あるノードを起点とする全てのエッジを
見つけるのは簡単だそうです。
(cdr (assoc node1 edges))とすればよいそうです。
ゲームオーバーの場所を見つけるのも、
(cdr (assoc node2 (cdr (assoc node1 edges))))とすりゃいいと。

ノードリストを作る

次は舞台となる街のノードを作ります。
各ノードには、ゲームオーバー道が近くのエッジにあるかどうか、
近くのノードに探しびとがいるか、あるいはヤバいやつがいるかといった
情報を持たせます。
近くにいるかどうかといった情報を付与するには、
そもそも近くのノードはどれかを知らねばなりません。
というわけで隣接するノードを知る関数です。

CL-USER> (defun neighbors (node edge-alist)
           (mapcar #'car (cdr (assoc node edge-alist))))
NEIGHBORS
CL-USER> (defun within-one (a b edge-alist)
           (member b (neighbors a edge-alist)))
WITHIN-ONE
CL-USER>

先程出てきたネストしたalistの利点とその応用ですね。

探しびとが近くにいるかどうかは、2ノード離れててもわかるようにします。
というわけで2つのノードの距離が2以下であるかどうか調べる関数です。

CL-USER> (defun within-two (a b edge-alist)
           (or (within-one a b edge-alist)
               (some (lambda (x)
                       (within-one x b edge-alist))
                     (neighbors a edge-alist))))
WITHIN-TWO
CL-USER>

ふむ。orを置いておいて、どれかの条件が真ならOKにすると。
まずはwithin-onですね。当然です。
そして、someか…リストに関数を適用した時、
一個でも真なら真を返す関数ということですね。
引数のリストは、aの隣接するノードをすべて出したもの、
それらに対してwithin-oneが真を出せば、
距離2のノードがあるってことですね。
よし、さっきに比べたらだいぶ簡単です。次行きます。

必要なユーティリティ関数ができたということで、
最終的なノードのalistを作る関数を作ります。
気力を振り絞って…。

CL-USER> (defun make-city-nodes (edge-alist)
           (let ((wumpus (random-node)) ;探し人のいる場所をランダムに決める。
                 (glow-worms (loop for i below *worm-num* ;belowなのでiは0~2(*worm-num*は3)
                                  collect (random-node)))) ;つまりここで3地点がglow-wormリストに含まれる
             (loop for n from i to *node-num* ;全てのノードに対して以下の処理を実行
                  collect (append (list n) ;ノードの番地を括弧に入れて付与される情報を待ち構えている。
                                  (cond ((eql n wumps) '(wumpus)) ;もしそのノードに探し人がいるなら
                                        ((within-two n wumpus edge-alist) '(blood!))) ;もし2ノード以内に探し人がいるなら
                                  (cond ((member n glow-worms) '(glow-worms)) ;もしそのノードにやばい奴がいるなら
                                        ((some (lambda (worm) ;もし1ノード以内にやばい奴がいるなら
                                                 (within-one n worm edge-alist))
                                               glow-worms)
                                         '(lights!)))
                                  (when (some #'cdr (cdr (assoc n edge-alist))) ;もし伸びてるエッジにゲームオーバーエッジがあるなら
                                    '(sirens!))))))
MAKE-CITY-NODES
CL-USER>

ふう、コメントしていったほうが理解しやすいですね。
もっと早くこの方法を取るべきでした。
いや、そもそもここであんまり複雑なことしてないか。

ゲームを開始するための関数

グラフの初期化ルーチンをまとめていきます。

CL-USER> (defun new-game ()
           (setf *congestion-city-edges* (make-city-edges))
           (setf *congestion-city-nodes* (make-city-nodes *congestion-city-edges*))
           (setf *player-pos* (find-empty-node))
           (setf *visited-nodes* (list *player-pos*))
           (draw-city))
NEW-GAME
CL-USER>

知らない関数が2つ!
まずfind-empty-nodesは何も情報が入っていないノードを
見つけるための関数です。
いきなりゲームクリアしたりやばい奴と同じノードにいたら白けますからね。

CL-USER> (defun find-empty-node ()
           (let ((x (random-node)))
             (if (cdr (assoc x *congestion-city-nodes*))
                 (find-empty-node)
                 x)))
FIND-EMPTY-NODE
CL-USER>

これは簡単ですね。random-nodeで場所を探して、
そこのcdrがnilでなければ再帰nilならOKです。

で、draw-cityはその名の通り舞台の街を描きます。

CL-USER> (defun draw-city ()
           (ugraph->png "/Users/user/Desktop/Lisp/city" *congestion-city-nodes* *congestion-city-edges*))
DRAW-CITY
CL-USER>

それでは…new-gameを実行してみます!

CL-USER> (new-game)
; Evaluation aborted on #<SYSTEM::SIMPLE-UNBOUND-VARIABLE #x000000020035B839>.
CL-USER>

エラーでした。Iは定義してないぞ!と怒られたのですが、
これだけいろんな関数があるとどこだかわからないですね。
まあ、探します。
…make-city-nodesな感じです。修正。

CL-USER> (defun make-city-nodes (edge-alist)
           (let ((wumpus (random-node)) ;探し人のいる場所をランダムに決める。
                 (glow-worms (loop for i below *worm-num* ;belowなのでiは0~2(*worm-num*は3)
                                  collect (random-node)))) ;つまりここで3地点がglow-wormリストに含まれる
             (loop for n from 1 to *node-num* ;全てのノードに対して以下の処理を実行 ;;i->1に修正
                  collect (append (list n) ;ノードの番地を括弧に入れて付与される情報を待ち構えている。
                                  (cond ((eql n wumpus) '(wumpus)) ;もしそのノードに探し人がいるなら ;;ここもwumpsになってた
                                        ((within-two n wumpus edge-alist) '(blood!))) ;もし2ノード以内に探し人がいるなら
                                  (cond ((member n glow-worms) '(glow-worms)) ;もしそのノードにやばい奴がいるなら
                                        ((some (lambda (worm) ;もし1ノード以内にやばい奴がいるなら
                                                 (within-one n worm edge-alist))
                                               glow-worms)
                                         '(lights!)))
                                  (when (some #'cdr (cdr (assoc n edge-alist))) ;もし伸びてるエッジにゲームオーバーエッジがあるなら
                                    '(sirens!))))))
MAKE-CITY-NODES
CL-USER> 

気を取り直して…

CL-USER> (new-game)
NIL
CL-USER>

f:id:programcat:20181002221147p:plain
感動的です…!

まだまだこの章でやることはあるのですが、
もう体力の限界です…。
明日また頑張ります。おやすみなさい。