Settlements, Regions, Routes and Labels

It’s time to cover some stuff not related to a heightmap or biomes. This is a first narration of this kind and I’m going to cover most of them right in this post. These topics are settlements, regions, routes and labels. It’s not like I don’t want to describe every topic separately,  but I spent months to make it work and didn’t save all the materials / screenshots to show you. So I’ll omit my progress steps and just highlight the final result.

I’m not going to cover the rendering part. It’s the most time consuming thing which is still in progress, while the post already promises to be long.

Cities

Let’s start with settlements as it’s a key to other elements generation. There are at least 3 main questions here — what kind of settlements we need, how many and where are the best positions to place them. Initially my map generator was designed for my medieval Dynasty simulator and I had 2 of 3 questions already answered. A settlement was considered as a dynasty manor. It’s not a universal idea that fit a common fantasy map, so I decided to turn them into towns and cities (capitals). The general term for both types is burg. I know it’s not a real word in English, but I like a historical vibes it brings and its general meaning of a walled town. As of quantity, the precondition was to generate at least 500 manors withing 7 cultural areas.

The settlement placement is a complex problem. We cannot just select a random points, placement should be logical, burgs should not be too close to each and highly concentrated in general. I tried a dozens of variants, including a full economical simulation, but had to simplify the routine to improve the performance. In general the placement routing is:

1. Rank land polygons by geographical suitability
2. Place capitals on best spots not too close to each other
3. Unite capitals by roads
4. Re-rank land polygons based on generated road system
5. Place towns on best spots

First thing we have to do is to evaluate the geographical features in order to find best positions. The idea is that towns which are placed on the best spots will get an advantage and become capitals. Capitals in their turn will form a road system and get even more advantages.

The first considered geographical feature is a land elevation — mountainous regions are not suitable for towns and get less points. The next one should be (not yet implemented) biome, for obvious reasons lowland desert is not preferable to temperate mountainous forest.

The next factor is harbor. We are generating islands and having a sheltered sea haven is a big advantage. For each coastal land polygon I check how many ocean polygons it’s bordering. The land polygons having only one sea neighbor are the ones with a sheltered haven.

The polygons having a river also get an advantage. The bonus depends on a river flux value. A spots with a river confluence or near the river estuary get additional bonus points.

Now, when we have score for each land polygon, we sort them in descending order and add the site of the first polygon to a new array. Based on a user defined capitals count we define a minimal distance between capitals, so new capitals won’t be generated too close to existing ones. For each next polygon we invoke a distance check and if it is passed, we add the polygon’s site to a burgs array. Do the same until all capitals are placed.

20 capitals placement gif

As you can see from the gif above capitals distribution is pretty good. I’m not even sure I can place them better manually. From the first glance there are too much coastal attraction, but it’s hard to imagine an Island capitals located far from a coastline or a major river.

All the described calculations take about 3 milliseconds, it’s pretty fast and we can move forward.

Roads

To continue with settlements we have to add some “economical simulation”. I don’t want to place all burgs just based on a geographical ranking, to make the distribution more plausible I want to unite previously defined capitals with roads and re-rank land polygons based on path availability and repetition.

To generate a route between two points we need to implement a path finding algorithm. It’s a well-know problem, described in various sources and comprehensively covered by Amit Patel. I’m not going to even try to do something comparable and will just state that I have used two algorithms — A* (to find a path between two points) and Dijkstra (to find a path from one points to all).

We have precreated graph, so the first step is already done. The next step is to define a path finding rules. To get a plausible-looking roads algorithm should consider traveled distance (the shorter the better), polygon elevation (avoid mountains if possible), existing roads (pave a new way only if it’s really needed), existing burgs (pass through burgs by the way if any), region borders (new border is a new customs duty) and even rivers (towns usually located on a river banks).

It took a lot of time to make it work as even a small change in any modifier drastically change the output. Existing roads modifier was especially hard to fine-tune. It didn’t work as desired, so I change the modifier to a constant value. It means that a movement using existing path costs 0.15, while a new road creation is much more expensive and depends on the described constituents. The result is pretty neat:

Map with generated capitals and main roads

Path finding algorithms are slow and I’m not sure I can significantly improve the performance here. I’ve tried to use Dijkstra and unite all capitals in one turn, but the generated road systems were too much aligned to a source cities. So I’m still using a straightforward approach and just unite all capitals one be one. Not the best variant, only this part takes about 85ms.

Towns

Claiming a new road element I assign a path attribute = 1 to the appropriate polygon. Each time this polygon is used as a road I increment this value. When roads generation is completed we get a path value assigned to all polygons with roads. Now we can re-evaluate the road polygons, i.e. add “economical” bonus to the “geographical evaluation” score. Crossroads get even more additional points and I founds them a good spot to place taverns or other points of interest in the future.

The next step is to sort land polygons by score and repeat a burgs generation routing up to the moment when all burgs are defined. In this case I don’t check the actual distance between settlements, we have about 500 towns and this is too much calculations.

Selecting a polygon as appropriate place for a burg I set all the neighboring polygons as used, so I can omit the distance check. The problem here is that the town generation is too monotonous, usually the most scored polygons are located close to each other and it’s not possible to get a town somewhere in a mountains, even on a river and near a road. So I have to add a small random factor the the scores prior to the polygons sorting. This randomness helps to make towns distribution more disperse, but I have a strong feeling that distance check should work better. Not super happy with the result, but it’s still quite good:

Map with generated capitals, main roads and towns

Nothing special here, so towns generation usually lakes about 10 milliseconds.

Regions

Having all cities and towns defined we can divide land into regions. One region per capital. Initially regions were considered as areas uniting towns of the same culture, now I’m almost ready concede regions as countries.

To define a region we need to assign a region number to each land polygon and then unite all polygons of the same region into one big polygon. The are no any build-in functions here, so it requires quite a lot of calculation, especially a part when we combine separate polygons into one big area.

Assignment part is easier. For each town we detect a closest capital city and assign its number as an actual region value. Then we do the same for all undefined land polygons, but looking for a closest manor. I have an option to determine a maximum distance to a closest manor, if the actual distance is greater, region won’t be assigned to the polygon and it become a neutral land. The neutral lands are good places too add some abandoned ruins or city-states in the future.

The logic above produces a good-looking, but too much unified regions. Our capitals are generated to be far from each other, and using a closest capital routine we get regions that look almost the same. To make it more interesting I introduced two custom parameters — disbalance and power. Each capital has unique attractiveness power, which is randomly assigned to it based on a disbalance value. Disbalance is the same for all capitals, it only controls the randomness of power definition. Calculating a distance to the closest capital we multiply this value by capital’s power. If capital located not on the same island, we double the distance as it should not be easy for city to get an overseas possessions. As all capitals have different “powers”, the regions vary in area. For some reasons user may want regions having almost the same area, so the disbalance value could be changed.

The same map showing regions, disbalance is medium

As I said before there are a lot of calculations behind these solid regions. It’s not fast, the definition and rendering take about 180ms.

Ports

The coastal settlements that have a safety harbor are considered as ports. Usually there are not much ports, so port have to be significant settlement even it’s not a capital. If island has settlements, but none of them is recognized as port, I invoke a separate function that find the best candidate to be a port or, if there are no coastal towns at all, remove implausible settlements and leave the island uninhabited. This routine is implemented to prevent a situation when island settlements are unreachable for an inter-island trade.

To show significance of the ports I have added one more routine. If a region capital is not a port, we draw a road from this capital to a closest port of the same region as a primary road. You may see this feature on the image below, the primary road on the top connects a capital and a port town.

Both features are small and fast, it takes about 5ms in general.

Secondary roads

The initial idea was that each and every settlement should be connected by roads. I don’t have and don’t want to generate villages, while even a small town is a center of trade and craft and should be connected with other settlements. Filling all the map with roads like on a screenshot above will turn the map into a mess, so I have to make a subtle secondary roads system, that won’t be distinct on a general view.

The first thing I’d tried was Dijkstra algorithm. I’d united all my towns by roads, but road system looked like a tree branches or river system. The problem was that I had a single function and wasn’t able to fine-tune it, even the idea was good. Jumping over a few other attempts, I decided to use an algorithm used for capital roads to add trunk roads and then just unite every not united town with a closest polygon. Simple routing and not a great result, but pretty good in general. If there are not too many towns roads look much better:

Secondary roads – general look

Secondary roads – detailed look

As there are hundreds of towns, the calculation is slow and takes about 180ms. Not sure how, but I hope to improve the performance in the future.

Sea routes

Going forward with the global connectivity idea we need to unite ports by sea lanes, representing both cabotage and direct inter-islands trade routes. Most of the redundant sea polygons were discarded on a graph optimization, so we can try to connect all ports at once using Dijkstra algorithm.

Firstly we need to prepare an array having all ports within an island on a separate dimension. Using Dijkstra we define only a start point and it will be connected with all other accessible points. Assigning the first port as a start point we get paths to it from all other ports on the map. To avoid the mess in sea routes, I set a significant penalty for a new route element creation.

To prevent an implausible inter-island connections and speed up calculation I generate only one mandatory route between islands. This route is path from a current to a biggest island on the map. I connect an island with other islands only if both are pretty substantial, i.e. have at least 4-5 ports. At the end all ports are connected and the connectivity level depends on both geographical (some ports get transit routes) and economical (island weight is considered) significance.

There is a bug here. We connect all island ports with a first port on the island, so there is always a gap on the opposite side of the island. People usually select the nearest way and hence these gaps look weirdly:

Ocean routes. Gaps are shown in orange frames

To fix it I need to define the most distant port from start point on the same island and check the cost of the path from it to other port via already created routes. If the cost is greater at least in 4 times than a direct route cost, the gap is identified and I draw a missed route here. Sounds difficult and it’s quite complicated and resource demanding. In general sea routes generation takes about 50ms, it’s acceptable time.

Still the same map, but now will all routes shown

I got a feedback that sea routes lay too close to coasts and it looks not cool. But I find it nice considering cabotage routes have to follow a coastline and I don’t have an easy way to outline it further.

Labels

This section will cover the settlement and region names generation. Initially I had a separate premade list of town names based on a historical names used in different cultures. I was happy with this approach for a Dynasty project, but for a Fantasy map generator I want names to be procedural.

To generate a plausible name I’m using a well-known approach based on Markov chain. A premade archive of a real-world English town names (available here) is used as a training material. Algorithm analyzing it and create an object, which in fact defines a probability of every letter to be used after a given letter. You may try this page to get into the idea.

There are several things that should be considered. Firstly I don’t allow generated name to contain 3 consonants or vowels in a row. Secondly I use spaces as a word end marker. If the name already has at least 3 letters and the next generated character is space, the word is completed. Thirdly I don’t want long words, so the maximum word length is seven letters.

Not the best implementation, but the result names sounds really good and fabulously. Here just a list of first 10 generated names without any manual intervention:

Waly, Gtonele, Ghurydo, Cheamam, Warorou, Bangest, Fowe, Blamors, Bord, Dheash

Next we need to generate a region names. There are two options here: we can generate a unique name or use a capital name as a base. In both cases we can change it to sound more like a country name. The easiest way is to replace the vowel ending to the Latin suffix -ia or just append it to the end. To make it more obvious here is the list of the same names as above turned into a region names:

Walia, Gtonelia, Ghurydia, Cheamamia, Waroria, Bangestia, Fowia, Blamorsia, Bordia, Dheashia

I’m not going to use this approach every time, but about 60-80% of region names follow this logic. We can also invent our own suffixes or entire meaningful roots like real-word –land or –stan, but I’ll leave it for a future.

When names are generated, we have to place the labels on a map. As of now I just place town names above the appropriate icons, not considering any features or possible intersections. As a workaround I made all labels draggable and editable. To place region labels I have to calculate a pole of inaccessibility of the region polygon. It’s not so easy to do, but hopefully there is a js library by Vladimir Agafonkin that resolves it quite fast (about 50ms).

The same map, again, now with labels and subdued routes

It’s all for today, all described features are available in the generator Demo. I appreciate if you like it or even use for a real D&D game. Do not hesitate to ask questions in the comments, report bugs, request new features or contact me directly via email.