Dynamic Rectangle Dungeon Room Generator

Hey guys. I’ve been working on this idea for about 3 days.
Basically I did not know how to generate a maze, so I thought, why not try?
Except, I want to use random rectangles instead of fixed cells for tile traversal.

I use a binary space partition structure to generate random slices of rectangular space, then I have the following rules:

  • if there are no rectangles on the stack, there are no more positions to move. The maze is done.
  • If the rectangle adjacent to our current position has been checked, do nothing.
  • If the rectangle adjacent to our current position (a) hasn’t been checked, but all rectangles adjacent to (a) have been checked, add (a) to the checked list. The current rectangle becomes that first one off of the stack, and this whole process repeats.
  • If the rectangle adjacent to our current position hasn’t been checked, add all rectangles across from (a) to a list. Out of that list, pick one to keep (b), add it to the checked rectangles, and to the stack. Add the adjacent and across to the set of rectangles that are of the path. Get the adjacent tile opposite of the direction we just checked, and add it to the checked list.

When the maze can no longer add rectangles, I have it erase dead ends until all rectangles have 2 or move neighbors.

Splitting the whole rectangular world into smaller rectangles: http://pastebin.com/U6A1Evuh
and the class to make the rectangles a-MAZE-ing: http://pastebin.com/aSaAiBWJ

When I display the result, it looks something like this

This is without the removal of dead ends

My next goal will probably be checking of adjacent rectangles, and combining the ones that have matching sides in the direction they are being checked.

So if I check A and B and A is above B, and B’s width is equal is A’s width, with their x positions being the same, they combine their area.

So that rooms are flush (and we don’t have a corridoor that leads into a corridor.

The door placement is possible with this:

Red = rooms with 1 doors.
Yellow = rooms with 2 doors.
Green = rooms with 3 doors.
Magenta = rooms with 4 doors.
White = rooms with 5 doors.
Cyan = rooms with 6 doors.


			public SetPairMap<Rectangle,Rectangle> doormap = new SetPairMap<>();
	public void placeDoors(){			
		for(Rectangle r: path){
			for(Rectangle adj: getAdjacent(r, false).getValues()){
					doormap.put(r, adj);					
					doormap.put(adj, r);

Just to clarify, the rooms that are red only see they have one door that THEY themselves generate. They can have more than one, but they don’t store their parent door. I may update this later when I show rooms that have their total doors displayed by color. As of now, it looks like red rooms could isolate from the rest of the path.

Finished Product pretty much:

Without sticking squares in. (Squares filling in the spaces makes the mazy look. This is better imo).

interesting solution!

How do you handle connections between rooms tho?
where do you place the corridor/door between 2 rooms, and what if a room has multiple neighbors, do you add multiple doors - and thus multiple paths for the player to take?

[quote]interesting solution!

How do you handle connections between rooms tho?
where do you place the corridor/door between 2 rooms, and what if a room has multiple neighbors, do you add multiple doors - and thus multiple paths for the player to take?
I will be working on this today.

My idea is that I will be going through the set of rectangles, and condense them into bigger ones if they match up flush with an adjacent one. After that, mark door positions. Corridors will be marked if they reach a threshold width to height ratio for later (when decorating them).

Door are easy, but there are specific ways to do it.
The simple way is to put a door down between rooms that are adjacent, in every room.
The more complex way to do it is pick a path from point A to point B, only make doors to follow that path. Get the rooms not used in that path, and branch off for the first rooms directly connected to the path, and connect doors the simple way (without letting it do it to the main path of rooms).

I’m thinking a good way to make dead end paths is to mark the dead ends as the target room, and start the branching room as path A, and use the same algorithm that makes the main path and so on. I type alot sorry lol.

What I’ll be working on next is determining which rooms connect to which rooms with doors.

I will do this without checking rooms. I will generate the rooms knowing ahead of time which path of rooms is a dead end or not.
I will generate a main path from point A to point B.
Then I will go down main path again, this time, making paths like I just did. However, I will only allow them to branch off in 1 direction, instead of going in every available adjacent rectangle. (After the initial branching away, they can add rooms however they want, following the main rules).

This way, I have a main path that does go from point A to B and also have dead end paths.

All of the rectangle rooms that are not blue are kept in a custom hashmap.
If they are:

  • Red: 1 Connection/Door : They are a dead end room.
  • Yellow: 2 Connections/Doors : These are between 2 rooms.
  • Green: 3 Connection/Door : They are between 3 rooms.


All I have to do is iterate over all of the colored rooms, and place doors between adjacent colored rooms into the blue rooms between the colored room connectors. (Connectors are every other room during the algorithm. They are separated by a blue room because blue rooms are not part of the algorithm.)
And bingo, they all connect without having like 4 doors taking up all the space on a room wall.

Final touch up:

What do you guys think?

well done, I like it, do you think to proper open source your work? I’m thinking to use it to improve my dungeon generation (random walk, see CryptoRL2 topic)


I don’t know how to open source it. It’s not documented.

Update of current state:

The doorways are real doorways now. The dots you see are positions to place game objects into the level.

I am using the same bsp tree using a multiples of 4, at intervals of up to 3 for the cell sizes I believe.
It might be slightly different now.
For instance: If I tell the bsp to split up rectangles, it takes the random number to split the rectangles apart, adds the minimum size into the expression, then floors it to a random multiple of minimumsize/4 so that the dimensions are a multiple of the minimum size.

This means sizes of sides can range from [],[][],[][][]…[][][][][][] depending on how many multiples of 4 your minimum size specified contains.

Now, I use a small enough minimum side size that the randoms can’t pinch my rooms so small that I can’t fit my game units in them.

I then take the generated rectangles, and have the world class handle them.

I scale them up, and then fit an int[][] of the width and height times an interval divider.
If I set my Divider ‘div’ to 8, it would make an int[][] of int[heightdiv][widthdiv] essentially.
So theoretically, I can have as much space in my rooms to fit 32x32 size tiles for sprites.

example of taking the default room rectangle, and turning it into space for the game:

	int scale = 5;
	int div = 4;
	public void setupRooms(Set<Rectangle> roomSet){
		Rectangle hold;
		int nX = 0;
		int nY = 0;
		int nW = 0;
		int nH = 0;
		int[][] tiles;
		for(Rectangle added: roomSet){
			nX = added.x*scale;
			nY = added.y*scale;
			nW = added.width*scale;
			nH = added.height*scale;
			testRoomMap.put(added.getBounds(),hold= new Rectangle(nX,nY,nW,nH));
			roomObjects.put(hold,tiles=new int[nH/div][nW/div]);	

I can help if you need help open sourcing it (documentation not required).

Is GitHub an acceptable host?
What questions do you have?

I don’t know how to use github. I used it back like a week or two when it came out, but never after.
Do you have skype?

i do. I’ll PM you my name.

well rats - the PM system isn’t working (captcha’s are broken). Let me think of a way to do this.

Got everything straightened out.