Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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:

  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 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

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

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;
}
share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.