BEAR Blog

Because everything is a resource.

GDD 2010 Pacman問題

| Comments

GDD 2010 Pacman Lv.3

GDD 2010 Dev Quiz

GDD2010のDev Quizの最終問題Pacman。DevQuizは見事不合格に終わったのですが、挑戦の記録というのと、提出後ですがLv.3が解けるようになったので記念に記します。

PHPで

普段使っているPHPでコーディングしました。WebではなくCLIです。1ファイルでコンソールでアニメが表示されるようにしました。現在のコードでのハイスコアはLv1, Lv2, Lv3それぞれ、41, 210, 489です。これは人の手をともわなないAI探索のみでのスコアです。

Pacman Lv.3 demo1

Pacman AI

最初にPacmanに適当な移動ロジックを組み込んでモンスターのいない迷路でドットが全部とれるかというところから始めました。

「誘惑に弱いけど好奇心が強く、失敗してもすぐに反省する」

こういうのどうだろう。Pacmanに性格をつけしてAIっぽい動きすれば面白いんじゃないかと。つまり…

  • 誘惑に弱い=隣接するドットを食べること優先
  • 好奇心=足跡を記録してなるべく行っていないところに行く
  • すぐに反省=反復強化学習

こんな感じです。実装にうつります。

まず移動可能な場所(上下左右、0〜4カ所)を調べます。0〜2カ所なら自動的に決めます。

0カ所=動けないので停止。
1カ所=その方向に移動。
2カ所=来た方向と逆の方向に(途中で反転しない)

※基本的にモンスターと同じです。

3、4カ所ある場合

移動可能な場所のうち、次の優先順位で方向を決めました。

  • 隣接するところにエサがあればその方向
  • 隣接するところで一回しか行ってなければその方向
  • 直線でエサが見えればその方向
  • 上記のどれにもあたらなければランダム

とりあえずこんなもので、この優先順位を変えたりできる仕組みもあればと。

モンスターのいない迷路を走らせてみる

迷路を自走させてみるとそれなりに効率的に走りドットを全て食べてくれます。ちょっと安心。
パックマンというより自走式掃除機ルンバのような動きです。みててなかなか面白い。

あとはモンスター…どうだろ?

モンスターは基本、壁と考えてみる。単にその場所にいけないという点で壁と同じ。つまりパックマン視点だと迷路が1フレーム単位で変化するようなもの。

元々迷路全体をしっかり把握してるわけでなし、上記のその場その場のロジックでドットが全部食べれるのだからまあ何万回も走らしたら全部適当に食べてくれるだろう…と。2

モンスターを組み込んでみる

取りかかるとパックマン自走のコーディングのヒントと思えるようなとこが多々あり…先にモンスターからやれば良かったとすぐに気づきます。orz

パックマン自走コードにも手をなおしつつ、それでも一つ一つモンスターを組み込みます。

例えば敵V3 はこんな感じ。

敵 V

  • 敵から見た自機の相対位置を (dx, dy) と表すものとします。次のルールを上から順に適用し、最初に選ばれた方向に移動します。

  • dy ≠ 0 でかつ dy の符号方向にあるマスが進入可能であれば、その方向に移動します。

  • dx ≠ 0 でかつ dx の符号方向にあるマスが進入可能であれば、その方向に移動します。
  • 現在位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動する。

こういうABSでの割り算で方向を出すとか、中学生の時にBASICで書いて以来かも…とか懐かしみながら組み込んで行きます。

1
$ddy = $dy/abs($dy);

敵L、敵R

面倒そうなモンスターのロジックが出てきました。現在の方向からみての右、左です。

敵 L

現在位置への進入方向から見て相対的に 左、前、右 の順で最初に進入可能なマスの方向に移動します。

「右向いてるキャラの左は上」を求めるような実装です。普段しているWebのプログラミングで現在の方向からの相対的な「右」とか「左」は中々でてきません。

どうしようか、「もし今右を向いてたら、”右”は下方向」「下を向いてたら右は…」こういうのを4つ書くかなあ…いや…

…それもちょっと…そもそも「右」とは何かっていうと..うーん、国語辞書でも苦しい感じの説明だよなあ….コーヒー飲みつつ色々考えながら窓の外を一分眺めます。

…配列で相対方向?

結局、「時計回り」の配列を用意して利用する方法を考えました。

1
2
3
4
5
6
    /**
     * 時計回り配列
     *
     * @var array
     */
    protected $_clockwiseDirection = array(array(0, 1), array(-1, 0), array(0, -1), array(1, 0));

array(0, 1)、array(-1, 0)…と下、左、上、右という時計回りの方向が並んでる配列(↓←↑→)です。

↓、←、↑、→と右回りの配列をつくって、1つ進んだら右回り、1つ後退したら左回り。

時計方向で並んでる配列の中で自分の「となりの右」が現在の方向から見た「右」です。配列の添字を1つ進めると右、減らすと左になります。一番右や左ではぐるっとまわって反対側の配列をとります。

うまく行きそうです。

モンスターはこれに優先順位があります。このようなコードになりました。4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    /**
     * モンスターL
     *
     * 現在位置への進入方向から見て相対的に 左、前、右 の順
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveL(array $maze, $pacmanX, $pacmanY)
    {
        $directionStrategy = $this->_getRelativeDirection(array(-1, 0, 1));
        $this->_setPositionStatus($maze, $directionStrategy, true);
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
     */

14行目:左(-1)、前(0)、右(1)を優先順位にした絶対方向座標が$directionStrategyとしてつくられます。
15行目: 迷路配列をみて、優先順位($directionStrategy)どおりの順番で壁ではないかチェックして移動可能な座標の配列をつくります。
16行目: 移動可能で優先順位の最も高い座標が配列の最初(0)にはいりっているのでそれを取り出します。

「特定の優先方向配列を用意して、その移動可能状態を調べ、個別ロジックによって移動方向を決定」…

これがキャラクターの移動の基本戦略となり、Pacmanにも利用しました。

モンスターの動きデバック用の迷路をつくり、動きを一つ一つ確認。コンソールでのPHPプログラムでしたがusleep()関数と画面クリアを使えば、コンソールでもアニメーションが見られるのがわかりました。

1
 echo "\033[;H\033[2J"; // これで画面クリア

いよいよモンスターのいる迷路をパックマンが自走

予想と違ってなかなか厳しい。最初はクリアできませんでした。….レベル1でさえも!!
当初、レベル3は現状の反復学習なし実装だと無理と確信します。

ところがレベル1は無理なのですが、レベル2をやると割とあっさりクリアできました。

???

debugモードで観察すると。効率よくするための「パックマンAI」が逆に正解ルートを必ず行けなくしてるのがわかりました。

レベル1の方針を変えます。

“ランダム”

何も考えずランダムに動かしてを繰り返すと数秒で最適解41点にたどりつけました。orz
レベル1、レベル2なんとか解けてそろそろタイムリミット。解けないLv.3の得点とソースコードを添えて提出しました。

不合格、そしてLv.3クリア

枠や開催場所によってはメアド入れたら通ったという方もいる中、GDD2010の参加不合格通知が届きます。結果からいうとパックマンはやる必要がないくらいの配点でした。5 自走パックマンに一生懸命で他の問題にほとんど手をつけてないのも原因でした。

しかししばらくして、やりかけだったプログラムの興味70%、勉強20%、パックマンLove10%という気持ちがLv.3解へのコーディングへと向かわせます。

反復学習の実装です。

深さ優先探索

深さ優先探索のイメージ

プログラムしたときは手法は思いついきで適当にした方法なのですが、実装が完全に終わって今日読んだオライリーの アルゴリズムクイックリファレンスで分かったのがこれは深さ優先探索というものなんだそうです。 6

wikiで以下のように説明されてます。

深さ優先探索(ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう)は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。

オライリー本からも引用します。

「出来る限り前方に進み、同じ状態を二度と本文せずに、目的状態への経路を見つけようとする。探索木によっては、盤面の数が大変多くなるので、深さ優先探索は最大探索深さが前もって定まっているような場合にのみ実用的になる。深さ優先探索は、これから訪問する盤面状態をスタックに積み、訪問した盤面状態を集合に保持して、管理する。深さ優先探索は、スタックから未訪問の盤面状態を取り出し、可能な手を用いて、次の盤面状態集合を計算して木を拡張する。目標状態に到達したら、探索は終了する。」

Pacmanでこう実装していました。7

  • ブランチは移動可能な場所が3つ以上あったとき
  • ブランチがあるときにそのゲーム状態をスタックに積む。
  • 失敗したらスタックからゲームを取り出し失敗する前まで戻ってゲーム再開
  • 自分の行動は記録し、失敗を繰り返さない

※ゲーム全体はゲームオブジェクトとして1つの変数になってるので、それをarray_pushで配列としてスタックに積みます。8

探索木

実際の動きはこのようになります。

h mark 行き先(h)をマークし pushed 失敗しても前回の状態に戻れるように前回ゲームをスタックにつみ h moved 進みます hh mark 行き先(hh)をマークし...  以下同様 h pushed hh moved hhk mark hh pushed hhk moved hhkk mark hhk pushed hhkk moved hhkkl mark hhkk pushed hhkkl moved hhkkl GAME OVER ゲームオーバーになったので hhkk is poped 積まれたゲームを上からとりだし hhkkl is marked 移動可能方向を確認。hhkklという方角はすでに探索してるのでいきません。 hhkk GAME OVER 移動できる方角がもうないのでここでもゲームオーバーです。 hhk is poped その前につまれたゲームを取り出し ....以下同様 hhkk is marked hhk GAME OVER hh is poped hhk is marked hhl mark

これを繰り返せば全ての木の枝が探索できるはずです。9

Lv.1でも全経路は無理?

ところがそんなに簡単ではありません。Lv1くらい無条件の全経路を調べられないかと思いましたが、やはり難しそうです。この動画が少し参考になるでしょうか。階乗の計算量は膨大です。

GDD Pacman LV.1 Deep-First Search

Lv2, Lv3では3つ以上の交差点でのみブランチをつくることにしました。また時間によるゲームオーバーからはスタックからゲームを取り出すことなしに、最初からやり直すのを繰り返す事にしました。10 11

幅優先探索

試してはいませんが、他の検索の紹介を。幅優先探索も同じ様に同じ状態を2度と訪問しないようにして、ゲーム状態を初期状態から近い順に評価します。深さ優先と違うのは、探索開始点から近いところから順に探索をしていくところです。深さ優先探索がスタックを使用するのに対して、幅優先探索はキューをする違いを理解すれば実装のイメージがわくのではないでしょうか。12

Lv.2, Lv.3の探索木

交差点だけブランチをつくるLv.2とLv.3でタイムオーバーまでゲームをしたら大体100ゲーム超ぐらいのゲームがスタックされます。Lv.2、Lv.3もあまり変わらなくLv.3がやや多いくらいです。

以下はタイムオーバーまで5回プレイした例です。

Lv.3 Score:284/296 Point:284 Game:700/700 Stacked Game:107 Score:277/296 Point:277 Game:700/700 Stacked Game:103 Score:277/296 Point:277 Game:700/700 Stacked Game:111 Score:269/296 Point:269 Game:700/700 Stacked Game:107 Score:267/296 Point:267 Game:700/700 Stacked Game:101 Lv.2 Score:131/147 Point:131 Game:300/300 Stacked Game:107 Score:129/147 Point:129 Game:300/300 Stacked Game:112 Score:120/147 Point:120 Game:300/300 Stacked Game:111 Score:127/147 Point:127 Game:300/300 Stacked Game:101 Score:135/147 Point:135 Game:300/300 Stacked Game:100

なかなか良いスコアです。これが一瞬で出るので、これを一晩ぶん回せば…と期待してしまいますがここからのスコアはなかなか伸びません。13 3ドット取り残しとゲームクリアではクイズの配点としての差はあまりないでしょうけど、プログラムの性能としては格段に違います。

それでもLv.3クリアが一瞬から数分程度でできるまでの性能になりました。僕のGDD2010はここで終わりです。

最後に

昔の事ですがファミコンやゲームボーイでアクションゲームをいくつか作ったことがあります。14 中高生の時もBASICや機械語15 でこういうキャラクタベースのゲームを趣味でつくったりしてました。16

思えばそれ以来のゲームプログラミングです。これからもこういうプログラムはする事はなかなかないと思うので貴重な機会となりました。参加はなりませんでしたが#gdd2010jpで他の参加者の話を聞いたりコードを見たりするのも楽しかったです。GDD2010JP DevQuiz ソース晒し祭りでもPHPや自動探査で解いてるコードが少ないのとどういう風にコーディングしたらいいかさっぱり分からないという方もTLで散見したりで、多少なりとも参考になればと思い記事をかきました。

最後にasannouさんの作製の素晴らしいガジェット17 を貼付けて終わりにします。Lv.3クリアのベストスコアです。18 長文読んで頂いてありがとうございました。

ソースコード

ダウンロードはcode pad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
<?php
/**
 * GDD 2010 DevQuiz Pacman for PHP 5.3
 *
 * @author @koriym
 */
/**
 * デバック用関数 p
 */
function p($values = '') {
    $trace = debug_backtrace();
    $file = $trace[0]['file'];
    $line = $trace[0]['line'];
    $method = (isset($trace[1]['class'])) ? " ({$trace[1]['class']}" . '::' . "{$trace[1]['function']})" : '';
    $fileArray = file($file, FILE_USE_INCLUDE_PATH);
    $p = trim($fileArray[$line - 1]);
    unset($fileArray);
    preg_match("/p\((.+)[\s,\)]/", $p, $matches);
    $varName = isset($matches[1]) ? $matches[1] : '';
    //    $label = "$varName in {$file} on line {$line}$method";
    $label = "on line {$line}$method";
    $values = is_bool($values) ? ($values ? "true" : "false") : $values;
    echo "\n{$varName}=[". print_r($values, true) . "] $label\n";
}
/**
 * キャラクターインターフェイス
 *
 * @param string $MyChar 文字
 * @param int    $y      y座標
 * @paramint     $x      x座標
 *
 */
interface Character_Interface{
    public function __construct($myChar, $y, $x);
}
/**
 * キャラクター
 *
 */
abstract class Character implements Character_Interface
{
    /**
     * キャラ文字
     *
     * @var string
     */
    protected $_char;
    /**
     * X座標
     *
     * @var int
     */
    protected $_x;
    /**
     * Y座標
     *
     * @var int
     */
    protected $_y;
    /**
     * X移動
     *
     * @var int
     */
    protected $_dx = 0;
    /**
     * Y移動
     *
     * @var int
     */
    protected $_dy = 0;
    /**
     * 移動可能座標
     *
     * @var array
     */
    protected $_wayToGo = array();
    /**
     * 移動可能場所数
     *
     * @var int
     */
    protected $_wayToGoCount = 0;
    /**
     * 時計回り配列
     *
     * @var array
     */
    protected $_clockwiseDirection = array(array(0, 1), array(-1, 0), array(0, -1), array(1, 0));
    /**
     * コンストラクタ
     *
     * @param string $myChar
     * @param int    $x
     * @param int    $y
     */
    public function __construct($myChar, $x, $y)
    {
        $this->_myChar = $myChar;
        $this->_x = $x;
        $this->_y = $y;
    }
    /**
     * ポジション取得
     *
     * @return array
     */
    public function getPosition(){
        return array($this->_x, $this->_y);
    }
    /**
     * データ取得
     *
     * @return array
     */
    public function get()
    {
        return array($this->_myChar, $this->_x, $this->_y, $this->_dx, $this->_dy);
    }
    /**
     * キャラクタの移動可能状態をセット
     *
     * @param array $maze              迷路
     * @param array $directionStrategy 移動方向戦略
     *
     * @return void
     */
    protected function _setPositionStatus($maze, $directionStrategy)
    {
        $cnt = 0;
        $this->_wayToGo = array();
        $wayToGo = array();
        foreach ($directionStrategy as $item) {
            list($dx, $dy) = $item;
            $x = $this->_x + $dx;
            $y = $this->_y + $dy;
            $isExist = isset($maze[$y][$x]);
            if ($isExist &#038;&#038; $maze[$y][$x] === '.' || $maze[$y][$x] === ' ') {
                $this->_wayToGo[] = array('dy' => $dy, 'dx' => $dx);
                $cnt++;
            }
            $this->_wayToGoCount = $cnt;
        }
    }
}
/**
 * パックマン
 *
 */
class Pacman extends Character
{
    /**
     * 方向履歴
     *
     * @var string
     */
    private $_joyStick = '';
    /**
     * 移動足跡
     *
     * @var array
     */
    private $_footprintMap = array();
    /**
     * 移動足跡初期化
     *
     * @param int $width 幅
     * @param int $hight 高さ
     *
     * @return void
     */
    public function setFootprintMap($width, $hight)
    {
        for ($i = 0; $i < $hight ; $i++) {
            $this->_footprintMap[$i] = array_fill(0, $width, 0);
        }
    }
    /**
     * パックマン移動
     *
     * @param array        $maze     迷路
     * @param int          $time     タイム
     * @param Pacman_Dicon $strategy DIコンテナ
     *
     * @return void
     */
    public function move($maze, $time, Pacman_Dicon $dicon)
    {
        $this->_wayToGo = array();
        $funcMoveStrategy = $dicon->get('move');
        $this->_setPositionStatus($maze, $dicon->get('direction'));
        try {
            list($this->_dx, $this->_dy, $takeSnapShot) = $r = $funcMoveStrategy($this->_x, $this->_y, $this->_dx, $this->_dy, $maze, $this->_wayToGoCount, $this->_wayToGo, $this->_footprintMap, $this->_joyStick);
        } catch (Exception $e) {
            Pacman_Quiz::$pacmanThought[$this->_joyStick][$this->_dy][$this->_dx] = true;
            throw $e;
        }
        if ($takeSnapShot) {
            $c = $this->getJoyStickChar($this->_dx,$this->_dy);
            Pacman_Quiz::$pacmanThought[$this->_joyStick][$this->_dy][$this->_dx] = true;
        }
        $this->_x += $this->_dx;
        $this->_y += $this->_dy;
        $this->_joyStick .= self::getJoystickChar($this->_dx, $this->_dy);
        $this->_footprintMap[$this->_y][$this->_x]++;
        $result = array($this->_x, $this->_y, $this->_dx, $this->_dy, $takeSnapShot);
        return $result;
    }
    /**
     * 方向からジョイスティック名を取得
     *
     * @param int $dx
     * @param int $dy
     *
     * @return string
     */
    public static function getJoyStickChar($dx, $dy) {
        $joyStickCharacters = array('j', 'h', 'k', 'l', '.');
        $direction = array_search(array($dx, $dy), array(array(0, 1), array(-1, 0), array(0, -1), array(1, 0), array(0,0)));
        $result = $joyStickCharacters[$direction];
        return $result;
    }
    /**
     * 足跡文字列取得
     *
     * @return string
     */
    public function getJoystick()
    {
        return $this->_joyStick;
    }
}
/**
 * パックマンDIコンテナ
 *
 */
class Pacman_Dicon
{
    /**
     * サービス取得
     *
     * @param string $service サービス取得名
     *
     * @return mixed
     */
    public function get($service)
    {
        switch ($service) {
            case 'direction':
                $directionStrategy = array(array(-1, 0), array(0, -1), array(1, 0), array(0, 1));
                shuffle($directionStrategy);
                return $directionStrategy;
                break;
            case 'move':
                $function =  function ($x, $y, $dx, $dy, $maze, &#038;$wayCnt, $wayToGo, $footprintMap, $joystick)
                {
                    switch ($wayCnt) {
                        case 0:
                            // 動けない
                            return array(0, 0, false);
                        case 1:
                            // 行き止まりなので唯一いける方向へ
                            $togo = $wayToGo[0];
                            return array($togo['dx'], $togo['dy'], false);
                        case 2:
                            // バックじゃない方
                            $isReverse0 = ($dx === ($wayToGo[0]['dx'] * -1) &#038;&#038; $dy === ($wayToGo[0]['dy'] * -1));
                            $isReverse1 = ($dx === ($wayToGo[1]['dx'] * -1) &#038;&#038; $dy === ($wayToGo[1]['dy'] * -1));
                            if ($isReverse0 || $isReverse1) {
                                $i = !$isReverse0 ? 0 : 1;
                                return array($wayToGo[$i]['dx'], $wayToGo[$i]['dy'], false);
                            } else {
                                break;
                            }
                        case 3:
                        case 4:
                            // 交差点で考える
                            break;
                    }
                    // 同じ行動はとらない
                    $wayToGoFiltered = array();
                    foreach ($wayToGo as $toGo) {
                        if (!isset(Pacman_Quiz::$pacmanThought[$joystick][$toGo['dy']][$toGo['dx']])) {
                            $wayToGoFiltered[] = $toGo;
                        } else {
                            $wayCnt--;
                        }
                    }
                    if (!$wayToGoFiltered) {
                        // どこも行けない
                        throw new Exception('no_way_to_go');
                    } else {
                        $wayToGo = $wayToGoFiltered;
                    }
                    foreach ($wayToGoFiltered as $toGo) {
                        if ($maze[$y + $toGo['dy']][$x + $toGo['dx']] === '.') {
                            return array($toGo['dx'], $toGo['dy'], true);
                        }
                    }
                    foreach ($wayToGoFiltered as $toGo) {
                        if ($footprintMap[$y + $toGo['dy']][$x + $toGo['dx']] < = 1) {
                            return array($toGo['dx'], $toGo['dy'], true);
                        }
                    }
                    foreach ($wayToGoFiltered as $toGo) {
                        $dx = $toGo['dx'];
                        $dy = $toGo['dy'];
                        while (true) {
                            if ($maze[$y + $dy][$x + $dx] === '.') {
                                $find = true;
                                break;
                            } elseif (!isset($maze[$y + $dy][$x + $dx]) || $maze[$y + $dy][$x + $dx] === '#') {
                                $find = false;
                                break;
                            }
                            $dx++;
                            $dy++;
                        }
                        if ($find === true) {
                            return array($toGo['dx'], $toGo['dy'], true);
                        }
                    }
                    $dx = $wayToGoFiltered[0]['dx'];
                    $dy = $wayToGoFiltered[0]['dy'];
                    return array($dx, $dy, true);
                };
        }
        return $function;
    }
}
/**
 * パックマンDIコンテナ 問題1用
 *
 */
class Pacman_Dicon_Q1 extends Pacman_Dicon
{
    /**
     * サービス取得
     *
     * @param string $service サービス取得名
     *
     * @return mixed
     */
        public function get($service)
    {
        switch ($service) {
            case 'direction':
                //$directionStrategy = array(array(-1, 0), array(0, -1), array(1, 0), array(0, 1), array(0, 0));
                $directionStrategy = array(array(-1, 0), array(0, -1), array(1, 0), array(0, 1));
                shuffle($directionStrategy);
                return $directionStrategy;
            case 'move':
                $function =  function ($x, $y, $dx, $dy, $maze, &#038;$wayCnt, $wayToGo, $footprintMap, $joystick)
                {
                    if ($wayToGo) {
                        $dx = $wayToGo[0]['dx'];
                        $dy = $wayToGo[0]['dy'];
                        return array($dx, $dy, true);
                    } else {
                        throw new Exception('no_way_to_go');
                    }
                };
        }
        return $function;
    }
}
/**
 * モンスター
 */
class Monster extends Character
{
    /**
     * 最初?
     *
     * @var bool
     */
    private $_init = true;
    /**
     * モンスターL
     *
     * @var string
     */
    private $_j = 'L';
    /**
     * 移動
     *
     * @param array $maze
     * @param int   $pacmanX
     * @param int   $pacmanY
     *
     * @return void
     */
    public function move($maze, $pacmanX, $pacmanY)
    {
        $this->_wayToGo = array();
        if ($this->_init === true) {
            //時刻 t = 0 においては、初期位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動します。
            $this->_init = false;
            $this->_setPositionStatus($maze, $this->_clockwiseDirection);
            $this->_dy = $this->_wayToGo[0]['dy'];
            $this->_dx = $this->_wayToGo[0]['dx'];
        } else {
            //下、左、上、右 の順
            $this->_setPositionStatus($maze, $this->_clockwiseDirection);
            switch ($this->_wayToGoCount) {
                case 1:
                    // 行き止まりなので唯一いける方向へ
                    $togo = $this->_wayToGo[0];
                    $this->_dy = $togo['dy'];
                    $this->_dx = $togo['dx'];
                case 2:
                    // バックじゃない方
                    $isReverse = ($this->_dx === ($this->_wayToGo[0]['dx'] * -1) &#038;&#038; $this->_dy === ($this->_wayToGo[0]['dy'] * -1));
                    if ($isReverse) {
                        $this->_dy = $this->_wayToGo[1]['dy'];
                        $this->_dx = $this->_wayToGo[1]['dx'];
                    } else {
                        $this->_dy = $this->_wayToGo[0]['dy'];
                        $this->_dx = $this->_wayToGo[0]['dx'];
                    }
                    break;
                case 3:
                case 4:
                    // モンスターに応じて
                    $method = '_move' . $this->_myChar;
                    list($this->_dx, $this->_dy) = $this->$method($maze, $pacmanX, $pacmanY);
                    if ($this->_dx == 0 &#038;&#038; $this->_dy == 0){
                        p("error $this->_myChar");exit();
                    }
                    break;
                default:
            }
        }
        $this->_y += $this->_dy;
        $this->_x += $this->_dx;
        // もし以前パックマンがいたところに移動したら”王手”。パックマンは前にモンスターがいたところには移動できない。仮に壁にする。
        $makeMeWall = ($this->_x === $pacmanX &#038;&#038; $this->_y === $pacmanY);
        $wall = $makeMeWall ? array('x' => $this->_x - $this->_dx, 'y' => $this->_y - $this->_dy) : false;
        $result = array($this->_x, $this->_y, $this->_myChar, $wall);
        return $result;
    }
    /**
     * モンスターV
     *
     * 敵から見た自機の相対位置を (dx, dy) と表すものとします。次のルールを上から順に適用し、最初に選ばれた方向に移動します。
     *
     * 1. dy ≠ 0 でかつ dy の符号方向にあるマスが進入可能であれば、その方向に移動します。
     * 2. dx ≠ 0 でかつ dx の符号方向にあるマスが進入可能であれば、その方向に移動します。
     * 3. 現在位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動する。
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveV(array $maze, $pacmanX, $pacmanY)
    {
        $dx = $pacmanX - $this->_x;
        $dy = $pacmanY - $this->_y;
        // 1
        if ($dy !== 0 ) {
            $ddy = $dy/abs($dy);
            if (isset($maze[$this->_y + $ddy][$this->_x]) &#038;&#038; $maze[$this->_y + $ddy][$this->_x] !== '#') {
                return array(0, $ddy);
            }
        }
        // 2
        if ($dx !== 0 ){
            $ddx = $dx/abs($dx);
            if (isset($maze[$this->_y][$this->_x + $ddx]) &#038;&#038; $maze[$this->_y][$this->_x + $ddx] !== '#') {
                return array($ddx, 0);
            }
        }
        // 3
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターH
     *
     * 敵 V とほぼ同じです。唯一異なるのは 、進行方向を決めるルールのうち
     * 最初の二つのルールの適用順序が入れ替わるところです。
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveH(array $maze, $pacmanX, $pacmanY)
    {
        $dx = $pacmanX - $this->_x;
        $dy = $pacmanY - $this->_y;
        // 2
        if ($dx !== 0 ){
            $ddx = $dx/abs($dx);
            if (isset($maze[$this->_y][$this->_x + $ddx]) &#038;&#038; $maze[$this->_y][$this->_x + $ddx] !== '#') {
                return array($ddx, 0);
            }
        }
        // 1
        if ($dy !== 0 ) {
            $ddy = $dy/abs($dy);
            if (isset($maze[$this->_y + $ddy][$this->_x]) &#038;&#038; $maze[$this->_y + $ddy][$this->_x] !== '#') {
                return array(0, $ddy);
            }
        }
        // 3
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターL
     *
     * 現在位置への進入方向から見て相対的に 左、前、右 の順
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveL(array $maze, $pacmanX, $pacmanY)
    {
        $directionStrategy = $this->_getRelativeDirection(array(-1, 0, 1));
        $this->_setPositionStatus($maze, $directionStrategy, true);
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターR
     *
     * 現在位置への進入方向から見て相対的に 右、前、左  の順
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveR(array $maze, $pacmanX, $pacmanY)
    {
        $directionStrategy = $this->_getRelativeDirection(array(1, 0, -1));
        $this->_setPositionStatus($maze, $directionStrategy, true);
        $result = array($this->_wayToGo[0]['dx'], $this->_wayToGo[0]['dy']);
        return $result;
    }
    /**
     * モンスターJ
     *
     * 最初は敵Lの行動、次回は敵Rの行動、さらに次回はまた敵Lの行動、と繰り返します。
     *
     * @param array $maze    迷路
     * @param int   $pacmanX パックマンX座標
     * @param int   $pacmanX パックマンY座標
     *
     * @return array
     */
    private function _moveJ(array $maze, $pacmanX, $pacmanY)
    {
        $method = "_move{$this->_j}";
        $result = $this->$method($maze, $pacmanX, $pacmanY);
        $this->_j = ($this->_j === 'L') ? 'R' : 'L';
        return $result;
    }
    /**
     * 進行方向に対しての相対方向(左右など)戦略の配列を作成
     *
     * @param interger $relativeDirection 1=右, -1=左
     *
     * @return array
     */
    private function _getRelativeDirection($relativeDirections)
    {
        $result = array();
        $currentDirection = array($this->_dx, $this->_dy);
        foreach ($relativeDirections as $relativeDirection) {
            $pos = array_search($currentDirection, $this->_clockwiseDirection);
            $directionIndex = $pos + $relativeDirection;
            if ($directionIndex === -1 ) {
                $directionIndex = 3;
            }
            if ($directionIndex === 4 ) {
                $directionIndex = 0;
            }
            array_push($result, $this->_clockwiseDirection[$directionIndex]);
        }
        return $result;
    }
}
/**
 * ゲーム
 *
 */
class Pacman_Game
{
    /**
     * スコア
     *
     * @var int
     */
    private $_score = 0;
    /**
     * クリアスコア
     *
     * @var int
     */
    private $_clearScore = 0;
    /**
     * 制限時間
     *
     * @var int
     */
    private $_timeOut = 50;
    /**
     * 時間
     *
     * @var int
     */
    private $_time = 0;
    /**
     * パックマン
     *
     * @var Pacman
     */
    private $_pacman;
    /**
     * モンスター
     *
     * @var array
     */
    private $_monsters = array();
    /**
     * 迷路
     *
     * @var array
     */
    private $_maze = array();
    /**
     * キャラ付迷路
     *
     * @var array
     */
    private $_mazeWithChar;
    /**
     * キャラなし迷路
     *
     * @var array
     */
    private $_mazeWithoutChar;
    /**
     * パックマンX座標
     *
     * @var int
     */
    private $_pacmanX;
    /**
     * パックマンY座標
     *
     * @var int
     */
    private $_pacmanY;
    /**
     * デバック?
     *
     * @var bool
     */
    private $_debug = false;
    /**
     * デバックアニメーション時間
     *
     * @var int
     */
    private $_debugTime = 0;
    /**
     * デバックアニメーション?
     *
     * @var bool
     */
    private $_debugAnimation = false;
    /**
     * パックマンDIコンテナ
     *
     * @var Pacman_Dicon
     */
    private $_pacmanDicon;
    /**
     * __clone
     */
    public function __clone()
    {
        $this->_pacman = clone $this->_pacman;
        $cloneMonsters = array();
        foreach ($this->_monsters as $monster) {
            $cloneMonsters[] = clone $monster;
        }
        $this->_monsters = $cloneMonsters;
    }
    /**
     * 迷路から必要なオブジェクトやプロパティをセット
     *
     * +Pacmanオブジェクト
     * +Monsterオブジェクト
     * +ドットの数
     * +キャラクターがいない迷路
     */
    private function _injectFromMaze($maze)
    {
        $point = 0;
        $this->_pacman = null;
        $this->_monsters = array();
        for ($y = 0; isset($maze[$y]); $y++) {
            for($x = 0 ; $x < count($maze[$y]); $x++) {
                $char = $maze[$y][$x];
                if ($char === '@') {
                    $this->_pacman = new Pacman($char, $x, $y);
                    $this->_pacman->setFootprintMap(count($maze[0]), count($maze));
                    $maze[$y][$x] = ' ';
                } elseif ($char === '.') {
                    $point++;
                } elseif (preg_match('/[A-Z]/', $char, $matches)) {
                    $this->_monsters[] = new Monster($char, $x, $y);
                    $maze[$y][$x] = ' ';
                }
            }
        }
        $this->_clearScore = $point;
        $this->_maze = $maze;
    }
    /**
     * 問題1
     *
     * @return void
     */
    public function _injectQuestionOne()
    {
        $maze = array();
        $maze[] = $this->_split('###########');
        $maze[] = $this->_split('#.V..#..H.#');
        $maze[] = $this->_split('#.##...##.#');
        $maze[] = $this->_split('#L#..#..R.#');
        $maze[] = $this->_split('#.#.###.#.#');
        $maze[] = $this->_split('#....@....#');
        $maze[] = $this->_split('###########');
        $this->_injectFromMaze($maze);
        $this->_pacmanDicon = new Pacman_Dicon_Q1();
        $this->_timeOut = 50;
    }
    /**
     * 問題2
     *
     * @return void
     */
    public function _injectQuestionTwo()
    {
        $maze = array();
        $maze[] = $this->_split('####################');
        $maze[] = $this->_split('###.....L..........#');
        $maze[] = $this->_split('###.##.##.##L##.##.#');
        $maze[] = $this->_split('###.##.##.##.##.##.#');
        $maze[] = $this->_split('#.L................#');
        $maze[] = $this->_split('#.##.##.##.##.##.###');
        $maze[] = $this->_split('#.##.##L##.##.##.###');
        $maze[] = $this->_split('#.................L#');
        $maze[] = $this->_split('#.#.#.#J####J#.#.#.#');
        $maze[] = $this->_split('#L.................#');
        $maze[] = $this->_split('###.##.##.##.##.##.#');
        $maze[] = $this->_split('###.##.##R##.##.##.#');
        $maze[] = $this->_split('#................R.#');
        $maze[] = $this->_split('#.##.##.##.##R##.###');
        $maze[] = $this->_split('#.##.##.##.##.##.###');
        $maze[] = $this->_split('#@....R..........###');
        $maze[] = $this->_split('####################');
        $this->_injectFromMaze($maze);
        $this->_pacmanDicon = new Pacman_Dicon();
        $this->_timeOut = 300;
    }
    /**
     * 問題3
     *
     * @return void
     */
    public function _injectQuestionThree()
    {
        $maze = array();
        $maze[] = $this->_split('##########################################################');
        $maze[] = $this->_split('#........................................................#');
        $maze[] = $this->_split('#.###.#########.###############.########.###.#####.#####.#');
        $maze[] = $this->_split('#.###.#########.###############.########.###.#####.#####.#');
        $maze[] = $this->_split('#.....#########....J.............J.......###.............#');
        $maze[] = $this->_split('#####.###.......#######.#######.########.###.#######.#####');
        $maze[] = $this->_split('#####.###.#####J#######.#######.########.###.##   ##.#####');
        $maze[] = $this->_split('#####.###L#####.##   ##L##   ##.##    ##.###.##   ##.#####');
        $maze[] = $this->_split('#####.###..H###.##   ##.##   ##.########.###.#######J#####');
        $maze[] = $this->_split('#####.#########.##   ##L##   ##.########.###.###V....#####');
        $maze[] = $this->_split('#####.#########.#######.#######..........###.#######.#####');
        $maze[] = $this->_split('#####.#########.#######.#######.########.###.#######.#####');
        $maze[] = $this->_split('#.....................L.........########..........R......#');
        $maze[] = $this->_split('#L####.##########.##.##########....##....#########.#####.#');
        $maze[] = $this->_split('#.####.##########.##.##########.##.##.##.#########.#####.#');
        $maze[] = $this->_split('#.................##............##..@.##...............R.#');
        $maze[] = $this->_split('##########################################################');
        $this->_injectFromMaze($maze);
        $this->_pacmanDicon = new Pacman_Dicon();
        $this->_timeOut = 700;
    }
    /**
     * 初期化
     *
     * @return void
     */
    public function init()
    {
        // init
        $this->_time = 0;
        $this->_score = 0;
        $this->_mazeWithChar = $this->_mazeWithoutChar = $this->_maze;
        $this->_pacmanX = $this->_pacmanY = 0;
    }
    /**
     * パックマン取得
     *
     * @return Pacman
     */
    public function getPacman()
    {
        return $this->_pacman;
    }
    /**
     * 1ゲームプレイ
     *
     * @return array
     */
    public function runGame()
    {
        // init
        $lastGame = clone $this;
        $isHit = $isTimeOut = $isClear = false;
        Pacman_Quiz::$gameCount++;
        // main
        while (!$isHit &#038;&#038; !$isClear) {
            $this->_time++;
            $isTimeOut = ($this->_time >= $this->_timeOut);
            if ($isTimeOut === true) {
                break;
            }
            // モンスター
            $this->_runMonsters();
            // pacman
            list($this->_pacmanX, $this->_pacmanY, $dx, $dy, $takeSnapShot) = $this->_pacman->move($this->_mazeWithChar, $this->_time, $this->_pacmanDicon);
            if ($this->_mazeWithoutChar[$this->_pacmanY][$this->_pacmanX] === '.') {
                $this->_score++;
                $this->_mazeWithoutChar[$this->_pacmanY][$this->_pacmanX] = ' ';
            }
            // 描画
            $this->_mazeWithChar[$this->_pacmanY- $dy][$this->_pacmanX - $dx] = ' ';
            $this->_mazeWithChar[$this->_pacmanY][$this->_pacmanX] = '@';
            if ($takeSnapShot === true) {
                //  パックマンが曲がるのでスナップショット
                $joy = $lastGame->getPacman()->getJoystick();
                array_push(Pacman_Quiz::$games, $lastGame);
            }
            // 後処理
            $isClear = ($this->_score == $this->_clearScore);
            //            $restDot = $this->_clearScore - $this->_score;
            //            $isTimeOut = ($restDot > $this->_timeOut - $this->_time || $this->_time >= Pacman_Quiz::$minClearTime + $restDot);
            $isHit = $this->_hitCheck($this->_pacmanX, $this->_pacmanY);
            if ($this->_debug) {
                $this->_showCompositScreen($this->_mazeWithoutChar);
                usleep($this->_debugTime);
                if ($this->_debugAnimation) {
                    echo "\033[;H\033[2J"; // clear screen
                }
            }
            $joy = $this->_pacman->getJoystick();
            $lastGame = clone $this;
        }
        if ($isTimeOut) {
            //            $this->_checkRepeatGame();
            $this->_gameOver('TimeOut', $this->_mazeWithChar);
            return true;
        }
        if ($isHit) {
            throw new Exception('hit');
            return;
        }
        if ($isClear) {
            if ($this->_time >= Pacman_Quiz::$minClearTime) {
                return false;
            }
            Pacman_Quiz::$minClearTime = $this->_time;
            $this->_gameOver('Clear', $this->_mazeWithChar, true);
            return;
        }
        return;
    }
    /**
     * ゲームを繰り返していないかdebugチェック
     *
     * @return void
     */
    private function _checkRepeatGame()
    {
        static $joystat = array();
        $joy = $this->_pacman->getJoystick();
        $key = md5($joy);
        if (isset($joystat[$key])) {
            $joystat[$key]++;
            echo "repeated. $joy\n";
        } else {
            $joystat[$key] = 1;
        }
    }
    /**
     * モンスター移動
     *
     * @return void
     */
    private function _runMonsters()
    {
        $this->_mazeWithChar = $this->_mazeWithoutChar;
        foreach ($this->_monsters as $monster) {
            list($monsterX, $monsterY, $myChar, $wall) = $monster->move($this->_mazeWithoutChar, $this->_pacmanX, $this->_pacmanY);
            $this->_mazeWithChar[$monsterY][$monsterX] = $myChar;
            if (is_array($wall)) {
                $this->_mazeWithChar[$wall['y']][$wall['x']] = '#';
            }
        }
    }
    /**
     * ハイスコアセット
     *
     * @return void
     */
    public function setHighScore()
    {
        if ($this->_score > Pacman_Quiz::$highscore) {
            Pacman_Quiz::$highscore = $this->_score;
        }
    }
    /**
     * Game Over画面出力
     *
     * @param string $reason       ゲームオーバーの理由
     * @param string $mazeWithChar キャラクター付迷路
     *
     * @return void
     */
    public function _gameOver($reason, $mazeWithChar, $forceShow = false) {
        if ($forceShow || $this->_score > Pacman_Quiz::$highscore) {
            Pacman_Quiz::$highscore = $this->_score;
            echo $this->_showCompositScreen($mazeWithChar);
            $msg = ($reason === 'clear') ? "Game Clear" : "GAME OVER($reason)" ;
            echo "High Score:" . Pacman_Quiz::$highscore . ' total:'. Pacman_Quiz::$gameCount . " $msg\n\n";
        }
        return;
    }
    /**
     * ヒットチェック
     *
     * @param $pacmanX パックマンX座標
     * @param $pacmanY パックマンY座標
     *
     * @return bool
     */
    public function _hitCheck($pacmanX, $pacmanY)
    {
        $isHit = false;
        foreach ($this->_monsters as $monster) {
            list($monsterX, $monsterY) = $monster->getPosition();
            if ($pacmanX === $monsterX &#038;&#038; $pacmanY == $monsterY) {
                $isHit = true;
            }
        }
        return $isHit;
    }
    /**
     * デバックモード
     *
     * @param int $time アニメーションタイム
     *
     * @return void
     */
    public function setDebug($time = 0) {
        $this->_debugTime =  $time * 1000;
        $this->_debugAnimation = (is_integer($time) &#038;&#038; $time > 0) ? true : false;
        $this->_debug = true;
    }
    /**
     * 迷路配列作成
     *
     * @return array
     */
    private function _split($str)
    {
        $result = array();
        for ($i = 0 ; $i < strlen($str); $i++){
            $result[] = substr($str, $i, 1);
        }
        return $result;
    }
    /**
     * ゲーム画面描画
     *
     * @reutnr void
     */
    private function _showCompositScreen(array $maze, $debug = false)
    {
        $characters = $this->_monsters;
        array_push($characters, $this->_pacman);
        foreach ($characters as $character) {
            list($char, $x, $y, $dx, $dy) = $character->get();
            $maze[$y][$x] = $char;
        }
        echo "\n";
        foreach ($maze as $y) {
            echo implode('', $y) . "\n";
        }
        $point = ($this->_score === $this->_clearScore) ? ($this->_timeOut - $this->_time) + $this->_score : $this->_score;
        echo "Score:{$this->_score}/{$this->_clearScore} Point:{$point} Game:{$this->_time}/{$this->_timeOut} Stacked Game:" . count(Pacman_Quiz::$games) . " \n";
        echo "High Score: ". Pacman_Quiz::$highscore . ' total: '. Pacman_Quiz::$gameCount . "\n";
        echo "Play:" . $this->_pacman->getJoystick() . "\n";
    }
}
/**
 * パックマンクイズ
 *
 * @author akihito
 */
class Pacman_Quiz
{
    /**
     * パックマンの行動
     */
    public static $pacmanThought = array();
    /**
     * ゲーム
     */
    public static $games = array();
    /**
     * ハイスコア
     *
     * @var int
     */
    public static $highscore = 0;
    /**
     * クリア最小時間
     *
     * @var int
     */
    public static $minClearTime = 999;
    /**
     * ゲーム回数
     *
     * @var int
     */
    public static $gameCount = 0;
    /**
     * TimeOutの時にゲームをpopするか
     *
     * @var bool
     */
    private $_popOnTimeOut = false;
    /**
     * TimeOutの時にゲームをpopするかを設定
     *
     * @param bool $setPopOnTimeout
     */
    public function setPopOnTimeout($setPopOnTimeout)
    {
        $this->_setPopOnTimeout = $setPopOnTimeout;
    }
    /**
     * クイズ実行
     *
     * @return void
     */
    public function run($injector = '_injectQuestionThree', $debug = null)
    {
        $game = new Pacman_Game();
        if (isset($debug)) {
            $game->setDebug($debug);
        }
        $game->$injector();
        $game->init();
        $firstGame = clone $game;
        array_push(Pacman_Quiz::$games, $firstGame);
        do {
            if (!$game) {
                echo "All Game is Over.\n";
                break;
            }
            try {
                $result = $game->runGame();
                $game = array_pop(Pacman_Quiz::$games);
            } catch (Exception $e) {
                $game = array_pop(Pacman_Quiz::$games);
                $result = false;
            }
            $this->_showCounter();
            // Time Out
            if ($result === true &#038;&#038; !$this->_popOnTimeOut) {
                self::$pacmanThought = array();
                self::$games = array(Pacman_Quiz::$games[0]);
                $game = array_pop(Pacman_Quiz::$games);
            }
        } while(true);
    }
    /**
     * クイズ実行 (問題1用)
     *
     * @return void
     */
    public function run1($injector = '_injectQuestionOne', $debug = null)
    {
        $game = new Pacman_Game();
        if (isset($debug)) {
            $game->setDebug($debug);
        }
        $game->$injector();
        $game->init();
        $firstGame = clone $game;
        array_push(self::$games, $firstGame);
        do {
            try {
                $result = $game->runGame();
            } catch (Exception $e) {
            }
            $game->setHighScore();
            self::$games = array();
            self::$pacmanThought = array();
            $game = clone $firstGame;
        } while(true);
    }
    /**
     * カウンタ表示
     *
     * @return void
     */
    private function _showCounter()
    {
        static $i = 0;
        if (++$i % 1000 === 0) {
            echo ".$i";
        }
    }
}
// クイズ実行
$quiz = new Pacman_Quiz();
//$quiz->setPopOnTimeout(true); // true:TimeOutしてもスタックからゲームを取り出すモード
//$quiz->run1('_injectQuestionOne');
//$quiz->run('_injectQuestionTwo');
// 問題3
//$quiz->run('_injectQuestionThree', true); //逐次画面描画
$quiz->run('_injectQuestionThree', 100);    //アニメーション
//$quiz->run('_injectQuestionThree');       //ハイスコアチャレンジ
  1. この動画はAIによる移動です。再現プレイではありません。 []
  2. 結局その見通しは大甘でした []
  3. AKABE? []
  4. モンスタークラスにそれぞれの性格のモンスターがメソッドとして実装されていて迷路とPacmanの座標を受け取ったメソッドが進行方向を配列で返します。 []
  5. 95%以上得点が圧縮調整されてました。参加者の得点が高かったのでしょう []
  6. それぐらい知っとけという感じですが []
  7. 正に深さ優先探索! []
  8. ゲームオブジェクトはプロパティとしてモンスターやパックマンのオブジェクトなどゲーム要素全てもっています。 []
  9. メモリと時間が許せば []
  10. その方がスコアが良く、ランダムで繰り返しても同じゲームが再現することがほとんどありませんででした []
  11. ゲームオーバー時に積まれたゲームスタックを再評価し、10,000回に一回しか出ないような良いスコアの途中のゲーム状態から再開してみる..など色々やってみましたがあまりスコアアップに繋がりませんでした。オライリー本にもありますが"大器晩成型"のスコアがとであがってくるタイプのを消してしまうからではないかと思いました。 []
  12. これも膨大なメモリを要します。他にもいろいろな探索がオライリー本に紹介されてますがどれが一番向いてたのでしょうか []
  13. 残りドットが少なくなったら取りにいくロジックを追加したらかなり性能があがるかもしれません []
  14. アセンブラは16bitのスーパーファミコン(65816)、メガドライブ (680000+Z80)までやりました []
  15. 懐かしい響き! []
  16. 自機が”@”でした!当時いろんなゲームの自機が@。PC-6001用ASCIIのAXシリーズとか... []
  17. 動作確認にも大変世話になりました []
  18. AI検索のみの移動です。人の手による修正はありません []