移動アルゴリズムの難しさ：未経験無職ゲーム制作日記２日目
こんばんは。さいとうです。
昨日の日記で移動アルゴリズムについて考えてみましたが、その後さっぱり進展せず今の時間になりました。
一人で考えることの限界を突破したので、Google先生に訊いてみることにしました。
今日はその辺をお話しします。
１．移動アルゴリズムを考える難しさ
前提として私はプログラマ未経験なので、どんなアルゴリズムを考えるにしてもハードルは高いと思ってます。
ですが、今回は調べてみて、早めに白旗降ってGoogleに頼った自分をほめてあげたい。
それくらい面倒くさい、もといややこしいものでした。
まずは参考にしているページと、載っていたコードをどうぞ。
// 探索手続きSearch
Procedure Search(ax,ay,mv,di);
var down,num:integer;
begin
// すでにチェック済みだったらこれ以上の探索は無意味(Par2-1)
if mvrec[ax,ay]<>'' then exit;
// 現在の地点にあるマップ情報を取り出して、ウェイトを計算(Par2-2)
down:=0; num:=GW1.BGf[0,ax,ay];
if (num=1) then down:=1;
if (num=2) then down:=2;
if (num=3) then down:=10;
// 歩数がマイナスになった地点へは進めないので思考中断(Par2-3)
if mv-down<0 then begin
exit;
end;
// マークをします(Par2-4)
GW1.BGf[1,ax,ay]:=0;
mvrec[ax,ay]:='1';
// さらに現在の位置からアンカーを伸ばす(Par2-5)
if di<>3 then Search(ax,ay-1,mv-down,1);
if di<>4 then Search(ax+1,ay,mv-down,2);
if di<>1 then Search(ax,ay+1,mv-down,3);
if di<>2 then Search(ax-1,ay,mv-down,4);
end;
/*
*引用元：http://gumina.sakura.ne.jp/CREATION/OLD/MAKING/SESS03.htm
*ゲープロ講座セッション３：戦術型ＳＬＧの移動アルゴリズム（２）
*- 移動アルゴリズムのソースを解析する
*/この記事が書かれたのが1999年ということにまず驚きですね…
ファイアーエムブレムがファミコンの時代からあるので、ネットの普及時からこういった情報が出回っているのは当然と言えば当然なのでしょうが、先人たちの恩恵に頭が上がりませんね。
ではざっくりとこのページの内容の説明をしていきます。
マス目を移動する能力が６マス分あるキャラの移動可能なマス目を、何も考えずにすべて確認しようとすると、「４×３^５ ＝９７２回」の探索回数が必要です。
（しかもこれ、来た道は確認しないという、当たり前ですがなかなか面倒くさい手順を追って、です。）
さらに「すでに確認済みのマス（移動の可不可を問わない）は確認しない」という条件を加えてあげると、探索回数が十分の一以下に激減するとのこと。
実行時の負荷を考えると、なるべく動作は軽くしたいので、この内容は行幸でした。
（ちなみに下の画像が昨日の私が考えていた移動可能か探索するアルゴリズムですが、このやり方だと972回どころか4096回の探索回数になってましたね…）
興味を持たれて、しっかりと内容を確認したければぜひリンク先に飛ぶことをお勧めします。
文体も柔らかで、分かりやすく説明されています。
本当にすごい。
２．アルゴリズム解説
上記のページでは５つの区画に分けて、コードを解説していました。
①指定のマスはチェック済みかを確認。
②マップ上に存在する全種類の地形の進入コストを記載。
③キャラの残っている移動力から、指定マスへの進入が可能か確認。
④進入コストが払えるなら、移動可能であることをマーク。
（不可なら不可であるとマーク。）
指定マスがチェック済みであるとマーク。
⑤指定マスから１マス隣りへ移る。（来た道は確認しない。）
すごく短く、PCに無駄な負担を掛けない、とてもきれいなコードでした。
上手く表現できませんが、とても感動しました。
３．最後に
早くコードを書いていきたいので、今日はこの辺で終わりにします。
また明日進捗があれば報告します。
あと忘れていましたが、明後日がITパスポートの試験日でした。
過去問道場を５０問程度やってみたら８割強だったので、もう勉強しません（笑）
今はやりたいこと山積みなので、試験勉強もそこそこに、書きたいコード書いていきます。
今日も最後まで読んでいただきありがとうございました。
それではまた明日。