City-region generation

Question

I am currently making a procedural generated map and wanted to add regions to the cities indicating their reach, the way I am achieving it currently is by expanding outwards from the city center until either the reach of the city is exceeded or water/mountain terrain is met, a bit like raytracing I assume:

This gives the issues seen above, making big ugly/unnatural holes and not filling areas out of "sight" but arguably within the city's reach. City regions are supposed to be blocked by mountains ranges and larger bodies of water, but should curve around small lakes/rocks in a natural way. I can provide my current code put I believe it's fundamentally flawed for what I want to do, and is not usable.

Basically the desired region I want to great should look something like this:

I am at a bit of a loss what to search for to find literature about this topic, whether it be something like an algorithm or hints of some sort, so basically I am asking what this is called. (Any tips/tricks would also be greatly appreciated)

Answer 1

To follow up on comments by @Ranth & @JackFrost, a breadth first search spreading away from the point of origin should give you the desired result. When doing so:

• Use an 8 way neighborhood (I.E. allow diagonal search movement)
• Use a Euclidean metric for distances to encourage 1 diagonal movement over 2 cardinal movements
• Limit the search by whatever you want the maximum radius to be
• Make obstacles impassable or increase the movement cost of their cells

Because the search will need to either wrap around obstacles or move more slowly through them, you won't get a perfect circle around your point of origin. If things still look too smooth &/or you have an area without obstacles, you could always add some fake obstacles for the running the city perimeter search.

As with most PCG stuff, you'll probably need to experiment a bit to find what you want. I like to use Perlin / simplex noise &/or Poisson disk distributions for that sort of thing, but to each their own.

Answer 2

I believe this could be achieved using the flood fill algorithm that basically calculates all connected areas in a given space, depending on how you want it to work however as it might lead to areas say opposite a river (where the river runs all the way along the largest area that the city can take) not being included in the area that would need special handling.

In terms of growth you could simple increase the radius of the circle and let the flood fill select the area inside that circle.

In terms of implementation the best way is to follow a tutorial but Wikipedia also has a decent Pseudo code implementation: https://en.wikipedia.org/wiki/Flood_fill#Pseudocode

Answer 3

As stated Kyranstar in his comment maybe Cellular automaton can be a solution.

Claim new terrain using some random logic that check terrain type, water presence (a city usualy grows near a river or seacost) ..