迷路探索プログラム、こうNatter

せんちゃ · 投稿記事 by **せんちゃ** » 14年前

CODE:

#include	"maze.h"
#pragma warning( disable : 4996 )


static	CurrentState	getCurrent	( void );
static	void			initMaze	( int, int, CurrentState );
static	CurrentState	findNext	( CurrentState ); 

static	int				mazeHeight = 0;							  // 迷路のサイズ
static	int				mazeWidth  = 0;
static	CurrentState	pos		   = { 0, 0, DirDown, MapStart }; // 現在位置

//	プレーヤー情報を持つ構造体
static	PlayerInfo		player = { "Sencha" , initMaze, findNext, getCurrent };

//	プレーヤーの情報を返す関数
//		"Sencha"の部分以外、変更しないこと
PlayerInfo*		getSenchaInfo	( void )
{
	return	&player;
}

//	現在位置の情報を返す関数
//		変更しないこと
static	CurrentState	getCurrent	( void )
{
		return pos;
}

//■□■□■□■□■□■□■□■□■□■□■□
//↓↓↓　ココから！             　　↓↓↓
//■□■□■□■□■□■□■□■□■□■□■□

//============//
//ドキュメント//
//========================================================================
//～変数宣言ルール～
//グローバル変数は頭文字大文字、ローカル変数は全部小文字にします。
//定数は基本的には全部大文字が望ましいが、
//今回はあらかじめ用意されている定数の命名規則に従い、
//頭文字だけ大文字にする
//
//～デバッグ用処理について～
//コメントアウトだとカッコ悪いのでif definedで一つ一つ括っています。
//処理を付け加える場合はこちらの命名規則に従ってください。
//基本的には「__DEBUG_xxxx__」という命名規則でやっています。
//
//～ソースの追加をしたい場合～
//・ソース管理者以外がプログラムを書き換えたい場合、
//まずちゃんとバックアップを取ってからやること
//=========================================================================

//----------------------------------------------------------------------------------------
//簡単にデバッグしたい場所をリンクできるようにデバッグ用のマクロを用意しておきました。
//ビルドをかけたらメッセージが表示されるので、ダブルクリックすれば飛びたい箇所に飛べます
//----------------------------------------------------------------------------------------

#define __STR2__(x) #x
#define __STR1__(x) __STR2__(x)
#define __DBG__ __FILE__ "("__STR1__(__LINE__)") : Debug Message: "
#define __CHP__ __FILE__ "("__STR1__(__LINE__)") : Check Point  : "
#define DEBUG_PROGRAM       __DBG__ 
#define CHECK_POINT         __CHP__


/*--------------------------------*/
//別ファイルの変数はここで処理
/*--------------------------------*/
extern char* dirString[];


/*-------------------*/
//データ構造体
/*-------------------*/
typedef struct{
	int       vx;
	int       vy;
	int next_dir;
	int  ret_dir;
}VtPm_t;


/*-------------------*/
//プリプロセッサ
/*-------------------*/
#define X_Max              ( 128 ) //最大X
#define Y_Max              ( 128 ) //最大Y
#define FirstPos           (  10 ) //一回通った道
#define SecondPos          (  20 ) //二回通った道
#define SearchEnd          (   1 ) //サーチ終了
#define MapDataMax         (   4 ) //マップの種類はMapStart,MapGoal,MapAisle,MapWallの4種類

/*-------------------*/
//グローバル変数
/*-------------------*/
CurrentState                Search; //サーチ用構造体
char Maze[Y_Max][X_Max]      = {0}; //迷図のコピー
char DirInput  [4096]        = {0}; //ゲームに使用する記憶
char BeforeStep[2048]        = {0}; //以前の方向、行き止まって前の道に戻るときに使う
int  State                   =  0 ; //道探索状況、1で終了
int  RecursiveCount          =  0 ; //再帰回数のカウンタ
int  RecursiveCountForBackTo =  0 ; //行き止まって戻るときに、前のステップでどの方向を示しているかを取得するためのカウンタ
int  Ret                     =  0 ; //どれだけ元のポジションに戻るかカウント
int  Once                    =  0 ; //関数RecursiveSearch()を一回だけ読み込むための変数
int  NextDir                 =  0 ; //DirInputの配列番号を指定するポインタ

/*----------------------*/
//上下左右の処理データ
/*----------------------*/
const VtPm_t VtPm[DirMax] = { 
	{  0 , -1 , DirUp    , DirDown  } , //上方向移動
	{  0 , +1 , DirDown  , DirUp    } , //下方向移動
	{ -1 ,  0 , DirLeft  , DirRight } , //左方向移動
	{ +1 ,  0 , DirRight , DirLeft  } , //右方向移動
};

/*----------------------*/
//マップデータ
/*----------------------*/
const int ScanData[MapDataMax] = { 
	MapStart ,
	MapGoal  ,
	MapAisle , 
	MapWall  ,
};


//-------------------------------------------
//迷図のスキャン
//-------------------------------------------
void ScanningMaze( void )
{
	int i;
	CurrentState get; //データ入手用構造体

	//今回の迷図は最大サイズが60*60ですが余分にサイズをとってあります。
	//処理はcanPassThrough()で読み取った地点にある数値を代入しているだけです。
	for( get.y = 0 ; get.y  YES -> [END]   ↑
//　　　↓NO                      ↑
//2.YES -> [再帰呼び出し]
//      ↓NO
//3.[その道を通れなくする]
//      ↓
//4.[前に呼び出した関数の2の地点に戻る]
//      ↓
//5.戻った回数だけretの値とRecursiveCountを演算

//--------------------------------------
//再帰サーチ
//--------------------------------------
void RecursiveSearch( int x , int y )
{
	int i;

#pragma message( DEBUG_PROGRAM "0010" )
#if defined __DEBUG_0010__
	printf( "DirInput = %s pos.x = %d pos.y = %d\nRecursiveCount = %d\n" , dirString[DirInput[RecursiveCount-1]] , x , y , RecursiveCount );
	getch();
#endif

	if( Maze[y][x] == MapGoal ){ 

#pragma message( DEBUG_PROGRAM "0015" )
#if defined __DEBUG_0015__
		printf( "ゴールに到着！ \n( %d , %d )\n" , x , y );
		_sleep( 2000 );
#endif
		State = SearchEnd; //ゴールに着いたら状態を1に
	}
	
	Maze[y][x] = FirstPos;

   //---------------------------------------------------
   //上下左右サーチ、空きがある場合、再帰する
   //---------------------------------------------------
	for( i = 0 ; i < DirMax ; i++ ){
		if( State !=1 ){ 
			if( Maze[y+VtPm[i].vy][x+VtPm[i].vx] == MapAisle ||
				Maze[y+VtPm[i].vy][x+VtPm[i].vx] == MapGoal ){
					DirInput[RecursiveCount]            = VtPm[i].next_dir;
					BeforeStep[RecursiveCountForBackTo] = VtPm[i].next_dir;
					RecursiveCount++;
					RecursiveCountForBackTo++;
					RecursiveSearch( x+VtPm[i].vx , y+VtPm[i].vy );
					//基本的に行き止まりにならなければretの数値は変わらないので
					//RecursiveCount -= retをしても中身は変わらない
					RecursiveCount -= Ret;
					//演算したらretはちゃんとリセットする
					Ret = 0;
			}	
		}
	}

	//------------------------------------------------------------------------------------------------------------------
	//全ての道が既に通った道と壁であった場合、ここで何か処理をしてから前の関数に戻る
	//～考え方～
	//前の関数に戻るということは方向も反対にしてあげなければいけない。
	//なので、関数の呼び出しトータル回数をカウントし、(その回数目のときはどの方向に移動していたかを記憶する)
	//ここの処理に来たときに呼び出し回数を減らしていくようにしてみる。
	//
	//
	//例えば0番目(最初)の関数は( x+1 , y )へ進んだとする、そのとき方向は右に登録され、カウントは1になる。
	//(x+1,y)の関数内で行き止まりを発見したとき、ここの処理へやってくるので、カウントを一回減らす。
	//以前の方向はカウント0に入っているので、カウント0の中身によって次の移動方向を反対方向に変える
	//
	//
	//これで前の関数に戻ると同時に方向もその方向に登録できる(はず)
	//
	//【1月28日16:20@更新】
	//思考ルーチンを若干変更
	//変更点　
	//・変数Ret追加
	//
	//
	//------------------------------------------------------------------------------------------------------------------
	if( State != 1 ){
		Ret++;
		//前に動いていた方向の逆方向に移動
		RecursiveCountForBackTo--; //カウントを戻す

		for( i = 0 ; i < DirMax ; i++ ){
			if( BeforeStep[RecursiveCountForBackTo] == VtPm[i].next_dir ){
				DirInput[RecursiveCount] = VtPm[i].ret_dir; 
			}
		}

		Maze[y][x] = SecondPos; //その道はもう通れないようにする
#pragma message( DEBUG_PROGRAM "0020" )
#if defined __DEBUG_0020__ 
		printf( "ret = %d  : ( %d , %d , DirInput = %s )\n " , ret , x , y , dirString[DirInput[RecursiveCount-1]] );
		getch();
#endif
		//RecursiveCount++;

	}
}

//---------------------------------------
//デバッグ用現在状況描画関数
//---------------------------------------
void Render( int next_dir )
{

#pragma message( DEBUG_PROGRAM "0030" )
#if defined __DEBUG_0030__
	getch();
	printf( "ゴールについた?\nnext = %d\n Count = %d\n"
		"pos_x = %d , pos_y = %d\n , 現在Maze = %d\n"
		"上 = %d , 下 = %d , 左 = %d , 右 = %d\n" 
		"DirInput[next_dir] = %d , DirInput[RecursiveCount] = %d", 
		next_dir , RecursiveCount ,
		pos.x , pos.y , Maze[pos.y][pos.x] , 
		Maze[pos.y-1][pos.x] , Maze[pos.y+1][pos.x] , Maze[pos.y][pos.x-1] , Maze[pos.y][pos.x+1] ,
		DirInput[next_dir] , DirInput[RecursiveCount] );
#endif
}

void SearchStart()
{
	if( Once == 0 ){
		RecursiveSearch( Search.x , Search.y );
		if( State == 1 ){

#pragma message( DEBUG_PROGRAM "0040" )
#if defined __DEBUG_0040__
			printf( "処理終了しました\n"  );
#endif
			NextDir        = 0;
			Once           = 1;
		}
	}
}

//■□■□■□■□■□■□■□■□■□■□■□
//↑↑↑↑↑↑↑↑　ココまで！　↑↑↑↑↑↑↑
//■□■□■□■□■□■□■□■□■□■□■□


//初期化の関数
static	void	initMaze	( int col, int row,					//	迷路のサイズ
							 CurrentState start )				//	スタート位置
{
	//	この下の3行は、変更しないこと。
	//	このほかに必要なものがあれば、追加することは可。
	mazeWidth  = col;
	mazeHeight = row;
	pos     = start;

	//----------------------------------
	//川岸の作った変数の初期化
	//----------------------------------
	memset( Maze       , 0 , Y_Max * X_Max );
	memset( DirInput   , 0 , 4096          );
	memset( BeforeStep , 0 , 2048          );
	State                   =  0 ; 
	RecursiveCount          =  0 ; 
	RecursiveCountForBackTo =  0 ; 
	Ret                     =  0 ; 
	Once                    =  0 ; 
	NextDir                 =  0 ; 

	//----------------------------------
	//探索用構造体の初期化
	//----------------------------------
	Search  = start;
	//----------------------------------
	//迷図のスキャン
	//----------------------------------
	ScanningMaze();

	//----------------------------------
	//迷路のサーチプログラム
	//----------------------------------
	SearchStart();
}


//次に進む場所を計算する関数
//次に進む場所を返すようになっていれば、変更可
static	CurrentState	findNext	( CurrentState	pos )
{
	//----------------------------------
	//次に進むコマの候補を求める 
	//----------------------------------
	CurrentState	next = pos;
	//----------------------------------
	//デバッグ用
	//----------------------------------
	Render( NextDir );
	//----------------------------------
	//次の方向
	//----------------------------------
	next.dir = DirInput[NextDir];

	switch ( next.dir ){
		case DirUp		: next.y--; break;
		case DirDown	: next.y++; break;
		case DirLeft	: next.x--; break;
		case DirRight	: next.x++; break;
	}

	// 次に進もうとしているセルの状態をチェックする
	if ( next.status = canPassThrough ( next ) ){
		pos = next;
	} 
	//----------------------------------
	//次の処理へ
	//----------------------------------
	NextDir++;

	return pos;
}

再帰を使った先読みのプログラムなのでいわゆるオーアアルゴリズムにも似ていますが、
同じ道は二度通らないトレモー法も使ってます。

というか基本的に二度通った道はサーチの段階で候補外となるので省略され、最終的に最短に近い道のりで行けます

作ったときはかなり感動しましたｗ

長所は複雑で入り組んだ迷路ほど力を発揮します。
複雑さが高い迷路ほど通れる候補が絞られるのでその分超早い

短所は面積の広い迷路ほど歩数がかかること。

壁が一切ない場合、全てしらみつぶしに探索するので恐ろしく時間がかかります
(おそらくそんな迷路は出てこないだろうけど…＾＾；)

さぁ、これでもう来週の月曜日も怖くない！

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31