BSP Room Generator v0.12

CSharp · Console

/Program.cs

//
// BSP Room Generator v0.12
// By Fangwei Lee
//

using System;
using System.Diagnostics;
using System.Drawing;
using System.Collections.Generic;

public struct Config
{
	public const int SEED = 7777;
	public const int MAP_WIDTH = 40;
	public const int MAP_HEIGHT =15;
	public const int MAX_LEAVES_COUNT = 100;
	public const int MIN_SIZE = 4; // so the min room size is N-1
	public const int MAX_SIZE = 20;
	public const float QUIT_RATE = 0.4f; // the possibility to quit splitting once big enough
	
	public const int SINGLE_DOOR_PROB = 2;
	public const int DOUBLE_DOOR_PROB = 1;
	public const int HALLWAY_DOOR_PROB = 2;
}

public struct R
{
	public static Random r;
}

//
// Main Program
//
public class Program
{
	//
	// Main Function
	//
	public static void Main()
	{
		Console.WriteLine("Room Generator v0.12 By Fangwei Lee\n");
		
		// Initialize random stream
		R.r = new Random(Config.SEED);
		
		// Create a tree object and assign dimension
		Tree tree = new Tree(1,1,Config.MAP_WIDTH-1,Config.MAP_HEIGHT-1);
			
		// Draw the dwelling
		tree.drawRooms();
		
		// Print all rooms from a tree
		tree.printRooms();
	}
}

//
// BSP Tree Class
//
public class Tree
{
	public Leaf root;
	public List<Leaf> tree = new List<Leaf>();
	public List<Room> rooms = new List<Room>();
	
	public Tree(int x, int y, int width, int height)
	{	
		// Create root
		root = new Leaf(x, y, width, height);
		tree.Add(root);
		
		// Loop through leaves and split
		int splitIdx = 0;
		while (splitIdx < tree.Count && tree.Count < Config.MAX_LEAVES_COUNT)
		{
			Leaf toSplit = tree[splitIdx];
		    if( toSplit.split() ) //attempt to split
			{ 
                tree.Add( toSplit.leftChild );
                tree.Add( toSplit.rightChild );
            }
			splitIdx ++;
		}
		
		// Now we can recursively travsal the tree and generate rooms at end leaves.
		root.createRooms();
		
		// Store rooms in list
		foreach (Leaf leaf in tree)
			if (leaf.room!=null)
				rooms.Add(leaf.room);
	}
	
	//
	// Print Rooms
	//
	public void printRooms()
	{
		Console.WriteLine("Room List:");
		foreach (Room r in rooms)
		{
			Console.WriteLine(r.asString());
		}
	}
	
	//
	// Draw Rooms
	//
	public void drawRooms()
	{
        char[][] lines = new char[Config.MAP_WIDTH][];
		
	
        for( int i = 0; i < Config.MAP_WIDTH; i++ ) 
		{
            lines[i] = new char[Config.MAP_HEIGHT];
            for( int j = 0; j < Config.MAP_HEIGHT; j++ )
                lines[i][j] =  '#';
        }
		
        int dungeonCount = -1;
        foreach( Leaf r in tree ) 
		{
			//Console.Write("hallcount="+r.halls.Count);
			foreach (Room h in r.doors)
			{
				int area = h.rect.Width*h.rect.Height;
				if (area == 1)
					lines[h.rect.X][h.rect.Y] = '0';
				else if (area == 2)
					for (int i = 0; i<h.rect.Width; i++)
						for (int j = 0; j<h.rect.Height; j++)
							lines[h.rect.X+i][h.rect.Y+j] = '0';
				else
					for (int i = 0; i<h.rect.Width; i++)
						for (int j = 0; j<h.rect.Height; j++)
							lines[h.rect.X+i][h.rect.Y+j] = '.';
			}
					
			if (r.room==null)
				continue;
			
            Room d = r.room;
            dungeonCount++;
			
            for( int i = 0; i < d.rect.Width; i++ ) 
                for( int j = 0; j < d.rect.Height; j++ )
					lines[ d.rect.X+i ][ d.rect.Y+j ] = '.';
        }
		
		Console.Write("\\");
		for( int i = 0; i < Config.MAP_WIDTH; i++ ) 
		{
			Console.Write(i%10);
		}
		Console.Write("\n");
        for( int j = 0; j < Config.MAP_HEIGHT; j++ ) 
		{
			Console.Write(j%10);
			for( int i = 0; i < Config.MAP_WIDTH; i++ ) 
				Console.Write(lines[i][j]);
			Console.Write("\n");
        }
		
		Console.WriteLine("\nLedgend:\n");
		Console.WriteLine("#: Wall");
		Console.WriteLine(".: Floor");
		Console.WriteLine("0: Single Door");
		Console.WriteLine("00: Double Door\n");
    }
}

//
// BSP Leaf Class
//
public class Leaf
{
	public uint id;
	public int x, y, width, height, seed;
	public Leaf parent, leftChild, rightChild;
	//public Rectangle room = new Rectangle();
	public Room room;
	public List<Room> doors = new List<Room>();
	//public List<Room> doors = new List<Room>();
	public enum Direction:byte { Left=0/*0b00*/, Right=1/*0b01*/, Top=2/*0b10*/, Bottom=3/*0b11*/ };
	public byte connectDir; // store which direction connect with it's sibling leaf

	//
	// Initializer
	//
	public Leaf(int inX, int inY, int inWidth, int inHeight, Leaf inParent=null, byte inConnectDir=0)
	{
		x = inX;
		y = inY;
		width = inWidth;
		height = inHeight;
		connectDir = inConnectDir;
		parent = inParent;
		
		if (parent == null)
		{
			id = 1;
		}
		else
		{
			if (connectDir == (byte)Direction.Top || connectDir == (byte)Direction.Left)
				id = (parent.id<<1);
			else
				id = (parent.id<<1)+1;
		}
		
		Debug.WriteLine("id="+id); // print id
	}
	
	//
	// Splitter
	//
	public bool split()
	{
		// Begin splitting the leaf into two children
		if (leftChild != null || rightChild != null)
			return false; // Bail out if it is alread splitted.
		
		// Sometimes just don't split at all
		if (R.r.NextDouble() < Config.QUIT_RATE && Math.Max(width, height) < Config.MAX_SIZE)
			return false;
		
		// Determine direction of split. Split on longer side for even distribution
		bool isSplitTopBottom = height>width;
		Debug.WriteLine(height+","+width+","+isSplitTopBottom);
		
		// Determine max possible size to split
		int max = (isSplitTopBottom?height:width) - Config.MIN_SIZE;
		if (max <= Config.MIN_SIZE)
			return false; // This dimension is too small to split
		
		int splitPos = R.r.Next(Config.MIN_SIZE, max);
		
		if (isSplitTopBottom)
		{
			leftChild = new Leaf(x, y, width, splitPos, this, (byte)Direction.Bottom); // leftChild is the top one
            rightChild = new Leaf(x, y + splitPos, width, height - splitPos, this, (byte)Direction.Top);
		}
		else
		{
			leftChild = new Leaf(x, y, splitPos, height, this, (byte)Direction.Right); // leftChild is the left one
            rightChild = new Leaf(x + splitPos, y, width - splitPos, height, this, (byte)Direction.Left);
		}
		return true; // We have made this far
	}
	
	//
	// Create Rooms
	//
	public void createRooms()
	{
		//Console.WriteLine("generating rooms");
		//Console.WriteLine(R.stream.Next(10));

		if (leftChild != null || rightChild != null)  //if current are has child areas, propagate the call
		{
		    // this leaf has been split, so go into the children leafs
	        if (leftChild != null)
				leftChild.createRooms();

	        if (rightChild != null)
				rightChild.createRooms();
			
			// if there are both left and right children in this Leaf, create a hallway between them
        	if (leftChild != null && rightChild != null)
			{
				//Rectangle leftRoom = leftChild.getRoomConnectToward(leftChild.connectDir);
				Room leftRoom = leftChild.getRoomConnectToward(leftChild.connectDir);
				createDoor(leftRoom, rightChild.getRoomNextTo(leftRoom));
			}

		}
		else // if leaf node, create a dungeon within the minimum size constraints
		{
            int roomHeight = Math.Max(height, Config.MIN_SIZE )-1;
            int roomWidth = Math.Max(width, Config.MIN_SIZE )-1;
			
			// create the room
            //room = new Rectangle(x, y, roomWidth, roomHeight);
			room = new Room(x, y, roomWidth, roomHeight);
			room.id = this.id;
			Debug.WriteLine("new room:"+x+","+y+","+roomWidth+","+roomHeight);
		}
	}
	
	//
	// Travsal until find a room
	//
	public Room getRoomConnectToward(byte connectDir)
	{
		Debug.WriteLine(connectDir);
		if (room!=null) // If the leaf has a room, usually an end leaf, return that room
		{
			return room;
		}
		else // Else divide and conquer its children
		{
			//Rectangle lRoom = new Rectangle();
			//Rectangle rRoom = new Rectangle();
			Room lRoom = new Room();
			Room rRoom = new Room();
			
			if (leftChild != null)
				lRoom = leftChild.getRoomConnectToward(connectDir);
			
			if (rightChild != null)
				rRoom = rightChild.getRoomConnectToward(connectDir);
			
			// Return room based on whether it's sibling is empty or not
			// Otherwise, return the room that's closer to connection
			if (lRoom==null && rRoom==null)
			{
	            return null; // no room in this branch
			}
	        else if (rRoom==null)
			{
  	       		return lRoom; // if right room is empty, return left room
			}
			else if (lRoom==null)
			{
 	        	return rRoom; // if left room is empty, return right room
			}
	        else
			{
				// return the room that's closer to connection
				switch (connectDir)
				{
					case (byte)Direction.Left: // if this leaf connect to the left
						if (rRoom.rect.Left==lRoom.rect.Left)
							return R.r.Next(2)==1?rRoom:lRoom; // pick random one if both children connect to the left
						else
							return rRoom.rect.Left<lRoom.rect.Left?rRoom:lRoom; // or pick the left most one
					
					case (byte)Direction.Right: // if this leaf connect to the right
						if (rRoom.rect.Right==lRoom.rect.Right)
							return R.r.Next(2)==1?rRoom:lRoom; // pick random one if both children connect to the right
						else
							return (rRoom.rect.Right>lRoom.rect.Right?rRoom:lRoom); // or pick the right most one

					case (byte)Direction.Top: // if this leaf connect to the top
						if (rRoom.rect.Top==lRoom.rect.Top)
							return R.r.Next(2)==1?rRoom:lRoom; // pick random one if both children connect to the top
						else
							return (rRoom.rect.Top<lRoom.rect.Top?rRoom:lRoom); // or pick the top most one
					
					case (byte)Direction.Bottom: // if this leaf connect to the bottom
						if (rRoom.rect.Bottom==lRoom.rect.Bottom)
							return R.r.Next(2)==1?rRoom:lRoom; // pick random one if both children connect to the bottom
						else	
							return (rRoom.rect.Bottom>lRoom.rect.Bottom?rRoom:lRoom); // or pick the bottom most one
					
					default:
						return R.r.Next(2)==1?rRoom:lRoom; // otherwise return random room.
				}
			}
		}
	}
	
	//
	// Travsal until find a room that next to input room
	//
	public Room getRoomNextTo(Room target)
	{
		if (room!=null)
		{
			return room;
		}
		else
		{
			Room lRoom = new Room();
			Room rRoom = new Room();
			
			if (leftChild != null)
				lRoom = leftChild.getRoomNextTo(target);
			
			if (rightChild != null)
				rRoom = rightChild.getRoomNextTo(target);
		
			if (getSharedWall(rRoom, target)!=null)
				return rRoom;
			
			else if (getSharedWall(lRoom, target)!=null)
				return lRoom;
				
			else
				return null;
		}
	}

	//
	// Create door
	//
	public void createDoor(Room l, Room r)
	{
		Room sharedWall = getSharedWall(r, l);
		
		if (sharedWall==null)
			return; // no shared wall
		
		bool isVertical = sharedWall.rect.Width < sharedWall.rect.Height;
		int wallWidth = isVertical?sharedWall.rect.Height:sharedWall.rect.Width;
		
		//int doorWidth = rnd.Next(1, wallWidth+1);
		int doorWidth = getDoorWidth(wallWidth);
		int margin = wallWidth - doorWidth;
		Debug.WriteLine(wallWidth+", "+doorWidth+", "+margin);
		
		if (margin<0)
			return;
		
		if (isVertical)
			doors.Add(new Room(sharedWall.rect.X, sharedWall.rect.Y + R.r.Next(margin), 1, doorWidth));
		else
			doors.Add(new Room(sharedWall.rect.X + R.r.Next(margin), sharedWall.rect.Y, doorWidth, 1));		 
	}
	
	//
	// shared wall
	//
	private Room getSharedWall(Room r, Room l)
	{
		if (r==null || l==null)
			return null;
		
		Room output = new Room(Rectangle.Intersect(Rectangle.Inflate(r.rect, 1, 1),Rectangle.Inflate(l.rect, 1, 1)));
		
		if (output.rect.Width*output.rect.Height < 3)
			return null; // return empty room if no shared wall
		
		if (output.rect.Width>1)
			output.rect.Inflate(-1, 0);
		
		if (output.rect.Height>1)
			output.rect.Inflate(0, -1);
		
		if (output.rect.Width != 1 && output.rect.Height != 1)
			return null; // no shared wall
		
		return output;
	}
	
	//
	// Determine door width
	//
	private int getDoorWidth(int max)
	{
		
		x = R.r.Next(Config.SINGLE_DOOR_PROB + Config.DOUBLE_DOOR_PROB + Config.HALLWAY_DOOR_PROB);
		Debug.WriteLine(max);
		if (x < Config.SINGLE_DOOR_PROB)
			return 1;

		else if (x >= Config.SINGLE_DOOR_PROB && x < Config.SINGLE_DOOR_PROB + Config.DOUBLE_DOOR_PROB)
			return Math.Min(2, max);

		else
			return max>=3?R.r.Next(3, max+1):max;
	}
}

//
// Object Class
//
public class Cell
{
	public uint id;
	public Rectangle rect;
}

//
// Room Class
//
public class Room:Cell
{
	public byte type;
	public Color mainColor;
	public Color accentColor;
	public Leaf leaf;
	
	enum RoomType:byte { livingRoom, bedRoom, kitchen, storage, foyer, corridor, bathRoom }
		
	public Room(int x, int y, int width, int height)
		
	{
		rect.X = x;
		rect.Y = y;
		rect.Width = width;
		rect.Height = height;
	}
	
	public Room(Rectangle r)
	{
		rect.X = r.X;
		rect.Y = r.Y;
		rect.Width = r.Width;
		rect.Height = r.Height;
	}
	
	public Room()
	{
		rect = new Rectangle();
	}
	
	public string asString()
	{
		return "id="+id+" "+rect;
	}
}

//
// Door Class
//
public class Door:Cell
{
	public byte type;
	public Color mainColor;
	public Leaf leaf;
	
	enum DoorType:byte { singleDoor, doubleDoor, hallWay }
}