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:
- pick a random x,y, width and height for the room
- check if these points collide with another room
- 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:
- generate a room with the randomly created x,y,width and height cordinates
- check if any point in this "temp room" collides with any point of any other room
- 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.