Java: Iteration to find a coordinate point that hasn't been used?

Question

I am using the following method to try to find a point (coordinate) that hasn't been previously used, and isn't within the bounds of items that have previously used and coordinates.

The way it works is I am rendering "bases" (RTS top-down game), and I am creating two random variable locations for x and y. I pass these, along with the bases texture, into the following method. The method loops through a list of rectangles that are the rectangles of each previously rendered base. If the point is within any of the rectangles, the method is called again using a different set of coordinates. It does this until it finds a set that isn't within a rectangle. It then adds a new rectangle to the list at these coordinates, and returns them so the game can render a new base.

However, the bases still overlap.

Here is the method:

private Point getCoords(int x, int y, Texture t){
    for (int i=bases.size()-1; i> -1; i--) {
        if (bases.get(i).contains(new Point(x,y))){
            x = new Random().nextInt(map.getWidth() * map.getTileWidth());
            y = new Random().nextInt(map.getHeight() * map.getTileHeight());
            getCoords(x, y, t);
        }
    }
    bases.add(new Rectangle(x,y,t.getImage().getWidth(), t.getImage().getHeight()));
    return new Point(x, y);
}

And here is where it is being called:

switch(ran){
            default:
                int x = new Random().nextInt(map.getWidth() * map.getTileWidth());
                int y = new Random().nextInt(map.getHeight() * map.getTileHeight());
                Point p = getCoords(x, y, temp);
                map.generateBase("air", p.x, p.y);
                break;
        }

Any ideas what is wrong here?

Thanks

Answer 1

There are several problems:

• Your algorithm might be overwritting good coordinates (free ones) with wrong coordinates, you dont have any condition to exit the loop/recursion if you find a good place

• You are checking for if rectangle contains the point, but later you are adding a rectanble, so it may not contain the point, but the rectangle created later may collide

try this

private Point getCoords(int x, int y, Texture t){
    boolean found = false;
    final int width = map.getTileWidth();
    final int height = map.getTileHeight();
    while(!found) {
            x = new Random().nextInt(map.getWidth() * width);
            y = new Random().nextInt(map.getHeight() * height);
            for (int i=bases.size()-1; i> -1; i--) {
                if (!bases.get(i).intersects(new Rectanble(x,y, width, height))){
                        found = true;
                } else found = false;
            }
    }

        bases.add(new Rectangle(x,y,t.getImage().getWidth(), t.getImage().getHeight()));
        return new Point(x, y);
}

*** EDIT: Im not sure if I had to use TileWidth and TileHeight or image width and image height for width and height :D

Answer 2

Okay so after some playing around, I found the issue is the rectangles that are saved are saved with a fixed location which means as the map moves, the rectangles don't. The fix is to loop through each bases and get the base's map position, rather than screen position, and check against this. Also, I found i was checking for a point in a rectangle, which may be outside the rectangle but leaves my bases overlapping still. So i now check for rectangle-rectangle collision instead

Answer 3

            int x = new Random().nextInt(map.getWidth() * map.getTileHeight());

Maybe a bad copy paste. It may be :

            int x = new Random().nextInt(map.getWidth() * map.getTileWidth());

In both codes :-D