ダンジョン生成してみよう

ayumegu(プログラマー)
よろしくお願いします。

こんにちは、あゆめぐです。
今回はダンジョン生成の基本部分。
アルゴリズムそのまま実装したものの状態まで書きました。
はい、相変わらずjavascriptです。
どこかのタイミングでいい加減にc#にしないとな〜と思うんですがjavascriptそのままいろいろ持ってけて便利すぎるんだ〜。
ほら私が好きなActionScript3.0もenchant.jsにしてもjavascript系だからね。

考え方

ダンジョンマップを生成するアルゴリズムの解説
こちらの二分割を繰り返す方法の方です。  
しかしながらこの実装だとアルゴリズムばればれなのでここからいろいろカスタマイズしないと。
均等に分割する方法はまだ作成していないので気が向いたときにやってみようかと思います。

他にもダンジョン生成にはいろんなアルゴリズムがあって
迷路自動生成アルゴリズム
上記サイトのような本当にダンジョンというのもあります。いや〜こういうの行き止まりばっかりでいらっとしてしまう私であります。

今回の作成結果

ダンジョン生成

問題点

  • 区画が二分割になっていくので最初の区画が大きかったりすると3つのルームしかなかったりしてしまう。
  • 道が一方通行しかない

ちょろっと処理追加すれば上記は解決するんですが。
私的には隣り合う区画同士しか道がないところをなんとかしたいんですよね〜。

今回書いたソース

参考書籍

  • ダンジョンゲームプログラミング(C++で書かれています)

ソース

ガーガーっと書いたのでリファクタリングとかしてないですがw
メソッドや変数の命名規則が自分の中でもあまり統率がとれていないw
DungeonTileData.js

一つのタイルを管理するクラスです
実際に運用するときはここにアイテム情報やトラップなどの情報も記載します

1
2
3
4
5
6
7
8
9
public class DungeonTileData {
  var isWall:boolean;               //壁ならTrue
  var isStepUp:boolean;         //上階段ならTrue;
  var isStepDown:boolean;           //下階段ならTrue

  public function DungeonTileData() {

  }
}

DungeonRect.js

区画を管理するクラスです。
区画の位置と中にある部屋の位置を持っています

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//ダンジョンの区画情報
public class DungeonRect {
  var rect_left:int;
  var rect_top:int;
  var rect_right:int;
  var rect_bottom:int;
  
  var room_left:int;
  var room_top:int;
  var room_right:int;
  var room_bottom:int;

  public function DungeonRect() {
  }
  
  //区画を設定
  public function setRect(left:int,top:int,right:int,bottom:int){
      rect_left = left;
      rect_top = top;
      rect_right = right;
      rect_bottom = bottom;
  }
  //部屋を設定
  public function setRoom(left:int,top:int,right:int,bottom:int){
      room_left = left;
      room_top = top;
      room_right = right;
      room_bottom = bottom;
  }
  
  //区域の幅を取得
  public function getRectW():int{
      return rect_right - rect_left;
  }
  
  //区域の高さを取得
  public function getRectH():int{
      return rect_bottom - rect_top;
  }
  
  //部屋の幅を取得
  public function getRoomW():int{
      return room_right - room_left;
  }
  
  //部屋の高さを取得
  public function getRoomH():int{
      return room_bottom - room_top;
  }
}

Dungeon.js

ダンジョン生成本体
説明はコメントでだいたい記載したので割愛。 階段はのぼりが適当なところ、下りが最後にできた部屋に配置しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
public class Dungeon{

  //-------------------マップ関連----------------------
  public var minRoomSize:int;           //最小部屋サイズ
  public var maxRoomSize:int;           //最大部屋サイズ
  public var mapWidth:int;          //アップの幅
  public var mapHeight:int;         //アップの高さ
  public var mapData:Array;         //マップデータ
  public var tileRectList:Array;        //区画情報

  private var m_upStepX:int;
  private var m_upStepY:int;
  private var m_downStepX:int;
  private var m_downStepY:int;

  function Dungeon(){
      mapData = new Array();
      minRoomSize = 3;
      maxRoomSize = 5;
      mapWidth = 30;
      mapHeight = 30;
  }    
  
  function CreateDungeon():Array{
      //一度全てを壁に
      AllWall();
      
      tileRectList = new Array();
      //区画を作る
      //まずは全体を1つの区画にする
      CreateRect(0, 0, mapWidth-1, mapHeight-1);
      
      //再起でどんどん区画を細かくする
      var i = Random.Range(0,2);
      var flag:boolean;
      if(i == 0){
          flag = false;
      }else if(i == 1){
          flag = true;
      }
      SplitRect(flag);
      
      Debug.Log("分割数" + tileRectList.length);
      
      //部屋を作る
      CreateRoom();
      
      //部屋同士をつなげる
      ConnectRoom();
      
      return mapData;
  }
  
  function GetTileData(x:int, y:int):DungeonTileData{
      return mapData[x + y * mapWidth];
  }
  
  // 指定矩形を壁か道にする(right,bottom自体のマスは塗らない)
  private function FillRect(left:int, top:int, right:int, bottom:int, isWall:boolean, isRoom:boolean):void{
      var x:int;
      var y:int;
      var tmp:int;
      if( left > right ){
          tmp = left;
          left = right;
          right = tmp;
      }
      if( top > bottom ){
          tmp = top;
          top = bottom;
          bottom = tmp;
      }

      for( y=top; y<bottom; y++ ){
          for( x=left; x<right; x++ ){
              
              var tile:DungeonTileData = mapData[y * mapWidth + x];
              tile.isWall = isWall;
              tile.isRoom = isRoom;
          }
      }
  }


  //区画から部屋を作る
  private function CreateRoom():void{
      var i:int;
      var w:int;
      var h:int;
      var cw:int;
      var ch:int;
      var sw:int;
      var sh:int;
      var rw:int;
      var rh:int;
      var rx:int;
      var ry:int;
      var rect:DungeonRect;
      var upStepRect:int = Random.Range(0, tileRectList.length - 1);
      for( i=0; i<tileRectList.length; i++ ){
          rect = tileRectList[i];
          //Debug.Log("区画の位置:左" + rect.rect_left + " 右" + rect.rect_right + " 上" + rect.rect_top + " 下" + rect.rect_bottom);
          // 矩形の大きさを計算 壁1ます 空き1ます 分割線1ますあける
          w = rect.getRectW() - 3;
          h =  rect.getRectH() - 3;
          
          // 区画に入る最小部屋の余裕を求める
          cw = w - minRoomSize;
          ch = h - minRoomSize;
          // Debug.Log("部屋の大きさの余裕は 横:" + cw + "縦:" + ch);
          // 部屋の大きさを決定する
          sw = Random.Range(0, cw) + minRoomSize;
          sh =  Random.Range(0, ch) + minRoomSize;
          if(sw > maxRoomSize) sw = maxRoomSize;
          if(sh > maxRoomSize) sh = maxRoomSize;
          
          Debug.Log("部屋の大きさは 横:" + sw + "縦:" + sh);
          rw = w - sw;
          rh = h - sh;
          
          // 部屋の位置を決定する 分割線1ますを除いた2ます分の補正
          rx = Random.Range(0, rw) + 2;
          ry = Random.Range(0, rh) + 2;
          var left:int = rect.rect_left + rx;
          var right:int = left + sw;
          var top:int =rect.rect_top + ry;
          var bottom:int = top + sh;
  
          // 求めた結果から部屋の情報を設定
          rect.setRoom(left, top, right, bottom);

          // 部屋を作る
          FillRect( rect.room_left, rect.room_top, rect.room_right, rect.room_bottom, false ,true);

          // のぼり階段設置する部屋なら適当な位置に上階段を配置
          var x:int;
          var y:int;
          if( i == upStepRect ){
              x = Random.Range(0, sw);
              y = Random.Range(0, sh);
              m_upStepX = rect.room_left + x;
              m_upStepY = rect.room_top + y;
              var tile:DungeonTileData = GetTileData(m_upStepX, m_upStepY);
              tile.isStepUp = true;
          }

          // 最後の部屋なら適当な位置に下階段を配置
          if( i ==tileRectList.length-1 ){
              x = Random.Range(0, sw);
              y = Random.Range(0, sh);
              m_downStepX = rect.room_left + x;
              m_downStepY = rect.room_top + y;
              tile = GetTileData(m_downStepX, m_downStepY);
              tile.isStepDown = true;
          }
      }
  }
  
  //道を作成する
  private function CreateRoad(rectANo:int, rectBNo:int):void{
      var rectA:DungeonRect = tileRectList[rectANo];
      var rectB:DungeonRect = tileRectList[rectBNo];
      
      // 区画は上下か左右のどちらで繋がっているかで処理をわける
      //上下でつながっているか?
      if(rectA.rect_bottom == rectB.rect_top ||  rectA.rect_top == rectB.rect_bottom){
          var x1:int;
          var x2:int;
          var y:int;
          
          //道の開始位置  // TODO or left right
          x1 = Random.Range(0, rectA.getRoomW()) + rectA.room_left;
          x2 = Random.Range(0, rectB.getRoomW()) + rectB.room_left;
          
          //rectAとrectBの位置関係
          if( rectA.rect_top > rectB.rect_top ){
              // B
              // A
              y = rectA.rect_top;
              FillRect( x1, y+1, x1+1, rectA.room_top, false, false);   // Aと横道をつなぐ道を作る
              FillRect( x2, rectB.room_bottom, x2+1, y, false, false); // Bと横道をつなぐ道を作る
          }else{
              // A
              // B
              y = rectB.rect_top;
              FillRect( x1,  rectA.room_bottom, x1+1, y, false, false);
              FillRect( x2, y, x2+1, rectB.room_top, false, false);
          }
          FillHLine( x1, x2, y, false );   // 横道を作る

      // 左右で左右で繋がっているか?
      }else if(rectA.rect_left == rectB.rect_right ||  rectA.rect_right == rectB.rect_left){
          var y1:int;
          var y2:int;
          var x:int;
          
          //道の開始位置 // or up down
          y1 = Random.Range(0, rectA.getRoomH()) + rectA.room_top;
          y2 = Random.Range(0, rectB.getRoomH()) + rectB.room_top;
          
          //rectAとrectBの位置関係
          if( rectA.rect_left > rectB.rect_left ){
              // BA
              x = rectA.rect_left;
              FillRect( rectB.room_right, y2, x, y2+1, false ,false);
              FillRect( x+1, y1, rectA.room_left, y1+1, false ,false);
          }else{
              // AB
              x = rectB.rect_left;
              FillRect( rectA.room_right, y1, x, y1+1, false ,false);
              FillRect( x, y2, rectB.room_left, y2+1, false ,false);
          }
          FillVLine( y1, y2, x, false);    // 横道を作る
      }
      
  }
  
  // 指定の横を壁か道にする
  private function FillHLine( left:int,  right:int, y:int, isWall:boolean):void{
      var x:int;
      var tmp:int;
      if( left > right ){
          tmp = left;
          left = right;
          right = tmp;
      }
      for( x=left; x<=right; x++ ){
          var tile:DungeonTileData = mapData[y * mapWidth + x];
          tile.isWall = isWall;
      }
  }
  
  // 指定の縦を壁か道にする
  private function FillVLine( top:int, bottom:int, x:int, isWall:boolean):void{
      var y:int;
      var tmp:int;
      if( top > bottom ){
          tmp = top;
          top = bottom;
          bottom = tmp;
      }
      for( y=top; y<=bottom; y++ ){
          var tile:DungeonTileData = mapData[y * mapWidth + x];
          tile.isWall = isWall;
      }
  }


  //部屋同士をつなげる
  private function ConnectRoom():void{
      for( var i:int =0; i<tileRectList.length -1; i++ ){
          CreateRoad( i, i+1 );
      }
  }

  
  //区画を二分割にする
  private function SplitRect(isVertical:boolean):void{
      //分ける区画情報を取得
      var parent:DungeonRect;
      parent = tileRectList[tileRectList.length -1];

      var a:int;
      var b:int;
      var ab:int;
      var p:int;
      var child:DungeonRect;
      
      //分割する
      if(isVertical){        //横に分割
          // 区分を分割できるかのチェック
          if( parent.getRectW() < (minRoomSize+3)*2+1 ){
              // 分割できるほど今の区画は広くないので終了
              return;
          }
          // 左端のA点を求める 最小の部屋のサイズと通路の分は取っておく
          a = parent.rect_left + minRoomSize + 2;

          // 右端のB点を求める 
          b = parent.rect_right - minRoomSize - 2;

          // ABの距離を求める
          ab = b - a;
          if(maxRoomSize < ab) ab = maxRoomSize;
          
          // AB間のどこかに決定する
          p = a + Random.Range(0, ab) + 1;
          // 新しく右の区画を作成する
          child = new DungeonRect();
          child.setRect( p, parent.rect_top, parent.rect_right,  parent.rect_bottom);
          tileRectList.push(child);

          // 元の区画の右を p 地点に移動させて、左側の区画とする
          parent.rect_right = child.rect_left;
      
      }else{             //縦に分割
          // 区分を分割できるかのチェック
          if( ( parent.getRectH()) < (minRoomSize+3)*2+1 ){
              // 分割できるほど今の区画は広くないので終了
              return;
          }
          // 上端のA点を求める 最小の部屋のサイズと通路の分は取っておく
          a =  parent.rect_top + minRoomSize + 2;

          // 下端のB点を求める 
          b = parent.rect_bottom - minRoomSize - 2;

          // ABの距離を求める
          ab = b - a;
          if(maxRoomSize < ab) ab = maxRoomSize;

          // AB間のどこかに決定する
          p = a + Random.Range(0, ab) + 1;
          // 新しく右の区画を作成する
          child= new DungeonRect();
      
          child.setRect(parent.rect_left, p, parent.rect_right,  parent.rect_bottom);
          tileRectList.push(child);

          // 元の区画の右を p 地点に移動させて、左側の区画とする
          parent.rect_bottom = child.rect_top;
      
      }
      
      // 次の分割をランダムで決定するために入れ替える
      if( Random.Range(0, 2)){
          var rect:DungeonRect = tileRectList[tileRectList.length - 1];
          tileRectList[tileRectList.length - 1]  = tileRectList[tileRectList.length - 2];
          tileRectList[tileRectList.length - 2]  = rect;
      }
      
      var rect1:DungeonRect = tileRectList[tileRectList.length-1];
      var rect2:DungeonRect = tileRectList[tileRectList.length-2];
      
      Debug.Log("できた区画1:左" + rect1.rect_left + " 右" + rect1.rect_right + " 上" + rect1.rect_top + " 下" + rect1.rect_bottom);
      Debug.Log("できた区画2:左" + rect2.rect_left + " 右" + rect2.rect_right + " 上" + rect2.rect_top + " 下" + rect2.rect_bottom);

      // 子の部屋をさらに分割する
      SplitRect( !isVertical );
      
  }
  
  //全体を1つの区画にする
  private function CreateRect(left:int, top:int, right:int, bottom:int):void{
      var dunRect:DungeonRect = new DungeonRect();
      dunRect.rect_left = 0;
      dunRect.rect_right = mapWidth - 1;
      dunRect.rect_top = 0;
      dunRect.rect_bottom = mapHeight - 1;
      tileRectList[0] = dunRect;
  }

  
  //全てを壁に
  function AllWall():void{
      for(var y:int = 0; y < mapHeight; y++){
          for(var x:int = 0; x < mapWidth; x++){
              var tileData:DungeonTileData = new DungeonTileData();
              mapData[y * mapWidth + x] = tileData;
              tileData.isWall = true;
          }
      }
  }
}

使い方

適当にタイルを2dToolkitで表示しただけですが
Manager.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var mapData:Array;   // dungeon
var tileObjList:Array;  // gameObjectList
function Start () {
  
  mapData = new Array();
  var dungeon:Dungeon = new Dungeon();
  tileObjList = new Array();
  dungeon.CreateDungeon();
  
  for(var y:int = 0; y < dungeon.mapHeight; y++){
      for(var x:int = 0; x < dungeon.mapWidth; x++){
          var tile:DungeonTileData = dungeon.GetTileData(x,y);
          var tileObj:GameObject = Instantiate(Resources.Load("Prefabs/Tile"));
  
          tileObj.transform.position.x = x;
          tileObj.transform.position.y = y;
          if(tile.isWall){
              tileObj.GetComponent(tk2dSprite).spriteId = 22;
          }else{
              tileObj.GetComponent(tk2dSprite).spriteId = 20;
          }
          
          
          // step
          if(tile.isStepUp){
              tileObj.GetComponent(tk2dSprite).spriteId = 145;
          }else if(tile.isStepDown){
              tileObj.GetComponent(tk2dSprite).spriteId = 156;
          }
          
          
          tileObjList.push(tileObj);
      }
  }
}

ちょちょっと

ちょちょっと前回のすごろく記事で作成した経路探索を組み込めばこんな感じになります。
掘っておくとあゆめぐちゃんが階段まで動きます。
通路の数ちょっと増やしています。
ダンジョン生成(経路探索入り)

今回の感想

さてさてこれをカスタマイズして好きなダンジョンを作れるようにならないとね。

あと個人用と会社用で複数macを使っているのでAirDropすごく便利!!と思いました。
それからwindowsだとunity簡単に複数起動できるのにmacだと簡単にいかなくて下記の記事にお世話になりました
Mac版のUnityで複数のプロジェクトを同時に開く方法

はい、今回はここまで〜。