移動力にしたがってマップを移動していくタイプの
戦略シミュレーションゲームがあります。
昔だと大戦略といえば通用したのでしょうが、
最近だとスーパーロボット大戦とかファイアーエムブレムとか言えばいいんでしょうかね？
その移動アルゴリズムについて作成してみました。
普通に書くとこんな感じですかね？
class Board{
public:
int mx, my;
int *bd;
Board(int mx, int my):mx(mx), my(my){
bd = new int [mx * my];
}
~Board(){
delete [] bd;
}
int & operator()(int x, int y){return bd[mx * y + x];}
int size()const{return mx * my;}
void fill(int a){
for(int i = 0; i < size(); i++){bd[i] = a;}
}
};
bool range(int x, int y, Board &board){
if (x < 0 || y < 0) return false;
if (board.mx <= x || board.my <= y) return false;
return true;
}
void check(Board &map, Board &out, int x, int y, int now = 0){
// ボード範囲内かのチェック
if (range(x, y, map) == false) return;
int move = map(x, y);
// 空白か移動力が大きい(遠回りしている)なら探索する
if (out(x, y) == 0 || move + now < out(x, y)){
out(x, y) = move + now;
count++;
check(map, out, x + 1, y, now + move);
check(map, out, x - 1, y, now + move);
check(map, out, x, y + 1, now + move);
check(map, out, x, y - 1, now + move);
}
}
int main(void){
Board board(10, 10);
Board idou(10, 10);
board.fill(1);
idou.fill(0);
check(map, out, 7, 5);
}
Boardクラスは単なる二次元配列を作るためのクラスです。
boardがそのマスの地形(必要移動力)が入った変数、
idouがそのマスに移動するために必要な移動力を計算する変数となっています。
check関数を実行すると、idouに計算結果が帰ってきます。
さて、これは余り効率が良い方法とは言えません。
再帰を使っていますので、まず今回の場合は右、左、下、上の順で探索しています。
最初に右に移動した場合を全て探索した後、次は左、下、上、というふうに探索するわけです。
すると、以下のような状態が起こります。
A地点からB地点に行く場合、明らかに遠回りしています。
しかし、再帰を使った場合は、下→左というルートを探索する前に
右→下→左→左というルートを確認します。
実際は、これ以上の更なる無駄なルートを探索しています。
そこで、まずは１歩で移動できるマスすべてを探索した後、
２歩で移動できるマス、３歩で移動できるマス、という風に探索するとよいでしょう。
この方法を使うためにキューを使います。
check関数は以下のように変更します。
struct Data{
int x, y, move;
Data(int x, int y, int move):x(x), y(y), move(move){}
};
void check(Board &map, Board &out, int x, int y){
std::deque<Data> queue;
queue.push_back(Data(x, y, 0));
while(!queue.empty()){
Data &dat = queue.front();
if (range(dat.x, dat.y, map)){
int move = map(dat.x, dat.y);
if (out(dat.x, dat.y) == 0 || move + dat.move < out(dat.x, dat.y)){
out(dat.x, dat.y) = move + dat.move;
count++;
queue.push_back(Data(dat.x + 1, dat.y, dat.move + move));
queue.push_back(Data(dat.x - 1, dat.y, dat.move + move));
queue.push_back(Data(dat.x, dat.y + 1, dat.move + move));
queue.push_back(Data(dat.x, dat.y - 1, dat.move + move));
}
}
queue.pop_front();
}
}
計算したい物をキューの後ろに入れ、先頭から計算していきます。
まず、スタート地点を登録して、その後１歩で移動できる４箇所がキューに入ります。
それらを順に計算し、２歩で移動できる場所が後ろに追加されます。
キューなので、１歩で移動できる場所がすべて探索された後、２歩目の探索が始まります。
最初の再帰を使う方法を「深さ優先探索」、次のキューを使う方法を「幅優先探索」と言います。
どちらを使うか、というのは問題によって様々なのですが、
今回の場合は一歩目、二歩目という感じで順番に探索するほうが向いています。
次回はキューの大きさについて考えてみます。