Generating rooms in a map

Question

I'm working on a game in JavaScript and I'm trying to generate rooms in a map. For this example, the map is 32 by 24 (each tile is 32 by 32 pixels).

A room is made up of a collection of tiles. A room is always in a square or rectangle shape. For example, 16,16,8,8 would make a room that draws from the top left corner at 16 by 16 and the bottom right corner at 24 by 24.

How the algorithm works:

1. pick a random x,y, width and height for the room
2. check if these points collide with another room
3. if it fails repeat points 1 and 2 (it will only repeat problems 1 and 2 1000 times before finally giving up and deciding it can't fit any more rooms in)

This is done by this code here:

 //make sure a room doesn't clash here
 while (maxTrys > 0) {
 var x = randomValue(2, tileX - MAXROOMSIZE); //starting top left corner tile's x position
 var y = randomValue(2, tileY - MAXROOMSIZE);//starting top left corner tile's y position
 var width = randomValue(MINROOMSIZE, MAXROOMSIZE); //width of room in tiles sqaures e.g 3 = 96 pixels
 var height = randomValue(MINROOMSIZE, MAXROOMSIZE);//height of room in tiles e.g 3 = 96 pixels
 if (locationIsFine(x, y, width, height) == true) { //if we've found a location we're happy with
 roomStore.push(createRoom(i, x, y, width, height));
 break;
 }
 maxTrys--;
 }

How it checks if a point collides with another room:

1. generate a room with the randomly created x,y,width and height cordinates
2. check if any point in this "temp room" collides with any point of any other room
3. if it does we know there is a collision

The code for this is the following:

var locationIsFine = function(x, y, width, height) {
 //turn the cordinates into a fake room
 var tempTiles = new Array();
 for (var i = 0; i < width; i++) {
 for (var j = 0; j < height; j++) {
 tempTiles.push(new tile(tileset,x+ j,y + i,0,null,ScreenManager));
 }
 }
 //make sure room wont hit any other rooms, we do this by checking if edges of a room collide with an exisiting room
 for (var i = 0; i < roomStore.length; i++) {
 for (var j = 0; j < tempTiles.length; j++) {
 if (roomStore[i].intersects(tempTiles[j].getX(), tempTiles[j].getY()) == true) {
 return false;
 }
 }
 }
 return true;
}

The intersects method looks like this:

this.intersects = function (x,y) {
 /* find the biggest and smallest points in the room*/
 for (var i = 0; i < tiles.length; i++) {
 if (tiles[i].getX() == x && tiles[i].getY() == y) {
 return true;
 }
 }
 return false;
}

My problem with this is that it is really really slow. After running it a few times, it can take 5-8 seconds to generate the rooms and normally it gives up after the 5th room. I am 100% sure the bottleneck is coming from this code as if I set maxTrys to a smaller number, the program runs quicker.

Answer 1

In your locationIsFine it seems you check for each room in your roomStore if any of its tiles intersect with a tile inside your new/fake room.

It would probably be worth wile to add some basic checks which (the larger your roomStore will grow, the more it) will reduce the number of checks needed.

This is actually a rectangle intersection problem. Between rectangles, if one isn't completly to the left, right, above or below the other, they will intersect; so checking on that is the fastest way and will save you the check on each and every tile against each and every tile of the other room. This will save you from creating the tilesets for the fake room.

So a start to enhance the algorithm would be this.

var locationIsFine = function(x, y, width, height) {
 //make sure room wont hit any other rooms, we do this by checking if edges of a room collide with an exisiting room
 for (var i = 0; i < roomStore.length; i++) {
 // roomStore[i] completly left or completly right of new room
 if(roomStore[i].X > x+width || roomStore[i].x+roomStore[i].Width < x) continue;
 // roomStore[i] completly above or completly below new room
 if(roomStore[i].Y > y+height || roomStore[i].Y+roomStore[i].Height < y) continue;
 //if a room is neither completely to the right nor completely to the left as well as
 //not completly above nor completely below, it will intersect
 return false;
 }
 return true;
}

Answer 2

Instead of checking a proposed room against all other rooms, try a different algorithm. Let's trade time for space:

• Create an array representing all grid points, and assign all values to 0. This is a room property, to indicate which room the point belongs to.

• When a room is placed, update the room id of all member points.

• To collision detect, just step through the proposed points of a new room checking for pre-existing assignments.

• Instead of picking a random room position and size chosen at once, pick a random unassigned point; then instead of a random room size, start with the smallest room size and repeatedly expand the room in one direction until you hit another room.

When done placing, delete the grid array.

All these combined should allow you to build everything very quickly.

Answer 3

1. style

replace

var x = ...
var y = ...
var width = ...
var height = ...

with

var x = ... ,
 y = ... ,
 width = ... ,
 height = ... ,

to make it more readable, less verbose, and easier to maintain.

2. performance

replace

 for (var i = 0; i < roomStore.length; i++) {

with

 for (var i = 0, len=roomStore.length; i < len; i++) {

to prevent getting the roomStore length on each loop