ページ 11

最短経路の選択

Posted: 2011年9月06日(火) 04:43
by あさか
本当にすみません・・・。
最短経路に関しては自力で出来ると踏んでいたのですが、何故か障害物を一つだと決め込んでプログラムを組んでしまいましたorz

冷静に考えたら障害物は複数あるものですよね・・・。


現在組んだプログラムの内容は
①目標の座標 から 現在地点の座標を引く

②座標の差分から場合分けし、最短経路を割り出す。

③最短経路途中に障害物があった場合は迂回。(迂回先に障害物があった場合の対策無し)

④一マス進む度に専用の配列にキャラの進んだ向きを数値化して保存

⑤最後にその配列を描画関数に渡して配列の0から値を1づつ増やしていって移動モーションを描画

こんな状態です。
一見するとちょっと手直しすればいけそうな気がしますが、実はこれ全部一つの関数内でif文多用で頑張ってしまいましたorz|||

複数の障害物を避けて最短経路を進むには再帰がどうしても必要になってくるので、全部書き直ししようかと思います。
そこでどの様な再帰関数にしたら良いか簡単にアドバイスを貰えると助かります。

障害物だけに限らず、移動コストの掛かるマップについても考えないといけないのですよね。
 (例えば移動ポイント3の状態で、移動に2ポイント必要な地形を2マス分進んでしまうなど。一見遠回りに見える移動ポイント1地形を選択して移動しないとダメ)


キャラが一マス毎に移動する時の向きを配列に保存する方法だと再帰使った場合生かせなくなりますよね。
ちょっと便利な方法かなぁと思っていたのですがorz

Re: 最短経路の選択

Posted: 2011年9月06日(火) 11:17
by softya(ソフト屋)
いわゆる最短経路の探索ってやつですね。

ここら辺が参考になるのでは。
「ゲームプログラム」
http://www5f.biglobe.ne.jp/~kenmo/progr ... am_ind.htm
戦術SLGの作り方

Re: 最短経路の選択

Posted: 2011年9月06日(火) 13:24
by あさか
ご返信有難う御座います

そちらのサイトも見てみたのですが
ブレゼンハムの線分描画アルゴリズム
は実装出来ている状態です。

肝心のA* による経路探索の内容が何度読んでもよく分からないのですよねorz

この方もC言語で書いてらっしゃるのでしょうか?
使用言語よりも考え方の方が重要なのですけれども。


この方の行っている事の最終段階としては最短経路のマップの値を全てある値に変化させているのですよね?

という事は移動描画の際に隣接マスを調べていき、ある値になっているマスを通っていけば目標地点にたどり着ける訳ですか。
if文場合分けで方向も決めれるしこちらの方が良さそうですねorz

肝心の中身がサッパリですが。。

Re: 最短経路の選択

Posted: 2011年9月06日(火) 14:07
by softya(ソフト屋)
A*は解説があちこちにあるので、そちらを読まれてはどうでしょうか?
「A* アルゴリズム」or「A-star アルゴリズム」で検索できます。A-starの元となるアルゴリズムはダイクストラ法なので、まずそちらを調べた方が良いかもしれません。
私も忘れているので時間がとれたら調べてみます。

Re: 最短経路の選択

Posted: 2011年9月08日(木) 04:52
by あさか
アルゴリズムを理解し、実装したのですが
キャラを一度クリックした後、即また同じ地点をクリックしたと判定されてしまいデバッグすらままなりません。

何が原因なのかもよく分からず、一応該当箇所のプログラムだけ書きます。

コード:

	int test = 0;

	if(( GetMouseInput() & MOUSE_INPUT_LEFT ) != 0){
		test = 1;
	}

	//通常状態で左クリックが押されたら
	switch(mouse_input_state){
		case 0:
			test = GetMouseInput() & MOUSE_INPUT_LEFT;
			if( test == 1 ){
				if( (character_map_data[ select_botan ][ masuY ][ masuX ] == 1) || (character_map_data[ select_botan ][ masuY ][ masuX ] == 2)){
					for(number = 0; number < 3; number++){
						if( (mob_testarray[number].z == select_botan) && (mob_testarray[number].y == masuY) && (mob_testarray[number].x == masuX)){
							//情報を保存しておく
							number_s = number;
							z_s = select_botan;
							y_s = masuY;
							x_s = masuX;
							//移動可能範囲を調べる関数を呼び出し
							Search_move_range(mob_testarray[number].z, mob_testarray[number].y, mob_testarray[number].x, mob_testarray[number].move_point);
							//上下移動可能キャラの場合、別階層の範囲も表示させる
							if(mob_testarray[number].fly == 1){
								if(mob_testarray[number].z == 0){
									Search_move_range(mob_testarray[number].z+1, mob_testarray[number].y, mob_testarray[number].x, mob_testarray[number].move_point-1);
								}else if(mob_testarray[number].z == 1){
									Search_move_range(mob_testarray[number].z-1, mob_testarray[number].y, mob_testarray[number].x, mob_testarray[number].move_point-1);
								}
							}
							//マウスの状態を一段階進める
							mouse_input_state++;
							//マウスが現在どの段階にいるかの情報を受け渡す
							mouse_input_state_receive(mouse_input_state);
                                                                                          test  =  0;
						}
					}
				}
			}break;
		//移動可能範囲表示中
		case 1:
			printf("マウス左クリック:%d\n",GetMouseInput() & MOUSE_INPUT_LEFT);
			if( test == 1 ){
				if(MapData[select_botan][masuY][masuX] == FLASH ){
					//移動最短経路を探索する関数呼び出し
					Make_dirrection(z_s,y_s,x_s,select_botan,masuY,masuX,mob_testarray[number_s].move_point);
					mouse_input_state++;
					//描画関数に移動方向配列の情報を受け渡し
					dirrection_array_data_recrive(save_four_dirrection_array);
					//マウスの状態を送る
					mouse_input_state_receive(mouse_input_state);
					//目標地点の座標を保存しておく
					z_s = select_botan;
					y_s = masuY;
					x_s = masuX;
					//キャラクターを移動中の値に変更する
					mob_testarray[number_s].mob_number = mob_testarray[number_s].mob_number + 20;
					//FLASHの値を元に戻す
					for(fz=0; fz<MAP_HEIGHT; fz++){
						for(fy=0; fy<MAP_LENGTH; fy++){
							for(fx=0; fx<MAP_WIDTH; fx++){
								if(MapData[fz][fy][fx] == FLASH){
									MapData[fz][fy][fx] = 0;
								}
							}
						}
					}
				}
			}
			//右クリックが押されたら状態を戻す
			if( ( GetMouseInput() & MOUSE_INPUT_RIGHT ) != 0 ){
				//FLASHの値を元に戻す
				for(fz=0; fz<MAP_HEIGHT; fz++){
					for(fy=0; fy<MAP_LENGTH; fy++){
						for(fx=0; fx<MAP_WIDTH; fx++){
							if(MapData[fz][fy][fx] == FLASH){
								MapData[fz][fy][fx] = 0;
							}
						}
					}
				}
				mouse_input_state = 0;
				//マウスが現在どの段階にいるかの情報を受け渡す
				mouse_input_state_receive(mouse_input_state);
			}break;
		//キャラクター移動中
		case 2:
普通でしたらマウス入力関数が終わった後は左クリック判定が0に戻り、関数が呼び出された時も0のままですよね?
一体何故ダブルクリックされたとみなされてしまうのでしょうか・・・。

Re: 最短経路の選択

Posted: 2011年9月08日(木) 10:28
by softya(ソフト屋)
とりあえず変な所
test = GetMouseInput() & MOUSE_INPUT_LEFT;
if( test == 1 ){
これは、test == 1とは限りません。
&はビット論理演算ですからね。
test != 0
なら問題ないです。

Re: 最短経路の選択

Posted: 2011年9月08日(木) 14:14
by あさか
あぁおっしゃる通りです。
書き間違ってました。

しかし直してみても結果が変わらず・・・。

Re: 最短経路の選択

Posted: 2011年9月08日(木) 14:22
by softya(ソフト屋)
普通でしたらマウス入力関数が終わった後は左クリック判定が0に戻り、関数が呼び出された時も0のままですよね?
GetMouseInput() の事でしたら押している間はずっと該当ビットが1ですが、そこは大丈夫ですか?
そういう前提になっていない様に見えますが。

Re: 最短経路の選択

Posted: 2011年9月08日(木) 14:55
by あさか
あぁ・・・なるほど。
デバックで見る限り、どうやらそれが原因の様です。有難う御座いますm(_ _)m

一回関数の処理が終わった後、GetMouseInput() を0に戻すにはどのようにすれば宜しいでしょうか?
GetMouseInput() に値は代入出来ないですし・・・、GetMouseInput() の動きを一時的に止めれれば良いのですが・・・。

Re: 最短経路の選択

Posted: 2011年9月08日(木) 15:03
by softya(ソフト屋)
止めるなんてことは出来ませんので、「ゲームプログラミングの館」で使われているキーの押されているフレーム数をカウントするテクニックを使います。
「2.9章 全てのキーの入力状態を取得する」
http://dixq.net/g/02_09.html
これと同じ手法で、マウスクリックをチェックする関数を作ります。
LEFTとRIGHTをそれぞれ押している間フレーム数をカウントして離したら0に戻すって事ですね。
でLEFTカウントが==1なら押された直後と判定すればよいでしょう。

Re: 最短経路の選択

Posted: 2011年9月13日(火) 00:25
by あさか
画面スクロールさせる際に同じように実装したら有り得ないスピードでスクロールしてしまったので、ソフト屋さんに今教わった方法で描画していた事に今更気付きました。
ちょっと考えを広げればそこからマウスにも応用出来たのに情けないです。
何から何まで有難う御座いますm(_ _)m