迷路探索プログラムを作るにはどうしたらいいですか？？＞＜；

質問

Borland C++っていうので、プログラムを書いて、４*4マスの小さい迷路で走らせるんですが、C言語がまったくわからないので困っています。
Borlandでプログラムを作って、コマンドプロンプトを使ってネットにあった迷路のソフトを使って走らせるんですが、パソコン自体使い慣れていないのでどうしたらいいのかわかりません。左手拡張法と求心法とトレモー法のどれかを作って、掲載してもらえないでしょうか？非常に困っているのでお願いします。

回答No.3

Interest · ベストアンサー

ANo.2=Interestです。
コードを見てピンと来ました。それ持ってます。谷口さんという方が書かれたマイクロマウスシミュレータ（シェアウエア）ですよね。私もそのシミュレータを使ってマイクロマウスの迷路探索アルゴリズムの動作検証をしています。

昨年そのシミュレータで、左手法、拡張左手法、ポテンシャル法の３通りのアルゴリズムを実装して、３通りとも正しく動作することを確認しました。ソースコードの量がここで紹介するにはちょっと多すぎるので、考え方を示すためにソースコードの一部だけ紹介します。

// ----------------------------------------------------------------------------
// << private >>
//　関数 simpleLeftHandMethod
//　概要 単純な左手法で迷路解くためのマウスの動作を作る。
//
//　引数 *this ナビゲータのオブジェクト
// *cart 台車オブジェクトへのポインタ
//　戻り値 なし
//
// [ 左手法の簡単な説明 ]
// 左、前、右、後ろの順に優先順位をつけて壁をチェックして移動する。
// ----------------------------------------------------------------------------
void simpleLeftHandMethod(Navigator *this, Cart *cart){

CartCommand command;
CartCommand command2;

//前方、左側、右側は、マウスの進行方向に向かってみた場合

if( FALSE == Cart_getLeftWall() ){ // 左側に壁がなければ左を向く。
command.action = CART_TURN_LEFT;
command.volume = 90;
Cart_setCommand( cart, command );
Navigator_updateDir( this, 90 );
}
else if( FALSE == Cart_getFrontWall() ){ // 前方に壁がなければそのまま。

}
else if( FALSE == Cart_getRightWall() ){ // 右側に壁がなければ右を向く。
command.action = CART_TURN_RIGHT;
command.volume = 90;
Cart_setCommand( cart, command );
Navigator_updateDir( this, -90);
}
else{ // 三方向に(左側,前方,右側)に壁があるのでＵターンする。
command.action = CART_TURN_180;
command.volume = 0;
Cart_setCommand( cart, command );
Navigator_updateDir( this, 180 );
}

// 何はともあれ、前に進む。
command2.action = CART_MOVE_BLOCK;
command2.volume = 1;
Cart_setCommand( cart, command2 );
Navigator_updatePos( this, command2.volume );
}

// ----------------------------------------------------------------------------
// << private >>
//　関数 extendLeftHandMethod
//　概要 拡張左手法で迷路解くためのマウスの動作を作る。
//
//　引数 *this ナビゲータのオブジェクト
// *cart 台車オブジェクトへのポインタ
//　戻り値 なし
//
// [ 拡張左手法の簡単な説明 ]
// 基本的な考え方は単純左手法と同じだが、初めてきた区画の周囲に来たことが
// ある区画がある場合は”仮想壁”を設ける。
//
// ----------------------------------------------------------------------------
void extendLeftHandMethod(Navigator *this, Cart *cart){

uchar x, y;
MouseDir dir;
uchar wallData;

CartCommand command;
CartCommand command2;

x = Navigator_getPosX(this);
y = Navigator_getPosY(this);
dir = Navigator_getDir(this);

wallData = 0;

Navigator_updateVirtualWall( this, cart); // 仮想壁を記録する。

// 以降の処理は仮想壁を利用して単純左手法と同じアルゴリズムでよい。
wallData = Map_getVirtualWall(this->map, x, y);

// 左側に壁がなければ左を向く。
if( ((NORTH == dir) && !(WEST_WALL_MASK & wallData)) ||
((EAST == dir) && !(NORTH_WALL_MASK & wallData)) ||
((SOUTH == dir) && !(EAST_WALL_MASK & wallData)) ||
((WEST == dir) && !(SOUTH_WALL_MASK & wallData)) ){

command.action = CART_TURN_LEFT;
command.volume = 90;
Cart_setCommand( cart, command );
Navigator_updateDir( this, 90 );
}
else if( // 前方に壁がなければそのまま。
((NORTH == dir) && !(NORTH_WALL_MASK & wallData)) ||
((EAST == dir) && !(EAST_WALL_MASK & wallData)) ||
((SOUTH == dir) && !(SOUTH_WALL_MASK & wallData)) ||
((WEST == dir) && !(WEST_WALL_MASK & wallData)) ){

}
else if( // 右側に壁がなければ右を向く。
((NORTH == dir) && !(EAST_WALL_MASK & wallData)) ||
((EAST == dir) && !(SOUTH_WALL_MASK & wallData)) ||
((SOUTH == dir) && !(WEST_WALL_MASK & wallData)) ||
((WEST == dir) && !(NORTH_WALL_MASK & wallData)) ){

command.action = CART_TURN_RIGHT;
command.volume = 90;
Cart_setCommand( cart, command );
Navigator_updateDir( this, -90);
}
else{ // 三方向に(左側,前方,右側)に壁があるのでＵターンする。
command.action = CART_TURN_180;
command.volume = 0;
Cart_setCommand( cart, command );
Navigator_updateDir( this, 180 );
}

// 何はともあれ、前に進む。
command2.action = CART_MOVE_BLOCK;
command2.volume = 1;
Cart_setCommand( cart, command2 );
Navigator_updatePos( this, command2.volume );

}

設計はオブジェクト指向ですが、実装はCです。
Navigatorの責務
　迷路の壁情報と通過回数を保持・更新します。
　迷路内でのマウスの位置、方向を保持・更新します。
Cartの責務
　前進、ターンなど与えられた走行コマンドを実行します。

補足

お返事がおそくなってすみません（汗）
書いてあるプログラムがなんなのか調べてみました。書いてある意味はわかったのですが、このままコンパイルすると未定義のシンボルNavigatorがエラーとでてうまくいきません。どうしたらいんでしょうか？

回答No.4

Interest

> このままコンパイルすると未定義のシンボルNavigatorがエラーとでてうまくいきません。

そうでしょうね。なにせ、『ソースコードの量がここで紹介するにはちょっと多すぎるので、考え方を示すためにソースコードの一部だけ紹介します。』という前提で公開したコードの一部なのですから。

機械的に数えてみたところ、私がシミュレーション用に書いたソースコードは（コメント文を差し引いた実行可能な）コード行数で1300行程度ありました。ここで公開できる大きさで無いことは分かっていただけると思います。

> どうしたらいんでしょうか？

（単純な）左手法、拡張左手法がどのようなものか、ソースコードから読み取っていただけたことと思います。概念さえ分かってしまえば、それを実装できるかどうかは設計・実装する人の技量にかかってきます。

どうしても実装したコードを見たいということでしたら、（このサイトでは個人が特定できるような情報は載せるなと言うことになっているので）mixiのマイクロマウスコミュニティで相談してもらえれば、こっそりソースコード差し上げます。

・・・と思ったら、今日マイクロマウスコミュニティでそういう質問している方すでにいらっしゃいますね。

補足

親切にしてくださってありがとうございます。
実を言うとmixiのマイクロマウスコミュニティで質問しているのも私です（汗）mixiでソースコードをもらえないでしょうか？
大変迷惑をかけてすみません（汗）

回答No.2

Interest

丸投げっぽい質問の仕方すると、削除されちゃいますよ～

> 左手拡張法と求心法とトレモー法のどれかを作って

こういう言い方をするのは大体マイクロマウス系の人なので
まずはここの過去ログ見てください。
QNo.2633652 経路探索について
　　http://okwave.jp/qa2633652.html

QNo.1553632 迷路を脱出する経路探索プログラムをＣ言語で作成するには？
　　http://okwave.jp/qa1553632.html

> C言語がまったくわからないので困っています。

C言語そのものが分からないと、説明を受けても何のことだか理解できないですよね。教科書読むより作りながら実戦で覚えたほうがはるかに記憶に残りますが・・・

> ネットにあった迷路のソフトを使って走らせるんですが

具体的にどのソフトですか？ URL出せますか？

ちなみに私はマイクロマウス作ってます。

回答No.1

yaemon_2006

#include <stdio.h>

#define Y 20
#define X 16

typedef struct maze{
int map[Y][X];
int maxy, maxx;
int starty, startx;
int goaly, goalx;
} MAZE;

void Direction(MAZE *maze)
{
int y = maze->starty, x = maze->startx;

while(y != maze->goaly || x != maze->goalx){
if(maze->map[y][x + 1] == 2) maze->map[y][x ++] += 1;
else if(maze->map[y + 1][x] == 2) maze->map[y ++][x] += 2;
else if(maze->map[y][x - 1] == 2) maze->map[y][x --] += 3;
else if(maze->map[y - 1][x] == 2) maze->map[y --][x] += 4;
else break;
}
return;
}

void Print(MAZE *maze)
{
char *marks[] = {"■", " ",}, *arrows[] = {"→", "↓", "←", "↑",};
int y, x, arrow;

if(maze->map[maze->starty][maze->startx] == 2) Direction(maze);
for(y = 0; y < maze->maxy; y ++){
for(x = 0; x < maze->maxx; x ++){
if(maze->map[y][x] == -1) maze->map[y][x] = 1;
if((y == maze->starty && x == maze->startx) ||
(y == maze->goaly && x == maze->goalx)){
arrow = 2 * (y == maze->goaly);
if(y == 0) arrow += 1;
else if(x == maze->maxx - 1) arrow += 2;
else if(y == maze->maxy - 1) arrow += 3;
printf("%s", arrows[arrow & 3]);
}
else if(maze->map[y][x] > 2) printf("%s", arrows[maze->map[y][x] - 3]);
else printf("%s", marks[maze->map[y][x]]);
}
putchar('\n');
}
return;
}

void Route(MAZE *maze)
{
int y = maze->starty, x = maze->startx;

while(!(y == maze->goaly && x == maze->goalx)){
if(maze->map[y][x + 1] == 1 && x + 1 < maze->maxx) maze->map[y][x ++] = 2;
else if(maze->map[y + 1][x] == 1 && y + 1 < maze->maxy) maze->map[y ++][x] = 2;
else if(maze->map[y][x - 1] == 1 && x - 1 >= 0) maze->map[y][x --] = 2;
else if(maze->map[y - 1][x] == 1 && y - 1 >= 0) maze->map[y --][x] = 2;
else if(maze->map[y][x + 1] == 2 && x + 1 < maze->maxx) maze->map[y][x ++] = -1;
else if(maze->map[y + 1][x] == 2 && y + 1 < maze->maxy) maze->map[y ++][x] = -1;
else if(maze->map[y][x - 1] == 2 && x - 1 >= 0) maze->map[y][x --] = -1;
else if(maze->map[y - 1][x] == 2 && y - 1 >= 0) maze->map[y --][x] = -1;
else return;
}
maze->map[y][x] = 2;
return;
}

int main(void)
{
MAZE maze = {{
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,},
{0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,},
{0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0,},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0,},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0,},
{0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,},
{0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0,},
{0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,},
{0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0,},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0,},
{0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0,},
{0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0,},
{0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0,},
{0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,},},
Y, X, 0, 1, Y - 1, X - 2,};

Print(&maze);
putchar('\n');
Route(&maze);
Print(&maze);
return 0;
}

補足

実際にコンパイルしてみて実行してみましたが、動作しませんでした（；＿；）自分でもかなり考えてはいるんですが、よくわかりません・・・。一応、サンプルの一部みたいなのがあったんですが・・・。この意味もよくわからなくて（汗）
#include <conio.h>
#include <stdio.h>
#include "mms.h"

void main()
{
if(SimInit()==0) { //マイクロマウスシミュレーターを初期化する
puts("先にマイクロマウスシミュレーターを実行してください。\n");
puts("-----------------何かキーを押してください。\n");
while(kbhit()==0) //何かキーが押されたら終了
;
return; //終了
}
puts("Enterを押すとスタートします。\n");
while(getch()!=Enter)
;
puts("--------------------------------------------------------");
puts("途中で止まってしまったり、同じところをループしている場合");
puts("何かキーを押すと終了します。\n");

MouseInit(); //マウスを初期化する(マウスをスタート位置に戻す)

while(kbhit()==0) { //何かキーが押されたら終了

//前方、左側、右側は、マウスの進行方向に向かってみた場合

if(InputLW()==0) //左側に壁がなければ
TurnLeft(90); //左90度回転
else if(InputFW()==0) //前方に壁がなければ
; //そのまま
else if(InputRW()==0) //右側に壁がなければ
TurnRight(90); //右90度回転
else
Turn180(); //三方向に(左側,前方,右側)に壁が
//あるので、Uターンする

MoveBlock(1); //1ブロック進む

if(InputGL()==1) { //ゴールエリアに到達したら
puts("ゴール！\n");
puts("何かキーを押してください。\n");
while(kbhit()==0) //何かキーが押されるのを待つ
;
break; //迷路探索終了
}
}
MouseInit(); //マウスを初期化する(マウスをスタート位置に戻す)
}

どうすればいいでしょうか？