3
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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

Three stages of terrain analysis: height field, buildable mask, distance field

  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:

    Animation of the distance field propagating

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)

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – DMGregory Jul 21 '16 at 17:08
  • \$\begingroup\$ 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. \$\endgroup\$ – jgallant Jul 21 '16 at 17:11
  • \$\begingroup\$ 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. \$\endgroup\$ – DMGregory Jul 21 '16 at 17:13
  • \$\begingroup\$ I think it could work. \$\endgroup\$ – jgallant Jul 21 '16 at 17:14
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – DMGregory Jul 21 '16 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.