実行中の画面
迷路ファイルの読み込み、画面表示など、 実際に解く部分以外をまとめたものです。 レベル4 (壁伝いでは抜けられない迷路の最短経路探索) までに対応しています。 迷路のサンプルも付いています。 なお、UNIX＋X11用のプログラムで、libsxが必要です。 Cygwinでもコンパイルできます。
Maze.tar.gzをダウンロードして、解凍してください。 GNU tarとgzipがあれば、
tar xvzf Maze.tar.gz
で解凍できます。
ファイルはMazeディレクトリ内に展開されます。
Mazeディレクトリに移動して (cd Mazeを実行して)、
makeでコンパイルします。
以下のファイルが含まれています。
利用可能な定数, 変数, 関数は、
ヘッダファイルmaze.hに書かれています。
| 名前 | 値 | 説明 |
|---|---|---|
UNKNOWN |
-4 | 不明 |
GOAL |
-3 | ゴール |
START |
-2 | スタート |
WALL |
-1 | 壁 |
ROUTE |
0 | 通路 |
| 名前 | 値 | 説明 |
|---|---|---|
DIR_UP |
0 | 上 |
DIR_RIGHT |
1 | 右 |
DIR_DOWN |
2 | 下 |
DIR_LEFT |
3 | 左 |
| 名前 | 値 | 説明 |
|---|---|---|
STAT_STEP1 |
1 | Step 1: 地図作成 |
STAT_SEARCH |
2 | Search: 最短経路探索 |
STAT_STEP2 |
3 | Step2: 最短経路を進む |
STAT_DONE |
4 | おしまい |
| 名前 | 値 | 説明 |
|---|---|---|
GO_LEFT |
-2 | 左に進む |
TURN_LEFT |
-1 | 左を向く (進まない) |
GO_FORWARD |
0 | 前に進む |
TURN_RIGHT |
+1 | 右を向く (進まない) |
GO_RIGHT |
+2 | 右へ進む |
GO_BACK |
-3 | 戻る (後ろを向いて、一歩進む) |
DONE |
-100 | おしまい |
| 名前 | 値 | 説明 |
|---|---|---|
VIEWSIZE |
300 | 3次元表示のサイズ |
MAPSIZE |
300 | 地図表示のサイズ |
TIMEOUT |
500 | AUTOの処理間隔 (msec) |
構造体ViewInfo型の変数Viewがあり、
自分の周辺がどのような状態であるのかを示しています。
ViewInfo構造体には下記のメンバがあります。
ViewInfo| メンバ | 型 | 説明 |
|---|---|---|
left |
int | 左側の状態 |
front |
int | 前方の状態 |
right |
int | 右側の状態 |
back |
int | 後方の状態 |
current |
int | 現在位置の状態 |
dir |
int | 向いている方向 |
x |
int | 現在のx座標 |
y |
int | 現在のy座標 |
その他に利用できる変数には、下記があります。
| 変数名 | 型 | 説明 |
|---|---|---|
HSize |
int | 迷路のサイズ (横方向) |
VSize |
int | 迷路のサイズ (縦方向) |
StartX |
int | スタート位置のx座標 |
StartY |
int | スタート位置のy座標 |
Info |
ViewInfo | 現在位置周辺の情報 |
DirX[] |
int | 方向DIR_*に動く時の、x座標の変化分 |
DirY[] |
int | 方向DIR_*に動く時の、y座標の変化分 |
以下の関数が使用できる。
関数はmazelib.cに書いてある。
void Show(int **Maze);Mazeが示す地図をテキスト端末に表示する
(グラフィック表示ではない)。
void GetViewInfo(ViewInfo *info, int **Maze,
int PosX, int PosY, int Dir);PosX, PosY) で、
方向Dirを向いた際に、
迷路Mazeにおける現在位置周辺の情報を
infoに格納する。
void SetViewInfo(ViewInfo *info, int **Maze);infoの情報を地図Mazeに格納する。
int GetNextViewInfo(ViewInfo *info, int **Maze, int next);Mazeにおいて、
現在の位置および進行方向がinfoである際に、
nextの行動をした結果をinfoに格納する。
成功すれば0を返す。
なお、壁に突入しようとした場合には-1を返し、
infoは変更しない。
ファイルmaze1.c
void Init();Mapにメモリを割り当てるプログラムが書いてある。
初期化する必要がない場合には、元のままにしておけば良い。
int Step1FindNext();Viewで示される
現在位置およびその周辺 (前後左右) の状況等を元に、
次の行動を決定し、その値を返す。
次の一歩のみを考える。
この関数は、DONEを返すまでは、
何度でも繰り返し呼び出される。void SearchPath();Step1FindNext()で作成した地図を元に、
最短経路を求める。
int Step2FindNext();Step1FindNext()と同様であるが、
最短経路を通るための行動を返す。
hsizeで横方向のサイズを指定
vsizeで縦方向のサイズを指定
beginとendの間に迷路を書く
#」が壁、
「 」が通路、
「S」がスタート、
「G」がゴール
hsize 10
vsize 10
begin
##########
#S # # #
# # # ##
# # # #
# ###### #
# # #
### # ####
# # #
#G# # ## #
##########
end
main()はファイルmazelib.cにあります。
自分でmaze1.cに追加してはいけません。
2003年5月16日〜6月13日のMaze.tar.gzには、 GetNextViewInfo()関数にバグがあります。 訂正版を置いておきます。
(作成: 2003年4月17日, 最終更新: 2003年6月20日)