Villages Concept and stuff

Immortius · Sep 17, 2012

On the other hand, describing it as a hive makes me wonder if you read Homestuck.

Skaldarnar · May 11, 2013

Heya, time for an update!

I was playing around with ways to place town centers and generate road networks.

Although the are a lot of papers and articles on road network generation using different techniques (e.g. L-systems[1], agent based simulation[2], template based generation[3]), the information on where to generate a city is quite rare.

It seems to me that in most fields of application this process is done either interactively or controled by given (statistical, topographical, ...) data (which yields more of a recreation of existing cities). While we may have some sort of player interaction in form of founding his/her own village, the majority of settlements should be generated automatically. Therefore, I would favour the data driven approach.

In order to guarantee a deterministic algorithm for settlement placement, wo ought to distinguish finite and infinite maps.

Finite Maps

On finite maps it should be doable to to search the whole map for suitable places during map generation. This could be done chunk wise or considering only clusters of chunks for calculation. A settlement value can be calculated using information of a fixed surrounding of the considered point, such as amount of water,reachable size of forests, elevation and so on. A predefined threshold (either fixed or a percentage value relative to the highest found value) would control wheter a new city is founded or not.

Since all this is done in the world's pre-processing, the algorithm can easily deal with conflicts (e.g. two adjacent points have the same settlement value).

Infinite Maps

The method described above will fail for infinite maps (it should be clear that we cannot check all points on an infinite map

), but using a modified version could do the job. The idea is to check discovered regions only, and expand the checked area during the player's exploration. The main issue with this approach is that it is not deterministic by default:

Think of two players approaching the same point (which would be the best place for a settlement in the local surrounding) from different directions. Both may find a "good" position near the optimal point (e.g. the first place that reaches the threshold value) and a settlement would be founded there.

Given some restrictions, the two cities might be too close to each other, resulting in a conflict. Moreover, city placement would not be deterministic since the settlement points are located at different positions. To avoid this problem, we have to check a larger area around considered points, but how large should the are be?

One possible solution would be to calculate a population density map (using an appropriate noise function) that defines differenct areas of various stages (e.g. 4 or 8) of population density. During exploration, the considered point has to be checked against all other points in the population area. By this approach, the described issue can be avoided. Moreover, the population stage can influence the threshold value for a settlement, yielding more natural results for village placement.

Illustration of the two-player conflict. For both players, the yellow area will be evaluated the same way, thus both players will "found" the same city.

Example

I want to give you a simple example on how the algorithm could found good sides for a settlement.

We start with the generated terrain map. You may consider this map as an extract of a larger (infinite) map.
In the next step we use Perlin noise for the population map. I reduced the noise range to just 4 levels. In the last image I have clustered the chunks in groups of 8x8.
In this example, the algorithm is only run for areas with high popluation density (white areas). The cities are marked by the red indicators. As mentioned above, this approach can be used to generate villages or small towns in areas with lower population.