戦術SLGの移動アルゴリズム

[ジャン]

ファイヤーエンブレムのような移動関数がわかりません。
http://www5f.biglobe.ne.jp/~kenmo/progr ... /move.html
↑ここのサイトとかをいくら読んでもわかりません。
教えてください。お願いします。

[softya（ソフト屋)]

分からない所は何処でしょうか？
書いてある以上のことは説明できると思えませんので、分からないポイントを具体的に質問していただけますか。

↓　その他参考になるサイト
「Article: ゲームプログラミング講座」
http://gumina.sakura.ne.jp/CREATION/OLD ... index.html
「シミュレーションゲーム作成工房　より強力な思考ルーチンを求めて」
http://www.jyouhoukaiseki.com/index.html

[ジャン]

戦術SLGの作り方（移動範囲を求める）
http://www5f.biglobe.ne.jp/~kenmo/progr ... ve.html#2a
このサイトの「Search4」関数と「Search」関数の中身がよくわからないです。
答えを教えてください。おねがいします。

[softya（ソフト屋)]

答えとは？どういう意味でしょう。アルゴリズムは十分に説明されていると思いますが。
ジャンさんが理解できている範囲でアルゴリズムを書きだしてもらえますか？それに過不足があれば書き加えますので。

後、私の紹介したサイトは見てもらえましたか？

【記入例】
Search4
(1)上方向。Search(x,y-1,移動力)をよびだす。
(2)下方向。Search(x,***,移動力)をよびだす。
(3)左方向。Search(***,y,移動力)をよびだす。
(4)右方向。Search(***,y,移動力)をよびだす。
わざと伏字にしました。

[ISLe]

質問者さんは、リンク先が参考にしたと書いてある 「戦術SLGの移動アルゴリズム」というページがリンク切れなので、そこに書いてあったであろうコードを書いてよこせ、自分で考える気はない、とおっしゃっているのでしょうかね。

(追記)
1. 「10×10」の配列を作成する
2. 初期位置は（6, 6）、移動力は「3」の移動データを作成する
という準備段階のところから分からないのでしょうか。

[softya（ソフト屋)]

>質問者さんは、リンク先が参考にしたと書いてある 「戦術SLGの移動アルゴリズム」というページがリンク切れなので、そこに書いてあったであろうコードを書いてよこせ、自分で考える気はない、とおっしゃっているのでしょうかね。

もし、そうなら残念ですね。
敵を避けるとか、地形の移動コストとか絡んでくると、このアルゴリズム自体を理解しないと応用が全くできないので今後つまづくと思うのですが。

[ジャン]

言葉数少なくてごめんなさい、これでも一生懸命なんです。
>>1. 「10×10」の配列を作成する
2. 初期位置は（6, 6）、移動力は「3」の移動データを作成する
という準備段階のところから分からないのでしょうか。

これはわかりますhantei[10][10]
初期配置cx cy
移動力moveで作りました。

>>後、私の紹介したサイトは見てもらえましたか？

ｃ＋＋初心者なので他の言語はわかりません
しばらく考えた結果serch4はわかりました。

コード:

 void serch4(int x, int y, int m){
	 cx=x;//上
	 cy=y-1;
	 serch(cx,cy,move); 
	 cx=x-1;//左
	 cy=y;
     　　　serch(cx,cy,move); 
	 cx=x+1;//右
	 cy=y;
	 serch(cx,cy,move);
	 cx=x;//下
	 cy=y+1;
	 serch(cx,cy,move);
 }

しかしserch関数のほうが分かりません。

コード:

 void serch(int x, int y, int m)
{
 	 move=m+hantei[x][y];
	 hantei[x][y]=move;
 }	
 if(move>0){
	serch4(cx,cy,move);
	serch(cx,cy,move);
	 }

あのサイトの
（移動力がなくなったので、(6, 4)地点に戻り、左を探索し、「Search」で「０」を設定します。）
とかちんぷんかんぷんです。

[softya（ソフト屋)]

codeタグを使ってくださいね。
後インデント(字下げ)は的確に行ってください。バグのもとになります。

>>後、私の紹介したサイトは見てもらえましたか？
>ｃ＋＋初心者なので他の言語はわかりません

pascalやＶＢが分からなくても考え方の説明があるので参考になるはずですよ。Ｃに比べて難しい所があるわけでも無いですし。

search4も、こんな風にまとめられます。

コード:

void search4(int x, int y, int m){
	search(x,y-1,m);//上
	search(x-1,y,m);//左
	search(x+1,y,m);//右
	search(x,y+1,m);//下
}

それとserch関数はコンパイルできる関数としても成立していませんし、参考サイトに書いてあること以外のことをしています。
もう一度searchのアルゴリズムを日本語で私の例のように書いてみてください。

>移動力がなくなったので、(6, 4)地点に戻り、左を探索し、「Search」で「０」を設定します。
これはきっちりアルゴリズムが組まれていれば自動的にそうなります。

この３つは分かるんですよね？
・たとえば、「Search4」で上を探索すると、「Search」で「２」を設定します。
・移動力がまだ残っていますので、「Search4」を再帰呼び出しし、上を探索して、「Search」で「１」を設定します。
・さらに、移動力がまだ残っていますので、「Search4」を再帰呼び出しし、上を探索して、「Search」で「０」を設定します。
ここをきっちりアルゴリズム化しましょう。

このアルゴリズムは、再帰呼び出しを使いますので再帰呼び出しも勉強してください。
「Ｃ言語編　第５６章　再帰呼び出し」
http://www.geocities.jp/ky_webid/c/056.html

[ジャン]

おかげさまでたぶん基本はできました。

コード:

 void search(int x, int y, int m)
{
	x2=x;
   　　　y2=y;
	smove=m-1；
	hantei[x2][y2]=smove;//代入
 }	
 void serch4(int x, int y, int m){ 
	search(x,y-1,m);//上
	if(smove>0)
    　　　serch4(x2,y2,smove);
    　　　search(x-1,y,m);//左
	if(smove>0)
	serch4(x2,y2,smove);
	search(x+1,y,m);//右
	if(smove>0)
    　　　serch4(x2,y2,smove);
    　　　search(x,y+1,m);//下
	if(smove>0)
    　　　serch4(x2,y2,smove);
 }

しかし、地形データを考慮して
「Search」関数で単純に移動力を「-1」としていたものを、地形の値から引くというのが
うまくいきません

コード:

void search(int x, int y, int m)
{
	x2=x;
    　　　y2=y;
	tikei=hantei[x2][y2];
	smove=m-tikei;
	hantei[x2][y2]=smove;//代入
 }	

こうすると何故エラーがでるのかわかりません。
ポイントを使えばいいのでしょうか？

[softya（ソフト屋)]

元のアルゴリズムの通りになっていないので無駄があります。
search4ですべきことをsearchでやっていたりします。
ところで、これって値が正しいか動作確認しましたか？

コード:

 void search(int x, int y, int m)
{
　　元のアルゴリズムにある内容が足りません。
    x2=x;　←　代入し直す意味はありません。バグのもとです。
   　　　y2=y;　←　インデントは正確に
    smove=m-1；　←　smoveは不要です。
    hantei[x2][y2]=smove;//代入
 }  
 void serch4(int x, int y, int m){ 
    search(x,y-1,m);//上
    if(smove>0)　←　他の関数の変数smoveをここで参照してはいけません。ブロック{}が無いのでif文の範囲が不明確です。初心者は{}を省略してはいけません。
    　　　serch4(x2,y2,smove);　←　ここにあってはいけません。
    　　　search(x-1,y,m);//左
    if(smove>0)
    serch4(x2,y2,smove);
    search(x+1,y,m);//右
    if(smove>0)
    　　　serch4(x2,y2,smove);
    　　　search(x,y+1,m);//下
    if(smove>0)
    　　　serch4(x2,y2,smove);
 }

こちらのエラーは貼りつけてもらえますか？
こうしたところエラーはないようですが。

コード:

int hantei[10][10];
void search(int x, int y, int m)
{
    int x2=x;
    int y2=y;
    int tikei=hantei[x2][y2];
    int smove=m-tikei;
    hantei[x2][y2]=smove;//代入
}}

ちなみに、searchとsearch4の説明には元のサイトで意図的か抜けている処理があります。
これは、これが組みあがったらそこも考えましょう。

戦術SLGやRPGは初心者向けとはとても言えない難しいジャンルです（中級～上級者向け）。
なので、苦労することになると思いますががんばってください。

[ISLe]

うまくいかないのは再帰呼び出しとは別の問題があるからです。

以下は、Search4関数とSearch関数が分からないだけならこの程度のコードは書いて提示してください、と投稿するつもりだったコードです。
昨日のうちに書いたので変数名などは質問者さんの名付けに倣ってないところがあります。

コード:

#include <stdio.h>
#include <string.h>
#define MAP_W 10
#define MAP_H 10
int map[MAP_H][MAP_W] = {
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
};
int work[MAP_H][MAP_W];
void print_work(void)
{
	int x, y;
	for(y=0;y<MAP_H;y++) {
		for(x=0;x<MAP_W;x++) {
			printf("%-2d", work[y][x]);
		}
		printf("\n");
	}
	printf("\n");
}
void Search4(int x, int y, int m);
void Search(int x, int y, int m)
{
	/* TODO */
	work[y][x] = m;
	/* TODO */
}
void Search4(int x, int y, int m)
{
	Search(x, y-1, m); /* 上 */
	Search(x, y+1, m); /* 下 */
	Search(x-1, y, m); /* 左 */
	Search(x+1, y, m); /* 右 */
}
int main(void)
{
	int x = 6-1;
	int y = 6-1;
	int m = 3;
	memcpy(work, map, sizeof(work));
	Search(x, y, m);
	print_work();
	return 0;
}

Search4関数は答えが出ているので埋めておきました。

このコードはTODOを埋めれば正しく動きます。
うまくいかない原因を見付けてください。

難易度は高いですが、コードは拍子抜けするくらいシンプルになります。

[ジャン]

これであっているでしょうか？

コード:

void serch4(int x, int y, int m);
 void search(int x, int y, int m)
 {
	 m--;
	 if(m>hantei[x][y]){
	 hantei[x][y]=m;//代入
	 }
	 if(m>0){
     serch4(x,y,m);
	 }
 }	
 void serch4(int x, int y, int m){ 
	search(x,y-1,m);//上
    search(x-1,y,m);//左
	search(x+1,y,m);//右
    search(x,y+1,m);//下
 }

関数の宣言なしにずっと考えていました。
なんてこったい。
ちなみにさきほどのソースは同じ答えが表示されてました。

地形を考慮して書き換えた所

コード:

void search(int x, int y, int m)
 {
	 m=m+hantei[x][y];
	 if(m>hantei[x][y]){
	 hantei[x][y]=m;//代入
	 }
	 if(m>0){
     serch4(x,y,m);
	 }
 }	

このようなエラーがでました。
↓
a2.exe の 0x00572d15 でハンドルされていない例外が発生しました: 0xC0000005: 場所 0x0087dffc に書き込み中にアクセス違反が発生しました。

[softya（ソフト屋)]

ISLeさんのコードに合わせて動くようにしてもらうか、全部のコードを提示してください。

これだと、既に移動値mが置かれている所に置かれると思います。条件が判断が不十分ですね。
m=m+hantei[x][y];

ISLeさんのコードを使えば、

コード:

void Search4(int x, int y, int m)
{
    print_work();
    Search(x, y-1, m); /* 上 */
    Search(x, y+1, m); /* 下 */
    Search(x-1, y, m); /* 左 */
    Search(x+1, y, m); /* 右 */
}

で途中経過を確認できます。

>a2.exe の 0x00572d15 でハンドルされていない例外が発生しました: 0xC0000005: 場所 0x0087dffc に書き込み中にアクセス違反が発生しました。
これの原因は
>ちなみに、searchとsearch4の説明には元のサイトで意図的か抜けている処理があります。
>これは、これが組みあがったらそこも考えましょう。
と関係します。

[ジャン]

ISLeさんのコードを使わせてもらいます
これであっていますでしょうか

コード:

#include<iostream>
#include <string.h>
#define MAP_W 10
#define MAP_H 10
int map[MAP_H][MAP_W] = {
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
};
int work[MAP_H][MAP_W];
void print_work(void)
{
    int x, y;
    for(x=0;x<MAP_H;x++) {
        for(y=0;y<MAP_W;y++) {
            printf("%-2d", work[x][y]);
        }
        printf("\n");
    }
    printf("\n");
}
void Search4(int x, int y, int m);
void Search(int x, int y, int m)
{
    /* TODO */
	//m--;
	m=m+map[x][y];
	if(m>work[x][y]){
    work[x][y] = m;
	}
	
	if(m>0){
	Search4(x,y,m);
	}
    /* TODO */
}
void Search4(int x, int y, int m)
{
	print_work();
    Search(x, y-1, m); /* 上 */
    Search(x, y+1, m); /* 下 */
    Search(x-1, y, m); /* 左 */
    Search(x+1, y, m); /* 右 */
}
int main(void)
{
    int x = 6-1;
    int y = 6-1;
    int m = 3;
    memcpy(work, map, sizeof(work));
    Search4(x, y, m);
    print_work();

	fflush(stdin);//止める 
	getchar(); 

	return 0;
}

配列を別々に作ればよかったんですね。

[softya（ソフト屋)]

大丈夫だと思います。
まず、ここまでお疲れ様でした。

さて、残っている問題として
int x = 3-1;
int y = 3-1;
を起点とするとどうなるか試してみてください。
あとこの対処方法を考えて見ましょう。

[ジャン]

こうですね

コード:

void Search4(int x, int y, int m)
{
	print_work();
	if(0<x&&x<10&&0<y&&y<10){
    Search(x, y-1, m); /* 上 */
    Search(x, y+1, m); /* 下 */
    Search(x-1, y, m); /* 左 */
    Search(x+1, y, m); /* 右 */
	}
}

&&の書き方がなかなか思い出せませんでした。

[bitter_fox]

こうですね

コード:

void Search4(int x, int y, int m)
{
	print_work();
	if(0<x&&x<10&&0<y&&y<10){
    Search(x, y-1, m); /* 上 */
    Search(x, y+1, m); /* 下 */
    Search(x-1, y, m); /* 左 */
    Search(x+1, y, m); /* 右 */
	}
}

&&の書き方がなかなか思い出せませんでした。

起点を
int x = 0;
int y = 3-1;
などにすると

コード:

-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1

となってしまいます。

[ISLe]

質問にあるリンクの先のページにちょろっと書いてあるのですが、配列を広げて番人を置くとプログラムがシンプルになります。
さらにマップの参照を間接的に行うようにすれば、配列とかサイズとか実装に依存しなくなるので、複雑な構造のマップにも対応できます。

番人の真上を起点にしたら破綻しますが、マップ上にいるユニットを起点とするわけですから、実際には起点の座標チェックは済んでいると考えることができます。

[ジャン]

>>配列を広げて番人を置く
侵入できない地形で囲むんですね。

>>マップの参照を間接的に行うようにすれば
配列をポインタで参照するということでしょうか？
ポインタはまだよくわかりません。

>>番人の真上を起点にしたら破綻しますが、マップ上にいるユニットを起点とするわけですから、実際には起点の座標チェックは済んでいると考えることができます。

serch4関数の中身はこれでＯＫなんですね。

[ISLe]

>>配列を広げて番人を置く
侵入できない地形で囲むんですね。

そうです。

>>マップの参照を間接的に行うようにすれば
配列をポインタで参照するということでしょうか？
ポインタはまだよくわかりません。

配列に直接アクセスするのではなく、
m = get_map(x, y);
のように関数に処理を移して必要移動力を得るようにするということです。
例えば配列のサイズを実際に広げなくても、配列の範囲外だったら最大移動量(番人)を返すように関数を組むこともできます。

>>番人の真上を起点にしたら破綻しますが、マップ上にいるユニットを起点とするわけですから、実際には起点の座標チェックは済んでいると考えることができます。
serch4関数の中身はこれでＯＫなんですね。

いわゆる「運用でカバー」というやつですけど。
悪い意味で使われることが多いですが、手を抜けるところではしっかり手を抜くというのがプログラミングでは大切だと思います。