それなりブログ

とあるWebエンジニアのそれなりのブログ、JavaScript/Node.js/Python/PHP/ゲーム作成 など

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

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

generate-maze-by-clustering

使用例:

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

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

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

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

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

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

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

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

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

何なのかなぁ 知りたいなぁ (チラッ チラッ


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


コメントを残す

メールアドレスが公開されることはありません。

Categories

Archives