自動生成のダンジョンを作る①

迷路アルゴリズム

自動生成のダンジョンが作れれば、繰り返し遊べるローグライクなゲームを開発することが可能になります。

そこでまず、迷路を自動生成するためのアルゴリズムを調べました。

有名なところでは以下のものがあるようです。

• Buckblog: Maze Generation: Kruskal's Algorithm

• Buckblog: Maze Generation: Prim's Algorithm

• Buckblog: Maze Generation: Recursive Backtracking

• Buckblog: Maze Generation: Aldous-Broder algorithm

• Buckblog: Maze Generation: Growing Tree algorithm

• Buckblog: Maze Generation: Hunt-and-Kill algorithm

• Buckblog: Maze Generation: Wilson's algorithm

• Buckblog: Maze Generation: Eller's Algorithm

• Buckblog: Maze Generation: Sidewinder algorithm

• Buckblog: Maze Generation: Binary Tree algorithm

上から順にメジャーなアルゴリズムというわけではありませんが、KruskalのアルゴリズムでUnityで実装した事例を調べたところ、以下の動画が見つかりました。

 

www.youtube.com

 

プロジェクトもGithubにアップしてくれています。

github.com

 

こちらのコードを参考にしながら、次回以降自動生成ダンジョンを作っていきます。

 

 

ringogames.hatenablog.com