目前还没有将房间连接起来，但是它使用所描述的算法生成了不错的地下城。（不幸的是，它是用Java编写的，但我尝试添加了一些注释来澄清正在进行的操作。）
public static class Rectangle {
private static int MIN_SIZE = 5;
private static Random rnd = new Random();
private int top, left, width, height;
private Rectangle leftChild;
private Rectangle rightChild;
private Rectangle dungeon;
public Rectangle(int top, int left, int height, int width) {
this.top = top;
this.left = left;
this.width = width;
this.height = height;
}
public boolean split() {
if( leftChild != null ) //if already split, bail out
return false;
boolean horizontal = rnd.nextBoolean(); //direction of split
int max = (horizontal ? height : width ) - MIN_SIZE; //maximum height/width we can split off
if( max <= MIN_SIZE ) // area too small to split, bail out
return false;
int split = rnd.nextInt( max ); // generate split point
if( split < MIN_SIZE ) // adjust split point so there's at least MIN_SIZE in both partitions
split = MIN_SIZE;
if( horizontal ) { //populate child areas
leftChild = new Rectangle( top, left, split, width );
rightChild = new Rectangle( top+split, left, height-split, width );
} else {
leftChild = new Rectangle( top, left, height, split );
rightChild = new Rectangle( top, left+split, height, width-split );
}
return true; //split successful
}
public void generateDungeon() {
if( leftChild != null ) { //if current are has child areas, propagate the call
leftChild.generateDungeon();
rightChild.generateDungeon();
} else { // if leaf node, create a dungeon within the minimum size constraints
int dungeonTop = (height - MIN_SIZE <= 0) ? 0 : rnd.nextInt( height - MIN_SIZE);
int dungeonLeft = (width - MIN_SIZE <= 0) ? 0 : rnd.nextInt( width - MIN_SIZE);
int dungeonHeight = Math.max(rnd.nextInt( height - dungeonTop ), MIN_SIZE );;
int dungeonWidth = Math.max(rnd.nextInt( width - dungeonLeft ), MIN_SIZE );;
dungeon = new Rectangle( top + dungeonTop, left+dungeonLeft, dungeonHeight, dungeonWidth);
}
}
}
这里是一个测试类，用于演示其用法：
import java.util.ArrayList;
import java.util.Random;
public class GenerateDungeon {
private static Random rnd = new Random();
public static void main(String[] args) {
ArrayList<Rectangle> rectangles = new ArrayList<Rectangle>(); // flat rectangle store to help pick a random one
Rectangle root = new Rectangle( 0, 0, 60, 120 ); //
rectangles.add( root ); //populate rectangle store with root area
while( rectangles.size() < 19 ) { // this will give us 10 leaf areas
int splitIdx = rnd.nextInt( rectangles.size() ); // choose a random element
Rectangle toSplit = rectangles.get( splitIdx);
if( toSplit.split() ) { //attempt to split
rectangles.add( toSplit.leftChild );
rectangles.add( toSplit.rightChild );
}
}
root.generateDungeon(); //generate dungeons
printDungeons(rectangles); //this is just to test the output
}
private static void printDungeons(ArrayList<Rectangle> rectangles) {
byte [][] lines = new byte[60][];
for( int i = 0; i < 60; i++ ) {
lines[ i ] = new byte[120];
for( int j = 0; j < 120; j++ )
lines[ i ][ j ] = -1;
}
byte dungeonCount = -1;
for( Rectangle r : rectangles ) {
if( r.dungeon == null )
continue;
Rectangle d = r.dungeon;
dungeonCount++;
for( int i = 0; i < d.height; i++ ) {
for( int j = 0; j < d.width; j++ )
lines[ d.top + i ][ d.left+ j ] = dungeonCount;
}
}
for( int i = 0; i < 60; i++ ) {
for( int j = 0; j < 120; j++ ) {
if( lines[ i ][ j ] == -1 )
System.out.print( '.');
else
System.out.print( lines[ i ][ j ] );
}
System.out.println();
}
}
}
你在Java中的版本帮助了我，并且我决定用C#草图绘制它，也许会对其他人有帮助。
public class BspTree
{
public RectInt container;
public RectInt room;
public BspTree left;
public BspTree right;
public BspTree(RectInt a)
{
container = a;
}
internal static BspTree Split(int numberOfOperations, RectInt container)
{
var node = new BspTree(container);
if (numberOfOperations == 0)
{
return node;
}
var splitedContainer = SplitContainer(container);
node.left = Split(numberOfOperations - 1, splitedContainer[0]);
Debug.Log(numberOfOperations);
node.right = Split(numberOfOperations - 1, splitedContainer[1]);
Debug.Log(numberOfOperations);
return node;
}
private static RectInt[] SplitContainer(RectInt container)
{
RectInt c1, c2;
bool horizontal = Random.Range(0f, 1f) > 0.5f ? true : false;
if (horizontal)
{
c1 = new RectInt(container.x, container.y, (int)(container.width * Random.Range(0.3f, 0.6f)), container.height);
c2 = new RectInt(container.x + c1.width, container.y, container.width - c1.width, container.height);
}
else
{
c1 = new RectInt(container.x, container.y, container.width, (int)(container.height * Random.Range(0.3f, 0.6f)));
c2 = new RectInt(container.x, container.y + c1.height, container.width, container.height - c1.height);
}
return new RectInt[] { c1, c2 };
}
并将其与Monobehaviour统一使用
public class DungeonCreator : MonoBehaviour
{
[Range (1, 400)]
public int widthRange;
public bool shouldDebugDrawBsp;
private BspTree tree;
void Start()
{
RectInt rect = new RectInt(0, 0, widthRange, widthRange);
tree = BspTree.Split(4, rect);
}
public void DebugDrawBsp()
{
if (tree == null) return;
DebugDrawBspNode(tree);
}
public void DebugDrawBspNode(BspTree node)
{
// Container
Gizmos.color = Color.green;
// top
Gizmos.DrawLine(new Vector3(node.container.x, node.container.y, 0), new Vector3Int(node.container.xMax, node.container.y, 0));
// right
Gizmos.DrawLine(new Vector3(node.container.xMax, node.container.y, 0), new Vector3Int(node.container.xMax, node.container.yMax, 0));
// bottom
Gizmos.DrawLine(new Vector3(node.container.x, node.container.yMax, 0), new Vector3Int(node.container.xMax, node.container.yMax, 0));
// left
Gizmos.DrawLine(new Vector3(node.container.x, node.container.y, 0), new Vector3Int(node.container.x, node.container.yMax, 0));
// children
if (node.left != null) DebugDrawBspNode(node.left);
if (node.right != null) DebugDrawBspNode(node.right);
}
private void OnDrawGizmos()
{
if (shouldDebugDrawBsp)
{
DebugDrawBsp();
}
}
}