Placing rectangles in a rectangular grid with obstacles

Minkowski sums come to mind, though it may be overkill. The approach is this: "Expand" the obstacles by the shape of the building to be inserted, and similarly "reduce" the building to a point, and any remaining open space will accept the new building. This reduces the problem to that of finding the closest point in a set to a given point.

In the interest of productivity, though, I'd make sure that an O(N*M) (grid size) check is the bottleneck; the grid is pretty coarse, isn't it?

The grid is not so big, it's approximately 128*128, but it would seem quite inefficient to find every single possible placement and then check which is the one closest to the target point.

To find the possible placements I could check every single tile to see if the building is placeable in the rectangle defined by that tile as its upper-left corner. If that rectangle overlaps something, then that tile is marked as invalid, and so are all the tiles in the rectangle. However, I still need to check almost every tile.

If I start in the upper left corner of the map sweeping from left to right and from top to bottom, the worst possible scenario would be if the target point lies in the lower-right corner of the map. In that case, I'd need to check (128-building.Width)*(128-building.Height)*building.Width*building.Height tiles, which seems too much brute force-ish. I mean, the average Factory is 4*3 tiles wide, which would yield 186000 tile checks....

The problem with the approach you propose is that I don't have a list of the obstacles, but rather have a function which, given a certain tile tells me if it's buildable or not. To expand the "obstacles" I'd have to sweep the board and group nearby unbuildable tiles into groups, which is too computationally expensive.

Quote:

Original post by diegovar The grid is not so big, it's approximately 128*128, but it would seem quite inefficient to find every single possible placement and then check which is the one closest to the target point.

Going the brute-force route, the idea would be to check near the target point first, and quit when you find one, not check everywhere and then pick the nearest. But, that's a minor nitpick...

Quote:

To find the possible placements I could check every single tile to see if the building is placeable in the rectangle defined by that tile as its upper-left corner. If that rectangle overlaps something, then that tile is marked as invalid, and so are all the tiles in the rectangle.

At this point, you can expand that point and add the set of expanded tiles to your "don't put the building here" map. So, best case, with a building size of 4x3, that'd cut out 5*7=35 tiles to check, not just 12. This benefit will diminish with sparse clumps of obstacles and near edges, but it's still a big improvement. This may not be immediately visualizable, so let me know if I need to host a picture somewhere to explain better...

Quote:

However, I still need to check almost every tile. If I start in the upper left corner of the map sweeping from left to right and from top to bottom, the worst possible scenario would be if the target point lies in the lower-right corner of the map. In that case, I'd need to check (128-building.Width)*(128-building.Height)*building.Width*building.Height tiles, which seems too much brute force-ish. I mean, the average Factory is 4*3 tiles wide, which would yield 186000 tile checks....

Given what I suggested above, I think this figure is pessimistic.

Quote:

The problem with the approach you propose is that I don't have a list of the obstacles, but rather have a function which, given a certain tile tells me if it's buildable or not. To expand the "obstacles" I'd have to sweep the board and group nearby unbuildable tiles into groups, which is too computationally expensive.

Nah, you don't need to group nearby tiles into groups, you can leave them separate. At the very worst, constructing a map of obstacle squares will take only 128*128=16k checks, an order of magnitude less than your estimate above. If 50% of the tiles are obstacles, that's only another 8k "expansions," which is a pretty lightweight thing when dealing with even grids. For each blocked tile, simply mark each (2*buildingWidth)-1 by (2*buildingHeight)-1 rectangle around the obstacle on a "buildable" map as unbuildable. That's a hidden inner loop, but all it's doing is marking something as true or false, not checking anything, so it should be quick.

Also, with only a function to tell you if a tile is occupied or not, there's no easy way to get around the upper bound of 128*128 calls to that function. You need the info one way or another, and you'll have to create your own sparse representation (a matrix should work fine).