【ゲームプログラミング】その5. マップ自動生成のアルゴリズム

2020年6月13日

こんばんは、てぃってぃ(嫁)の夫です。

「スマホでローグライク開発」第5回です。
今回の記事は「マップ自動生成のアルゴリズム」の実装です。不思議のダンジョンなどで定番の、入る度に地形が変わるマップです。

実際に出力したマップ

先に成果物をお見せします。その方が読んでくれる気が起きると思うのでw
出力結果をテキストファイルに落としました。

自動生成マップ(40×30)
自動生成マップ(40×30)
自動生成マップ(60×40)

後ほどの説明の為に、マップに記号を付けています。
・☆★ … 区域の頂点
・△▲ … 部屋の頂点

方針

「区域分割法」という方法を用います。
全体マップの分割を繰り返して、「区域」を作成し、その区域内で「部屋」を作成して、部屋同士を接続する感じです。

ネットにもたくさんヒントがあったのですが、頭の悪い私には理解できず(笑)、参考にするのはあきらめて自作しちゃいました。2日程度でぱぱーっと作ったので、色々とクオリティに突っ込みどころはあるかと思いますが、誰かの参考になればと思いますので、載せておきたいと思います。

実装

以下、実装方法のメモ書きです。
注意)ほんとーーに、2日程度で仕事終わりの状態で家で仕上げた、テスト不十分の完全オリジナルソースなので、参考程度にしてください。バグっていても責任とれませんw

① 全体マップを区域分割する

全体マップを複数の区域に分割していきます。1つの区域を「Rect」と呼びます。イメージはこんな感じです。

ローグ開発_マップ自動生成_3
ローグ開発_マップ自動生成_4
ローグ開発_マップ自動生成_5
ローグ開発_マップ自動生成_6

処理としては、全体マップのサイズ定義、マップ実体の定義、区域クラスの定義が必要です。
(注)ちなみにdefineは「X_RECT_MIN」「Y_RECT_MIN」を変えるとややおかしくなったかも。部屋の最小幅を「4」から変えたい場合は調整必要。(そのうちやるかも、やらないかも…)

そして、実際に分割する処理です。綺麗(偏りなく)に分割していく方法として、以下を入れてみました。
・分割対象は「最も面積が広い区域」
・分割方向は「長さが長い辺」

② 区域内に部屋を作成する

区域毎に、区域頂点から乱数だけずらした位置に、新たに部屋頂点を作成します。イメージはこんな感じ。

処理イメージもそのまんまです。簡単。

③ 部屋から区域の境界へ線を伸ばす

部屋毎に、区域の境界線に向かって線を伸ばします。イメージはこんな感じ。

ローグ開発_マップ自動生成_8

部屋頂点を結んだ線上の任意の点(乱数でずらす)から、区域の境界線に線を伸ばします。

④ 区域の境界線上の通路を結ぶ

区域の境界線をなめていき、通路が存在する場合、通路から通路へと線を結びます。

ローグ開発_マップ自動生成_9

処理としては、区域頂点を順番に見て、通路が隣接している場合には、通路と通路の間も通路に変える感じです。(イミフ)

これでほぼ完成なのですが、画像でいうRect[0]のように、接続する区域の通路がなく、行き止まりになることもあります。行き止まりを許容する場合はここで終わりですが、許容しない場合は次の「⑤」の処理が必要になります。

⑤ 行き止まりの点から他の通路へ接続する

行き止まりの点があれば、行き止まりの通路と垂直方向の直線上に存在する他の通路に接続します。

ローグ開発_マップ自動生成_10

処理としては、区域頂点を走査していき、行き止まりの点があれば、そこから垂直方向の直線を走査し、通路が見つかれば接続する、という感じです。

これでめでたく、全ての処理が終了になります。お疲れ様でした。

あとがき

っったのしぃっっ
アルゴリズムを作るのは読むより作る方が断然面白いですね。
次はいよいよこのマップデータを組み込んで、実際のマップチップを描画するところまでいこうと思います。それでかなりゲームらしくなりそう。そして凄く順調で良い感じである!年内にゲームできちゃうかも?w

ご購読、ありがとうございました。