How to find a free patch of area in a tiled map?

Question

I've been trying to formulate the question and try to find some information on Google, but didn't managed to, so here it is... We've got a nice tropic-themed game that is about to be released soon, that uses a tile map and an A* pathfinding is utilized and everything works flawlessly.

Until when it comes to the point where I need to somehow find unoccupied patch of area on the map that matches certain criteria, so that I can guide the player to place their just bought map objects on.

The map is 200x200 tiled map and it holds instances of each tile that determine two things - if it is occupied and if it is a water or a ground tile. These are already used for the A* pathfinding algorithm that I've put into the game.

Let's say the player buys a water-placible map object from the store and the map object occupies 5x5 tiles for instance. I need to guide the player to a free patch of water tiles where they can place that map object.

Any guidance and/or reference to such algorithms will be highly appreciated :) Thanks

EDIT: It turns out that I need to find such a patch as close as possible to given point (centre of viewport for instance). This will improve user experience

Answer 1

Method 1 Here's a fairly brute-force algorithm:

1. Scan across each row, left to right, top to bottom, until you hit an unoccupied tile of the correct type. (You can skip the far right columns/bottom rows once you get too close for the placement to fit)

2. Once you find a valid tile, check all tiles that would be within the placement footprint, if you put the top left corner here. Start with the tile furthest away (the bottom-right corner of the placement), and gradually work back.

3. If you find an invalid tile (wrong type/already occupied), mark all tiles in the rectangle containing your proposed top-left corner and the obstacle as "explored", and resume searching with the next tile after the proposed top-left corner.

4. As you continue your main scan, skip over any tiles marked "explored"

5. If your search in 2 does not find an obstacle, return your proposed top-left corner as a valid placement and terminate.

Steps 3 & 4 are a small improvement over straight-up brute force search, in that they keep you from repeatedly checking the same patch. Starting from the opposite corner lets you skip as many tiles as possible using this trick.

Method 2 If you need to improve on this (profile, to see if it's worth your trouble), you can keep a bit of helper data with each tile: the size of the largest unoccupied square of the same type with that tile as its top-left corner.

Fill this data in once during map generation, by brute force if need be, then update it any time a tile changes state (search a rectangle up & left of the changed tile for any tiles that count it in their largest square. Decrease their largest square so that it ends just before the changed tile. You can end this search early once you've gone as far as the widest placeable item in your game.)

Now you can find a rectangle of the right size with a linear scan of the map. You can shape this scan any way you want - say searching an expanding spiral out from the focus of the player's current view, so that you can minimize the camera move required.

If you need even faster lookups (doubtful), you can use this data to sort your tiles into a heap (or series of heaps) by largest-placeable-area. Then in a O(1) operation you can pluck out a tile big enough for a given placement, or correctly conclude that none exists. (Just watch out, if you always choose the biggest-available area, regardless of the size of the placement, you'll tend to fritter away your wide open space on small placements)

That kind of acceleration structure can be expensive to maintain though, so only do it if your searches for placeable areas are causing noticeable problems.

Answer 2

A similar problem is finding the largest square block in a binary matrix and the algorithm actually gives the number of largest square blocks for every cell if this cell is top-left of the square block.

A very good documentation of the algorithm is the answer by Joy Dutta in the Dynamic programming - Largest square block question on SO.