アルゴリズムに関する質問、議論総合スレ
■ このスレッドは過去ログ倉庫に格納されています
0063Po
NGNG議題:n方向に移動可能なマップ上でのユニットの移動可能範囲の特定(微妙に汎用化)
条件:ユニットの移動力は移動により増加しないものとする(重要)
マップと同じだけの大きさの0で初期化された解答格納用テーブルmap2(真ならば移動可能を示す)、
ユニットの機動力move、がすでに宣言されていて利用できるものとする
解法:n方向に再帰する。再帰関数内では以下の処理を行う
コツ:map2には前回検索時の機動力が入る。これで比較処理での無駄が少しだけ省けるはずだ
void moveable(前回から見た移動方向, ユニットの座標,その他必要なものは考えれ)
{
int i;
ユニット座標の移動処理; /* ここでのユニットってのは実物じゃない。検索用のもの */
move = move - この地点への移動コスト; /* これも実物のじゃないぞ */
/* すでに今回より機動力が多い状態での再帰検索がなされているなら再帰検索を打ち切る */
/* テーブルは0で初期化されているため、これで機動力が0以下の場合にも対応できる点に注意 */
if (map2>=move) {
return;
} else {
map2=move; /* 移動できたぞ、と */
}
for(i=0; i<n; ++i)moveable(i, ...); /* n方向の再帰関数の呼び出し */
}
こんなんでいいのか?
まあ、はじめの呼び出しをどうやればいいかは宿題だな。
テーブルの初期化を含めて、それも一つの関数にしておくと楽だな。
■ このスレッドは過去ログ倉庫に格納されています