Rectangle overlapping in Java

Question

I'm trying to make a random map generator. It should create a random sized rooms at random coordinates, and remove the room it it overlaps with other rooms. However, the overlap checking isn't working. Here are the relevant parts of code:

public static void generateMap() {
    rooms[0] = new Room(0,10,10,5); // For some reason doesn't work without this?
    for (int i=0;i<ROOMS;i++) {
        int x = randomWithRange(0,WIDTH);
        int y = randomWithRange(0,HEIGHT);
        int height = randomWithRange(MINROOMSIZE,MAXROOMSIZE);
        int width = randomWithRange(MINROOMSIZE,MAXROOMSIZE);
        while (x+width > WIDTH) {
            x--;
        }
        while (y+height > HEIGHT) {
            y--;
        }
        Room room = new Room(x,y,width,height);
        if (room.overlaps(rooms) == false) {
            rooms[i] = room;
        }

    }
}

And then the Room class:

import java.awt.*;

public class Room {
    int x;
    int y;
    int height;
    int width;

public Room(int rx, int ry, int rwidth, int rheight) {
    x = rx;
    y = ry;
    height = rheight;
    width = rwidth;
}
boolean overlaps(Room[] roomlist) {
    boolean overlap = true;
    Rectangle r1 = new Rectangle(x,y,width,height);
    if (roomlist != null) {
        for (int i=0;i<roomlist.length;i++) {
            if (roomlist[i] != null) {
                Rectangle r2 = new Rectangle(roomlist[i].x,roomlist[i].y,roomlist[i].width,roomlist[i].height);
                if (!r2.intersects(r1) && !r1.intersects(r2)) {
                    overlap = false;
                }
                else {
                    overlap = true;
                }
            }                
        }
    }
    return overlap;
}

}

So I've been testing this, and it removes a few rooms each time, but there's always some that are overlapping depending on the number of rooms of course. There must be some stupid easy solution I just can't see right now... Also, why doesn't it generate any rooms unless I manually add the first one? Thanks

Answer 1

For your first issue where you have initialized first room, you don't have to do that.

rooms[0] = new Room(0,10,10,5); // For some reason doesn't work without this?

You just need to check for first room and no need to check for overlap as it is the first room. For the second issue, you can return true at the first time you find an intersect otherwise return false at the end of the loop.

Code for your reference.

class Room {
int x;
int y;
int height;
int width;

public Room(int rx, int ry, int rwidth, int rheight) {
    x = rx;
    y = ry;
    height = rheight;
    width = rwidth;
}

boolean overlaps(Room[] roomlist) {
    Rectangle r1 = new Rectangle(x, y, width, height);
    if (roomlist != null) {
        for (int i = 0; i < roomlist.length; i++) {
            if (roomlist[i] != null) {
                Rectangle r2 = new Rectangle(roomlist[i].x, roomlist[i].y, roomlist[i].width, roomlist[i].height);
                if (r2.intersects(r1)) {
                    return true;
                } 
            }
        }
    }
    return false;
}
}

public class RoomGenerator {
private static final int ROOMS = 10;
private static final int WIDTH = 1200;
private static final int HEIGHT = 1000;
private static final int MINROOMSIZE = 10;
private static final int MAXROOMSIZE = 120;

public static void main(String[] args) {
    generateMap();
}

public static void generateMap() {
    Room rooms[] = new Room[10];
    for (int i = 0; i < ROOMS; i++) {
        int x = randomWithRange(0, WIDTH);
        int y = randomWithRange(0, HEIGHT);
        int height = randomWithRange(MINROOMSIZE, MAXROOMSIZE);
        int width = randomWithRange(MINROOMSIZE, MAXROOMSIZE);
        while (x + width > WIDTH) {
            x--;
        }
        while (y + height > HEIGHT) {
            y--;
        }
        Room room = new Room(x, y, width, height);
        if( i ==0)
        {
            rooms[0] = room;
        }else if (room.overlaps(rooms) == false) {
            rooms[i] = room;
        }
    }
}

private static int randomWithRange(int min, int max) {
    // TODO Auto-generated method stub
    Random r = new Random();
    return r.nextInt((max - min) + 1) + min;
}
}

Answer 2

Your problem is this part of overlaps function:

overlap = false;

What is happening in your code is that you keep checking rooms if they overlap or not, but if you find one which overlaps, you keep going. And then when you find a room which does not overlap, you reset the flag. Effectively the code is equivalent with just checking the last room.

Remove the overlap flag completely. Instead of overlap = true; statement put return true; (because at this point we know that at least one room is overlapping). Don't do anything when you find out that the room is not overlapping with other room (in the for cycle). At the end, after the for cycle just return false; Fact that code execution got to that point means there is no overlapping room (otherwise it would have just returned already)

Note: I believe that condition !r2.intersects(r1) && !r1.intersects(r2) is redundant. .intersects(r) should be commutative, meaning that that r1.intersects(r2) and r2.intersects(r1) give the same results.