Is there an existing algorithm to find suitable locations to place a town on a heightmap?

I've been experimenting with random generation of a "map" with the intention of building a basic sort of procedural map generator. Generating a reasonable heightmap using libnoise hasn't been that much of an issue.

I am considering using A* or similar to plot two main "roads" across the terrain from top to bottom and left to right, intersecting in the middle of a town in some relatively flat section of the terrain.

I am unsure of the best way to go about locating the optimal point to place the town though. I created a "steepness" map as another map which looks at the points surrounding each point on the heightmap to determine the steepness and then sets 1 if steep and 0 if not to create a "mask" of steep and flat areas.

How then could I determine the largest rectangle area that will fit within those flat areas?

Or perhaps I need to re-look at this a different way and place the "town" first then build the terrain around it rather than trying to place it into an existing terrain.

Here's one (relatively exhaustive) method you can try:

1. Take your terrain heighmap (left)

2. Mask the areas that are too steep to build on (orange, center)

3. Propagate a distance field from the too-steep region (blue-green gradients, right) until you reach your maximum town radius:

(You can also use the Jump Flooding Algorithm to speed up this part)

The resulting gradient represents the maximum radius city that can be placed at each point. The highest overall peak in the gradient represents the placement point for the largest possible city this map can house (or, the one with the most padding around it)

If you do not want to alter the existing terrain that you generated, then a viable approach could be to use a flood fill algorithm.

Have your flood fill check for the largest fillable area that is inside of a specified height range.

This approach would require you to define at what height you would like your town to be placed.

If you are not opposed to modifying the terrain you generated, possibly utilize an erosion style algorithm, that will subtract data from higher areas, and place them at lowest areas near that original peak. You would more than likely have to taper off this effect at the edges of your area.

• Unfortunately a basic flood fill won't distinguish between a broad contiguous area (like a nice flat plateau) and a distributed web of connected points spread out in narrow snaking curves (like a fractal network of riverbeds) if they have similar total area. You'd want an algorithm that looks at the shape of the space, not just picking the largest set of connected points. Commented Jul 21, 2016 at 17:08
• There are things you can do to mitigate this, such as checking where the topmost/bottommost/leftmost/rightmost tiles are in the floodfilled areas, and then checking to see if the resulting Tile count is large enough to accomodate that area. Commented Jul 21, 2016 at 17:11
• Still doesn't quite capture the requirements. I can have a contiguous patch big enough for a town, with long snaking limbs at the periphery that make its bounds big enough to fail such a sparseness check. Commented Jul 21, 2016 at 17:13
• I think it could work. Commented Jul 21, 2016 at 17:14
• Here's an example of the type of problem I'm describing. Without an additional criterion, we can't distinguish between the left case (which does not contain a good place to put a town) and the right case (which does) Commented Jul 21, 2016 at 17:42