MAZE・迷路
最終更新日:08.12.27


第一章 「まずは、ここから」
■はじめに
私が迷路を作ることに興味を持ったのは、パソコンを手にしたのとほぼ同時期だった様に思います(もう10年以上も昔になります)。
雑誌に掲載されていたBASICで作られたプログラムを見て、どうやって作っているのだろうと、迷路の作り方を必死で解析しました。 その時覚えたのが、道を延ばすタイプと、壁を延ばすタイプの2種のアルゴリズムでした。
その一方で、マイクロマウス(迷路を脱出するロボット)にたずさわり、迷路の回答を見つける方法を覚えました。
いつしか、迷路を作ってその回答を求め、その回答のできばえに興味を持つようになりました。

これから紹介させて頂くのは、そんなことを何度も繰り返してきた過程で私が感じた不満と、その過程で行ってきた対応策です。
ただ、長い時間をかけてきたにもかかわらず、未だに完璧な対応策は見つかっていません。
これを読んで、少しでも興味が持てたら、是非トライしてみて下さい。


■説明に入る前に
迷路座標 迷路サンプル 迷路概念
図1 図2 図3

これから説明させて頂く迷路は、図1の様な座標で考えています。 そして、各座標が道又は壁になることにより迷路を構成します。 図2が実際に作った迷路の例です。白が道、黒が壁です。
そして、座標として考えたときに便利なのは、(偶数, 偶数)の座標は必ず道、(奇数, 奇数)の座標は必ず壁、 それ以外の座標はランダムに道又は壁になることで、迷路が構成されている事です。 図3の白の部分が必ず道の座標、黒の部分が必ず壁の座標、グレーの部分がランダムに道又は壁になる座標です。 図2と図3を見比べて頂けると、そうなっていることが分かります。

説明の都合上、いくつか決めておきたいことがあります。
まず、迷路の大きさを表す為に、x方向、y方向それぞれのドット数を、gSizeX、gSizeYで定義します。 図2のケースでは、gSizeX=15、gSizeY=15ということになります(どちらも奇数になります)。
また、ある座標の状態を変更するファンクションとして、void SetPoint(short x, short y, char type)を考えます。 これは、(x, y)の座標の状態をtypeに変更すると共に、画面上への反映を行います。
また、ある座標の状態を取得するファンクションとして、char GetPoint(short x, short y)を考えます。 これは、(x, y)の座標の状態を返します。
そして、各座標の状態を表す定数として、kRoad:道、kWall:壁、kPreWall:作りかけの壁の3種と、回答の経路であることを表すkAnsを考えます。
また、スタートは左上、すなわち(2, 2)とし、ゴールは右下、すなわち(gSizeX-3, gSizeY-3)として考えることとします。

なお、画面上への反映は、ちょっと手を加えた方が良いかもしれません。 まず、最外周を囲んでいる道は、迷路作成上の都合で設けているものなので、表示する際には、削除します。 また、スタート、ゴールがどこであるのかを視覚的にわかりやすくするためには、(2, 1)、(gSizeX-3, gSizeY-2)を道(kRoad)とするのが有効です。


| HOME | MAZE・迷路 | 迷路 第二章 |
E-MAIL:aanda@nifty.com(AKIO HOSOKAWA)