ノエリアラボラトリー

日々の研究と開発の成果を書くよ

穴掘り法とA*で迷路を作って解く過程を可視化した話

Java JavaFX

せっかくだからブログに書いておこうかなと。

A*はwikipediaによると

「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。

とのこと。ヒューリスティック関数には単純なユークリッド距離を用いている。

穴掘り法は迷路の自動生成の一種で他にも種類があるらしい。使えそうなものを探してきたので詳しくは知らない。

コード

github.com

アルゴリズムについて

両者を区別するのは面倒なのでこういうインタフェースを作った。

public interface Executor {
    void launch();
    boolean canContinue();
    void continueDo();
    void clear();
}

上から初期状態、終了条件、メインフロー、状態初期化。

A*は大体こんな感じの実装になっている。細かい部分は省略。

初期状態：スタートとゴールがあり、スタートが現在地で通過済み

  1. 現在地から四方の壁でなく行ったことのない点を探す
  2. これまでのルートと1の点を足して解候補に加える
  3. 解候補の中でヒューリスティック関数が最良のものを現在地にする

終了条件：現在地がゴール地点なら終了

穴掘り法は大体こんな感じの実装になっている。細かい部分は省略。

初期状態：奇数×奇数のフィールド全てが壁でスタート地点は真ん中

  1. 進行方向をランダムに決める。
  2. 進行方向2つ先が壁なら2つ通路にして2つ先を現在地にする
  3. 2を満たさなければ別の進行方向を選ぶ。なければあるまで戻る。

終了条件：進める場所がこれ以上なければ終了

可視化について

ビューとロジックの橋渡しとしてこういうインタフェースを作った。

public interface Point {
    boolean canWalk();
    boolean isStart();
    boolean isGoal();
    void start();
    void goal();
    void road();
    void route();
    void block();
}

これだけでは足りなかったのでA*と穴掘り法で追加で必要な処理を渡すインタフェースを別に用意した。

JavaFXではGridPaneにButtonを大量に配置してCSSで色を変えることで可視化を表現している。 ButtonにPointを実装したもの使うことでビューとロジックを何とか繋げた。もっといいやり方がありそう。

所感

当初院生だった私はA*のソルバーだけ作って満足していた。 名前が「迷路作るやつ」だったので迷路を作りたいなぁとは思っていて実現させた。

JavaFXを使っている人はJava9が目前に迫った今でもほとんど見ないけど定期的にやっていきたい。 たぶん今回のものを一部変えてライフゲームでも作ると思う。