前回（企画編）からだいぶ時間が空いてしまいましたが、続きを書いていこうと思います。
前回（企画編）はこちら。
Unity でローグライクゲームを作ってみよう（企画編）
ブログを公開して早1か月。何かゲームを作りたいなと思う毎日ですが、なかなかまとまった時間も取れないし、そもそもゲームを作れるだけのスキルも不足しているという状態です。でもそんなんじゃいつまで経っても何もできなくなってしまうので、これを...
www.kurage.net
2017.01.28
今回はマップの自動生成に関するお話です。
整数の配列に「0を壁、1を床」といった具合で生成していこうと思います。
自動生成を行うためにはアルゴリズムが重要になってきます。
今回は全体をいくつかの区画に分け、そのうちのいくつかの区画に部屋を作っていくような方法を取ります。
ではさっそくアルゴリズムについて説明していきましょう。
マップ自動生成のアルゴリズム
今回は 16 x 16 のサイズのマップで考えていきます。
大きな区画に分割する
まずは部屋を配置する場所を決めるため、部屋を作れる最小サイズ（今回は6マス分）以上が残るように適当に分割していきます。
乱数を絡ませて、長さがまちまちになるように、分割したりしなかったりするようにします。
4つの区画に分割しました。
また、この区画の境目は後々部屋同士を繋ぐ通路になります。
区画に部屋を作る
区画の分割が終わったら、次に部屋を作っていきます。
区画を最低6マス取っていたのは、部屋のサイズを最低4マスにするためです。
4マス未満にならないように乱数を使って適当な大きさの部屋を作ったり作らなかったりしていきます。
4つの区画のうち、3つの区画に部屋ができました。
出入り口を作る
部屋ができたところで、通路から部屋に入るための出入り口を作ります。
最低1本の通路ができるように乱数を使って適当に配置していきます。
通路が作れました。
余分な通路を削除する
このままではマップの端まで通路が続いてしまっているので、マップの端に接している通路を部屋への入り口、または他の通路との交差点まで消しこんでいきます。
今回の対象は×をつけたマスになります。
×をつけたマスを消しました。これで完成です。
全ての通路と部屋を同じ色で塗れば・・・
ほら、まさにローグライクのマップみたいでしょう？
こんな感じで生成すればそれなりのマップが作れます。
それでは肝心のソースコードの説明に移っていこうと思います。
マップ自動生成のコード
ソースコードは C# で記述しています。
といっても JavaScript でも書き方こそ違えど、やっていることは一緒なのでほとんど移植でできると思います。
大きな区画に分割する
区画の分割は下記の順序で処理していきます。
- 区画の List を作り、初期値としてマップ全体を入れる
- List を回し、区画を縮小すると同時に縮小した部分を新しい区画として List に追加する
- 区画がある程度増えるまで 2. を繰り返す
- 最大部屋数を上回るか、区画が分割できなくなったら終了
public void CreateRange(int maxRoom) {
// 区画のリストの初期値としてマップ全体を入れる
rangeList.Add(new Range(0, 0, mapSizeX - 1, mapSizeY - 1));
bool isDevided;
do {
// 縦 → 横 の順番で部屋を区切っていく。一つも区切らなかったら終了
isDevided = DevideRange(false);
isDevided = DevideRange(true) || isDevided;
// もしくは最大区画数を超えたら終了
if (rangeList.Count >= maxRoom) {
break;
}
} while (isDevided);
}
public bool DevideRange(bool isVertical) {
bool isDevided = false;
// 区画ごとに切るかどうか判定する
List<Range> newRangeList = new List<Range>();
foreach (Range range in rangeList) {
// これ以上分割できない場合はスキップ
if (isVertical && range.GetWidthY() < MINIMUM_RANGE_WIDTH * 2 + 1) {
continue;
} else if (!isVertical && range.GetWidthX() < MINIMUM_RANGE_WIDTH * 2 + 1) {
continue;
}
// 40％の確率で分割しない // ただし、区画の数が1つの時は必ず分割する
if (rangeList.Count > 1 && RogueUtils.RandomJadge(0.4f)) {
continue;
}
// 長さから最少の区画サイズ2つ分を引き、残りからランダムで分割位置を決める
int length = isVertical ? range.GetWidthY() : range.GetWidthX();
int margin = length - MINIMUM_RANGE_WIDTH * 2;
int baseIndex = isVertical ? range.Start.Y : range.Start.X;
int devideIndex = baseIndex + MINIMUM_RANGE_WIDTH + RogueUtils.GetRandomInt(1, margin) - 1;
// 分割された区画の大きさを変更し、新しい区画を追加リストに追加する
// 同時に、分割した境界を通路として保存しておく
Range newRange = new Range();
if (isVertical) {
passList.Add(new Range(range.Start.X, devideIndex, range.End.X, devideIndex));
newRange = new Range(range.Start.X, devideIndex + 1, range.End.X, range.End.Y);
range.End.Y = devideIndex - 1;
} else {
passList.Add(new Range(devideIndex, range.Start.Y, devideIndex, range.End.Y));
newRange = new Range(devideIndex + 1, range.Start.Y, range.End.X, range.End.Y);
range.End.X = devideIndex - 1;
}
// 追加リストに新しい区画を退避する。
newRangeList.Add(newRange);
isDevided = true;
}
// 追加リストに退避しておいた新しい区画を追加する。
rangeList.AddRange(newRangeList);
return isDevided;
}
区画に部屋を作る
次に区画に部屋を配置していきます。
部屋の配置は下記の順番で処理します。
- 区画のリストをシャッフルする
（最初の区画には必ず部屋を作るため） - シャッフルした区画のリストを回す
- 区画に部屋を作るかどうかの判定を行う
（一つも部屋がない or 70％の確率で部屋を作る） - 部屋を作る場合は区画の中にランダムな大きさの部屋を作る
- 全ての区画に対して処理が終わったら終了
private void CreateRoom() {
// 部屋のない区画が偏らないようにリストをシャッフルする
rangeList.Sort((a, b) => RogueUtils.GetRandomInt(0, 1) - 1);
// 1区画あたり1部屋を作っていく。作らない区画もあり。
foreach (Range range in rangeList) {
// 30％の確率で部屋を作らない
// ただし、最大部屋数の半分に満たない場合は作る
if (roomList.Count > maxRoom / 2 && RogueUtils.RandomJadge(0.3f)) {
continue;
}
// 猶予を計算
int marginX = range.GetWidthX() - MINIMUM_RANGE_WIDTH + 1;
int marginY = range.GetWidthY() - MINIMUM_RANGE_WIDTH + 1;
// 開始位置を決定
int randomX = RogueUtils.GetRandomInt(1, marginX);
int randomY = RogueUtils.GetRandomInt(1, marginY);
// 座標を算出
int startX = range.Start.X + randomX;
int endX = range.End.X - RogueUtils.GetRandomInt(0, (marginX - randomX)) - 1;
int startY = range.Start.Y + randomY;
int endY = range.End.Y - RogueUtils.GetRandomInt(0, (marginY - randomY)) - 1;
// 部屋リストへ追加
Range room = new Range(startX, startY, endX, endY);
roomList.Add(room);
// 通路を作る
CreatePass(range, room);
}
}
出入り口を作る
次に部屋から通路に伸びる出入り口を作っていきます。
先ほどの最後にある「CreatePass」から処理が繋がっています。
通路を作る処理は以下の順番で行います。
- 部屋に対して伸ばせる通路の向きを確認する
（マップの端に位置する区画では端に向けて通路は延ばせない） - 伸ばせる通路の向きを List に入れ、シャッフルする
（最初の方向は必ず通路を作るため） - 伸ばせる通路の向きに対して通路を作るかどうか判定する
（最初の通路 or 20％の確率で通路を作る） - 通路を作る場合は通路を追加する
- 全ての部屋に対して判定が終わったら終了
private void CreatePass(Range range, Range room) {
List<int> directionList = new List<int>();
if (range.Start.X != 0) {
// Xマイナス方向
directionList.Add(0);
}
if (range.End.X != mapSizeX - 1) {
// Xプラス方向
directionList.Add(1);
}
if (range.Start.Y != 0) {
// Yマイナス方向
directionList.Add(2);
}
if (range.End.Y != mapSizeY - 1) {
// Yプラス方向
directionList.Add(3);
}
// 通路の有無が偏らないよう、リストをシャッフルする
directionList.Sort((a, b) => RogueUtils.GetRandomInt(0, 1) - 1);
bool isFirst = true;
foreach (int direction in directionList) {
// 80%の確率で通路を作らない
// ただし、まだ通路がない場合は必ず作る
if (!isFirst && RogueUtils.RandomJadge(0.8f)) {
continue;
} else {
isFirst = false;
}
// 向きの判定
int random;
switch (direction) {
case 0: // Xマイナス方向
random = room.Start.Y + RogueUtils.GetRandomInt(1, room.GetWidthY()) - 1;
roomPassList.Add(new Range(range.Start.X, random, room.Start.X - 1, random));
break;
case 1: // Xプラス方向
random = room.Start.Y + RogueUtils.GetRandomInt(1, room.GetWidthY()) - 1;
roomPassList.Add(new Range(room.End.X + 1, random, range.End.X, random));
break;
case 2: // Yマイナス方向
random = room.Start.X + RogueUtils.GetRandomInt(1, room.GetWidthX()) - 1;
roomPassList.Add(new Range(random, range.Start.Y, random, room.Start.Y - 1));
break;
case 3: // Yプラス方向
random = room.Start.X + RogueUtils.GetRandomInt(1, room.GetWidthX()) - 1;
roomPassList.Add(new Range(random, room.End.Y + 1, random, range.End.Y));
break;
}
}
}
余分な通路を削除する
最後に余分な通路を削除していきます。
通路の削除は以下の順番で処理していきます。
- 通路のリストを最後に追加された順番で回す
- 通路が部屋の入り口に接しているか判定する
- どの部屋からも接続されなかった通路を削除する
- 全ての通路を処理したら終了
- 次にマップの外周に接している通路を探す
- マップの外周に接している通路を部屋の入り口、または別の通路との交差点まで削除する
- 外周を全てチェックし終わったら終了
と、ここまでの結果をいったん2次元配列に反映しています。
隣り合ったセルが壁か床かを判断するためです。
（ソースコード内では int[,] map）
private void TrimPassList(ref int[,] map) {
// どの部屋通路からも接続されなかった通路を削除する
for (int i = passList.Count - 1; i >= 0; i--) {
Range pass = passList[i];
bool isVertical = pass.GetWidthY() > 1;
// 通路が部屋通路から接続されているかチェック
bool isTrimTarget = true;
if (isVertical) {
int x = pass.Start.X;
for (int y = pass.Start.Y; y <= pass.End.Y; y++) {
if (map[x - 1, y] == 1 || map[x + 1, y] == 1) {
isTrimTarget = false;
break;
}
}
} else {
int y = pass.Start.Y;
for (int x = pass.Start.X; x <= pass.End.X; x++) {
if (map[x, y - 1] == 1 || map[x, y + 1] == 1) {
isTrimTarget = false;
break;
}
}
}
// 削除対象となった通路を削除する
if (isTrimTarget) {
passList.Remove(pass);
// マップ配列からも削除
if (isVertical) {
int x = pass.Start.X;
for (int y = pass.Start.Y; y <= pass.End.Y; y++) {
map[x, y] = 0;
}
} else {
int y = pass.Start.Y;
for (int x = pass.Start.X; x <= pass.End.X; x++) {
map[x, y] = 0;
}
}
}
}
// 外周に接している通路を別の通路との接続点まで削除する
// 上下基準
for (int x = 0; x < mapSizeX - 1; x++) {
if (map[x, 0] == 1) {
for (int y = 0; y < mapSizeY; y++) { if (map[x - 1, y] == 1 || map[x + 1, y] == 1) { break; } map[x, y] = 0; } } if (map[x, mapSizeY - 1] == 1) { for (int y = mapSizeY - 1; y >= 0; y--) {
if (map[x - 1, y] == 1 || map[x + 1, y] == 1) {
break;
}
map[x, y] = 0;
}
}
}
// 左右基準
for (int y = 0; y < mapSizeY - 1; y++) {
if (map[0, y] == 1) {
for (int x = 0; x < mapSizeY; x++) { if (map[x, y - 1] == 1 || map[x, y + 1] == 1) { break; } map[x, y] = 0; } } if (map[mapSizeX - 1, y] == 1) { for (int x = mapSizeX - 1; x >= 0; x--) {
if (map[x, y - 1] == 1 || map[x, y + 1] == 1) {
break;
}
map[x, y] = 0;
}
}
}
}
これできれいなマップの形になるので、マップの2次元配列を返却すればあとはゲーム側でそれに合わせてマップを描画するだけになります。
ここまでの進捗
マップの自動生成ロジックが出来上がりました。
記事の中では紹介していないユーティリティクラスなんかもありますので、興味のある方はぜひ GitHub からソースコードを落としてみてください。
kurage1119/sample-unity-roguelike
今回実装した処理の大部分は「MapGenerator.cs」に入っています。
次回は「タップした場所にキャラクターを移動させる」をやってみたいと思います。
ではまた。
コメント