第64回 プログラミングについて『迷路を通ろう！（その１）』
迷路といえば、映画の『ラビリンス』とか、人間が歩けるような大きな迷路などを思い浮かべるかたも多いのではないでしょうか。『ラビリンス』はデビッドボーイがなかなか良くて、わくわくして見たものです。そこで、という訳では全然ないのですが、今回からは迷路を考えてみましょう。
プログラムのコンテストには迷路を作るプログラムが課題になることもあります。どれだけ高速に複雑な迷路を作ることができるかを競うのですが、なかなか優れたものがあるようです。しかしながら今回からは、迷路そのものを作ることではなく、迷路を通ることを本題としていきます。
プリント基板設計用のＣＡＤでは迷路を通ることを主目的としたプログラムがあります。コンピュータを扱っていてプリント基板を見たことのない方は多分いないと思いますので詳しい説明はしませんが、プリント基板上の部品と部品を接続するには、パターンという銅箔の線で行ないます。このパターンを自動的に生成しようというのが、自動配線プログラムです。
自動配線といっても、ロボットが半田ゴテを持って銅箔を半田付けするのではなく、どのように配線をするかを計算するものです。要するに、基板上の部品の接続すべき端子と端子が迷路の出発点と終着点になり、接続に関係のない端子や他のパターンなどが障害物になる訳です。
迷路を探索する方法には、『線分探索法』と『迷路探索法』の２種類が基本的なアルゴリズムとして古くから考えられています。現在では、自動配線プログラムはかなり進歩していて、配線の効率が良くなっていますが、基本はこの２つのアルゴリズムを使用しています。まず下の図を見て下さい。
・・・・・・・・・Ｔ
ＸＸＸＸ・・・Ｘ・・
・・・・・・・Ｘ・・
・・・・・・・Ｘ・・
・・ＸＸＸＸ・・・・
・・・・ＳＸ・・・・
・・Ｘ・・Ｘ・・ＸＸ
・・Ｘ・・Ｘ・・・・
・・Ｘ・・・・・・・
・・ＸＸＸＸＸＸ・・
この図で、・は障害物のない点で、Ｘは障害物、Ｓは出発地点、Ｔは目標地点と解釈して下さい。
線分探索法というのは、最初にＳの地点から横に線を引きます。次にその線から縦に線を引きます。再びその縦の線から横に線を引いていきます。これを繰返していき、線がＴに到達したところで、探索を終了して、経路を決定します。
・・・・・・・・・Ｔ ・・・・・・・・・Ｔ ・・・・・・・・・Ｔ
ＸＸＸＸ・・・Ｘ・・ ＸＸＸＸ・・・Ｘ・・ ＸＸＸＸ・・・Ｘ・・
・・・・・・・Ｘ・・ ｜｜・・・・・Ｘ・・ ＋＋ーーーーーＸ・・
・・・・・・・Ｘ・・ ｜｜・・・・・Ｘ・・ ＋＋ーーーーーＸ・・
・・ＸＸＸＸ・・・・ → ｜｜ＸＸＸＸ・・・・ → ｜｜ＸＸＸＸ・・・・
ーーーーＳＸ・・・・ ＋＋ー＋ＳＸ・・・・ ＋＋ー＋ＳＸ・・・・
・・Ｘ・・Ｘ・・ＸＸ ｜｜Ｘ｜・Ｘ・・ＸＸ ｜｜Ｘ＋ーＸ・・ＸＸ
・・Ｘ・・Ｘ・・・・ ｜｜Ｘ｜・Ｘ・・・・ ｜｜Ｘ＋ーＸ・・・・
・・Ｘ・・・・・・・ ｜｜Ｘ｜・・・・・・ ｜｜Ｘ＋ーーーーーー
・・ＸＸＸＸＸＸ・・ ｜｜ＸＸＸＸＸＸ・・ ｜｜ＸＸＸＸＸＸ・・
↓
・・・・・・＋ーーＴ ーーーー＋＋＋ーーＴ ・・・・｜｜｜・・Ｔ
ＸＸＸＸ・・｜Ｘ・・ ＸＸＸＸ｜｜｜Ｘ・・ ＸＸＸＸ｜｜｜Ｘ・・
・＋ーーーー＋Ｘ・・ ＋＋ーー＋＋＋Ｘ・・ ＋＋ーー＋＋＋Ｘ・・
・｜・・・・・Ｘ・・ ＋＋ーー＋＋＋Ｘ・・ ＋＋ーー＋＋＋Ｘ・・
・｜ＸＸＸＸ・・・・ ← ｜｜ＸＸＸＸ＋＋ーー ← ｜｜ＸＸＸＸ｜｜・・
・＋ーーＳＸ・・・・ ＋＋ー＋ＳＸ＋＋ーー ＋＋ー＋ＳＸ｜｜・・
・・Ｘ・・Ｘ・・ＸＸ ｜｜Ｘ＋ーＸ｜｜ＸＸ ｜｜Ｘ＋ーＸ｜｜ＸＸ
・・Ｘ・・Ｘ・・・・ ｜｜Ｘ＋ーＸ｜｜｜｜ ｜｜Ｘ＋ーＸ｜｜｜｜
・・Ｘ・・・・・・・ ｜｜Ｘ＋ーー＋＋＋＋ ｜｜Ｘ＋ーー＋＋＋＋
・・ＸＸＸＸＸＸ・・ ｜｜ＸＸＸＸＸＸ｜｜ ｜｜ＸＸＸＸＸＸ｜｜
次に迷路探索法は、出発点Ｓから縦または横に１ステップで移動できる点に印 1 を、次に印 1 から１ステップで移動出来るところに印 2 を付けます。これを繰り返し、Ｔに到達したところで探索を終了して、経路を決定します。
・・・・・・・・・Ｔ ・・・・・・・・・Ｔ ・・・・・・・・・Ｔ
ＸＸＸＸ・・・Ｘ・・ ＸＸＸＸ・・・Ｘ・・ ＸＸＸＸ・・・Ｘ・・
・・・・・・・Ｘ・・ ・・・・・・・Ｘ・・ ・・・・・・・Ｘ・・
・・・・・・・Ｘ・・ ・・・・・・・Ｘ・・ ・・・・・・・Ｘ・・
・・ＸＸＸＸ・・・・ → ・・ＸＸＸＸ・・・・ → ・・ＸＸＸＸ・・・・
・・・1 ＳＸ・・・・ ・・2 1 ＳＸ・・・・ ・3 2 1 ＳＸ・・・・
・・Ｘ・1 Ｘ・・ＸＸ ・・Ｘ2 1 Ｘ・・ＸＸ ・・Ｘ2 1 Ｘ・・ＸＸ
・・Ｘ・・Ｘ・・・・ ・・Ｘ・2 Ｘ・・・・ ・・Ｘ3 2 Ｘ・・・・
・・Ｘ・・・・・・・ ・・Ｘ・・・・・・・ ・・Ｘ・3 ・・・・・
・・ＸＸＸＸＸＸ・・ ・・ＸＸＸＸＸＸ・・ ・・ＸＸＸＸＸＸ・・
↓
151413121112131415Ｔ ・・・・・・・・・Ｔ
ＸＸＸＸ101112Ｘ1415 ＸＸＸＸ・・・Ｘ・・
7 6 7 8 9 1011Ｘ1314 ・・・・・・・Ｘ・・
6 5 6 7 8 9 10Ｘ1213 ・・・・・・・Ｘ・・
5 4 ＸＸＸＸ9 101112 ← 途中省略 ← ・4 ＸＸＸＸ・・・・
4 3 2 1 ＳＸ8 9 1011 4 3 2 1 ＳＸ・・・・
5 4 Ｘ2 1 Ｘ7 8 ＸＸ ・4 Ｘ2 1 Ｘ・・ＸＸ
6 5 Ｘ3 2 Ｘ6 7 8 9 ・・Ｘ3 2 Ｘ・・・・
7 6 Ｘ4 3 4 5 6 7 8 ・・Ｘ4 3 4 ・・・・
8 7 ＸＸＸＸＸＸ8 9 ・・ＸＸＸＸＸＸ・・
↓
・・・・・・＋ーーＴ
ＸＸＸＸ・・｜Ｘ・・
・＋ーーーー＋Ｘ・・
・｜・・・・・Ｘ・・
・｜ＸＸＸＸ・・・・
・＋ーーＳＸ・・・・
・・Ｘ・・Ｘ・・ＸＸ
・・Ｘ・・Ｘ・・・・
・・Ｘ・・・・・・・
・・ＸＸＸＸＸＸ・・
線分探索法でも、迷路探索法でも同じことが言えるのですが、探索を終了した後の経路の決定において複数の経路が考えられるのですが、通常はできる限り短い経路で折れ曲がりの少ないように決定するようにします。
今回は、迷路探索法によるプログラムを考えていきます。上の迷路探索法の図をみていて気が付くことは、出発点から順に１、２、３、４ .... と番号を振っていったとき到着点が遠い時には、その数値がとんでもなく大きくなっていく可能性があります。当然のことながら、マトリクスを作って探索を行ないますので、１つの点に使用するバイト数が２バイトとか４バイトになってしまうとメモリーを大量に消費してしまうことになります。
やはり世の中には頭のいい人がいるもので、２ビットあれば実現できる方法というものがあるのです。実際にはプログラムを作るときには２ビットでは面倒なので、１バイトにしますが、次のように数値を振っていくようにするのです。これは２ステップ以内で移動できる点に印１を、次にその印１から２ステップ以内で移動できる点に印２を、再び印２から２ステップ以内で移動できる点に印１を付けていくようにします。
・・・・・・・・・Ｔ ・・・・・・・・・Ｔ ・・・・・・・・・Ｔ
ＸＸＸＸ・・・Ｘ・・ ＸＸＸＸ・・・Ｘ・・ ＸＸＸＸ・・・Ｘ・・
・・・・・・・Ｘ・・ ・・・・・・・Ｘ・・ ・１・・・・・Ｘ・・
・・・・・・・Ｘ・・ ・・・・・・・Ｘ・・ １１１・・・・Ｘ・・
・・ＸＸＸＸ・・・・ → ・２ＸＸＸＸ・・・・ → １２ＸＸＸＸ・・・・
・・１１ＳＸ・・・・ ２２１１ＳＸ・・・・ ２２１１ＳＸ・・・・
・・Ｘ１１Ｘ・・ＸＸ ・２Ｘ１１Ｘ・・ＸＸ １２Ｘ１１Ｘ・・ＸＸ
・・Ｘ・１Ｘ・・・・ ・・Ｘ２１Ｘ・・・・ １１Ｘ２１Ｘ１・・・
・・Ｘ・・・・・・・ ・・Ｘ２２２・・・・ ・１Ｘ２２２１１・・
・・ＸＸＸＸＸＸ・・ ・・ＸＸＸＸＸＸ・・ ・・ＸＸＸＸＸＸ・・
↓
・・・２２２・・・Ｔ ・・・・・・・・・Ｔ ・・・・・・・・・Ｔ
ＸＸＸＸ１２２Ｘ・・ ＸＸＸＸ１・・Ｘ・・ ＸＸＸＸ・・・Ｘ・・
２１２２１１２Ｘ・・ ２１２２１１・Ｘ・・ ２１２２・・・Ｘ・・
１１１２２１１Ｘ２・ １１１２２１１Ｘ・・ １１１２２・・Ｘ・・
１２ＸＸＸＸ１１２２ ← １２ＸＸＸＸ１１・・ ← １２ＸＸＸＸ・・・・
２２１１ＳＸ２１１２ ２２１１ＳＸ２１１・ ２２１１ＳＸ２・・・
１２Ｘ１１Ｘ２２ＸＸ １２Ｘ１１Ｘ２２ＸＸ １２Ｘ１１Ｘ２２ＸＸ
１１Ｘ２１Ｘ１２２１ １１Ｘ２１Ｘ１２２１ １１Ｘ２１Ｘ１２２・
２１Ｘ２２２１１２２ ２１Ｘ２２２１１２２ ２１Ｘ２２２１１２２
２２ＸＸＸＸＸＸ２１ ２２ＸＸＸＸＸＸ２１ ２２ＸＸＸＸＸＸ２・
↓
・１１２２２１１・Ｔ ２１１２２２１１２Ｔ ・・・・・・＋ーーＴ
ＸＸＸＸ１２２Ｘ１・ ＸＸＸＸ１２２Ｘ１２ ＸＸＸＸ・・｜Ｘ・・
２１２２１１２Ｘ１１ ２１２２１１２Ｘ１１ ・＋ーーーー＋Ｘ・・
１１１２２１１Ｘ２１ １１１２２１１Ｘ２１ ・｜・・・・・Ｘ・・
１２ＸＸＸＸ１１２２ → １２ＸＸＸＸ１１２２ → ・｜ＸＸＸＸ・・・・
２２１１ＳＸ２１１２ ２２１１ＳＸ２１１２ ・＋ーーＳＸ・・・・
１２Ｘ１１Ｘ２２ＸＸ １２Ｘ１１Ｘ２２ＸＸ ・・Ｘ・・Ｘ・・ＸＸ
１１Ｘ２１Ｘ１２２１ １１Ｘ２１Ｘ１２２１ ・・Ｘ・・Ｘ・・・・
２１Ｘ２２２１１２２ ２１Ｘ２２２１１２２ ・・Ｘ・・・・・・・
２２ＸＸＸＸＸＸ２１ ２２ＸＸＸＸＸＸ２１ ・・ＸＸＸＸＸＸ・・
探索が終了したら、到達点から逆に２、２、１、１か１、１、２、２の順に出発点に辿っていき経路を決定します。私が最初にこのアルゴリズムを見たのは１５年以上も前のことですが、この２ステップずつということに気が付いた人は（誰が考えたのかは、私は知りません）よっぽど頭を悩ましたのだろうと思いつつも、目からウロコが落ちたような気がしたものです。
さてそれでは、実際にプログラムを考えていきましょう。今回使用する関数は４6回目の芋虫を作ったときのものを流用していますので参考にして下さい。全体のプログラムの流れは大きく、
（１）画面の消去、ランダム関数の初期化。
（２）迷路の作成と表示。
（３）経路の探索と決定。
の順です。
まずは、メイン関数の部分。
/* ヘッダーファイルのインクルード */
#include <stdio.h>
#include <sys\timeb.h>
#include <time.h>
#include <stdlib.h>
#include <malloc.h>
/* 動的なメモリの確保／解放を行なうマクロ */
#define NEW(type,element) (type *)malloc(sizeof(type)*(element))
#define DELETE(addr) free(addr)
/* マトリクス（迷路）のサイズ */
#define XSIZE 78
#define YSIZE 22
/* マトリクスの各要素に設定する値 */
#define ROUT1 1 /* 経路探索時の印１に使用 */
#define ROUT2 2 /* 経路探索時の印２に使用 */
#define FIXED 3 /* 決定した経路に使用 */
#define DOOR1 4 /* 入口 */
#define DOOR2 5 /* 出口 */
#define WALL 6 /* 壁（障害物）*/
/* マトリクス */
char matrix[XSIZE+1][YSIZE+1];
/* 経路探索時に使用します */
struct rout_data_strct{
int x,y;
struct rout_data_strct *prev,*next;
};
struct rout_data_strct *rout_data=NULL;
main()
{
clear_screen(); /* 画面の消去 */
initialize_random(); /* ランダム関数の初期化 */
set_frame(); /* マトリクスの周辺に壁を設定する */
set_door(); /* 入口、出口の設定 */
make_maze(); /* 迷路の作成 */
redraw_matrix(); /* 迷路の再描画 */
routing(); /* 経路の探索、決定 */
move_cursor(1,YSIZE+1);
}
ここまでは特に難しいところはありません。次に画面を消去する関数 clear_screen()。この関数は４６回目に説明してありますので、リストのみを記載します。
clear_screen()
{
printf("%c[2J",0x1b);
fflush(stdout);
}
次はランダム関数の初期化 initialize_random()。
initialize_random()
{
struct _timeb t;
_ftime(&t);
srand(t.millitm);
}
ランダムな値を返す関数 rand() は初期値が同じときには返してくる値は常に同じ値を同じ順番になりますので、プログラムの起動時に時間のパラメータを使用して初期値を変えるようにするために、このように時間をＯＳから受け取っています。
マトリクス（迷路）の周辺に壁を設定する関数 set_frame() は次のものです。
set_frame()
{
int x,y;
for(x=1;x<=XSIZE;x++){
for(y=1;y<=YSIZE;y++){
matrix[x][y]=0;
}
}
for(x=1;x<=XSIZE;x++){
matrix[x][1 ]=WALL;
matrix[x][YSIZE]=WALL;
}
for(y=1;y<=YSIZE;y++){
matrix[1 ][y]=WALL;
matrix[XSIZE][y]=WALL;
}
}
ループがいっぱいありますが、要するにマトリクスの周辺の要素に値 WALL を代入しています。ただちょっと気にしておいて欲しいのは、後々のプログラムを簡単にするためにマトリクスの０番の要素は使用していないことです。
だいぶ長くなってしまったので、続きはまた次回にしましょう。
