Simple example of BSP dungeon generation
質問
I was originally trying to follow this algorithm to create a little simple roguelike dungeon in C#. But I guess I'm just too stupid, because my result always came out a jumbled mess of crap.
I then switched over to my own algorithm, which produces not-great but semi-recognizable-as-a-dungeon results.
Does anyone have any examples of doing it the BSP way, as described in the linked article? It would be best if it weren't encumbered by a bunch of game details/library calls, because (again) I'm stupid.
(If you're especially masochistic and want me to post the code I had, I can, but I figured it'd be too much for an SO question.)
解決
This doesn't link the rooms yet, but it generates okay dungeons using the algorithm described. (Unfortunately it is in Java but I tried to add some comments to clarify what is being done.)
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);
}
}
}
And here's a test class to demonstrate its usage:
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();
}
}
}