(cache) ダンジョン生成してみよう

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

考え方

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

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

今回の作成結果

ダンジョン生成

問題点

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

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

今回書いたソース

参考書籍

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

ソース

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

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

public class DungeonTileData {
  var isWall:boolean;               //壁ならTrue
  var isStepUp:boolean;         //上階段ならTrue;
  var isStepDown:boolean;           //下階段ならTrue

  public function DungeonTileData() {

  }
}

DungeonRect.js

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

//ダンジョンの区画情報
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

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

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();
      //区画を作る
      //まずは全体を１つの区画にする
      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 = parent.rect_left + minRoomSize + 2;

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

          // ＡＢの距離を求める
          ab = b - a;
          if(maxRoomSize < ab) ab = maxRoomSize;
          
          // ＡＢ間のどこかに決定する
          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 =  parent.rect_top + minRoomSize + 2;

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

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

          // ＡＢ間のどこかに決定する
          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 );
      
  }
  
  //全体を１つの区画にする
  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

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);
      }
  }
}