[ 図１ ]

《規定》
・ＰＣの移動歩数を暫定的に６とする。
・平地マスは歩数１、荒地マスは歩数２、岩マスは歩数１０を必要とする。

　いきなりちょっとした「テクニック」を使っています。岩マスは「進めない」ではなくて、ウェイト１０にしておきます。ＰＣは６歩しか歩けないのですから結局進めないマスです。「結局同じじゃない」と思うかもしれませんが、アルゴリズム上ではまったく変わってきます。「問題は単純化すること」はこの世界の原則です。ちなみに上の絵ではＰＣの歩数は３になっていることを確認しておいてくださいね。真下は荒地のせいで３つ進めない状態なのです。
　移動歩数をｍｖではなく、６としている所は「問題の具体化」を意味します。本来は変数にしておくべきなのですが、変数は便利な反面、可変なのでイメージが掴みにくくなるのです。とりあえず仮の数値を用意してあげれば、「ふむふむ、本来はＰＣは平地は６歩進めるんだな」と感覚的に理解が容易になるのです。

　一つ規定をした上で、以下の移動アルゴリズムを与えます。前回のそれよりさらに単純に、そして分かりやすく具体的になっていますんで、「多少は」安心してくださいね。

《試行》
１、初期化として、一時的に全マスは移動できない範囲であるということにします。上の図でいくなら、白っぽくなった箇所がゼロの状態だと思ってください。
２、ＰＣのマスから、隣接する上下左右それぞれのマスに対して、以下の事を調べます。４方向について調べ終わったら処理完了です。
３、移動歩数値からそのマスの地形ウェイト数を減らします。マイナスになればその地点へは移動できないと分かり、一つの思考は終了します。
４、そうでないなら、少なくとも到達可能である事はわかったので、マークを付けてあげます。マークが付いた所は、実装時には白く光って表示されるというわけです。
５、その地点からさらに３方向に対して、３.以下の思考を繰り返します。なお３方向というのは、４方向のうち戻る方角を除いたものです。

　この結果、マークされた所を光らせてみればめでたく「移動可能地点」がしっかり表示されるはずです。あなたがＳＬＧ構築に興味があって、このアルゴリズムに完全に納得していないなら、必ず手で書いて試してみてください。これをトレースと言います。書き方は完全に任せますので。なおその場合、移動歩数が６だと長くなってしまうので、２や３あたりから試してみると良いでしょう。完成予想図が思い浮かばない人も、やはり紙にトレースしましょう。アルゴリズムというものは、頭が明確に理解していない限り、コンピュータに実装させることなんてできるわけがないのです。

　この２-５の流れは再帰処理と呼ばれています。ぱっと見では「繰り返し」のように感じますが、単なる繰り返しではありません。一つの流れからいくつもの流れができあがり、またその流れの一つからいくつもの流れを実行しています。具体的に何回３〜５の流れを繰り返しているのかを計算すると……移動歩数がｍｖで、マップが仮にすべて平地（ウェイト１）とした場合、４×３の（ｍｖ−１）乗回となります。ｍｖは暫定的に６としたわけですから、４×3^5 ＝９７２回です。最近のコンピュータの性能のことですから、ほんの一瞬で計算してくれますが（ＭＳＸのようなマシンを使って、ＢＡＳＩＣで強引に処理させてみると時間かかりますよ〜）、人間はまじめにやる気はすでにありません。でも人間はこの完成図は予測できます。全部平地とした場合、長さ６のダイヤ（正方菱形）となるはずです。
　ちなみに、ある処理から回数限定で別な処理を掘って行くことを「アンカーを辿る（伸ばす）」とも言われています。ウェブに詳しい人は知っているかも知れませんね。この言葉によって処理を「歩数６でアンカーを辿る」と短く説明することができます。
　それはともかくとして、９７２回はいくらなんでも計算のさせすぎですね。正直効率悪いです。どの辺の効率が悪いかは明白で、同じ地点にマーキングをしたり、そこからまた同じ場所へ移動しているのです。「上→左」と、「左→上」で到達できる地点は同じで、その後の思考もほぼ同じなのです。ここで、先程のアルゴリズムには追加をしてあげます。「既にマークをした地点に来たら、そこからどこにも伸ばさないで流れを終える」これだけで回数は十分の一以下に激減します。アルゴリズムというのは考える人がちょっと仕組みを変えるだけで、サッパリと綺麗になったり、絶望的に劣悪なものにもなるのです。

// ユニット上のＰＣをクリックした時の処理
begin
  // マップ情報の初期化
  for i:=0 to 255 do for j:=0 to 255 do begin
    GW1.BGf[1,i,j]:=1;
    mvrec[i,j]:='';
  end;

  // 四方向にアンカーを伸ばす
  Search(px,py-1,mv,1);
  Search(px+1,py,mv,2);
  Search(px,py+1,mv,3);
  Search(px-1,py,mv,4);

  // この結果、画面表示ルーチンへ
end;

　ではプログラムソースを紹介しましょう。この言語環境はDelphi3.1J+TGWですが、アルゴリズムというのは基本的に言語非依存ですから、多少なりプログラム経験のある方は自分の使っている言語での再現が可能なはずです。では解説を始めましょう。上のソースは、先の試行１.と２.とそのまんま一致しています。ただ、プログラムスタイル的に細かくなっています。まず GW1.BGf[1,i,j] ですが、これが最終的に移動可能範囲を表示するためのマップフィルタです。iとjはマップ上のx,y座標を指します。この配列には１（移動不能っぽいですね）か０（移動可能っぽいですね）の情報のどちらかを書きこみます。また、mvrec[i,j] は、マークフラグを指します。ヌル状態はまだ到達していない地点、１は既に到達が確認された地点であることを示します。
　こうした初期化処理の後、アンカーを伸ばしています。３.から５.の再帰的試行は一つの手続きにまかせることにします。引数は４つあり、順番に検索対象x座標、同y座標、残り移動歩数、移動方向通知引数を示します。この関数の具体的なルーチンは次の通りです。

// 探索手続き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;

　これが手続き部分の全てです。３. から５.の試行通りになっていることを確認してください。これら２つの処理の結果、図１のような画面を表示する準備が整うというわけです。プログラム経験者は、「あら、ほんとこれだけでできるんですか〜」と感じるのではないでしょうか。
　ソースで一応流れをコメントしているので、あとは簡単に説明を加えていきます。Par2-2で、まず本当のマップから現在位置の地形情報を取り出しています。鷹月の使っているTGWコンポーネントでは配列によってマップを保持しています。 GW1.BGF[0,x,y] は地形マップ、GW1.BGf[1,x,y]は移動可能フィルタのマップを示します。この情報を元に、マップ表示のあと、透過処理で黒いフィルタをかけて、移動可能／不能地点をビジュアル的に表現するのです。グラフィック周りは今回のアルゴリズムとは直接関係はありませんので全て省略していますが。
　ともかく、検索対象のマップ情報を取り出します。１が平地、２が荒地、３が岩山であり、それぞれ減少歩数down を設定しています。その結果、残り歩数がマイナスにならないならば、マークをして、アンカーを続けていきます。
　最後のパラグラフ（Par2-5）が、アンカーを広げる部分です。第４引数がここで活躍します。１が上、２が右、３が下、４が左を示し、「自分が来た方角にはアンカーを戻さない」ということを実現しています。

　さて、アルゴリズムは理解できましたでしょうか。ぱっと見程度では分からなくて当然です。それでもアルゴリズムはかなり平易であることは間違いないのです。

[ 図２ ]

- 鷹月ぐみな