7
\$\begingroup\$

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:

Picture of the issue, can't post image directly

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: enter image description here

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ Can't you just expand into random points next to already adjacent claimed territory, as long as they aren't in natural barriers? \$\endgroup\$ – Kyranstar Sep 9 '15 at 21:29
  • \$\begingroup\$ I would strongly question the shape of your 'desired' second example - the first desired result is fairly natural (aside from the gaps along the edges of the lake at the top right and the 'ray' of city at the bottom), but the second looks incredibly artificial to me. The answers here are reasonable, but I think you should probably start by questioning your hypotheses. \$\endgroup\$ – Steven Stadnicki Sep 10 '15 at 22:58
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This would create a fairly perfect circle around the town right? Making it uneven would require a fairly large change to the code right? But on that looking through the wikipage I saw the queue example of storages, and got me thinking that a pathfinding breadth-first-search algorithm might work right? \$\endgroup\$ – Ranth Sep 10 '15 at 14:54
  • 1
    \$\begingroup\$ Heya with a breadth-first-search you could essentially find all locations within x distance from the city via a path that could be travelled and then as the city grows increase the length of path limit to a larger size. I have used breadth-first-search but not for something like that so I'm not 100% sure on implementation in this specific case! \$\endgroup\$ – JackFrost Sep 10 '15 at 15:58
  • \$\begingroup\$ Dijkstra's likely could also work, and you could add random weights to make it not output a perfect circle. \$\endgroup\$ – Tally Aug 8 '18 at 2:18
0
\$\begingroup\$

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) ..

|improve this answer|||||
\$\endgroup\$

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.