System Note
$ cat /proc/ai-disclosure
本記事の構成および論理分析にはAI（人工知能）を使用しています。情報の正確性は、システム管理者（UNIXユーザー）による手動検証済みです。
【経路探索で遊ぼう】C言語で迷路の最短ルートを探す｜幅優先探索をコードで見る | UNIX Cafe
ゲームや地図アプリでは、「スタートからゴールまで、どう進めばよいか」を探す場面がよく出てきます。
今回は、この 経路探索 を C言語 で遊びながら見ていきます。迷路を数字の配列で表し、上下左右に進める場所を調べ、最後は最短ルートを * で表示します。
使う考え方は 幅優先探索 です。名前は少し難しそうですが、やっていることは「近い場所から順番に調べる」だけです。
最後に、同じ考え方を Python で書くとどう表せるかも補足します。この記事ではC言語を主役にして、Pythonは見比べるための別表現として扱います。
目次
経路探索ってなに？
経路探索は、スタート地点からゴール地点までの道を探す処理です。
たとえば、迷路なら「壁を避けながらゴールへ行けるか」を調べます。さらに一歩進めると、「何歩で着けるか」「一番短い道はどれか」も調べられます。
| 記号 | 意味 |
|---|---|
S | スタート |
G | ゴール |
. | 通れる道 |
# | 通れない壁 |
* | 見つけた最短ルート |
この記事では、斜め移動は使いません。上、下、左、右の4方向だけに進めるルールにします。
基本ルール
迷路をコードで扱いやすくするために、まずは数字の配列として持ちます。
0は通れる道1は通れない壁- 左上を
(0, 0)とする xは右へ進むほど増えるyは下へ進むほど増える
C言語の2次元配列では、maze[y][x] の順番で読むのがポイントです。座標としては (x, y) と言いたくなりますが、配列では先に行番号の y、次に列番号の x を書きます。
その1：迷路を配列で表示する
まずは、数字の配列を迷路らしく表示してみます。
path_maze.c という名前で、次のコードを作ってみます。
#include <stdio.h>
#define HEIGHT 5
#define WIDTH 7
int main(void) {
int maze[HEIGHT][WIDTH] = {
{0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0}
};
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
if (maze[y][x] == 1) {
printf("#");
} else {
printf(".");
}
}
printf("\n");
}
return 0;
}main関数の読み方
maze は迷路そのものです。0 なら道、1 なら壁として扱います。
外側の for 文は y を上から下へ進めます。内側の for 文は x を左から右へ進めます。
maze[y][x] == 1 なら #、それ以外なら . を表示します。1行分を表示し終えたら、最後に printf("\n"); で改行します。
実行してみる
macOSやLinuxのターミナルなら、次のようにコンパイルして実行できます。
gcc -std=c99 path_maze.c -o path_maze
./path_maze実行結果は次のようになります。
...#...
##.#.#.
.....#.
.###.#.
.......数字の配列が、文字の迷路として見えるようになりました。
その2：ゴールに着けるか調べる
次は、スタートからゴールへ着けるかどうかを調べます。
ここで使うのが、幅優先探索です。スタートに近い場所から順番に調べていくので、迷路の探索に向いています。
path_reachable.c という名前で、次のコードを作ってみます。
#include <stdio.h>
#define HEIGHT 5
#define WIDTH 7
#define MAX_QUEUE (HEIGHT * WIDTH)
typedef struct {
int x;
int y;
} Point;
int main(void) {
int maze[HEIGHT][WIDTH] = {
{0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int visited[HEIGHT][WIDTH] = {0};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
Point queue[MAX_QUEUE];
int head = 0;
int tail = 0;
Point start = {0, 0};
Point goal = {6, 4};
queue[tail++] = start;
visited[start.y][start.x] = 1;
while (head < tail) {
Point current = queue[head++];
if (current.x == goal.x && current.y == goal.y) {
printf("goal reached\n");
return 0;
}
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if (nx < 0 || nx >= WIDTH || ny < 0 || ny >= HEIGHT) {
continue;
}
if (maze[ny][nx] == 1 || visited[ny][nx]) {
continue;
}
visited[ny][nx] = 1;
queue[tail++] = (Point){nx, ny};
}
}
printf("goal not reached\n");
return 0;
}キューの読み方
幅優先探索では、これから調べる場所を順番待ちの列に入れていきます。この順番待ちの列を キュー と呼びます。
このコードでは、queue 配列をキューとして使っています。tail は新しく入れる場所、head は次に取り出す場所です。
queue[tail++] = start;でスタート地点をキューに入れますPoint current = queue[head++];で次に調べる場所を取り出しますwhile (head < tail)の間は、まだ調べる場所が残っています
上下左右の調べ方
dx と dy は、上下左右に1マス動くための表です。
i | dx[i] | dy[i] | 動き |
|---|---|---|---|
| 0 | 1 | 0 | 右へ1マス |
| 1 | -1 | 0 | 左へ1マス |
| 2 | 0 | 1 | 下へ1マス |
| 3 | 0 | -1 | 上へ1マス |
nx と ny は、次に試す場所です。配列の外に出る場所、壁の場所、すでに調べた場所は continue で飛ばします。
visited[ny][nx] = 1; は、「この場所はもう調べる予定に入れた」という印です。同じ場所を何度もキューに入れないために使います。
実行してみる
gcc -std=c99 path_reachable.c -o path_reachable
./path_reachable実行結果は次のようになります。
goal reachedこの迷路では、スタートからゴールまでたどり着けることがわかりました。
その3：何歩で着くか調べる
ゴールに着けることがわかったので、次は何歩で着けるかを調べます。
visited の代わりに dist という配列を使います。dist[y][x] には、スタートからその場所までの歩数を入れます。
path_distance.c という名前で、次のコードを作ってみます。
#include <stdio.h>
#define HEIGHT 5
#define WIDTH 7
#define MAX_QUEUE (HEIGHT * WIDTH)
typedef struct {
int x;
int y;
} Point;
int main(void) {
int maze[HEIGHT][WIDTH] = {
{0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int dist[HEIGHT][WIDTH];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
Point queue[MAX_QUEUE];
int head = 0;
int tail = 0;
Point start = {0, 0};
Point goal = {6, 4};
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
dist[y][x] = -1;
}
}
queue[tail++] = start;
dist[start.y][start.x] = 0;
while (head < tail) {
Point current = queue[head++];
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if (nx < 0 || nx >= WIDTH || ny < 0 || ny >= HEIGHT) {
continue;
}
if (maze[ny][nx] == 1 || dist[ny][nx] != -1) {
continue;
}
dist[ny][nx] = dist[current.y][current.x] + 1;
queue[tail++] = (Point){nx, ny};
}
}
printf("shortest distance = %d\n", dist[goal.y][goal.x]);
return 0;
}dist配列の読み方
dist は、各マスまでの距離を覚える配列です。最初はすべて -1 にしておきます。
ここでの -1 は、「まだ行き方がわからない」という印です。スタート地点だけは、スタートから0歩なので dist[start.y][start.x] = 0; にします。
新しい場所へ進めるときは、いまの場所の距離に1を足します。
dist[ny][nx] = dist[current.y][current.x] + 1;幅優先探索は近い場所から順番に調べるため、最初に入った距離がその場所への最短距離になります。
実行してみる
gcc -std=c99 path_distance.c -o path_distance
./path_distance実行結果は次のようになります。
shortest distance = 10この迷路では、スタートからゴールまで最短で10歩です。
その4：最短ルートを表示する
最後に、最短ルートそのものを表示します。
ゴールからスタートへ向かって、距離が1ずつ小さくなるマスをたどります。ゴールの距離が10なら、次は9、次は8、というように戻っていきます。
path_route.c という名前で、次のコードを作ってみます。
#include <stdio.h>
#define HEIGHT 5
#define WIDTH 7
#define MAX_QUEUE (HEIGHT * WIDTH)
typedef struct {
int x;
int y;
} Point;
int main(void) {
int maze[HEIGHT][WIDTH] = {
{0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int dist[HEIGHT][WIDTH];
char screen[HEIGHT][WIDTH];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
Point queue[MAX_QUEUE];
int head = 0;
int tail = 0;
Point start = {0, 0};
Point goal = {6, 4};
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
dist[y][x] = -1;
screen[y][x] = (maze[y][x] == 1) ? '#' : '.';
}
}
queue[tail++] = start;
dist[start.y][start.x] = 0;
while (head < tail) {
Point current = queue[head++];
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if (nx < 0 || nx >= WIDTH || ny < 0 || ny >= HEIGHT) {
continue;
}
if (maze[ny][nx] == 1 || dist[ny][nx] != -1) {
continue;
}
dist[ny][nx] = dist[current.y][current.x] + 1;
queue[tail++] = (Point){nx, ny};
}
}
if (dist[goal.y][goal.x] == -1) {
printf("goal not reached\n");
return 0;
}
Point current = goal;
while (!(current.x == start.x && current.y == start.y)) {
screen[current.y][current.x] = '*';
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if (nx < 0 || nx >= WIDTH || ny < 0 || ny >= HEIGHT) {
continue;
}
if (dist[ny][nx] == dist[current.y][current.x] - 1) {
current = (Point){nx, ny};
break;
}
}
}
screen[start.y][start.x] = 'S';
screen[goal.y][goal.x] = 'G';
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
printf("%c", screen[y][x]);
}
printf("\n");
}
printf("shortest distance = %d\n", dist[goal.y][goal.x]);
return 0;
}ルート復元の読み方
前半は、その3と同じように dist を作っています。違うのは、後半でゴールからスタートへ戻っているところです。
current をゴール地点から始めます。そして、上下左右の中から dist が1小さい場所を探します。
if (dist[ny][nx] == dist[current.y][current.x] - 1) {
current = (Point){nx, ny};
break;
}この条件に合う場所は、スタートへ1歩近づく場所です。そこへ current を移動しながら、通ったマスを * に変えていきます。
screen は表示用の配列です。元の maze を直接書き換えず、表示用に .、#、*、S、G を入れています。
実行してみる
gcc -std=c99 path_route.c -o path_route
./path_route実行結果は次のようになります。
S**#...
##*#.#.
..***#.
.###*#.
....**G
shortest distance = 10S から G まで、* をたどれば最短ルートになります。
幅優先探索の考え方
幅優先探索は、近い場所から順番に調べる探索方法です。
今回の迷路では、スタートから1歩で行ける場所、2歩で行ける場所、3歩で行ける場所、という順番で広がっていきます。
| 配列・変数 | 役割 |
|---|---|
maze | 道と壁を覚える |
queue | これから調べる場所を順番に並べる |
head | 次に取り出す場所 |
tail | 次に入れる場所 |
dist | スタートからの歩数を覚える |
dx、dy | 上下左右の動きを覚える |
このコードの肝は、「一度調べた場所をもう一度調べない」ことです。visited や dist を使うことで、同じ場所を何度もぐるぐる調べるのを防いでいます。
改造して遊ぶポイント
mazeの0と1を変えて、違う迷路にするstartやgoalの座標を変える- ゴールに着けない迷路を作って、
goal not reachedになるか試す HEIGHTとWIDTHを変えて、少し大きい迷路にする*以外の文字でルートを表示してみる
迷路を大きくする場合は、maze の行数と列数、HEIGHT、WIDTH が合っているかを確認してください。
C言語で書くときの注意点
- 2次元配列は
maze[y][x]の順番で読む - 配列の外へ出ないように、
nx < 0やnx >= WIDTHを必ず調べる headとtailは、キューの取り出し位置と追加位置を表す-1を「まだ行けていない場所」の印として使う(Point){nx, ny}は、C99で使える複合リテラルなので、コンパイル時に-std=c99を付ける
queue の大きさは HEIGHT * WIDTH にしています。迷路のマス数ぶんあれば、同じマスを重複して入れない限り足ります。
Pythonで書くとどうなる？
Pythonでは、キューに collections.deque を使うと書きやすくなります。
path_route.py という名前で、次のコードを作ってみます。
from collections import deque
HEIGHT = 5
WIDTH = 7
maze = [
[0, 0, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0],
]
start = (0, 0)
goal = (6, 4)
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
dist = [[-1] * WIDTH for _ in range(HEIGHT)]
screen = [["#" if maze[y][x] == 1 else "." for x in range(WIDTH)] for y in range(HEIGHT)]
queue = deque([start])
dist[start[1]][start[0]] = 0
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx = x + dx
ny = y + dy
if nx < 0 or nx >= WIDTH or ny < 0 or ny >= HEIGHT:
continue
if maze[ny][nx] == 1 or dist[ny][nx] != -1:
continue
dist[ny][nx] = dist[y][x] + 1
queue.append((nx, ny))
if dist[goal[1]][goal[0]] == -1:
print("goal not reached")
else:
x, y = goal
while (x, y) != start:
screen[y][x] = "*"
for dx, dy in directions:
nx = x + dx
ny = y + dy
if 0 <= nx < WIDTH and 0 <= ny < HEIGHT:
if dist[ny][nx] == dist[y][x] - 1:
x, y = nx, ny
break
screen[start[1]][start[0]] = "S"
screen[goal[1]][goal[0]] = "G"
for row in screen:
print("".join(row))
print(f"shortest distance = {dist[goal[1]][goal[0]]}")Python版の読み方
Python版でも、考え方はC言語版と同じです。
deque([start])で、スタート地点を入れたキューを作るpopleft()で、先に入れた場所から取り出すdistに、スタートからの歩数を覚えるscreenに、表示用の文字を入れる
C言語版では head と tail を自分で管理しました。Python版では deque がその役割を引き受けてくれます。
実行してみる
python3 path_route.py実行結果はC言語版と同じです。
S**#...
##*#.#.
..***#.
.###*#.
....**G
shortest distance = 10C言語版とPython版の違い
| 項目 | C言語 | Python |
|---|---|---|
| キュー | 配列、head、tail で管理する | deque を使う |
| 座標 | Point 構造体で持つ | (x, y) のタプルで持つ |
| 配列の初期化 | for 文で1マスずつ入れる | リスト内包表記で作れる |
| 範囲チェック | nx < 0 || nx >= WIDTH のように書く | 0 <= nx < WIDTH のように書ける |
C言語版は少し長くなりますが、キューの中身や配列の範囲チェックがはっきり見えます。Python版は短く書けるぶん、幅優先探索の流れを追いやすいです。
まとめ
今回は、C言語で迷路の経路探索をしました。
- 迷路は
0と1の2次元配列で表せる - 上下左右の移動は
dxとdyの配列でまとめられる - 幅優先探索は、近い場所から順番に調べる
distを使うと、スタートからの歩数を覚えられる- ゴールから距離が1小さいマスを戻ると、最短ルートを表示できる
経路探索は、迷路だけでなく、ゲームのマップ、乗り換え、ネットワーク、パズルなどにもつながる考え方です。
まずは小さな迷路で、壁の位置やゴールの位置を変えてみてください。少し変えるだけで、ルートや歩数が変わるので、探索の動きがかなり見えやすくなります。
C言語の次にUnityやUnreal Engineを学ぶ選択肢
用途ごとに選ぶ C言語のおすすめ本
この記事を書いた人
関連記事
-
【ベクトルで遊ぼう】C言語でマス目にひし形を描く｜向きと大きさをコードで見てみる | UNIX Cafe -
【フィボナッチで遊ぼう】C言語でfor文・再帰・メモ化を比べる｜Python版も補足で紹介 | UNIX Cafe
-
【素数で遊ぼう】C言語で割り算からエラトステネスのふるいまで｜定番問題をコードパズルにしてみた | UNIX Cafe
-
【ナップサック問題で遊ぼう】C言語で全探索から動的計画法まで｜定番問題をコードパズルにしてみた | UNIX Cafe
-
【ナップサック問題で遊ぼう】Pythonで全探索から動的計画法まで｜定番問題をコードパズルにしてみた | UNIX Cafe
-
【FizzBuzzで遊ぼう】PythonからC言語まで｜定番問題をコードパズルにしてみた | UNIX Cafe
