迷路探索のアルゴリズム

迷路探索のアルゴリズムを考えろという問題。

人生を書き換える者すらいた: 人材獲得作戦・４　試験問題ほか より。

このアルゴリズムは、やったことはなかったので、やってみました。

で、結果。Lv2 (最短性のチェックはせず、とにかく１本の到達経路を求めることまではできた) までしかできませんでした…orz

とにかく可能な限り G に近づくようにするようにやっていったので、実際には最短ルートがでるはずだとは思いますが、（間違っているかも）どちらにせよ Lv2 ですね…。

次の記事で、筆者曰くこの問題ができたから優秀な人材とは限らないけれど、できない人は”ほぼ確実に”優秀ではない、のではないかと。

このブログの自己紹介欄から「底辺プログラマ。」の一言が消えるのはまだまだ先か…。

以下コード。Java です。無駄に長い。

import java.awt.Point;

//2時間22分
public class MeiroSaitan {

char[][] chars = {
"**************************".toCharArray(),
"*S* *                    *".toCharArray(),
"* * *  *  *************  *".toCharArray(),
"* *   *    ************  *".toCharArray(),
"*    *                   *".toCharArray(),
"************** ***********".toCharArray(),
"*                        *".toCharArray(),
"** ***********************".toCharArray(),
"*      *              G  *".toCharArray(),
"*  *      *********** *  *".toCharArray(),
"*    *        ******* *  *".toCharArray(),
"*       *                *".toCharArray(),
"**************************".toCharArray()
};
Character[][] maps = new Character[13][26];
Point current = new Point(0, 0);
Point former = new Point(0, 0);
Point gPlace = new Point(0, 0);

public static void main(String[] args) {
new MeiroSaitan();
}

public MeiroSaitan() {
// S の位置を current に代入
for (int i = 0; i < chars.length; i++) {
for (int j = 0; j < chars[i].length; j++) {
maps[i][j] = new Character(chars[i][j]);

if (maps[i][j].equals('S')) {
current.x = j;
current.y = i;
former.x = j;
former.y = i;
}

if (maps[i][j].equals('G')) {
gPlace.x = j;
gPlace.y = i;
}
}
}

while (!maps[current.y][current.x].equals('G')) { // G に辿り着かない限り
former.x = current.x;
former.y = current.y;
if (whereIsG()[0] == S.RIGHT && whereIsG()[1] == S.DOWN) {
// 下がブロックでなければ
if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
//
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
//
else
System.out.println("I can't move!");
} else if (whereIsG()[0] == S.RIGHT && whereIsG()[1] == S.UP) {
// 上がブロックでなければ
if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
//
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
//
else
System.out.println("I can't move!");
} else if (whereIsG()[0] == S.LEFT && whereIsG()[1] == S.UP) {
// 左がブロックでなければ
if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
//
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
//
else
System.out.println("I can't move!");

} else if (whereIsG()[0] == S.LEFT && whereIsG()[1] == S.DOWN) {
// 左がブロックでなければ
if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
//
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
//
else
System.out.println("I can't move!");
}

if (hasGone(current.x, current.y) && !maps[current.y][current.x].equals('G')) {
maps[former.y][former.x] = 'x';
} else if (!maps[current.y][current.x].equals('G')){
maps[current.y][current.x] = '$';
}
// showCurrentState();
}
showCurrentState();
}

private boolean canMove(S s) {
switch (s) {
case UP:
if (maps[current.y - 1][current.x].equals('*')) {
return false;
} else {
return true;
}
case DOWN:
if (maps[current.y + 1][current.x].equals('*')) {
return false;
} else {
return true;
}
case RIGHT:
if (maps[current.y][current.x + 1].equals('*')) {
return false;
} else {
return true;
}
case LEFT:
if (maps[current.y][current.x - 1].equals('*')) {
return false;
} else {
return true;
}
}
return false;
}

private boolean hasGone(int x, int y) {
if (maps[y][x].equals('$') || maps[y][x].equals('x')) {
return true;
}
return false;
}

private boolean hasGone(S s) {
switch (s) {
case UP:
if (maps[current.y - 1][current.x].equals('x') || maps[current.y - 1][current.x].equals('$')) {
return true;
} else {
return false;
}
case DOWN:
if (maps[current.y + 1][current.x].equals('x') || maps[current.y + 1][current.x].equals('$')) {
return true;
} else {
return false;
}
case RIGHT:
if (maps[current.y][current.x + 1].equals('x') || maps[current.y][current.x + 1].equals('$')) {
return true;
} else {
return false;
}
case LEFT:
if (maps[current.y][current.x - 1].equals('x') || maps[current.y][current.x - 1].equals('$')) {
return true;
} else {
return false;
}
}
return false;
}

private boolean isBadRoute(S s) {
switch (s) {
case UP:
if (maps[current.y - 1][current.x].equals('x')) {
return true;
} else {
return false;
}
case DOWN:
if (maps[current.y + 1][current.x].equals('x')) {
return true;
} else {
return false;
}
case RIGHT:
if (maps[current.y][current.x + 1].equals('x')) {
return true;
} else {
return false;
}
case LEFT:
if (maps[current.y][current.x - 1].equals('x')) {
return true;
} else {
return false;
}
}
return false;
}

private void showCurrentState() {
System.out.println(former.x + ", " + former.y + " -> " + current.x + ", " + current.y);

for (int i = 0; i
< maps.length; i++) {
for (int j = 0; j
< maps[i].length; j++) {
System.out.print(maps[i][j]);
}
System.out.println();
}

System.out.println("----------");
}

private S[] whereIsG() {
S[] where = new S[2];

if (current.x < gPlace.x) {
where[0] = S.RIGHT;
} else {
where[0] = S.LEFT;
}

if (current.y < gPlace.y) {
where[1] = S.DOWN;
} else {
where[1] = S.UP;
}

return where;
}

enum S {
RIGHT, LEFT, UP, DOWN;
}
}

JavaFX で遊んでみた

JavaFX で遊んで見ました。

表示には Java Runtime Environment 6 update 10 以降が必要です。JavaFX Runtime のインストールを求められるので注意して下さい。

2011/10/02 WordPress.com は JavaScript をサポートしないようなのでプログラム自体を削除。

ちなみにコードはこちら。zlib/libpng license で配布します。

以下、アルゴリズム等のメモ。まぁ極めて初歩的なアルゴリズムですが。
あと最小値指定は自分で考えたので、間違っているかも。
(最大値指定は大学の授業で習ったので間違いないです。)

最大値を引数で指定できない場合は、
rand.nextDouble() % 最大値
のように剰余を取ります。

逆に最大値は指定できるが、最小値を引数で指定できない場合は、
rand.nextInt(最大値 – 最小値) +最小値

どちらも指定できない場合は
rand.nextDouble() % (最大値 – 最小値) + 最小値
です。

※rand.nextDouble(), rand.nextInt() は乱数生成関数。rand.nextInt() の引数は最大値

あと、コードを二つのファイルに分割する際、クラスのみを記述したファイル (Fireflies.fx) をメインファイルとして NetBeans に設定してしまったため、動作しないということがありました。Java だと main メソッドがなければ main クラスとして認識されませんが、Java FX だとそうでもないので、そこは気を付けなければいけませんね。

「噴き上がるユメの碧」と、その動画の 2:10 くらいのあたりのエフェクトに触発されて作りました。