individual game devlog

個人でスマホ用のゲームを作ってます

ランダムダンジョン生成のアルゴリズム

f:id:yuushimizu:20160601214357p:plain

キャラが動いた!

 

今回はダンジョン生成アルゴリズムを画像付きで紹介します。

 

基本的な流れは

1. 空間を分割する

2. 部屋を配置する

3. 通路を作る

というよくあるものになっています。

 

1. 空間を分割する

 f:id:yuushimizu:20160601214842p:plain

フロア全体を適当な数で分割して各部屋の領域を決めます。今回は4x3にしました。実際には生成時にランダムで決めています。

 

2. 部屋を配置する

f:id:yuushimizu:20160601215442p:plain

領域の中にランダムに部屋を作ります。隣の部屋と3マス以上開くようにして配置すると通路を作るのが楽になります。

 

3. 通路を作る

f:id:yuushimizu:20160601220025p:plain

部屋同士を通路でつなげます。

 

通路を作るときにはフロアが分断されないように注意する必要がありますが、迷路生成のアルゴリズムを使うと、すべての部屋をつなげて通路を作ることができます。私は「穴掘り法」を使っています。

f:id:yuushimizu:20160601221455p:plain

こんな感じで、フロア全体を1つの迷路として考えます。

 

また、実際に部屋をつなげるときには以下のようにしています。

 

1. 両方の部屋の出口を決めます。

f:id:yuushimizu:20160601222239p:plain

 

2. 片方の出口から通路を適当に伸ばします。

f:id:yuushimizu:20160601222314p:plain

 

3. 反対側も横位置が同じになるように伸ばします。

f:id:yuushimizu:20160601222608p:plain

 

4. つなげます。

f:id:yuushimizu:20160601222655p:plain

 

縦につなげるときもXとYを変えて同じようにしています。

 

これで基本的な形ができあがりますが、このままだとシンプルすぎるのでいろいろと処理を追加しています。

 

4. 部屋を通路化

f:id:yuushimizu:20160601223352p:plain

部屋の大きさを1マスにして通路とみなします。部屋の数を減らして通路を長くしたり、丁字路や袋小路を作ったりできます。

 

5. 行き止まりを消す

f:id:yuushimizu:20160601223838p:plain

出口が1つだけの行き止まりの部屋を消します。なんとなくランダム感が増します。再帰的に2つ以上の部屋を消すこともあります。

 

6. 通路を増やす

f:id:yuushimizu:20160601224527p:plain

今のままだとどの部屋にも1通りの行き方でしか行けないので、通路を増やします。つながっていない部分にランダムに通路を作ります。(今回は全部つながってしまいましたが。)

 

7. 部屋を結合する

f:id:yuushimizu:20160601225108p:plain

通路でつながっている2つの部屋を結合して1つの部屋にします。大きい部屋を作れたり、領域をまたいで部屋を配置できるのでランダム感が増します。

 

おわり

f:id:yuushimizu:20160601225609p:plain

とりあえず完成です。

 

説明の都合上、1つずつ順番に処理していきましたが、実際には、部屋数や通路の場所や結合する部屋などのフロア全体の構造を決めてから部屋の配置と通路の作成をしたほうがシンプルになります。(結合時に再配置をしなくて済むので。)

 

今は上で説明したことくらいしかしてませんが、他にも迷路部屋を作ったり、水路を作ったり、もっといろんな要素を追加していくつもりです。

 

あとこのアルゴリズムで作られるダンジョンは綺麗すぎる気がするので、別のアルゴリズムも混ぜていろいろやりたい感じです。