迷路の経路探索ラストです。
スタートからゴールまでプレイヤーを動かすようにしてみます。
10.スタートからゴールまでの経路を辿る
関数名 Process 戻り値 なし 引 数 迷路、結果 機 能 スタートからゴールまでの経路を辿る |
void Process(const int maze[ROW][COL], const int result[ROW][COL])
{
int x = START_X;
int y = START_Y;
int goalStep = result[GOAL_Y][GOAL_X];
int nowStep = 1;
while (nowStep != goalStep) {
if (result[y - 1][x] == nowStep + 1) {
y--;
}
else {
if (result[y][x + 1] == nowStep + 1) {
x++;
}
else {
if (result[y + 1][x] == nowStep + 1) {
y++;
}
else {
x--;
}
}
}
nowStep++;
}
}
|
経路は１つしかありませんので、スタートから周りを調べ歩数から１多いマスを調べながら移動します。
SetResult関数の逆を考えれば良いですね。
しかし、これでは画面に何も表示されませんので移動しているかどうか分かりません。
表示のために、迷路配列を引数で受け取っていますが使っていませんね。
表示のプログラムを書く必要がありますが、これは関数に分けましょう。
11.移動途中の画面を表示する
関数名 ShowProcess 戻り値 なし 引 数 迷路、Ｘ座標、Ｙ座標 機 能 迷路を表示する（プレイヤーがいるところはプレイヤーを表示する） |
void ShowProcess(const int maze[ROW][COL], const int x, const int y)
{
const char PLAYER[3] = "Ｐ";
const char GRAPHIC[MAP_KIND][3] = { "□", "Ｓ", "Ｇ", "■" };
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
if (i == y && j == x) {
printf(PLAYER);
}
else {
printf("%s", GRAPHIC[maze[i][j]]);
}
}
printf("\n");
}
printf("\n");
getchar();
}
|
最後のところに
getchar();
が入っていますから、エンターキーを押すことで次に進みます。
これを先ほどのProcess関数から呼び出します。
void Process(const int maze[ROW][COL], const int result[ROW][COL])
{
int x = START_X;
int y = START_Y;
int goalStep = result[GOAL_Y][GOAL_X];
int nowStep = 1;
while (nowStep != goalStep) {
ShowProcess(maze, x, y);
if (result[y - 1][x] == nowStep + 1) {
y--;
}
else {
if (result[y][x + 1] == nowStep + 1) {
x++;
}
else {
if (result[y + 1][x] == nowStep + 1) {
y++;
}
else {
x--;
}
}
}
nowStep++;
}
ShowProcess(maze, x, y);
}
|
最後の行でも呼び出さないと、ゴールしたところが見れません。
では、プログラム全体を書いておきます。
<sample program 158-01>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ROW 11
#define COL 11
#define MAP_KIND 4
#define DIRECTION 4
#define START_X 1
#define START_Y 1
#define GOAL_X (COL - 2)
#define GOAL_Y (ROW - 2)
#define NONE -1
enum {
UP,
RIGHT,
DOWN,
LEFT,
};
enum {
FLOOR,
START,
GOAL,
WALL,
};
void InitializeMaze(int maze[ROW][COL]);
void ShowMaze(const int maze[ROW][COL]);
void GenerateMaze(int maze[ROW][COL]);
void ClearPath(int path[ROW][COL]);
void ShowPath(const int path[ROW][COL]);
void CheckPath(const int maze[ROW][COL], int path[ROW][COL], const int x, const int y, const int count);
void ClearResult(int result[ROW][COL]);
void SetResult(const int path[ROW][COL], int result[ROW][COL]);
void ShowResult(const int result[ROW][COL]);
void Process(const int maze[ROW][COL], const int result[ROW][COL]);
void ShowProcess(const int maze[ROW][COL], const int x, const int y);
int main(void)
{
int maze[ROW][COL];
int path[ROW][COL];
int result[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
ClearPath(path);
CheckPath(maze, path, START_X, START_Y, 1);
ShowPath(path);
ClearResult(result);
SetResult(path, result);
ShowResult(result);
Process(maze, result);
return 0;
}
void InitializeMaze(int maze[ROW][COL])
{
int i;
int j;
for (i = 1; i < ROW - 1; i++) {
for (j = 1; j < COL - 1; j++) {
maze[i][j] = FLOOR;
}
}
for (i = 0; i < ROW; i++) {
maze[i][0] = WALL;
maze[i][COL - 1] = WALL;
}
for (j = 1; j < COL - 1; j++) {
maze[0][j] = WALL;
maze[ROW - 1][j] = WALL;
}
for (i = 2; i < ROW - 2; i += 2) {
for (j = 2; j < COL - 2; j += 2) {
maze[i][j] = WALL;
}
}
maze[START_Y][START_X] = START;
maze[GOAL_Y][GOAL_X] = GOAL;
}
void ShowMaze(const int maze[ROW][COL])
{
const char GRAPHIC[MAP_KIND][3] = { "□", "Ｓ", "Ｇ", "■" };
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
printf("%s", GRAPHIC[maze[i][j]]);
}
printf("\n");
}
printf("\n");
}
void GenerateMaze(int maze[ROW][COL])
{
int i;
int j;
for (i = 2; i < ROW - 2; i += 2) {
for (j = 2; j < COL - 2; j += 2) {
switch (rand() % DIRECTION) {
case UP:
maze[i - 1][j] = WALL;
break;
case RIGHT:
maze[i][j + 1] = WALL;
break;
case DOWN:
maze[i + 1][j] = WALL;
break;
case LEFT:
maze[i][j - 1] = WALL;
break;
}
}
}
}
void ClearPath(int path[ROW][COL])
{
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
path[i][j] = NONE;
}
}
}
void ShowPath(const int path[ROW][COL])
{
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
printf("%3d", path[i][j]);
}
printf("\n");
}
printf("\n");
}
void CheckPath(const int maze[ROW][COL], int path[ROW][COL], const int x, const int y, const int count)
{
if (path[y][x] != NONE && path[y][x] < count) {
return;
}
path[y][x] = count;
if (maze[y][x] == GOAL) {
return;
}
if (maze[y - 1][x] != WALL) {
CheckPath(maze, path, x, y - 1, count + 1);
}
if (maze[y][x + 1] != WALL) {
CheckPath(maze, path, x + 1, y, count + 1);
}
if (maze[y + 1][x] != WALL) {
CheckPath(maze, path, x, y + 1, count + 1);
}
if (maze[y][x - 1] != WALL) {
CheckPath(maze, path, x - 1, y, count + 1);
}
}
void ClearResult(int result[ROW][COL])
{
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
result[i][j] = NONE;
}
}
}
void SetResult(const int path[ROW][COL], int result[ROW][COL])
{
int x = GOAL_X;
int y = GOAL_Y;
int nowStep = path[y][x];
while (path[y][x] != 1) {
result[y][x] = nowStep;
if (path[y - 1][x] == nowStep - 1) {
y--;
}
else {
if (path[y][x + 1] == nowStep - 1) {
x++;
}
else {
if (path[y + 1][x] == nowStep - 1) {
y++;
}
else {
x--;
}
}
}
nowStep--;
}
result[y][x] = 1;
}
void ShowResult(const int result[ROW][COL])
{
const char WALL[3] = "■";
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
if (result[i][j] == NONE) {
printf(WALL);
}
else {
printf("%2d", result[i][j]);
}
}
printf("\n");
}
printf("\n");
}
void Process(const int maze[ROW][COL], const int result[ROW][COL])
{
int x = START_X;
int y = START_Y;
int goalStep = result[GOAL_Y][GOAL_X];
int nowStep = 1;
while (nowStep != goalStep) {
ShowProcess(maze, x, y);
if (result[y - 1][x] == nowStep + 1) {
y--;
}
else {
if (result[y][x + 1] == nowStep + 1) {
x++;
}
else {
if (result[y + 1][x] == nowStep + 1) {
y++;
}
else {
x--;
}
}
}
nowStep++;
}
ShowProcess(maze, x, y);
}
void ShowProcess(const int maze[ROW][COL], const int x, const int y)
{
const char PLAYER[3] = "Ｐ";
const char GRAPHIC[MAP_KIND][3] = { "□", "Ｓ", "Ｇ", "■" };
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
if (i == y && j == x) {
printf(PLAYER);
}
else {
printf("%s", GRAPHIC[maze[i][j]]);
}
}
printf("\n");
}
printf("\n");
getchar();
}
|
<実行結果>
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 -1 9 10 11 -1 13 -1 -1 -1 -1 4 -1 8 -1 -1 -1 12 -1 -1 7 6 5 6 7 8 9 10 11 -1 -1 8 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 7 8 9 10 11 -1 21 -1 -1 10 -1 8 -1 -1 -1 -1 -1 20 -1 -1 11 -1 9 -1 15 16 17 18 19 -1 -1 -1 -1 10 -1 14 -1 18 -1 20 -1 -1 13 12 11 12 13 -1 19 -1 21 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ■■■■■■■■■■■ ■ 1 2 3■■■■■■■ ■■■ 4■■■■■■■ ■■■ 5■■■■■■■ ■■■ 6■■■■■■■ ■■■ 7■■■■■■■ ■■■ 8■■■■■■■ ■■■ 9■1516171819■ ■■■10■14■■■20■ ■■■111213■■■21■ ■■■■■■■■■■■ ■■■■■■■■■■■ ■Ｐ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ ■■■■■■■■■■■ ■ＳＰ□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ ■■■■■■■■■■■ ■Ｓ□Ｐ■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ ・ ・ 途中省略 ・ ・ ■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□Ｐ■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ ■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■Ｐ■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ ■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｐ■ ■■■■■■■■■■■ 続行するには何かキーを押してください・・・
これで再帰呼び出しの章は終了です。
ゲームを題材にしましたが、色々なプログラムで応用されている考え方ですから、調べたり試したりしてみてください。