Finding Empty Relief Rectangles in Grid-Graph

Question

The city in my game is randomly generated, but it is a graph of roads and intersections that only rectangles can form:

As you can see, my landscape is pretty empty. I want to find each empty rectangle and save it in the list of rectangles, forming lots.

As you can see in this illustration, I filled in 3 'lots', and in 1 I showed 3 rectangles of which it is made.

My data structures:

package com.jkgames.gta; import android.graphics.Bitmap; import android.graphics.RectF; public class Intersection extends Entity { Road topRoad; Road leftRoad; Road bottomRoad; Road rightRoad; Bitmap image; public Bitmap getImage() { return image; } public void setImage(Bitmap image) { this.image = image; } public Intersection(RectF rect, Bitmap image) { setRect(rect); setImage(image); } public Road getTopRoad() { return topRoad; } public void setTopRoad(Road topRoad) { this.topRoad = topRoad; } public Road getLeftRoad() { return leftRoad; } public void setLeftRoad(Road leftRoad) { this.leftRoad = leftRoad; } public Road getBottomRoad() { return bottomRoad; } public void setBottomRoad(Road bottomRoad) { this.bottomRoad = bottomRoad; } public Road getRightRoad() { return rightRoad; } public void setRightRoad(Road rightRoad) { this.rightRoad = rightRoad; } @Override public void draw(GraphicsContext c) { c.drawRotatedScaledBitmap(image, getCenterX(), getCenterY(), getWidth(), getHeight(), getAngle()); } } public class Road extends Entity { private Bitmap image = null; private Intersection startIntersection; private Intersection endIntersection; private boolean topBottom; public Road(RectF rect, Intersection start, Intersection end, Bitmap image, boolean topBottom) { setRect(rect); setStartIntersection(start); setEndIntersection(end); setImage(image); setTopBottom(topBottom); } @Override public void draw(GraphicsContext c) { //Rect clipRect = c.getCanvas().getClipBounds(); //c.getCanvas().clipRect(getRect()); float sizeW; float sizeH; if(isTopBottom()) { sizeW = getWidth(); sizeH = (sizeW / image.getWidth()) * image.getHeight(); } else { sizeW = getHeight(); sizeH = (sizeW / image.getWidth()) * image.getHeight(); } int numTiles = isTopBottom() ? (int)Math.ceil(getHeight() / sizeH) : (int)Math.ceil(getWidth() / sizeW); for(int i = 0; i < numTiles; ++i) { if(isTopBottom()) { c.drawRotatedScaledBitmap( image, getRect().left + (sizeW / 2.0f), (getRect().top + (sizeH / 2.0f)) + (sizeH * i), sizeW, sizeH, 0.0f); } else { c.drawRotatedScaledBitmap( image, getRect().left + (sizeH / 2.0f) + (sizeH * i), getRect().top + (sizeH / 2.0f), sizeW, sizeH, (float)Math.PI / 2.0f); } } // c.getCanvas().clipRect(clipRect); } public Bitmap getImage() { return image; } public void setImage(Bitmap image) { this.image = image; } public Intersection getStartIntersection() { return startIntersection; } public void setStartIntersection(Intersection startIntersection) { this.startIntersection = startIntersection; } public Intersection getEndIntersection() { return endIntersection; } public void setEndIntersection(Intersection endIntersection) { this.endIntersection = endIntersection; } public boolean isTopBottom() { return topBottom; } public void setTopBottom(boolean topBottom) { this.topBottom = topBottom; } } 

A city is a list of roads and intersections.

Is there any algorithm that could generate these lots and their rectangles?

thanks

Answer 1

The easiest way that comes to my mind is to use the fill fill algorithm to create a list of regions. So basically

 foreach square: if the square isn't part of a region: create a new empty region list add the square to it recursivly add all neighboring squares to the region 

The end result will be that you will have a list of regions in which you can do whatever you want (look and see if there is a building on any of the contained squares, color for the user, etc.) ..

Note. To determine if a square is part of a region or not, I would add a flag or something to the square data structure, so when you start, you look at and clear all of these flags, and then how you add the square to the area, which you set this flag, and when you want to check if there is a square in the region, all you have to do is check if this flag is set or not. Thus, you get a linear time algorithm for creating a list of regions.

As Marcus noted in the comments here, this “flag” can actually be a pointer / link to a Lot object that contains a list of your squares, which would probably be convenient to have anyway.

Answer 2

 for (int y = 0; y < height; y++) for (int x = 0; x < width; x++) { if (x > 0 && squares[y][x].isConnectedTo(squares[y][x-1]) { // Connected from the left squares[y][x-1].getLot().addSquare(squares[y][x]); if (y > 0 && squares[y][x].isConnectedTo(squares[y-1][x]) { // Connected from both the left and above squares[y-1][x].getLot().mergeWith(squares[y][x].getLot()); } } else if (y > 0 && squares[y][x].isConnectedTo(squares[y-1][x]) { // Connected from above squares[y-1][x].getLot().addSquare(squares[y][x]); } else { // Not connected from either createNewLot().addSquare(squares[y][x]); } } 

• Lot.addSquare(…) adds a square to the lot and calls setLot(…) on the square.
• Lot.mergeWith(…) combines two lots and reassigns the assigned squares if they are not the same.
• Square.isConnectedTo(…) checks to see if they are neighbors and that there is no road between them.

You can optimize this using a data structure with unrelated sets.