p5.js サンゴ礁を用いた経路探索
サンゴ礁を使って経路探索するプログラムを作成してみました。
イメージとしては
スタート地点にあるサンゴ礁がどんどん成長していき、ゴール地点に到達する
という感じです。
左の画像はプログラムの実行結果。
右の画像は、左の画像に経路（黄色の線）を手書きで記入したもの。
緑色の長方形は障害物です。
サンゴ礁は障害物を避けて成長してきます。
右下にスタート地点を置き、左上にゴール地点を置いています。
デモページとソースコードは以下にあります。
よかったら見てみてください。
アルゴリズムの説明
今回作成したプログラムは、以前書いた以下の記事をもとに作りました。
サンゴ礁を生成するプログラムに、障害物やスタート地点、ゴール地点を追加した感じです。
経路探索は大体以下のような流れで行われます。
サンゴ礁が成長することによって徐々に経路が現れてきます。
初期状態。スタート地点にサンゴ礁がある。
サンゴ礁にくっつく点がゴール地点から出現し、ランダムウォークを始める。
※ゴール地点からは無限に点を出現させるようにしています
点が広がり始める。
いくつかの点が徐々にスタート地点に近づいていく。
スタート地点のサンゴ礁に白い点がくっつき、サンゴ礁の一部になった。
いくつか白い点がサンゴ礁がくっつき、サンゴ礁の一部になった。
サンゴ礁にくっつく点の数がどんどん多くなり、サンゴ礁が徐々に成長していく。
成長してきた。
みるみるうちにゴール地点にサンゴ礁の先端が近づいていく。
ゴール地点までもう少し。
ゴール地点に到達。
スタート地点からゴール地点までの経路が生成されました。
見やすいように手書きで経路（黄色の線）を記入してます。
やっていることは
白い点をゴール地点からランダムウォークさせて、
ということだけですが、経路が生成されるのがなかなか面白い！
今回紹介したサンゴ礁を生成するような仕組みについては研究分野があって
「Diffusion-limited aggregation」というみたいです（略してDLAという）。
Diffusion-limited aggregationで検索するといろいろ情報が出てくると思うので
興味のある方は調べてみてください。
今日はここまで！
次回は、今回作成したプログラムからいろいろな経路を生成して、
どういう性質をもった経路が生成されるのか考察してみたいと思います。
最後までお読みいただきありがとうございました。
次回
