GDD2010 DevQuiz パックマンの解法 Ver.ひらくん
0 Comments
ひらくん
さてDevQuizの締め切りが過ぎたのでおおっぴらに自分のはちゃめちゃなソースをさらしたいと思います。
とりあえずチャレンジ最中は試行錯誤の繰り返しでしたのでそこら中に無駄なソースやコメントアウトがあふれていますが、あえてそのままにしています。
本来であれば敵の種類毎にクラスを定義し、継承したりと理解しやすい手法で作れると思うのですが時間とメモリ節約の為、強引に処理しています。サブルーチンにまとめられそうな部分も面倒だったのでコピペでごまかしてたりします（苦笑
とまあ言い訳はここらへんで、実際にどのように考えていったか頭の中をさらしていくことにしましょう。
まずは問題の条件から私が着目したのは以下の２点。
１ 自分は「上・下・左・右・待機」という５つの行動ができる
２ 制限時間がある
この条件のみを考えると正解となる文字列は「５^制限時間」の中に存在することになります。要はこの中から「壁にぶつかったり」「敵にぶつかったり」する行動パターンを削除していけば、おのずと解が得られるわけです。ただし「５^制限時間」ってのはLV1だけでもとんでもない数字になってしまいます。私の手元にあるMSIの風子たんはあまり頭がよろしくないのでそんな計算は土台無理なわけです。そこで時刻毎のマップの状態を事前に計算しておき、現在の自機（以下パックマン）の座標から次の時刻（t+1）へ向けて移動可能な場所を順次割り出すという方法をとってみることにしました。なんとなくLV3を題材に解説するのは大変そうなのでLV1を題材に解説していきたいと思います。
※ソースがすごく長いので以下のソースを他のテキストエディタなどにコピペしてソース以下の解説を読むほうがわかりやすいかもしれません。。。（￣▽￣；
※ソースのダウンロードはこちら
【マップの読込】
ソースの9～77行までがマップの読み込み部分です。
マップデータをメモリ内に読込んで一行ごとに処理しています。36行でマップデータの一行を一文字ずつに分解し多次元配列に読みこんでいます。
37行目から分割したデータを一文字ずつチェックして文字の種類に応じた処理を行っています。40～44行がパックマンの初期設定。46行がクッキーのカウント。48～71が敵の初期設定です。敵は共通の初期設定を設定したのちに種類毎に配列に格納します。
これにてマップデータの読込は完了です。ここで後々失敗に気がつくのですがマップの座標を[y][x]で設定してしまいました。自分の頭の中では座標はいつも[x][y]で考えているのでちょっとソースが解りにくくなってしまった。。。まあ何はともあれこれで $Map[y][x] と指定すればいつでもマップの内容を参照することが出来るようになったわけです。
【敵キャラクターの動きを計算する】
敵の仕様を見ると L/R/J はパックマンの動きをいっさい考えずに動きます。つまりこの三種類の敵はパックマンがどのようなルートを辿っても必ず同じ動きをすることになります。常に同じ動きをするのであれば三種類の敵の動きは事前に全て計算しておくことができます。そこで@NGBlockという配列を準備して、時間＝tにおける L/R/J の位置をハッシュテーブルにして入れることにしました。
ここで注意すべきはｔにおける敵の状態を個々の個体できちんと管理しなければならない事です。最初私はｔにおける各敵の座標だけをまとめて一つの$NGBlock[t]の中にいれていたのですがそれではゲームオーバーの条件の一つである「時刻 t-1 における自機と敵 x の位置と、時刻 t における自機と敵 x の位置が交換されている。」という判定ができないことに気がつきました。ささっとシミュレータなどを組んだ人で自機が敵をすりぬけてしまう人はこの判定がうまくいってないのが原因だと思います。そこでｔにおける敵ｘの位置を、
$NGBlock[t][x]
の中に入れることにしました。これでそれぞれの敵の遷移を追う事ができるようになりました。この部分のソースは87～147行までの部分です。L/R/Jのtにおける座標を順番に計算しています。
この三種はほとんど動作が同じで違うのは交差点に入った時の動きだけです。交差点マスに入ったさいに優先する方向がちがうだけなのでサブルーチンに方向の優先順を渡す事でロジックを使いまわしています。Jに関しては交差点にはいるたびに方向が変わるのでR/Jにない'think'というパラメータを持たせ、サブルーチン内で引数の値が自動で切り替わるよう処理を行っています。
さあこれで時刻ｔにおける敵の座標は
$NGBlock[t][x]
の中にハッシュのキーとして設定されました。時刻tに移動したパックマンの座標が仮にX,Yだとすると、
$NGBlock[t][x]{X/Y} = 'True';
が成立すればその座標には敵がいるのでアウトになります。
敵キャラクタ H/V に関してはパックマンの位置によって行動が変化するのでパックマンの動きを計算する処理で同時に計算していいくことにします。
【パックマンの動きを計算する】
さて、いよいよパックマンの動きを計算していきます。基本的な考えはこうです。
１）時刻tのパックマンの座標から時刻t+1で生存可能な座標を計算する
２）パックマンの座標を再設定
３）t+1して１）の処理に戻る
上記の処理を制限時間分繰り返せばとりあえず制限時間内で生存可能なルートを取得することができます。当初は時刻tでパックマンが生存可能な座標を
$Pacmans[t]
の中に配列で入れようとしていました。
例：LV1スタート時点のパックマンの動き
$Pacmans[0] = (初期配置のパックマン);
・上は壁なので移動できない
・下も壁なので移動できない
・左には移動できる
・右には移動できる
・立ち止まっても大丈夫
$Pacmans[1] = (左に移動したパックマン,右に移動したパックマン,立ち止まったパックマン);
とまあこんな感じでどんどん値を蓄積しそれぞれのパックマンには自分が$Pacmans[t-1]の配列の中にあるどのパックマンから派生したものなのかを覚えさせておけば@Pacmansの中にパックマンの系図が作成されます。
$Pacmans[0] $Pacmans[1] $Pacmans[2]
初期配置のパックマン━┳━右に移動したパックマン━┳━左に移動したパックマン
┃
┣━左に移動したパックマン
┃
┗━立ち止まったパックマン
最終的に生き残ったパックマンから系図をさかのぼればルートが取得できます。
ただしこの方法では案の定膨大なメモリが必要になり風子たんはout of memoryです。最終的にはこの「配列の中に系図を作成する」という方法は断念し、派生したパックマンそれぞれに自分の過去の履歴を覚えさせていくことにしました（175行）。そうすれば$Pacmans[t-1]の中身はクリアしても問題なくなるので不要になった段階でメモリを解放（undef）できます。これでかなりのメモリが節約できるようになりました。
「さあ、メモリも節約できた一気に計算だ！」
と行きたいところですがまだ問題があります。時系列でパックマンを派生させる処理ですが移動する条件が絞られるとはいえこれでも膨大な数のパターンを検索していかなければならず現実的には無理があります。そうなると如何に効率よくルートを絞り込むかが重要になってくるわけです。ここで今回採用した絞り込みは、
・次世代派生処理を行う際にクッキーを多く取得しているパックマンを優先する
・次世代のパックマンを生み出せるのは各世代$MAXの数のパックマンだけ
上記二つの処理を導入することにしました。クッキーを多く取得しているパックマンを優先しているのは169行のsort処理。$MAXでの絞り込みは変数$Addをインクリメントしていき$Addが$MAXと等しくなった時にlastでループを抜けるようになっています。
この$MAXの数をマシンパワーと相談しつつ設定することにします。ただし後述しますがこの$MAXの値が大きければいいかと言うと今回のソースに限ってはそうではありませんでした。
さてメモリと計算回数の節約を行ったパックマン経路探索のメインループが166～188行までの部分です。
165行：時刻=0の始祖パックマンを設定します
166行：制限時間ループ開始
169行：時刻＝$countにおけるパックマンを整列して派生処理ループ開始
170行：$MAX制限判定用に$Addをインクリメント
172行：パックマン派生処理
173行：派生パックマンのループ開始
174行：$Pacmans[$count+1]に派生パックマンを格納
175行：ルートの記憶
176行：派生パックマンがマップ内のクッキーを全部食べていたら終了
さて基本的なルーチンは全てお話してしまいましたが H/V の実装のお話をしていなかったのでそちらを少々。
H/V はパックマンの座標位置に応じて動作がかわる場合があります。パックマンがどう動くかによってとうぜんH/Vの動きも変わってくるのである意味パックマンに依存した存在です。そこでパックマンに時刻tにおけるH/Vの座標をもたせておき（156,157行）パックマンの移動経路を決定する220行目に定義したパックマン派生処理「getSafety」の中でH/Vの動きも計算することにします。
getSafetyはパックマンを引数にとるサブルーチンです。戻り値はt+1の時に安全に生存できるパックマンの配列です。それではgetSafetyの中身を見ていきましょう
232～236行、まずは渡されたパックマンの座標から上下左右の座標を計算します。ルーチン内では東西南北の頭文字をとって$N $E $W $Sとしています$Fは動かない＝フリーズです。
239～243行：移動先が壁かどうかの判定
245～262行：事前に計算済の敵との衝突判定
264～287行：敵Vとの衝突を判定します
264～287行：敵Hとの衝突を判定します
敵Vと敵Hとの判定処理は殆ど一緒です。ですので敵Vの方の処理だけ解説したいと思います。
時刻tにおけるパックマンは時刻tにおける敵Vの座標を保持しています。
$Pacman->{'myVacuum'}
この中の値とパックマンを元にVmoveというサブルーチンを呼び出します。これはVの行動ロジックを実装したサブルーチンで必要に応じてパックマンの座標を参照しつつt+1における敵Vの位置を返します。ここで戻された値で衝突判定をするとともにgetSafetyで派生したパックマンにこの値を保持してもらいます。そうすればこの派生パックマンが自分の派生パックマンを生み出すgetSafetyを実行する際に利用されることとなります。この処理をHも同様に処理します。
以上のように「派生パックマンを繰り返し生み出し一番早くクッキーを食べ終わるパックマンを探し出す」というのが今回私が考えたロジックです。
【問題点】
$MAXの部分で少し述べましたが今回の処理で検索範囲を広げるために$MAXを大きくすると実は解が導き出せないことがあります。というのもパックマンの絞り込みで、
「クッキーを一番多く食べているパックマンを優先」
としてあるので単純に先行逃げ切りパックマンが生き残り易くなります。この状態で派生パックマンを処理する分母を増やすとこの先行逃げ切りパックマンが爆発的に増加し大器晩成型パックマンを駆逐してしまうのです。今回たまたま私のマシンのスペックが低かったことが功を奏して、
「$MAX大きいと全然計算が進まねーよ」
とケチくさく値を少しずつ増やして処理するということを行ったので解を導き出すことができました。
絞り込みを一切行わずに超ハイスペックマシンで処理すれば必ず最適解が見つかると思いますがそんな処理はネットブックしか持ってない私にとっては現実的ではありません。潰せるパターンはなるべく潰して、なるべく効率的な絞り込みをする必要があります。例えば同じ量のクッキーを食べているパックマンがいた時はなるべく異なるパターンの派生パックマンを残してパターンのバリエーションを広げてみるとか、試していないですがいろいろ考えられます。また、派生パックマンを生み出すさいにも「待機」と「後退」という選択肢の優先度を調整することでスコアが高い経路がでてきたり低いスコアの経路がでてきたりといろいろです。マップの内容に応じた処理を行ってみるのもなかなか楽しいです。例えばLV1のような狭苦しいマップではやっぱり相手が通り過ぎるのを待つために待機が結構必要だったり、逆にLV2のようにそこそこ広く行き止まりもないマップであれば待機も後退も優先度が下がるといった具合です。LV3では行き止まりの部分があるので「後退は効率悪いから処理しない」なんていうロジックだと絶対クリアできません。
以上、こんな汚いソースはお恥ずかしい限りですが折角参加したDevQuizですし多少なりとも参考になればと公開させていただきました。長々となってしまいましたがお付き合いくださりありがとうございます。
とりあえずチャレンジ最中は試行錯誤の繰り返しでしたのでそこら中に無駄なソースやコメントアウトがあふれていますが、あえてそのままにしています。
本来であれば敵の種類毎にクラスを定義し、継承したりと理解しやすい手法で作れると思うのですが時間とメモリ節約の為、強引に処理しています。サブルーチンにまとめられそうな部分も面倒だったのでコピペでごまかしてたりします（苦笑
とまあ言い訳はここらへんで、実際にどのように考えていったか頭の中をさらしていくことにしましょう。
まずは問題の条件から私が着目したのは以下の２点。
１ 自分は「上・下・左・右・待機」という５つの行動ができる
２ 制限時間がある
この条件のみを考えると正解となる文字列は「５^制限時間」の中に存在することになります。要はこの中から「壁にぶつかったり」「敵にぶつかったり」する行動パターンを削除していけば、おのずと解が得られるわけです。ただし「５^制限時間」ってのはLV1だけでもとんでもない数字になってしまいます。私の手元にあるMSIの風子たんはあまり頭がよろしくないのでそんな計算は土台無理なわけです。そこで時刻毎のマップの状態を事前に計算しておき、現在の自機（以下パックマン）の座標から次の時刻（t+1）へ向けて移動可能な場所を順次割り出すという方法をとってみることにしました。なんとなくLV3を題材に解説するのは大変そうなのでLV1を題材に解説していきたいと思います。
※ソースがすごく長いので以下のソースを他のテキストエディタなどにコピペしてソース以下の解説を読むほうがわかりやすいかもしれません。。。（￣▽￣；
※ソースのダウンロードはこちら
#!/usr/bin/perl
use utf8; #-ソースがUTF8だという宣言
use Encode;
use strict;
binmode STDOUT, ":utf8"; #-画面に出力したい文字コード
binmode STDERR, ":utf8"; #-エラー出力に使いたい文字コード
binmode STDIN, ":utf8"; #-標準入力から入ってくる文字コード
#--入力データを分解
my @buffer = ();
@buffer = <DATA>;
map {chomp $_} @buffer;
#--各種パラメータを設定
my $Time = shift(@buffer);
my ($Width,$Height) = split(/ /,shift(@buffer));
$Width--;
$Height--;
#-変数定義（一応書いておこう）
my $Pacman = {};
my @Vacuum = ();
my @Hades = ();
my @Lackey = ();
my @Rabid = ();
my @Jail = ();
my $CookieCount = 0;
my @NgBlock = ();
#--マップとキャラクターの作成
my @Map = ();
my $i = 0;
my $tmpChara;
for (@buffer) {
@{$Map[$i]} = split('',$_);
for (0..$Width) {
$tmpChara = $Map[$i][$_];
if ($tmpChara eq '@') {
$Pacman->{'StartX'} = $_;
$Pacman->{'StartY'} = $i;
$Pacman->{'X'} = $Pacman->{'StartX'};
$Pacman->{'Y'} = $Pacman->{'StartY'};
$Map[$i][$_] = ' ';
} elsif ($tmpChara eq '.') {
$CookieCount++;
} elsif ($tmpChara =~ /[VHLRJ]/) {
my $enemy = {};
$enemy->{'StartX'} = $_;
$enemy->{'StartY'} = $i;
$enemy->{'X'} = $enemy->{'StartX'};
$enemy->{'Y'} = $enemy->{'StartY'};
$enemy->{'direction'} = ".";
if ($tmpChara eq 'V') {
#-Vacuum
push(@Vacuum,$enemy);
} elsif ($tmpChara eq 'H') {
#-Hades
push(@Hades,$enemy);
} elsif ($tmpChara eq 'L') {
#-Lackey
push(@Lackey,$enemy);
} elsif ($tmpChara eq 'R') {
#-Rabid
push(@Rabid,$enemy);
} elsif ($tmpChara eq 'J') {
#-Jail
push(@Jail,$enemy);
}
$Map[$i][$_] = ' ';
}
print $tmpChara;
}
print "\n";
$i++;
}
print "\n";
print 'Target Cookies : ' . $CookieCount . "\n";
print 'Start Position : X='.$Pacman->{'StartX'} . "\n";
print 'Start Position : Y='.$Pacman->{'StartY'} . "\n";
#-事前に計算できる敵の動きは全て計算しておく
my $enemy;
my $e_count=0;
#-Lackeyの処理
for $enemy (@Lackey) {
#-t=0におけるNgBlockに値を追加する（まあなんとなくね）
$NgBlock[0][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
#-t=1の位置を取得
&fastMove($enemy);
#-t=1におけるNgBlockに値を追加する
$NgBlock[1][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
my $count;
for $count (2..$Time-1) {
&Move($enemy,'LEFT/FORWARD/RIGHT');
$NgBlock[$count][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
}
$e_count++;
}
#-Rabidの処理
for $enemy (@Rabid) {
#-t=0におけるNgBlockに値を追加する（まあなんとなくね）
$NgBlock[0][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
#-t=1の位置を取得
&fastMove($enemy);
#-t=1におけるNgBlockに値を追加する
$NgBlock[1][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
my $count;
for $count (2..$Time-1) {
&Move($enemy,'RIGHT/FORWARD/LEFT');
$NgBlock[$count][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
}
$e_count++;
}
#-Jailの処理
for $enemy (@Jail) {
#-t=0におけるNgBlockに値を追加する（まあなんとなくね）
$NgBlock[0][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
#-t=1の位置を取得
&fastMove($enemy);
#-t=1におけるNgBlockに値を追加する
$NgBlock[1][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
#-Jailは二つのロジックを持つので最初のロジックを設定
$enemy->{'think'} = 'LEFT/FORWARD/RIGHT';
my $count;
for $count (2..$Time-1) {
&Move($enemy,$enemy->{'think'});
$NgBlock[$count][$e_count]{$enemy->{'X'}.'/'.$enemy->{'Y'}} = 'True';
}
$e_count++;
}
#-パックマンの動きを計算してみる
$Pacman->{'descent'} = 1;
$Pacman->{'parent'} = "none";
$Pacman->{'GetCookie'} = 0;
%{$Pacman->{'DoneCookie'}} = {};
$Pacman->{'Move'} = 'start';
@{$Pacman->{'myVacuum'}} = @Vacuum;
@{$Pacman->{'myHades'}} = @Hades;
my $count;
my @Pacmans = ();
my @tmpPacmans;
my $tmpPacman;
my $Add;
my $MAX = 400;
@{$Pacmans[0]} = ($Pacman);
for $count (0..$Time-1) {
print $count . "\n";
$Add = 0;
for $Pacman (sort mySort @{$Pacmans[$count]}) {
$Add++;
undef @tmpPacmans;
@tmpPacmans = &getSafety($Pacman,$Time);
for $tmpPacman (sort mySort @tmpPacmans) {
push(@{$Pacmans[$count+1]},$tmpPacman);
$tmpPacman->{'history'} = $Pacman->{'history'} . $tmpPacman->{'Move'};
if ($tmpPacman->{'GetCookie'} == $CookieCount) {
#print &getHistory($tmpPacman);
print $tmpPacman->{'history'} . "\n";
undef (@Pacmans);
exit;
}
}
if ($Add > $MAX) {
undef @{$Pacmans[$count]};
last;
}
}
}
for $Pacman (sort mySort @{$Pacmans[$Time]}) {
print "$_ GetCookie:" . $Pacman->{'GetCookie'} . " : " . $Pacman->{'history'} . "\n";
last;
}
undef (@Pacmans);
sub mySort() {
$b->{'GetCookie'} <=> $a->{'GetCookie'};
}
exit;
#---各種サブルーチン
sub getHistory() {
my $Pacman = @_[0];
my @Pacmans;
my $History;
push(@Pacmans,$Pacman);
for (@Pacmans) {
if ($_->{'parent'}{'Move'} ne 'start') {
push(@Pacmans,$_->{'parent'});
}
$History = $_->{'Move'} . $History;
}
return $History;
}
#-安全なブロックを取得する
sub getSafety() {
my $Pacman = @_[0];
my $MaxTime = @_[1];
my $count = $Pacman->{'descent'};
my $countBack = $count - 1;
my @Safe = ();
my $X = $Pacman->{'X'};
my $Y = $Pacman->{'Y'};
my @Vacuum = ();
my @Hades = ();
my $N = {'X' => $X,'Y' => $Y-1,'Safe' => 'true','Move' => 'k'};
my $E = {'X' => $X+1,'Y' => $Y,'Safe' => 'true','Move' => 'l'};
my $W = {'X' => $X-1,'Y' => $Y,'Safe' => 'true','Move' => 'h'};
my $S = {'X' => $X,'Y' => $Y+1,'Safe' => 'true','Move' => 'j'};
my $F = {'X' => $X,'Y' => $Y,'Safe' => 'true','Move' => '.'};
#-壁の判定
$N->{'Safe'} = 'false' if ($Map[$N->{'Y'}][$N->{'X'}] eq '#');
$E->{'Safe'} = 'false' if ($Map[$E->{'Y'}][$E->{'X'}] eq '#');
$W->{'Safe'} = 'false' if ($Map[$W->{'Y'}][$W->{'X'}] eq '#');
$S->{'Safe'} = 'false' if ($Map[$S->{'Y'}][$S->{'X'}] eq '#');
#-敵につかまるかの判定
my %enemyPositionBack;
my $e_count = 0;
for (@{$NgBlock[$count]}) {
if ($_->{$F->{'X'}.'/'.$F->{'Y'}} eq 'True') {
$F->{'Safe'} = 'false';
%enemyPositionBack = %{$NgBlock[$countBack][$e_count]};
$N->{'Safe'} = 'false' if ($enemyPositionBack{$N->{'X'}.'/'.$N->{'Y'}} eq 'True');
$E->{'Safe'} = 'false' if ($enemyPositionBack{$E->{'X'}.'/'.$E->{'Y'}} eq 'True');
$W->{'Safe'} = 'false' if ($enemyPositionBack{$W->{'X'}.'/'.$W->{'Y'}} eq 'True');
$S->{'Safe'} = 'false' if ($enemyPositionBack{$S->{'X'}.'/'.$S->{'Y'}} eq 'True');
}
$N->{'Safe'} = 'false' if ($_->{$N->{'X'}.'/'.$N->{'Y'}} eq 'True');
$E->{'Safe'} = 'false' if ($_->{$E->{'X'}.'/'.$E->{'Y'}} eq 'True');
$W->{'Safe'} = 'false' if ($_->{$W->{'X'}.'/'.$W->{'Y'}} eq 'True');
$S->{'Safe'} = 'false' if ($_->{$S->{'X'}.'/'.$S->{'Y'}} eq 'True');
$e_count++;
}
for (@{$Pacman->{'myVacuum'}}) {
my $tmpEnemy;
$tmpEnemy->{'X'} = $_->{'X'};
$tmpEnemy->{'Y'} = $_->{'Y'};
$tmpEnemy->{'direction'} = $_->{'direction'};
&VMove($tmpEnemy,$Pacman);
push(@Vacuum,$tmpEnemy);
}
my $tmpVacuum;
for (@Vacuum) {
if ($_->{'X'} eq $F->{'X'} and $_->{'Y'} eq $F->{'Y'}) {
$F->{'Safe'} = 'false';
for $tmpVacuum (@{$Pacman->{'myVacuum'}}) {
$N->{'Safe'} = 'false' if ($tmpVacuum->{'X'} eq $N->{'X'} and $tmpVacuum->{'Y'} eq $N->{'Y'});
$E->{'Safe'} = 'false' if ($tmpVacuum->{'X'} eq $E->{'X'} and $tmpVacuum->{'Y'} eq $E->{'Y'});
$W->{'Safe'} = 'false' if ($tmpVacuum->{'X'} eq $W->{'X'} and $tmpVacuum->{'Y'} eq $W->{'Y'});
$S->{'Safe'} = 'false' if ($tmpVacuum->{'X'} eq $S->{'X'} and $tmpVacuum->{'Y'} eq $S->{'Y'});
}
}
$N->{'Safe'} = 'false' if ($_->{'X'} eq $N->{'X'} and $_->{'Y'} eq $N->{'Y'});
$E->{'Safe'} = 'false' if ($_->{'X'} eq $E->{'X'} and $_->{'Y'} eq $E->{'Y'});
$W->{'Safe'} = 'false' if ($_->{'X'} eq $W->{'X'} and $_->{'Y'} eq $W->{'Y'});
$S->{'Safe'} = 'false' if ($_->{'X'} eq $S->{'X'} and $_->{'Y'} eq $S->{'Y'});
}
for (@{$Pacman->{'myHades'}}) {
my $tmpEnemy;
$tmpEnemy->{'X'} = $_->{'X'};
$tmpEnemy->{'Y'} = $_->{'Y'};
$tmpEnemy->{'direction'} = $_->{'direction'};
&HMove($tmpEnemy,$Pacman);
push(@Hades,$tmpEnemy);
}
my $tmpHades;
for (@Hades) {
$N->{'Safe'} = 'false' if ($_->{'X'} eq $N->{'X'} and $_->{'Y'} eq $N->{'Y'});
$E->{'Safe'} = 'false' if ($_->{'X'} eq $E->{'X'} and $_->{'Y'} eq $E->{'Y'});
$W->{'Safe'} = 'false' if ($_->{'X'} eq $W->{'X'} and $_->{'Y'} eq $W->{'Y'});
$S->{'Safe'} = 'false' if ($_->{'X'} eq $S->{'X'} and $_->{'Y'} eq $S->{'Y'});
$F->{'Safe'} = 'false' if ($_->{'X'} eq $F->{'X'} and $_->{'Y'} eq $F->{'Y'});
if ($F->{'Safe'} eq 'false') {
for $tmpHades (@{$Pacman->{'myHades'}}) {
$N->{'Safe'} = 'false' if ($tmpHades->{'X'} eq $N->{'X'} and $tmpHades->{'Y'} eq $N->{'Y'});
$E->{'Safe'} = 'false' if ($tmpHades->{'X'} eq $E->{'X'} and $tmpHades->{'Y'} eq $E->{'Y'});
$W->{'Safe'} = 'false' if ($tmpHades->{'X'} eq $W->{'X'} and $tmpHades->{'Y'} eq $W->{'Y'});
$S->{'Safe'} = 'false' if ($tmpHades->{'X'} eq $S->{'X'} and $tmpHades->{'Y'} eq $S->{'Y'});
}
}
}
#N=k,E=l,W=h,S=j
my $FORWARD;
my $LEFT;
my $RIGHT;
my $BACK;
if ($Pacman->{'Move'} eq 'k') {
$FORWARD = $N;
$LEFT = $W;
$RIGHT = $E;
$BACK = $S;
} elsif ($Pacman->{'Move'} eq 'l') {
$FORWARD = $E;
$LEFT = $N;
$RIGHT = $S;
$BACK = $W;
} elsif ($Pacman->{'Move'} eq 'h') {
$FORWARD = $W;
$LEFT = $S;
$RIGHT = $N;
$BACK = $E;
} elsif ($Pacman->{'Move'} eq 'j') {
$FORWARD = $S;
$LEFT = $E;
$RIGHT = $W;
$BACK = $N;
} else {
$FORWARD = $S;
$LEFT = $E;
$RIGHT = $W;
$BACK = $N;
}
if ($FORWARD->{'Safe'} eq 'true') {
push (@Safe,&makePacman($Pacman,$FORWARD));
}
if ($RIGHT->{'Safe'} eq 'true') {
push (@Safe,&makePacman($Pacman,$RIGHT));
}
if ($LEFT->{'Safe'} eq 'true') {
push (@Safe,&makePacman($Pacman,$LEFT));
}
if ($F->{'Safe'} eq 'true') {
push (@Safe,&makePacman($Pacman,$F));
}
if ($BACK->{'Safe'} eq 'true') {
push (@Safe,&makePacman($Pacman,$BACK));
}
my $tmpPacman;
for $tmpPacman (@Safe) {
for (@Vacuum) {
my $tmpEnemy;
$tmpEnemy->{'X'} = $_->{'X'};
$tmpEnemy->{'Y'} = $_->{'Y'};
$tmpEnemy->{'direction'} = $_->{'direction'};
push(@{$tmpPacman->{'myVacuum'}},$tmpEnemy);
}
for (@Hades) {
my $tmpEnemy;
$tmpEnemy->{'X'} = $_->{'X'};
$tmpEnemy->{'Y'} = $_->{'Y'};
$tmpEnemy->{'direction'} = $_->{'direction'};
push(@{$tmpPacman->{'myHades'}},$tmpEnemy);
}
}
undef @{$Pacman->{'myVacuum'}};
undef @{$Pacman->{'myHades'}};
undef %{$Pacman->{'DoneCookie'}};
return @Safe;
}
#-次世代パックマンの生成
sub makePacman() {
my $Parent = @_[0];
my $info = @_[1];
my $Pacman;
my @Swap;
$Pacman->{'X'} = $info->{'X'};
$Pacman->{'Y'} = $info->{'Y'};
$Pacman->{'Move'} = $info->{'Move'};
$Pacman->{'descent'} = $Parent->{'descent'} + 1;
$Pacman->{'GetCookie'} = $Parent->{'GetCookie'};
%{$Pacman->{'DoneCookie'}} = %{$Parent->{'DoneCookie'}};
# $Pacman->{'parent'} = $Parent;
if ($Map[$Pacman->{'Y'}][$Pacman->{'X'}] eq '.') {
if ($Pacman->{'DoneCookie'}{$Pacman->{'X'}.'/'.$Pacman->{'Y'}} ne 'True') {
$Pacman->{'GetCookie'} = $Pacman->{'GetCookie'} + 1;
$Pacman->{'DoneCookie'}{$Pacman->{'X'}.'/'.$Pacman->{'Y'}} = 'True';
}
}
return $Pacman;
}
#-初期位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動します
sub fastMove() {
my $enemy = @_[0];
my $X = $enemy->{'X'};
my $Y = $enemy->{'Y'};
if ($Map[$Y+1][$X] ne '#') {
#-下
$enemy->{'Y'} = $Y+1;
$enemy->{'direction'} = 'S';
} elsif ($Map[$Y][$X-1] ne '#') {
#-左
$enemy->{'X'} = $X-1;
$enemy->{'direction'} = 'W';
} elsif ($Map[$Y-1][$X] ne '#') {
#-上
$enemy->{'Y'} = $Y-1;
$enemy->{'direction'} = 'N';
} elsif ($Map[$Y][$X+1] ne '#') {
#-右
$enemy->{'X'} = $X+1;
$enemy->{'direction'} = 'E';
}
}
sub Move() {
my $enemy = @_[0];
my $X = $enemy->{'X'};
my $Y = $enemy->{'Y'};
my @think = split('/',@_[1]);
my $Wall = '';
my $N = {'X' => $X,'Y' => $Y-1};
my $E = {'X' => $X+1,'Y' => $Y};
my $W = {'X' => $X-1,'Y' => $Y};
my $S = {'X' => $X,'Y' => $Y+1};
$N->{'FORWARD'} = $N;
$N->{'LEFT'} = $W;
$N->{'RIGHT'} = $E;
$N->{'BACK'} = $S;
$N->{'direction'} = 'N';
$E->{'FORWARD'} = $E;
$E->{'LEFT'} = $N;
$E->{'RIGHT'} = $S;
$E->{'BACK'} = $W;
$E->{'direction'} = 'E';
$W->{'FORWARD'} = $W;
$W->{'LEFT'} = $S;
$W->{'RIGHT'} = $N;
$W->{'BACK'} = $E;
$W->{'direction'} = 'W';
$S->{'FORWARD'} = $S;
$S->{'LEFT'} = $E;
$S->{'RIGHT'} = $W;
$S->{'BACK'} = $N;
$S->{'direction'} = 'S';
my $NowDirection = '';
#-状態を設定
if ($enemy->{'direction'} eq 'N') {
$NowDirection = $N;
} elsif ($enemy->{'direction'} eq 'E') {
$NowDirection = $E;
} elsif ($enemy->{'direction'} eq 'W') {
$NowDirection = $W;
} elsif ($enemy->{'direction'} eq 'S') {
$NowDirection = $S;
}
#-通路の種別を選択
$Wall = 'FORWARD_' if ($Map[$NowDirection->{'Y'}][$NowDirection->{'X'}] ne '#');
$Wall .= 'LEFT_' if ($Map[$NowDirection->{'LEFT'}{'Y'}][$NowDirection->{'LEFT'}{'X'}] ne '#');
$Wall .= 'RIGHT_' if ($Map[$NowDirection->{'RIGHT'}{'Y'}][$NowDirection->{'RIGHT'}{'X'}] ne '#');
if ($Wall =~ /^$/) {
#-行き止まりなのでバックします
$enemy->{'X'} = $NowDirection->{'BACK'}{'X'};
$enemy->{'Y'} = $NowDirection->{'BACK'}{'Y'};
$enemy->{'direction'} = $NowDirection->{'BACK'}{'direction'};
} elsif ($Wall =~ /^(FORWARD|LEFT|RIGHT)_$/) {
#-通路なので進みます
$Wall =~ s/_//;
$enemy->{'X'} = $NowDirection->{$Wall}{'X'};
$enemy->{'Y'} = $NowDirection->{$Wall}{'Y'};
$enemy->{'direction'} = $NowDirection->{$Wall}{'direction'};
} else {
#-交差点なので考えます
my $Direction;
for $Direction (@think) {
if ($Wall =~ /${Direction}_/) {
$enemy->{'X'} = $NowDirection->{$Direction}{'X'};
$enemy->{'Y'} = $NowDirection->{$Direction}{'Y'};
$enemy->{'direction'} = $NowDirection->{$Direction}{'direction'};
if ($enemy->{'think'} eq 'LEFT/FORWARD/RIGHT') {
$enemy->{'think'} = 'RIGHT/FORWARD/LEFT';
} elsif ($enemy->{'think'} eq 'RIGHT/FORWARD/LEFT') {
$enemy->{'think'} = 'LEFT/FORWARD/RIGHT';
}
last;
}
}
}
return;
}
sub VMove() {
my $enemy = @_[0];
my $Pacman = @_[1];
if ($Pacman->{'descent'} == 1) {
&fastMove($enemy);
return;
}
my $X = $enemy->{'X'};
my $Y = $enemy->{'Y'};
my $Wall = '';
my $N = {'X' => $X,'Y' => $Y-1};
my $E = {'X' => $X+1,'Y' => $Y};
my $W = {'X' => $X-1,'Y' => $Y};
my $S = {'X' => $X,'Y' => $Y+1};
$N->{'FORWARD'} = $N;
$N->{'LEFT'} = $W;
$N->{'RIGHT'} = $E;
$N->{'BACK'} = $S;
$N->{'direction'} = 'N';
$E->{'FORWARD'} = $E;
$E->{'LEFT'} = $N;
$E->{'RIGHT'} = $S;
$E->{'BACK'} = $W;
$E->{'direction'} = 'E';
$W->{'FORWARD'} = $W;
$W->{'LEFT'} = $S;
$W->{'RIGHT'} = $N;
$W->{'BACK'} = $E;
$W->{'direction'} = 'W';
$S->{'FORWARD'} = $S;
$S->{'LEFT'} = $E;
$S->{'RIGHT'} = $W;
$S->{'BACK'} = $N;
$S->{'direction'} = 'S';
my $NowDirection = '';
#-状態を設定
if ($enemy->{'direction'} eq 'N') {
$NowDirection = $N;
} elsif ($enemy->{'direction'} eq 'E') {
$NowDirection = $E;
} elsif ($enemy->{'direction'} eq 'W') {
$NowDirection = $W;
} elsif ($enemy->{'direction'} eq 'S') {
$NowDirection = $S;
}
#-通路の種別を選択
$Wall = 'FORWARD_' if ($Map[$NowDirection->{'Y'}][$NowDirection->{'X'}] ne '#');
$Wall .= 'LEFT_' if ($Map[$NowDirection->{'LEFT'}{'Y'}][$NowDirection->{'LEFT'}{'X'}] ne '#');
$Wall .= 'RIGHT_' if ($Map[$NowDirection->{'RIGHT'}{'Y'}][$NowDirection->{'RIGHT'}{'X'}] ne '#');
if ($Wall =~ /^$/) {
#-行き止まりなのでバックします
$enemy->{'X'} = $NowDirection->{'BACK'}{'X'};
$enemy->{'Y'} = $NowDirection->{'BACK'}{'Y'};
$enemy->{'direction'} = $NowDirection->{'BACK'}{'direction'};
} elsif ($Wall =~ /^(FORWARD|LEFT|RIGHT)_$/) {
#-通路なので進みます
$Wall =~ s/_//;
$enemy->{'X'} = $NowDirection->{$Wall}{'X'};
$enemy->{'Y'} = $NowDirection->{$Wall}{'Y'};
$enemy->{'direction'} = $NowDirection->{$Wall}{'direction'};
} else {
#-交差点なので考えます
my $dx = $Pacman->{'X'} - $enemy->{'X'};
my $dy = $Pacman->{'Y'} - $enemy->{'Y'};
if ($dy != 0) {
if ($dy > 0) {
if ($Map[$S->{'Y'}][$S->{'X'}] ne '#') {
$enemy->{'X'} = $S->{'X'};
$enemy->{'Y'} = $S->{'Y'};
$enemy->{'direction'} = $S->{'direction'};
return;
}
} else {
if ($Map[$N->{'Y'}][$N->{'X'}] ne '#') {
$enemy->{'X'} = $N->{'X'};
$enemy->{'Y'} = $N->{'Y'};
$enemy->{'direction'} = $N->{'direction'};
return;
}
}
}
if ($dx != 0) {
if ($dx > 0) {
if ($Map[$E->{'Y'}][$E->{'X'}] ne '#') {
$enemy->{'X'} = $E->{'X'};
$enemy->{'Y'} = $E->{'Y'};
$enemy->{'direction'} = $E->{'direction'};
return;
}
} else {
if ($Map[$W->{'Y'}][$W->{'X'}] ne '#') {
$enemy->{'X'} = $W->{'X'};
$enemy->{'Y'} = $W->{'Y'};
$enemy->{'direction'} = $W->{'direction'};
return;
}
}
}
&fastMove($enemy);
}
return;
}
sub HMove() {
my $enemy = @_[0];
my $Pacman = @_[1];
if ($Pacman->{'descent'} == 1) {
&fastMove($enemy);
return;
}
my $X = $enemy->{'X'};
my $Y = $enemy->{'Y'};
my $Wall = '';
my $N = {'X' => $X,'Y' => $Y-1};
my $E = {'X' => $X+1,'Y' => $Y};
my $W = {'X' => $X-1,'Y' => $Y};
my $S = {'X' => $X,'Y' => $Y+1};
$N->{'FORWARD'} = $N;
$N->{'LEFT'} = $W;
$N->{'RIGHT'} = $E;
$N->{'BACK'} = $S;
$N->{'direction'} = 'N';
$E->{'FORWARD'} = $E;
$E->{'LEFT'} = $N;
$E->{'RIGHT'} = $S;
$E->{'BACK'} = $W;
$E->{'direction'} = 'E';
$W->{'FORWARD'} = $W;
$W->{'LEFT'} = $S;
$W->{'RIGHT'} = $N;
$W->{'BACK'} = $E;
$W->{'direction'} = 'W';
$S->{'FORWARD'} = $S;
$S->{'LEFT'} = $E;
$S->{'RIGHT'} = $W;
$S->{'BACK'} = $N;
$S->{'direction'} = 'S';
my $NowDirection = '';
#-状態を設定
if ($enemy->{'direction'} eq 'N') {
$NowDirection = $N;
} elsif ($enemy->{'direction'} eq 'E') {
$NowDirection = $E;
} elsif ($enemy->{'direction'} eq 'W') {
$NowDirection = $W;
} elsif ($enemy->{'direction'} eq 'S') {
$NowDirection = $S;
}
#-通路の種別を選択
$Wall = 'FORWARD_' if ($Map[$NowDirection->{'Y'}][$NowDirection->{'X'}] ne '#');
$Wall .= 'LEFT_' if ($Map[$NowDirection->{'LEFT'}{'Y'}][$NowDirection->{'LEFT'}{'X'}] ne '#');
$Wall .= 'RIGHT_' if ($Map[$NowDirection->{'RIGHT'}{'Y'}][$NowDirection->{'RIGHT'}{'X'}] ne '#');
if ($Wall =~ /^$/) {
#-行き止まりなのでバックします
$enemy->{'X'} = $NowDirection->{'BACK'}{'X'};
$enemy->{'Y'} = $NowDirection->{'BACK'}{'Y'};
$enemy->{'direction'} = $NowDirection->{'BACK'}{'direction'};
} elsif ($Wall =~ /^(FORWARD|LEFT|RIGHT)_$/) {
#-通路なので進みます
$Wall =~ s/_//;
$enemy->{'X'} = $NowDirection->{$Wall}{'X'};
$enemy->{'Y'} = $NowDirection->{$Wall}{'Y'};
$enemy->{'direction'} = $NowDirection->{$Wall}{'direction'};
} else {
#-交差点なので考えます
my $dx = $Pacman->{'X'} - $enemy->{'X'};
my $dy = $Pacman->{'Y'} - $enemy->{'Y'};
if ($dx != 0) {
if ($dx > 0) {
if ($Map[$E->{'Y'}][$E->{'X'}] ne '#') {
$enemy->{'X'} = $E->{'X'};
$enemy->{'Y'} = $E->{'Y'};
$enemy->{'direction'} = $E->{'direction'};
return;
}
} else {
if ($Map[$W->{'Y'}][$W->{'X'}] ne '#') {
$enemy->{'X'} = $W->{'X'};
$enemy->{'Y'} = $W->{'Y'};
$enemy->{'direction'} = $W->{'direction'};
return;
}
}
}
if ($dy != 0) {
if ($dy > 0) {
if ($Map[$S->{'Y'}][$S->{'X'}] ne '#') {
$enemy->{'X'} = $S->{'X'};
$enemy->{'Y'} = $S->{'Y'};
$enemy->{'direction'} = $S->{'direction'};
return;
}
} else {
if ($Map[$N->{'Y'}][$N->{'X'}] ne '#') {
$enemy->{'X'} = $N->{'X'};
$enemy->{'Y'} = $N->{'Y'};
$enemy->{'direction'} = $N->{'direction'};
return;
}
}
}
&fastMove($enemy);
}
return;
}
__DATA__
50
11 7
###########
#.V..#..H.#
#.##...##.#
#L#..#..R.#
#.#.###.#.#
#....@....#
###########
【マップの読込】
ソースの9～77行までがマップの読み込み部分です。
マップデータをメモリ内に読込んで一行ごとに処理しています。36行でマップデータの一行を一文字ずつに分解し多次元配列に読みこんでいます。
37行目から分割したデータを一文字ずつチェックして文字の種類に応じた処理を行っています。40～44行がパックマンの初期設定。46行がクッキーのカウント。48～71が敵の初期設定です。敵は共通の初期設定を設定したのちに種類毎に配列に格納します。
これにてマップデータの読込は完了です。ここで後々失敗に気がつくのですがマップの座標を[y][x]で設定してしまいました。自分の頭の中では座標はいつも[x][y]で考えているのでちょっとソースが解りにくくなってしまった。。。まあ何はともあれこれで $Map[y][x] と指定すればいつでもマップの内容を参照することが出来るようになったわけです。
【敵キャラクターの動きを計算する】
敵の仕様を見ると L/R/J はパックマンの動きをいっさい考えずに動きます。つまりこの三種類の敵はパックマンがどのようなルートを辿っても必ず同じ動きをすることになります。常に同じ動きをするのであれば三種類の敵の動きは事前に全て計算しておくことができます。そこで@NGBlockという配列を準備して、時間＝tにおける L/R/J の位置をハッシュテーブルにして入れることにしました。
ここで注意すべきはｔにおける敵の状態を個々の個体できちんと管理しなければならない事です。最初私はｔにおける各敵の座標だけをまとめて一つの$NGBlock[t]の中にいれていたのですがそれではゲームオーバーの条件の一つである「時刻 t-1 における自機と敵 x の位置と、時刻 t における自機と敵 x の位置が交換されている。」という判定ができないことに気がつきました。ささっとシミュレータなどを組んだ人で自機が敵をすりぬけてしまう人はこの判定がうまくいってないのが原因だと思います。そこでｔにおける敵ｘの位置を、
$NGBlock[t][x]
の中に入れることにしました。これでそれぞれの敵の遷移を追う事ができるようになりました。この部分のソースは87～147行までの部分です。L/R/Jのtにおける座標を順番に計算しています。
この三種はほとんど動作が同じで違うのは交差点に入った時の動きだけです。交差点マスに入ったさいに優先する方向がちがうだけなのでサブルーチンに方向の優先順を渡す事でロジックを使いまわしています。Jに関しては交差点にはいるたびに方向が変わるのでR/Jにない'think'というパラメータを持たせ、サブルーチン内で引数の値が自動で切り替わるよう処理を行っています。
さあこれで時刻ｔにおける敵の座標は
$NGBlock[t][x]
の中にハッシュのキーとして設定されました。時刻tに移動したパックマンの座標が仮にX,Yだとすると、
$NGBlock[t][x]{X/Y} = 'True';
が成立すればその座標には敵がいるのでアウトになります。
敵キャラクタ H/V に関してはパックマンの位置によって行動が変化するのでパックマンの動きを計算する処理で同時に計算していいくことにします。
【パックマンの動きを計算する】
さて、いよいよパックマンの動きを計算していきます。基本的な考えはこうです。
１）時刻tのパックマンの座標から時刻t+1で生存可能な座標を計算する
２）パックマンの座標を再設定
３）t+1して１）の処理に戻る
上記の処理を制限時間分繰り返せばとりあえず制限時間内で生存可能なルートを取得することができます。当初は時刻tでパックマンが生存可能な座標を
$Pacmans[t]
の中に配列で入れようとしていました。
例：LV1スタート時点のパックマンの動き
$Pacmans[0] = (初期配置のパックマン);
・上は壁なので移動できない
・下も壁なので移動できない
・左には移動できる
・右には移動できる
・立ち止まっても大丈夫
$Pacmans[1] = (左に移動したパックマン,右に移動したパックマン,立ち止まったパックマン);
とまあこんな感じでどんどん値を蓄積しそれぞれのパックマンには自分が$Pacmans[t-1]の配列の中にあるどのパックマンから派生したものなのかを覚えさせておけば@Pacmansの中にパックマンの系図が作成されます。
最終的に生き残ったパックマンから系図をさかのぼればルートが取得できます。
ただしこの方法では案の定膨大なメモリが必要になり風子たんはout of memoryです。最終的にはこの「配列の中に系図を作成する」という方法は断念し、派生したパックマンそれぞれに自分の過去の履歴を覚えさせていくことにしました（175行）。そうすれば$Pacmans[t-1]の中身はクリアしても問題なくなるので不要になった段階でメモリを解放（undef）できます。これでかなりのメモリが節約できるようになりました。
「さあ、メモリも節約できた一気に計算だ！」
と行きたいところですがまだ問題があります。時系列でパックマンを派生させる処理ですが移動する条件が絞られるとはいえこれでも膨大な数のパターンを検索していかなければならず現実的には無理があります。そうなると如何に効率よくルートを絞り込むかが重要になってくるわけです。ここで今回採用した絞り込みは、
・次世代派生処理を行う際にクッキーを多く取得しているパックマンを優先する
・次世代のパックマンを生み出せるのは各世代$MAXの数のパックマンだけ
上記二つの処理を導入することにしました。クッキーを多く取得しているパックマンを優先しているのは169行のsort処理。$MAXでの絞り込みは変数$Addをインクリメントしていき$Addが$MAXと等しくなった時にlastでループを抜けるようになっています。
この$MAXの数をマシンパワーと相談しつつ設定することにします。ただし後述しますがこの$MAXの値が大きければいいかと言うと今回のソースに限ってはそうではありませんでした。
さてメモリと計算回数の節約を行ったパックマン経路探索のメインループが166～188行までの部分です。
165行：時刻=0の始祖パックマンを設定します
166行：制限時間ループ開始
169行：時刻＝$countにおけるパックマンを整列して派生処理ループ開始
170行：$MAX制限判定用に$Addをインクリメント
172行：パックマン派生処理
173行：派生パックマンのループ開始
174行：$Pacmans[$count+1]に派生パックマンを格納
175行：ルートの記憶
176行：派生パックマンがマップ内のクッキーを全部食べていたら終了
さて基本的なルーチンは全てお話してしまいましたが H/V の実装のお話をしていなかったのでそちらを少々。
H/V はパックマンの座標位置に応じて動作がかわる場合があります。パックマンがどう動くかによってとうぜんH/Vの動きも変わってくるのである意味パックマンに依存した存在です。そこでパックマンに時刻tにおけるH/Vの座標をもたせておき（156,157行）パックマンの移動経路を決定する220行目に定義したパックマン派生処理「getSafety」の中でH/Vの動きも計算することにします。
getSafetyはパックマンを引数にとるサブルーチンです。戻り値はt+1の時に安全に生存できるパックマンの配列です。それではgetSafetyの中身を見ていきましょう
232～236行、まずは渡されたパックマンの座標から上下左右の座標を計算します。ルーチン内では東西南北の頭文字をとって$N $E $W $Sとしています$Fは動かない＝フリーズです。
239～243行：移動先が壁かどうかの判定
245～262行：事前に計算済の敵との衝突判定
264～287行：敵Vとの衝突を判定します
264～287行：敵Hとの衝突を判定します
敵Vと敵Hとの判定処理は殆ど一緒です。ですので敵Vの方の処理だけ解説したいと思います。
時刻tにおけるパックマンは時刻tにおける敵Vの座標を保持しています。
$Pacman->{'myVacuum'}
この中の値とパックマンを元にVmoveというサブルーチンを呼び出します。これはVの行動ロジックを実装したサブルーチンで必要に応じてパックマンの座標を参照しつつt+1における敵Vの位置を返します。ここで戻された値で衝突判定をするとともにgetSafetyで派生したパックマンにこの値を保持してもらいます。そうすればこの派生パックマンが自分の派生パックマンを生み出すgetSafetyを実行する際に利用されることとなります。この処理をHも同様に処理します。
以上のように「派生パックマンを繰り返し生み出し一番早くクッキーを食べ終わるパックマンを探し出す」というのが今回私が考えたロジックです。
【問題点】
$MAXの部分で少し述べましたが今回の処理で検索範囲を広げるために$MAXを大きくすると実は解が導き出せないことがあります。というのもパックマンの絞り込みで、
「クッキーを一番多く食べているパックマンを優先」
としてあるので単純に先行逃げ切りパックマンが生き残り易くなります。この状態で派生パックマンを処理する分母を増やすとこの先行逃げ切りパックマンが爆発的に増加し大器晩成型パックマンを駆逐してしまうのです。今回たまたま私のマシンのスペックが低かったことが功を奏して、
「$MAX大きいと全然計算が進まねーよ」
とケチくさく値を少しずつ増やして処理するということを行ったので解を導き出すことができました。
絞り込みを一切行わずに超ハイスペックマシンで処理すれば必ず最適解が見つかると思いますがそんな処理はネットブックしか持ってない私にとっては現実的ではありません。潰せるパターンはなるべく潰して、なるべく効率的な絞り込みをする必要があります。例えば同じ量のクッキーを食べているパックマンがいた時はなるべく異なるパターンの派生パックマンを残してパターンのバリエーションを広げてみるとか、試していないですがいろいろ考えられます。また、派生パックマンを生み出すさいにも「待機」と「後退」という選択肢の優先度を調整することでスコアが高い経路がでてきたり低いスコアの経路がでてきたりといろいろです。マップの内容に応じた処理を行ってみるのもなかなか楽しいです。例えばLV1のような狭苦しいマップではやっぱり相手が通り過ぎるのを待つために待機が結構必要だったり、逆にLV2のようにそこそこ広く行き止まりもないマップであれば待機も後退も優先度が下がるといった具合です。LV3では行き止まりの部分があるので「後退は効率悪いから処理しない」なんていうロジックだと絶対クリアできません。
以上、こんな汚いソースはお恥ずかしい限りですが折角参加したDevQuizですし多少なりとも参考になればと公開させていただきました。長々となってしまいましたがお付き合いくださりありがとうございます。
