※この記事は、技術評論社の協力により、河西朝雄 著「Javaによるはじめてのアルゴリズム入門」（ISBN4-7741-1240-2）の内容をベースに執筆しています。
再帰呼び出し
再帰呼び出しとは、ある関数（メソッド）からその内部で再び自分自身を呼び出す方法です。再帰呼び出しは、2分木のような再帰的なデータ構造を扱うときに有効です。2つの枝を持つことができる2分木は、枝の中に１次元低い部分木を再帰的に持ちます。
迷路の作成と探索も、同様に再帰呼び出しによって記述できます。縦横のマス目の壁をランダムに進んで壁をとりはずせば、迷路を作ることができます。
ここで使用しているアルゴリズムは、次のようなしくみです。
縦NY×横NXの各マスに迷路配列m[][]を対応させ、その各要素に図のような上壁の有無、右壁の有無、訪問の有無の3つの情報をもたせます。
（i, j）位置から進む方向を乱数で、1:右、2:下、3:左、4:上の中から選択し、1マス進むことにします。その方向に進めるかは、そのマスがまだ見訪問である場合です。これを進む方向がなくなるまで再帰的に繰り返します。
壁は次の要領で取り壊していきます。
① 右へ進む場合は、今いる位置の右壁をとる
② 下へ進む場合は、進む位置の上壁をとる
③ 左へ進む場合は、進む位置の右壁をとる
④ 上へ進む場合は、今いる位置の上壁をとる
迷路の探索も、次のの要領で、出口に到達するか行き止まりにたどり着くまで再帰的に行います。
① （i, j）位置に訪問フラグ（第3ビット）をセットする
② （i, j）位置をスタックに保存
③ 出口に到達したら、スタックに保存されている通過経路を表示
④ もし右が空いていればvisit(i, j+1) を行う
⑤ もし下が空いていればvisit(i+1, j) を行う
⑥ もし左が空いていればvisit(i, j-1) を行う
⑦ もし上が空いていればvisit(I-1, j) を行う
⑧ スタック最上位の保存位置を捨てる
迷路の通過経路を保存するためのスタックとして配列ri[]、rj[]を用い、スタック位置をspで管理します。
MazeBeanの作成
このアルゴリズムを実装するために、MazeBeanを作成します。まず、JBuilderで、新規プロジェクトを作成します。次に、［ファイル｜新規］でオブジェクトギャラリを表示し、［JavaBean］を選択します。
迷路を表示するのは、javax.swing.JPanelを継承したMazePanelです。JavaBeanウィザードで、［クラス名］項目に”MazePanel”、［ベースクラス］に”javax.swing.JPanel” を指定して［OK］ボタンをクリックします。
次のように、Beanのコードを実装します。
package maze;
import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JPanel;
public class MazePanel extends JPanel {
private final int NX = 24, NY = 20; // マスの横と縦
private int[][] m = new int[60][60]; // 迷路配列
private int Si, Sj, Ei, Ej; // 入り口と出口
private int bp = 1, w = 15, h = 15; // 入り口の位置と壁の長さ
private int sp; // スタックポインタ
private int[] ri = new int[300]; // スタック
private int[] rj = new int[300];
private Color wallColor = new Color(0, 0, 0);
private Color routeColor = new Color(255, 0, 0);
private int delay = 50;
public MazePanel() {
generateMaze();
try {
jbInit();
} catch (Exception ex) {
ex.printStackTrace();
}
}
public void generateMaze() {
Si = 1;
Sj = 1;
Ei = NY;
Ej = NX;
for (int i = 0; i <= NY + 1; i++) {
for (int j = 0; j <= NX + 1; j++) {
if (i == 0 || j == 0 || i == NY + 1 || j == NX + 1) {
m[i][j] = 15;
} else {
m[i][j] = 3;
}
}
}
genmaze(Ei, Ej);
m[Ei][Ej] = m[Ei][Ej] & 0xd;
}
public void genmaze(int i, int j) {
int n;
m[i][j] = m[i][j] | 4;
while (m[i][j + 1] == 3 || m[i + 1][j] == 3 || m[i][j - 1] == 3 ||
m[i - 1][j] == 3) {
n = (int) (4 * Math.random() + 1);
if (n == 1 && m[i][j + 1] == 3) {
m[i][j] = m[i][j] & 0xd;
genmaze(i, j + 1);
} else if (n == 2 && m[i - 1][j] == 3) {
m[i][j] = m[i][j] & 0xe;
genmaze(i - 1, j);
} else if (n == 3 && m[i][j - 1] == 3) {
m[i][j - 1] = m[i][j - 1] & 0xd;
genmaze(i, j - 1);
} else if (n == 4 && m[i + 1][j] == 3) {
m[i + 1][j] = m[i + 1][j] & 0xe;
genmaze(i + 1, j);
}
}
}
void visit(int i, int j, Graphics g) {
int k, x, y, oldx = 0, oldy = 0;
m[i][j] = m[i][j] | 8;
ri[sp] = i;
rj[sp] = j;
sp++;
if (i == Ei && j == Ej) {
for (k = 0; k < sp; k++) {
x = (rj[k] - 1) * w + bp + w / 2;
y = (ri[k] - 1) * h + bp + h / 2;
if (k != 0) {
g.drawLine(oldx, oldy, x, y);
try {
Thread.sleep(delay);
} catch (java.lang.InterruptedException e) {
e.printStackTrace();
}
}
oldx = x;
oldy = y;
}
}
if ((m[i][j] & 2) == 0 && (m[i][j + 1] & 8) == 0) {
visit(i, j + 1, g);
}
if ((m[i + 1][j] & 1) == 0 && (m[i + 1][j] & 8) == 0) {
visit(i + 1, j, g);
}
if ((m[i][j - 1] & 2) == 0 && (m[i][j - 1] & 8) == 0) {
visit(i, j - 1, g);
}
if ((m[i][j] & 1) == 0 && (m[i - 1][j] & 8) == 0) {
visit(i - 1, j, g);
}
sp--;
}
public void paint(Graphics g) {
int i, j, x, y;
Si = 1;
Sj = 1;
Ei = NY;
Ej = NX;
w = this.getWidth() / NX;
h = this.getHeight() / NY;
g.setColor(getWallColor());
g.clearRect(0, 0, (NX + 3) * w, (NY + 6) * h);
g.drawLine(bp, bp, NX * 10 + bp, bp);
g.drawLine(bp, bp + h, bp, NY * h + bp);
g.drawLine(bp, NY * h + bp, NX * w + bp, NY * h + bp);
g.drawLine(NX * w + bp, bp, NX * w + bp, (NY - 1) * h + bp);
for (i = 1; i <= NY; i++) {
for (j = 1; j <= NX; j++) {
x = (j - 1) * w + bp;
y = (i - 1) * h + bp;
if ((m[i][j] & 1) == 1) {
g.drawLine(x, y, x + w, y);
}
if ((m[i][j] & 2) == 2) {
g.drawLine(x + w, y, x + w, y + h);
}
}
}
g.dispose();
}
public void showRoute() {
for (int i = 0; i < 60; i++) {
for (int j = 0; j < 60; j++) {
m[i][j] = m[i][j] & 7;
}
}
w = this.getWidth() / NX;
h = this.getHeight() / NY;
Graphics g = this.getGraphics();
g.setColor(getRouteColor());
visit(Si, Sj, g);
repaint();
}
public void setWallColor(Color wallColor) {
this.wallColor = wallColor;
}
public void setRouteColor(Color routeColor) {
this.routeColor = routeColor;
}
public void setDelay(int delay) {
this.delay = delay;
}
public Color getWallColor() {
return wallColor;
}
public Color getRouteColor() {
return routeColor;
}
public int getDelay() {
return delay;
}
private void jbInit() throws Exception {
}
}
このBeanでは、迷路の壁を描画する色を指定するWallColorプロパティと、ルートを描画する色を指定するRouteColorプロパティを定義しています。また、ルートの描画を遅延させる遅延時間をミリ秒単位で指定するDelayプロパティも定義します。
アプリケーションの作成
Beanを作成してしまえば、その実行結果をビジュアルに確認するアプリケーションを作るのは簡単です。［ファイル｜新規］メニューで［アプリケーション］を選択し、ウィザードを起動します。
ウィザードの最初のステップでは、［クラス名］にアプリケーションクラス名を指定します。ここでは、”MazeApp” と入力します。
［次へ］ボタンをクリックして、次のステップに進みます。ここでは、フレームクラス名として［クラス］項目に”MazeFrame”、［タイトル］に”迷路” と指定します。
［終了］ボタンをクリックして、ウィザードを終了させます。
MazeFrame.javaが表示されたら、［設計］タブをクリックしてUIデザイナを表示します。はじめにフレームの下端でマウスボタンを押して、適当な高さ（正方形ぐらい）になるようにドラッグします。
この操作は、以下のようにJavaコードに反映されています。もちろんコードによって、サイズを指定することもできます。
setSize(new Dimension(400, 400));
次に、MazeBeanをフレームに配置します。作成したBeanをすばやく配置するには、パレット上の［Bean］ボタンをクリックし、［選択］メニューを選びます。
表示された「Bean選択」ダイアログボックスで、［検索］タブをクリックし、［検索文字列］にmazeと入力して、MazePanelを探します。［一致リスト］に表示された ”MazePanel” を選択して［OK］ボタンをクリックします。
アイコンの形状が変わるので、フレームの真中ぐらいの場所をクリックします。
すると、次のように迷路を表示するBeanが配置されます。
次に、パレットからJButtonを選択し、フレーム下部をクリックします。配置したボタンのtextプロパティに “ルートの表示” と設定し、ボタンのキャプションを変更します。
ボタンをダブルクリックして、JButtonのactionPerfomedイベントを設定します。このイベントはボタンを押したときに発生します。
public void jButton1_actionPerformed(ActionEvent e) {
mazePanel1.showRoute();
}
ボタンをクリックすると、迷路のルート探索を行い、ルートを表示します。アプリケーションを実行し、［ルートの表示］ボタンをクリックすると、以下のように実行されます。
MazeBeanは、ルートの表示に現在のスレッドを使っています。そのため、ルート表示を行っている間は、アプリケーションはロックされてしまいます。マルチスレッドを用いれば、この問題は解決できます。ぜひ、MazeBeanを改良してみましょう。
