あたまがうにになる

防衛ゲームの最短ルートを選択する部分のサンプルをPHPで書いてみました。

大雑把に全体の流れを解説すると･･･
・ゴールから移動できる方向に1マスずつ移動しながらどんどん数字を埋めていく
・埋める数字は1から始まり移動が一歩増える毎に1増加していく
・移動先にすでに数字がある場合は、数字が小さい時に限り上書きする
・埋めれるマスが無くなったら終わり
重み付けが終わったらあとは、スタート地点からより数が小さい方向へ進んでいくと、ゴールまで勝手に到着します

  $start = array(); $goal = array(); // FIELDの2次元配列 // S:スタート地点 // G:ゴール地点 // -:通路 // *:障害物 // .:ルート $field = array( array( "-", "-", "*", "-", "S" ), array( "*", "-", "-", "*", "-" ), array( "-", "-", "-", "*", "-" ), array( "-", "*", "-", "-", "-" ), array( "G", "*", "-", "-", "-" ), ); print "初期のフィールド<br />".debug_field($field)."<hr />"; // スタートとゴールの座標ちぇき for ($y=0; $y<count($field); $y++) { for ($x=0; $x<count($field[$y]); $x++) { switch ($field[$y][$x]) { case "S": //スタート $start["x"] = $x; $start["y"] = $y; break; case "G": //ゴール $goal["x"] = $x; $goal["y"] = $y; break; default: break; } } } // 通路に重み付け set_field(&$field, $goal["y"], $goal["x"]+1, 1); //ゴールの右から set_field(&$field, $goal["y"], $goal["x"]-1, 1); //ゴールの左から set_field(&$field, $goal["y"]+1, $goal["x"], 1); //ゴール下から set_field(&$field, $goal["y"]-1, $goal["x"], 1); //ゴール上から print "重み付けが終了したフィールド<br />".debug_field($field)."<hr />"; set_route(&$field, $start["y"], $start["x"]); //スタートから最短ルートをセット print "ルート選択が終了したフィールド<br />".debug_field($field)."<hr />"; exit(); /** * FIELDに重み($point)をセット(再帰関数) * $field フィールド * $y Y座標 * $x X座標 * $point 通路の重み */ function set_field(&$field, $y, $x, $point) { if (!set_point(&$field, $y, $x, $point)) { return; //これ以上たどる必要なし } print "重み付け計算中のフィールド<br />".debug_field($field)."<hr />"; set_field(&$field, $y-1, $x, $point+1); //上 set_field(&$field, $y+1, $x, $point+1); //下 set_field(&$field, $y, $x-1, $point+1); //左 set_field(&$field, $y, $x+1, $point+1); //右 } /** * その通路を塗りかえれるかチェック * 塗りかえれる場合塗り替え * * @return false:無理 true:塗り替えした */ function set_point(&$field, $y, $x, $point) { // 座標の範囲の正当性チェック if ($y<0 || $y>=count($field)) { return false; } if ($x<0 || $x>=count($field[$y])) { return false; } // 通路かどうかチェック if ($field[$y][$x]=="S" || $field[$y][$x]=="G" || $field[$y][$x]=="*") { return false; } // まだ重みついてないので上書き可能 if ($field[$y][$x]=="-") { $field[$y][$x] = $point; return true; } // 重みついてるけど、新しいルートの方が近いので上書きできる if ($field[$y][$x] > $point) { $field[$y][$x] = $point; return true; } return false; } function set_route(&$field, $y, $x){ $point = $field[$y][$x]; print "ルート選択中のフィールド<br />".debug_field($field)."<hr />"; //通路決定 switch(check_route($field, $y, $x)) { case "right": $field[$y][$x+1] = "."; set_route(&$field, $y, $x+1); break; case "left": $field[$y][$x-1] = "."; set_route(&$field, $y, $x-1); break; case "up": $field[$y-1][$x] = "."; set_route(&$field, $y-1, $x); break; case "down": $field[$y+1][$x] = "."; set_route(&$field, $y+1, $x); break; } } /** * 上下左右のどのルートが一番数字が少ないか * @return int "right"or"left"or"up"or"down" */ function check_route($field, $y, $x) { $type = ""; $point = ""; $tmp_point = ""; if ($tmp_point = get_field_point($field, $y-1, $x)) { //上方向 if (!$point || $point>$tmp_point) { //通路候補 $type = "up"; $point = get_field_point($field, $y-1, $x); } } if ($tmp_point = get_field_point($field, $y+1, $x)) { //下方向 if (!$point || $point>$tmp_point) { //通路候補 $type = "down"; $point = get_field_point($field, $y+1, $x); } } if ($tmp_point = get_field_point($field, $y, $x-1)) { //左方向 if (!$point || $point>$tmp_point) { //通路候補 $type = "left"; $point = get_field_point($field, $y, $x-1); } } if ($tmp_point = get_field_point($field, $y, $x+1)) { //右方向 if (!$point || $point>$tmp_point) { //通路候補 $type = "right"; $point = get_field_point($field, $y, $x+1); } } return $type; } /** * ポイントがある場合ポイントを返す * @return int or null */ function get_field_point($field, $y, $x) { // 座標の範囲の正当性チェック if ($y<0 || $y>=count($field)) { return null; } if ($x<0 || $x>=count($field[$y])) { return null; } if (is_numeric($field[$y][$x])) { //数字なら return $field[$y][$x]; } } // デバッグ用のフィールド出力 function debug_field($field) { $str = "<table border=0>"; foreach ($field as $yfield) { $str .= "<tr>"; foreach ($yfield as $value) { $str .= "<td>$value</td>"; } $str .= "</tr>"; } $str .= "</table>"; return $str; }
実際に動作するサンプルも置いときますね。