ボンバーマンにおけるＣＰの思考ルーチンについて

[nayo]

現在ボンバーマンもどきを作っているのですがＣＰの思考ルーチンで行き詰ってしまいました

一応対人戦はできるのですがさすがに２人以上集まらないとできないゲームは厳しいと思ったので
ＣＰを作ろうと思った次第です

現在の考え方としては
マスの状態を通れるか通れないかのフラグ分けをし（爆発直前のマスも通れないとする）、それを利用して

・もしその場所が将来的に爆発する（通れないマス上）なら爆発しない位置まで移動
・そうでなければアイテムを探し、アイテムがあればその方向へ移動する
・アイテムが無ければ近くのプレイヤーを探し、プレイヤーが居たらプレイヤーの近くに移動し、
　一定距離内に入ったら特定の攻撃パターン（？）でボムを置く
・プレイヤーも近くに居なければソフトブロックを探し、
　ソフトブロックがあればソフトブロックの隣に移動し、ボムを置く
・これら以外ならフィールドの中央に向かって移動する

とすれば良いかな？と思っています

ここからが問題なのですが移動する方向を得る方法が分かりません
移動についてはhttp://www5f.biglobe.ne.jp/~kenmo/progr ... /move.htmlを参考に再帰を使って調べていこうと思ったのですが、
例えば、周りを調べて目的のマスが見付かったらその方向への探索は終了、
これを繰り返し、探索が終了した後、
最も近くの目的のマスへの最初の方向というものはどうやって得ればいいのでしょうか

と、非常に伝わりにくい文章で申し訳ないですがどなたかご回答お願いします


環境はVisual C++ 2008 Express Edition
ＤＸライブラリ使用、です

[たいちう]

> 最も近くの目的のマスへの最初の方向というものはどうやって得ればいいのでしょうか

あくまでも一例です。できるだけ理解しやすいアルゴリズムを考えてみました。

キャラの現在地から任意のマスまで、障害物を迂回して最短何歩で辿り着けるかは分かりますか？
全てのマスに対応する二次元配列を-1で初期化し現在地を0で初期化します。
効率をかなり無視したアルゴリズムですが、まず、全てのマスを調べ、
0と接した全ての-1のマスを1とします。
次に、全てのマスを調べ、1と接した全ての-1のマスを2とします。
これを繰り返すと、全てのマスについて現在位置からの最短歩数が分かります。

目的のマスが複数あるみたいですので、最短歩数の配列を元に、目的地を1つ選びましょう。
目的地が分かれば、そこまでの歩数が分かります。仮に5歩としましょう。
5歩のマスの上下左右には、少なくとも1つ4歩のマスがあるはずです。
そこを探してそこまで戻りましょう。
同様に、4歩のマスの上下左右には、少なくとも1つ3歩のマスがあるはずです。
このように、1歩のマス、つまり現在地の隣のマスまで戻ることができますので、
現在地からの最初の方向とすることができます。


より良い方法はあると思いますが、とりあえず、これで実装してみてはいかがでしょうか。実験的に。
効率面や、動きのバリエーションについて疑問があれば、その後で再度尋ねてください。

[nayo]

返信遅れて申し訳ないです
素早い回答有難う御座います

自分なりにもう一度見直してＣＰを作ってみました
解決した方法としては

最初の４方向を調べる関数で調べる方向を保存しておき、
目的のマスが見付かった際にそこまでの移動距離と、向きを保存、
再度調べていないところを調べていき、また目的のマスが見付かったときは
前見付かった目的の場所と距離を比較し、近いなら更新、といった具合です

また、爆発する場所を通れないとすると全く動けないときなどもあるので、
現在のマスが爆発するなら爆発する場所でも通れるとし（ただし爆発直前は不可）、
安全な場所を探す、といった感じに変えました

まだ
・稀に自滅することがある
・ボムを同時に出す個数を制限（最大でも３個程度）
・再帰の検索距離を８以上にするとＦＰＳが30以下まで落ちる
といった感じなのでここら辺を改良していきたいと思います
自分で作って改めてＳＦＣのゲームでも凄いんだなと実感しました…

[たいちう]

> ・再帰の検索距離を８以上にするとＦＰＳが30以下まで落ちる

遅すぎますね。
その程度の検索がFPSに影響を及ぼすことは考えにくいので、
かなり無駄な処理が多いのでしょう。
もしご自身で解決できないようでしたらソースを載せてみてはどうかと。