クラスタリング法で迷路生成するnpmモジュール

2015年5月1日

「クラスタリング法」という手法で迷路生成をする npm モジュールを作成しました。

使用例：

$npm install -g generate-maze-by-clustering
$generate-maze-by-clustering 20 10
#########################################
#       #   # # #   #     # # #   #     #
##### ### # # # # ### ##### # ### ### ###
#   # #   # #   #   #     #         #   #
# # # # # ##### ### # ### # # ##### ### #
# #     #   # #   #     #   #     #     #
# ####### ### # ### ### # ### # ### ### #
#   #     # #     # # # # #   #   # #   #
# # # ### # # ##### # ##### ######### # #
# # # # #   #     #   #   # #   #   # # #
##### # # ##### ### ### # # # ### ### ###
#     #     #         # # #   # #       #
### ### ####### ######### # ### ##### ###
#     #   #   #   #     #     #     # # #
# ### # ### ### # # ############### ### #
# #   #     # # #       # # #   #   #   #
# ### ##### # # ##### # # # # ### ##### #
#   #   #   #   #     #                 #
# ######### # ##### # # ### # ### ### ###
#       #     #     # #   # # #   #     #
#########################################

JavaScript コード内で使うための API もあります。というかそっちが欲しかったです。
そちらは GitHub の README を参照願います。

コードの出来はともかく、テストコード内で走査して検証しているので動作は正しいと思います。
既存の動くnpmがなくもなかったんですが、その辺の保障が甘かったのでいっそ自作してみました。

クラスタリング法について

アルゴリズムは、クラスタリングによる迷路作成アルゴリズムというサイトを参照させていただきました。

古来より、迷路生成アルゴリズムには色々な方法があるのですが、その中でこの手法にしたのは、実装しやすかったのと、生成後の迷路が程よい感じだったためです。

その他の参考にしたサイトたちは以下です。

– 迷路自動生成アルゴリズム
– Maze generation algorithm – Wikipedia

ちなみに、この「クラスタリング法」という名称、該当する英語が見つからなく正式名称が不明でした。
たぶん、全然別の、より汎用的なアルゴリズムの一派とかな気がしているんですが、そこまでいくと追跡困難なので諦めました。

何なのかなぁ　知りたいなぁ (ﾁﾗｯﾁﾗｯ