無題

[つつ]

cで迷路を解こうとしているのですがうまくいっていません。

何かいい探索プログラムはありませんか？
とりあえず今のソースをのっけます。

#include "maze.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAZE_X (40)
#define MAZE_Y (40)

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

static int mazeHeight = 0; // 迷路のサイズ
static int mazeWidth = 0;
static int x, y;
static int search[MAZE_X][MAZE_Y];
static CurrentState pos = { 0, 0, DirDown, MapStart }; // 現在位置

static int a = 0; //経路探索状況

// プレーヤー情報を持つ構造体
// "蒲田"の部分のみ、変更すること
static PlayerInfo player = { "YON" , initMaze, findNext, getCurrent };

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

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

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

// 次に進む場所を計算する関数
// 次に進む場所を返すようになっていれば、変更可
static CurrentState findNext ( CurrentState pos )
{
CurrentState next = pos;
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;
} else {
// 上
pos.status = pos.status;
if (search[x][y-1]== MapWall)
{
pos.dir -= DirUp;
pos.status = MapAisle;
} else {
if (search[x][y-1]== MapAisle) {
pos.dir += DirDown;
}
}
// 下
if (search[x][y+1]== MapWall)
{
pos.dir += DirDown;
pos.status = MapAisle;
} else {
if (search[x][y+1]== MapAisle) {
pos.dir -= DirUp;
}
}

// 左
if (search[x-1][y]== MapWall)
{
pos.dir -= DirLeft;
pos.status = MapAisle;
} else {
if (search[x-1][y]== MapAisle) {
pos.dir += DirRight;
}
}
// 右
if (search[x+1][y]== MapWall)
{
pos.dir += DirRight;
pos.status = MapAisle;
} else {
if (search[x+1][y]== MapAisle) {
pos.dir -= DirLeft;
}
}
}
return pos;
}

[softya]

まず、どううまく行かないのかと意図しているアルゴリズムを箇条書きで書いてもらえますか。

[つつ]

すいませんうっかり忘れていました。


状態
・壁にぶつかったとしても方向を変えない状態です。
・壁を突き破ってしまいます。

意図
・最短経路の探索
・壁にぶつからなくても方向を変更したい。

こんな感じです。
*.hファイルです。
// マップ情報
#define MazeStart 'S' // スタート地点
#define MazeGoal 'G' // ゴール
#define MazeAisle ' ' // 通路

// 自分の進行方向
#define DirUp (0) // 上
#define DirDown (1) // 下
#define DirLeft (2) // 左
#define DirRight (3) // 右
#define DirMax (4) // 方向の種類数

// mapの状況
typedef enum { MapWall = 0, MapStart = 1, MapAisle = 2, MapGoal = 3 } MapStatus;

// 現在位置と方向
typedef struct {
int x; // 位置
int y;
int dir; // 進行方向
MapStatus status; // 現在地の状況
} CurrentState;

typedef struct {
char* name;
void ( *init ) ( int, int, CurrentState );
CurrentState ( *find ) ( CurrentState );
CurrentState ( *getCurrent ) ( void );
} PlayerInfo;

MapStatus canPassThrough ( CurrentState );

[つつ]

すいません意図の部分に追加です

意図
・一度通った場所を記憶して二度通らなくしたいです。

[つつ]

地図はこんなのを使用しています。

"+-----+---+------+---------+----+------+",
"S*****|***|******|*********|****|******|",
"+-+*******|***|******------+****+-----*|",
"G*|***|*******|**|*********************|",
"|*+---+---+---+**+---+---------------*-+",
"|*********|**********|*****************|",
"|*+*+*+*+*|**********|*-*-*-*-*-*-*-*-*|",
"|*********|**********|*****************|",
"|*+*+*+*+*+----------+------+------+-*-+",
"|***************************|******|***|",
"+---+---+-----------------+***+--+*|***|",
"|***|***|*****************|-+-*****+-+*|",
"|*|***|****+*+*+*+*+*+*+*+|*|**|*****|*|",
"|*|*|***|*****************|***-+*--+-+*|",
"+-+*|*|*|*|*|*|*|*|*|*|*|*|*|**|***|***|",
"|***|***+-+-+-+-+*+-+-+-+-+*+-*|*+*|***|",
"|***|*|*|*****|*****|*****|*|**|***|***|",
"|***|***|*-+-*|*-+-*|*-+-*+***-+---+-*-+",
"|***|*|*|**|**|**|**|**|**|*|**|***|***|",
"+-+*|***|**|*-+-*|*-+-*|**|*+-*|***|***|",
"|*|*|*|*|**|**|**|**|**|**|*|**|***|***|",
"|*|*|***|*-+-*|*-+-*|*-+-*|***-+***+--*|",
"|*|*+---+**|**|**|**|**|**|*|**|*******|",
"|***|***|**|*-+-*|*-+-*|**|*+-*|*******|",
"|***|***|**|**|**|**|**|**|*|**|***+-*-+",
"+-*-+***|*-+-*|*-+-*|*-+-*|***-+***|***|",
"|*******|**|**|**|**|**|**|*|**|***|***|",
"|*******|**|*-+-*|*-+-*|**|*+-*+---+*|*|",
"|*--+***|**|*****|*****|**|*|**|***|*|*|",
"|***|***+--+-----+-----+--+***-+*|*|*|*|",
"|***|***|*****************|*|**|***|*+-+",
"+-*-+---+---+----+----+-*-+-+-*|*|*|***|",
"|***********|*********|*****|**|***|***|",
"|*-*-*-*-*-*|*********|***|*|**|*|*|***|",
"|***********|*********|***|****|***|***|",
"+-*---------+--+**+---+---+*+--+*|*|*+-+",
"|**************|**|***|***|*|**|***|*|*|",
"|*--+****+---*****|*******+-+****|***|*|",
"|***|****|*****|******|********|***|***|",
"+---+----+-----+------+--------+---+---+"

「*」を空白に置き換えていただければ使用できます。

[softya]

これは、アルゴリズムの箇条書きじゃないですね。
日本語で、文章だけでアルゴリズムを書いてもらえますか。

[つつ]

すいません。

1:移動中に壁があるか探します。
2:探した結果、壁がない方向に進みます。
3:移動中の経路を記憶。
4:ゴールが見つからなかったら、探索経路を消去して再探索を行う。
1～4の繰り返し。
5:ゴールが見つかったら終了。


こんな感じでよろしいでしょうか？

[softya]

main部分が掲載されていないので、全体がどうやって動いているか分からないんでzip添付の形で動くのに必要なものを全てもらえませんか？

あと確認したいことがあります。

>1:移動中に壁があるか探します。
これは歩く１歩前だけを調べていますか？
それと壁が無い限り方向転換しないんでしょうか？

>2:探した結果、壁がない方向に進みます。
方向転換するアルゴリズムは、右回り、左回り、ランダム、それ以外の何れでしょう？

>3:移動中の経路を記憶。
アルゴリズムの記述に出来ていませんが、記憶した経路はどの様に利用されていますか？

>4:ゴールが見つからなかったら、探索経路を消去して再探索を行う。
今まで探索した経路情報は全て消去してしまうのでしょうか？

[つつ]

main部分が掲載されていないので、全体がどうやって動いているか分からないんでzip添付の形で動くのに必要なものを全てもらえませんか？

あと確認したいことがあります。

>1:移動中に壁があるか探します。
歩く一歩前のことです。
壁が有っても方向転換させていただけるとうれしいです。

>2:探した結果、壁がない方向に進みます。
ランダムでお願いします。

>3:移動中の経路を記憶。
記憶した経路を使いプログラム上で迷路を作成します。

>4:ゴールが見つからなかったら、探索経路を消去して再探索を行う。
すべて消してしまって結構です。

[softya]

将来どうしたいかじゃなくて今のアルゴリズムをお聞きしていますので、今のアルゴリズムを教えてください。
[訂正]今Ｃ言語で組み込んでいるつもりのアルゴリズムを書いて下さい。あるいは、組み込んでいないなら未作成と書いて下さい。

>>1:移動中に壁があるか探します。
>歩く一歩前のことです。
>壁が有っても方向転換させていただけるとうれしいです。
今のアルゴリズムは？

>>2:探した結果、壁がない方向に進みます。
>ランダムでお願いします。
今はどうしていますか？

>>3:移動中の経路を記憶。
>記憶した経路を使いプログラム上で迷路を作成します。
今のアルゴリズムと、この意味が分からないので説明してもらえますか？
プログラム上で迷路を作成してどうするのですか？経路情報を表示する？それとも別の意味？
元の迷路はmapファイル上にあるんですよね？

>>4:ゴールが見つからなかったら、探索経路を消去して再探索を行う。
>すべて消してしまって結構です。
今のアルゴリズムでお願いします。

[つつ]

今わ
1：移動中は必ず1歩前の状態を見ています。(壁か道か)
未作成

2：未作成

3：未作成

4：未作成

すいませんこんな状態で。

[softya]

これについての詳細もお願いします。

>>>3:移動中の経路を記憶。
>>記憶した経路を使いプログラム上で迷路を作成します。
>この意味が分からないので説明してもらえますか？
>プログラム上で迷路を作成してどうするのですか？経路情報を表示する？それとも別の意味？
>元の迷路はmapファイル上にあるんですよね？

意図が分からないんで、お願いします。

[つつ]

>>記憶した経路を使いプログラム上で迷路を作成します。
このことは忘れてください。
・一度通ったとこを通らないようにしてください。

元の迷路はmapファイル上には、あります。

[たいちう]

> 何かいい探索プログラムはありませんか？

プログラム自体はググるなり、ご自分で作成するなりしてもらうとして、
単純なアルゴリズムを書きます。

１．迷路の各マス目に対応する2次元配列を用意する。
２．2次元配列を0で初期化する。
３．スタートのマスに対応する2次元配列の要素に1を代入する。
４．1に隣接している0の要素に2を代入する。
５．2に隣接している0の要素に3を代入する。
．．．
６．nに隣接している0の要素に(n+1)を代入する。
７．ゴールのマスに数字が入るまで、手順６を繰り返す。
８．ゴールのマスから数字を降順に辿りスタートまでの順路を見つける。

[softya]

ほとんど未完成と考えて良いですね。

では、私は今出来ているものに近いアルゴリズムを提案します。
１．移動済みをマークする２次元配列を用意する。０クリアしておく。
２．移動分岐点をマークするスタックを用意する。
３．スタート地点をマークする。
４．今の位置から移動出来る方向を調べる。壁と移動済みの場所には移動出来ない。
５．移動先にゴールがあればゴールに移動して終了。
６．どこにも移動出来ない場合は、スタックから移動分岐点を取り出して４へ。
７．移動出来る方向が複数あったら、スタックに移動分岐点を記録する。
８．複数の移動方向の中の内からランダムで移動方向を決定する。１つしか無いならその方向を選択。
９．その方向に移動して移動済みをマークする。４へ戻る。

[つつ]

わざわざありがとうございます。

参考に打ってみます。

[つつ]

ありがとうございました