Ok 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 e.g. 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 repeate 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 bottle neck is coming from this code as if I set maxTrys too a smalelr number the program runs quicker.
can someone help me optimize this, I really need some help with this
many thanks
tl;dr all the looping I am coding to check if a point is with in a point has really slowed down my program
