ダンジョンを自動生成するアルゴリズム
ローグライクゲームに出てくるようなダンジョンを自動で生成するアルゴリズムを作ってみました。
生成例
ソースコード
package Blog; import java.util.*; import static java.lang.System.*; public class Blog { //ダンジョンの大きさ static int h = 20; static int w = 40; //部屋の幅の最小値（実際はこの値から2を引いたもの） static int roomSize = 5; //その他、変数など static char[][] map = new char[h][w]; static int[] dx = {0,1,0,-1}; static int[] dy = {-1,0,1,0}; public static void main(String[] args) { //最初に、マップを壁で埋める for (int i=0; i<h; i++) { for (int j=0; j<w; j++) { map[i][j] = '#'; } } //マップを複数のエリアに分割する //具体的にどういう処理をしているかというと、 // //①エリアAを、BとCに2分割する（splitVorHが偶数なら縦分割） //②新しくできたBとCのうち、片方を二度と分割できないようにする（Bとする） //③エリアCを、DとEに2分割する…… // //というような具合。 //エリアBとCを次で両方とも分割する仕様だと、部屋数が増えすぎるのでこのようにした。 //分割方向については、縦分割と横分割を交互にやらないと密室が発生してしまうのでこのようにした。 Deque<Area> areas = new ArrayDeque<>(); areas.addLast(new Area(new Point(0,0),new Point(w-1,h-1),false)); Random rnd = new Random(); int splitVorH = rnd.nextInt(2); while (true) { Area temp = null; for (Area area : areas) { if (area.canSplitVorH('V') || area.canSplitVorH('H')) { if (!area.splitEnd) temp = area; } } if (temp == null) break; areas.remove(temp); return2Area ra; if (splitVorH%2 == 0) { if (temp.canSplitVorH('V') && !temp.splitEnd) { //エリアを縦に分割 ra = temp.splitArea('V'); areas.addLast(ra.a); areas.addLast(ra.b); } else { //縦と横交互にと書いたが、実際はこの部分で横分割の判定も行うようになっている。 if (temp.canSplitVorH('H') && !temp.splitEnd) { ra = temp.splitArea('H'); areas.addLast(ra.a); areas.addLast(ra.b); } } } else { if (temp.canSplitVorH('H') && !temp.splitEnd) { //エリアを横に分割 ra = temp.splitArea('H'); areas.add(ra.a); areas.add(ra.b); } else { //こちらは縦分割の判定（横分割できなかった場合はここを実行） if (temp.canSplitVorH('V') && !temp.splitEnd) { ra = temp.splitArea('V'); areas.add(ra.a); areas.add(ra.b); } } } splitVorH++; } //各エリアごとに部屋の大きさを決め、部屋中央の座標を特定してリストに格納 List<Point> roomCenter = new ArrayList<>(); for (Area area : areas) { int h = rnd.nextInt(area.Height-(roomSize-1)) + (roomSize-2); int w = rnd.nextInt(area.Width-(roomSize-1)) + (roomSize-2); int sx = rnd.nextInt(area.botR.x-area.topL.x-w) + (area.topL.x + 1); int sy = rnd.nextInt(area.botR.y-area.topL.y-h) + (area.topL.y + 1); for (int i=0; i<h; i++) { for (int j=0; j<w; j++) { map[i+sy][j+sx] = '.'; if (i==h/2 && j==w/2) { roomCenter.add(new Point(j+sx,i+sy)); } } } } //部屋中央から通路へ道を伸ばす（ランダム） for (int i=0; i<roomCenter.size(); i++) { //上下左右どれから伸ばすかは、Collection.shuffle()で実装 ArrayList<Integer> list = new ArrayList<Integer>() {{ add(0); add(1); add(2); add(3); }}; Collections.shuffle(list); loop : for (int k=0; k<4; k++) { int y = roomCenter.get(i).y; int x = roomCenter.get(i).x; while (true) { y += dy[list.get(k)]; x += dx[list.get(k)]; //通路に行き当たらず、配列外に出てしまった場合はまた違う方向に伸ばす if (y<0 || y>h-1 || x<0 || x>w-1) { break; } else { if (map[y][x] == 'x') { map[y][x] = 'e'; x = roomCenter.get(i).x; y = roomCenter.get(i).y; while (true) { y += dy[list.get(k)]; x += dx[list.get(k)]; if (map[y][x]=='e') { break loop; } map[y][x] = '.'; } } } } } } //配列の範囲外へと繋がっている通路を塗りつぶしていく //移動先の座標が分かれ道か、あるいはeになるまで、#で埋めていく for (int i=0; i<w; i++) { if (map[0][i]=='x') { rec(0,i); } if (map[h-1][i]=='x') { rec(h-1,i); } } for (int i=0; i<h; i++) { if (map[i][0]=='x') { rec(i,0); } if (map[i][w-1]=='x') { rec(i,w-1); } } //最後に残ったeとxを道に変換しつつ、出力して終了 out.println(); out.println(); for (int i=0; i<h; i++) { out.print(" "); for (int j=0; j<w; j++) { if (map[i][j] != '#') map[i][j] = '.'; out.print(map[i][j]); } out.println(); } } //eもしくは分かれ道に行き当たるまで通路を壁で埋める再帰関数 static void rec(int y, int x) { if (y<0 || x<0 || h<=y || w<=x) {return;} if (map[y][x]=='e' || map[y][x]=='#') {return;} int n = 0; for (int i=0; i<4; i++) { int ty = y + dy[i]; int tx = x + dx[i]; if (ty<0 || tx<0 || h<=ty || w<=tx) {continue;} if (map[ty][tx]=='x' || map[ty][tx]=='e' || map[ty][tx]=='.') n++; } if (n >= 2) return; map[y][x] = '#'; rec(y,x+1); rec(y,x-1); rec(y+1,x); rec(y-1,x); } } //Areaクラス。 //メンバは、左上の座標・右下の座標・横幅・縦幅。 //メソッドは、縦あるいは横で分割可能かを判定するcanSplitVorHと、 //自らを2分割してその結果得られる2つのエリアを他クラスに格納するsplitArea。 class Area { Point topL; Point botR; int Width; int Height; boolean splitEnd; public Area(Point tl, Point br, boolean a) { this.topL = tl; this.botR = br; this.Width = br.x - tl.x + 1; this.Height = br.y - tl.y + 1; this.splitEnd = a; } public boolean canSplitVorH(char VorH) { if (VorH=='V') {if (Width>=Blog.roomSize*2+1) return true;} else {if (Height>=Blog.roomSize*2+1) return true;} return false; } public return2Area splitArea(char VorH) { Random rnd = new Random(); Area a; Area b; int temp = rnd.nextInt(2); if (VorH == 'V') { int x = rnd.nextInt(Width-Blog.roomSize*2) + Blog.roomSize; for (int i=topL.y; i<=botR.y; i++) { Blog.map[i][topL.x+x] = 'x'; } a = new Area(topL,new Point(x-1+topL.x,botR.y),temp==0?true:false); b = new Area(new Point(x+1+topL.x,topL.y),botR,temp==0?false:true); } else { int y = rnd.nextInt(this.Height-Blog.roomSize*2) + Blog.roomSize; for (int i=topL.x; i<=botR.x; i++) { Blog.map[topL.y+y][i] = 'x'; } a = new Area(topL,new Point(botR.x,topL.y+y-1),temp==0?true:false); b = new Area(new Point(topL.x,topL.y+y+1),botR,temp==0?false:true); } return2Area ra = new return2Area(a,b); return ra; } } //エリアを分割すると戻り値が2つになるので、それを受け取るクラスを作った。 class return2Area { Area a; Area b; return2Area(Area a, Area b) { this.a = a; this.b = b; } } //座標クラス。 class Point { int x; int y; Point(int a, int b) { this.x = a; this.y = b; } }
このアルゴリズムで生成されるダンジョンの特徴
・すべての部屋が連結している（密室がない）
・すべての部屋が長方形（ランダムな形、あるいは円形にできないこともないがめんどくさい）
・必ず通路＋部屋という構造になる（大部屋一つだけ、部屋同士が通路を介さずに繋がっている、通路だけ、などは生成されない）
