SRPG移動範囲と移動経路の求め方

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
taketoshi
記事: 222
登録日時: 13年前
住所: 日本国

SRPG移動範囲と移動経路の求め方

#1

投稿記事 by taketoshi » 11年前

移動範囲と経路を求めるプログラムを

http://gumina.sakura.ne.jp/CREATION/OLD ... SESS03.htm

こちらを参考に書いたのですが、うまく動作しなくて迷っています。
元言語はdelphiで書かれているようで読み解きながらCにしてみました。
狙った動作は移動範囲がひし形になり、移動経路もstring型の変数に記録したいです。
実際動作させるとひし形ではなく経路探索が途中で途切れてしまっています。移動経路も少しおかしいです。

コードは以下のように書きました。ご指導をお願いいたします。
► スポイラーを表示
ページトップ
アバター
softya（ソフト屋)
副管理人
記事: 11677
登録日時: 13年前
住所: 東海地方
連絡を取る:
softya（ソフト屋) に連絡する

Re: SRPG移動範囲と移動経路の求め方

#2

投稿記事 by softya（ソフト屋) » 11年前

これデバッガで追いかけましたか？
by softya（ソフト屋) 方針：私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います（代わりの方がいる保証は出来かねます）。
ページトップ
taketoshi
記事: 222
登録日時: 13年前
住所: 日本国

Re: SRPG移動範囲と移動経路の求め方

#3

投稿記事 by taketoshi » 11年前

ところどころブレークポイントを設定して数値をみてみましたがわかりませんでした。

ブレークポイント設定以外に何かよい追いかけ方はありますか？
ページトップ
アバター
softya（ソフト屋)
副管理人
記事: 11677
登録日時: 13年前
住所: 東海地方
連絡を取る:
softya（ソフト屋) に連絡する

Re: SRPG移動範囲と移動経路の求め方

#4

投稿記事 by softya（ソフト屋) » 11年前

配列を動的確保しているのでデバッガで見づらいんですよね。ってことでテストのために静的確保に切り替えましょう。
それと要所要所で
MoveResult
BlockCheck
MoveDirection
の内容をprintfしながらデバッガでトレースしてみて下さい。
by softya（ソフト屋) 方針：私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います（代わりの方がいる保証は出来かねます）。
ページトップ
taketoshi
記事: 222
登録日時: 13年前
住所: 日本国

Re: SRPG移動範囲と移動経路の求め方

#5

投稿記事 by taketoshi » 11年前

アドバイスありがとうございます。

少しデバッグかけてみたところ怪しい箇所を発見しました。
時間をかけて調べてみます。まだ解決とせず再度報告させていただきます。
ページトップ
YuO
記事: 947
登録日時: 13年前
住所: 東京都世田谷区

Re: SRPG移動範囲と移動経路の求め方

#6

投稿記事 by YuO » 11年前

リンク先のアルゴリズムではだめ，という話な気が……。

チェック済みフラグでは，地点Aから地点Bへの経路のうち，高コストな経路Cが低コストな経路Dよりも先に見つかった場合に，地点Bまでのコストを経路Cの場合のみで計算してしまいます。
# 実際には経路Dで計算しないといけない。
チェック済みフラグではなく，その地点への移動にかかったコストを記録しておき，そのコストより低いコストで移動できることがわかった場合はその地点から先を再計算しないといけません。
計算をせめてキューで行えば，単一コストにおいてちゃんと菱形に広がるんですけどね……。
# 左→下→右→上の順で深さ優先で探す都合上，形が歪になる。
オフトピック
リンク先のアルゴリズムに疑問を持ったので作った，C#でのお試し。
► スポイラーを表示
ページトップ
アバター
softya（ソフト屋)
副管理人
記事: 11677
登録日時: 13年前
住所: 東海地方
連絡を取る:
softya（ソフト屋) に連絡する

Re: SRPG移動範囲と移動経路の求め方

#7

投稿記事 by softya（ソフト屋) » 11年前

元サイトのアリゴリズムを検証していませんでしたが、taketoshiさんのコードには怪しい所があったので元が原因かもしれないのですね。

とりあえず、他の参考サイトを書いておきます。
「シミュレーションゲーム作成工房　より強力な思考ルーチンを求めて」
http://www.jyouhoukaiseki.com/index.html
「ゲームプログラム」
http://www5f.biglobe.ne.jp/~kenmo/progr ... am_ind.htm
by softya（ソフト屋) 方針：私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います（代わりの方がいる保証は出来かねます）。
ページトップ
taketoshi
記事: 222
登録日時: 13年前
住所: 日本国

Re: SRPG移動範囲と移動経路の求め方

#8

投稿記事 by taketoshi » 11年前

お二方お返事ありがとうございます。

>>YuOさん
リンク先のアルゴリズムだと、一度チェックしたところは再計算してくれないので
そこから先に伸びない箇所が存在してしまうということが分かりました。
残りの移動コストを記録するようにして、渡されたコストが記録されたコストより大きければ処理を抜けるようにしました。
そうしたところ、きれいなひし形を描きました。

>>softyaさん
ご提示ありがとうございます。移動経路はここを参考に書いておりました。
今どのようにやるか思考中ですが、経路はうまく記録できなくてとまっています。

スタックとかキューとかつかうんでしょうか・・・。

コード: 

/ 移動範囲検索テストP.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdafx.h"
#include<string>
using namespace std;

#define size 15
#define size2 15

int MoveResult[size][size2];
int BlockCheck[size][size2];
int CountCheck[size][size2];
string MoveDirection[size][size2];


int SerchClr(){

	int i,n;

	//配列の初期化 1が移動不可能
	for(i = 0;i < size ;++i){
		for(n = 0;n < size2;++n){
			MoveResult[i][n] = 1;
		}
	}

	//チェック用の配列を初期化 0が未チェック
	for(i = 0;i < size ;++i){
		for(n = 0;n < size2;++n){
			BlockCheck[i][n] = 0;
		}
	}

	//移動経路を記録した配列を初期化
	for(i = 0;i < size ;++i){
		for(n = 0;n < size2;++n){
			MoveDirection[i][n].clear();
		}
	}

	//マスを何回チェックしたか記録する配列を初期化
	for(i = 0;i < size ;++i){
		for(n = 0;n < size2;++n){
			CountCheck[i][n] = 0;
		}
	}
	return 0;
}

//再帰用関数
int Serch2(int ax,int ay,int cost,int di,string str){

	//バッファオーバーチェック
	if(ax < 0 || ax > size2 || ay < 0 || ay > size)return 0;

	//移動量を引いて処理を続けるか判定する
	if((cost-1) < 0)return 0;//コストがマイナスならば進めないので処理を抜ける
	//渡されたコストが記録されたコストより大きければ処理を抜ける小さければ続行する
	if(BlockCheck[ay][ax] > cost){return 0;}

	//フラグを立てる
	MoveResult[ay][ax] = 0;//移動可能にする
	BlockCheck[ay][ax] = cost;//コストの記録

	//経路情報を記録する
	CountCheck[ay][ax] += 1;
	MoveDirection[ay][ax] = str;
	printf("%s\n",MoveDirection[ay][ax].c_str());

	//暫定的にコストは-1 //最後の文字列が経路情報　
	if(di != 3)Serch2(ax,ay-1,cost-1,1,str += "U");//上
	if(di != 4)Serch2(ax+1,ay,cost-1,2,str += "R");//右
	if(di != 1)Serch2(ax,ay+1,cost-1,3,str += "D");//下
	if(di != 2)Serch2(ax-1,ay,cost-1,4,str += "L");//左
	return 0;
}

int Serch(int ax,int ay,int cost){

	//配列の初期化
	SerchClr();

	Serch2(ax,ay - 1,cost,1,"U");//上
	Serch2(ax + 1,ay,cost,2,"R");//右
	Serch2(ax,ay + 1,cost,3,"D");//下
	Serch2(ax - 1,ay,cost,4,"L");//左

	return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{

	int i,n;

	//原点をどこにするのかの数値を代入
	int ax = 8;
	int ay = 8;
	//移動できる量を代入
	int cost = 5;

	//目的地の数値を代入
	int goalx = 8;
	int goaly = 10;

	//検索実行
	Serch(ax,ay,cost);

	//経路文字列の確認
	printf("経路文字列 = %s\n",MoveDirection[goaly][goalx].c_str());

	//ゴールとスタート埋め込み
	MoveResult[goaly][goalx] = 3;
	MoveResult[ay][ax] = 5;

	//以下は確認作業
	int count = 0;
	for(i = 0;i < size;++i){
		for(n = 0;n < size2;++n){
			printf("%d,",MoveResult[i][n]);
			count ++;
			if(count == size2){
				printf("\n");
				count = 0;
			}
		}
	}

	printf("-----------------------\n\n");

	count = 0;
	for(i = 0;i < size;++i){
		for(n = 0;n < size2;++n){
			printf("%d,",BlockCheck[i][n]);
			count ++;
			if(count == size2){
				printf("\n");
				count = 0;
			}
		}
	}
	printf("-----------------------\n\n");
	count = 0;
	for(i = 0;i < size;++i){
		for(n = 0;n < size2;++n){
			printf("%2d,",CountCheck[i][n]);
			count ++;
			if(count == size2){
				printf("\n");
				count = 0;
			}
		}
	}
	//ここまで


	return 0;
	
}
ページトップ
taketoshi
記事: 222
登録日時: 13年前
住所: 日本国

Re: SRPG移動範囲と移動経路の求め方

#9

投稿記事 by taketoshi » 11年前

悩み続けましたが経路文字列まで取得できました！

経路文字列の渡し方がだめだったようです。
以下の箇所を手直ししたところうまく取得できました。

コード: 

//修正前
    //暫定的にコストは-1 //最後の文字列が経路情報　
    if(di != 3)Serch2(ax,ay-1,cost-1,1,str += "U");//上
    if(di != 4)Serch2(ax+1,ay,cost-1,2,str += "R");//右
    if(di != 1)Serch2(ax,ay+1,cost-1,3,str += "D");//下
    if(di != 2)Serch2(ax-1,ay,cost-1,4,str += "L");//左

//修正後
	//暫定的にコストは-1 //最後の文字列が経路情報　
	if(di != 3)Serch2(ax,ay - 1,cost-1,1,str + "U");//上
	if(di != 4)Serch2(ax + 1,ay,cost-1,2,str + "R");//右
	if(di != 1)Serch2(ax,ay + 1,cost-1,3,str + "D");//下
	if(di != 2)Serch2(ax - 1,ay,cost-1,4,str + "L");//左
ただ、ここでstring型にプラス演算子を追加してなぜ文字が追加されるのかが分からないです。
普通+=で末尾に追加のはずなのですが、コードは狙い通り動いているのですがなぜ動いたのか理解できてない状況です。

一度解決として、再度この質問はトピックを立てさせてもらいます。
ありがとうございました。
ページトップ
YuO
記事: 947
登録日時: 13年前
住所: 東京都世田谷区

Re: SRPG移動範囲と移動経路の求め方

#10

投稿記事 by YuO » 11年前

taketoshi さんが書きました:ただ、ここでstring型にプラス演算子を追加してなぜ文字が追加されるのかが分からないです。
普通+=で末尾に追加のはずなのですが、コードは狙い通り動いているのですがなぜ動いたのか理解できてない状況です。
デバッガで追ってみましたか。
taketoshi さんが書きました:一度解決として、再度この質問はトピックを立てさせてもらいます。
http://dixq.net/forum/viewtopic.php?f=3&t=12659
だと思うのですが，少し外している気がするのでここに追加してしまいます。
taketoshi さんが書きました:

コード: 

//修正前
    //暫定的にコストは-1 //最後の文字列が経路情報　
    if(di != 3)Serch2(ax,ay-1,cost-1,1,str += "U");//上
    if(di != 4)Serch2(ax+1,ay,cost-1,2,str += "R");//右
    if(di != 1)Serch2(ax,ay+1,cost-1,3,str += "D");//下
    if(di != 2)Serch2(ax-1,ay,cost-1,4,str += "L");//左
ここの部分の最初の行にブレークポイントをおき，strをウォッチに入れて，
ステップオーバーしながら実行する，ということをやってみましたか。
これだけで，+=ではいけないことがわかるのです。


ちなみに，経路履歴持たせる実装書いた人間が書くのもなんですが，経路は逆演算で求められます。

元の点Oからある点Aまで移動するのにかかるコストC(OA)は，OからAの隣接する経路上の点Bに移動するコストC(OB)と，BからAに移動するコストC(BA)の和です。
OからAまで移動するのにかかるコストから，Aに移動するコストを引いた値がOからのコストに等しい点をピックアップしていけば，それが逆順ですが経路になります。
この方法であれば，複数の経路がある場合に全ての経路を探索できます。
ページトップ
taketoshi
記事: 222
登録日時: 13年前
住所: 日本国

Re: SRPG移動範囲と移動経路の求め方

#11

投稿記事 by taketoshi » 11年前

>>YuOさん

解説ありがとうございます。
ブレークポイントをかましてステップ実行していましたがそもそもstringの仕様を理解していなかったので
UUUURLRとかどんどん文字が追加されていて悩んでいました。文字列の渡し方がおかしかったので大体この辺かなと睨んでいたのです。
別スレで回答をいただいたので理解は深まりました。

>>ちなみに，経路履歴持たせる実装書いた人間が書くのもなんですが，経路は逆演算で求められます。
softyaさんにご紹介いただいたページにこの経路方法も載っていたので試してませんが方法は知っていました。
ただ、読んでも理解が難しかったので言葉で説明いただいて感謝します。
敵の移動アルゴリズムはこっちのほうがいいかな？と思っています。
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る