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.

capitals placement
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:

2. Main roads
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:

3. Towns
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.

6-2. Regions
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:

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 island gaps
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.

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

8. Labels
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.

Advertisements

33 thoughts on “Settlements, Regions, Routes and Labels

  1. Dude, your generator is simply amazing! It is currently the best random map generator for people who want to edit the end result.

    Thank you for working on such a flexible and interesting tool.

    Liked by 1 person

  2. I’m not the one you where asking to but a toggle to view the position of tectonic plates in order to know where earthquakes are more frequent would be the first thing that comes to mind, also a customizable scale bar and making more clear when something is toggled or not in the menu would be appreciated.
    I could go on for days but I love this tool and your blog and I don’t want to overwhelm you with requests.

    Like

    1. Hi! There is no tectonic plates simulation as of now, so it’s kinda difficult to implement. I may add tectonics in the future.

      “Customizable scale bar” – added to my to-do list. Good idea.

      “more clear when something is toggled or not in the menu” – added to my to-do list; I don’t like the current UI at all, but however I’m going to improve it a bit.

      “I could go on for days” – please continue, I need all the feed you may provide 🙂

      Like

  3. About the tectonic plates: look at this map https://www.mapsofworld.com/thematic-maps/earthquake/major-tectonic-plates.html usually tectonic plates are either roughly a continent and surrounded by the ocean or are divided by a very big mountain chain so it shouldn’t be too hard to implement if you follow these lines. Look here for more info: https://www.reddit.com/r/mapmaking/comments/7i7rzd/tectonics_and_mountain_placing/dqwr314/ or here https://www.cartographersguild.com/showthread.php?t=2238

    For the scale bar: be sure to add both the imperial and metric system.

    The current UI isn’t great but for time being I think that simply changing the colour of something you toggle should work just fine, I’d prioritize adding some functions for now, but of course it’s your call.

    About other ideas: as of now your tool is perfect for a single continent but it’s not as great for world creation simply because you can add just one “island” (unless there’s just one continent in your world). One simple thing would be letting the users create more than one island so that each one will be a continent when the map is finished. The perfect thing would be letting the users select one of the island created and expanding/reducing just the selected one at time so that you have exactly the result you want and maybe each hill you create is grouped with an island so you effectively expand/reduce a group (continent) at time.

    One thing I’d add is a culture bar so that we can choose how many cultures we have (maybe a pop-up that suggests of how many cultures we should have, basically the calculation you do know, could be useful).

    Also: temperatures! Temperatures are so important look at this video if you want some info: https://www.youtube.com/watch?v=y3Kb_ik5f-I

    And this brings me to world simulation: ideally being able to select all the things that are here https://docs.google.com/spreadsheets/d/1Y2oVmNk9bjnG2tVtXoJGJLg9BPzSW63iVX0mXbJRWoE/edit#gid=0 (you should watch that video if have time) but I think that something like this requires a completely UI overhaul.

    I think that implementing all of this will take you a loooot of time so I’ll stop here but I just want to add that having a lot of things to implement doesn’t mean that your tool sucks, I know from personal experience that you can get overwhelmed with requests so just do what you like/think is more useful first. I love this tool, YOUR tool, I just happen to have ideas to improve it!

    Like

    1. Thanks for the great ideas!
      I may add tectonics, but don’t want it to be vice versa. So mountains should depend on plates, not conversely. And it’s not easy task, you are right.

      “For the scale bar: be sure to add both the imperial and metric system.” – sure, and your own custom scale could be a third option. It would be a toggle element, like minimap or even maybe with minimap.

      “changing the colour of omething you toggle” – will do it soon.

      “it’s not as great for world creation” – yes, I know. I cannot just say “create 3 islands”, it’s more like I set only general rules, templates, and generator create the world without ability to control the creation. There are some workarounds here. First, I can implement heightmap templates – https://azgaar.wordpress.com/2017/10/05/templates/. Second, I plan to allow user to “draw” the map shape, it will add a lot of free space for a world map creation. But even in this case the map scale is not enough for a good-looking world map. There is a possibility to enlarge the scale, here some experiments with scale:





      “how many cultures we have” – it’s in my to-do list

      As of temperatures, I consider temperature as part of biome definition. This is already developed, but not implemented to demo version. There are a lot of aspects here, like wind simulation etc. Hope I’ll manage to integrate this part to the Demo.

      Like

      1. Yeah I need to play with scale more. I love it!
        Have you changed anything? I can’t use the “-” anymore (it works but the white terrain area doesn’t retreat, even if all the other things interact with it as if it was retreated).
        Anyway, I can’t wait for the next version (I’ve played with the github repo a bit I can’t finalize the map after the terrain), but this is really great, I’d help you with development but I don’t really know anything about web development.

        Like

    1. Hi Dushan!

      As of now you can only try to customize the map (Options -> Customize -> Clear -> Add Hill -> Add Hill (repeat if needed) -> Complete), you cannot select template or “draw” the map. Both these options are in my to-do list.

      Like

  4. Hi there! I’m absolutely in love with your creation and wanted to use it to work on my homebrew campaign, but my biggest issue is that I can’t really save any of my maps to tweak later! I really hope a save option other than the .png files is implemented soon

    Like

  5. Your last update just brought this to a whole new level! The only thing I believe could possibly be lacking from this wonderful generator is some native “stickers” for forests, canyons and similar landscape features (with a click to insert option), this would remove most of the editing necessary for final use. Sorry for showing with stupid requests, but this is too good for me to stop prodding you for more.

    Like

    1. Hi! I’m planing to add an icon editor with some icons available by default and, maybe, an ability to use any external images as icons (like you are able to use any external font now). I’m working with save/load function this month, I hope I will cover icon editor in January.

      Like

  6. Hey, just found out about your generator and it is great! Is there a chance that export can be done in a higher resolution than currently possible? I’d love to be able to actually zoom all the way so that I can see the complete island and zoom in so I can see all the settlements.

    Like

  7. Hi, I’m loving your map generator so far! Is it possible to manually relocate capitals? I’d generated a map I really liked, but our group has already defined the socio-political layout of the world so I just started manually editing regions to match; however, my island nation’s capital was placed on the *far* side of the central island (away from the “mainland”)! I think moving it to the mainland-facing side would make more sense, as that would more easily facilitate trade with other nations (especially since the open ocean is much nastier than the channels!)

    Like

    1. Thanks! Yes, it’s possible. You need to open a “Burgs Editor” and there is a star-iconed button to change a capital. To open Editor you need to open a “Countries Editor” first and then click on a “Burgs” count (circle icon) for a country line.

      Like

  8. А будет ли реализована ручная коррекция границ страны? Есть моменты, когда небольшой кусочек страны явно лишний или линия границы проходит не так, как нужно.
    Возможно это уже реализовано, но я не смог найти.

    Like

    1. It’s the “brush” button in the Countries editor (see https://imgur.com/5itBMhZ ). After clicking it, select the country from the list that you wish to reassign territory to, adjust your brush size, and “paint” the incorrect territories.

      Be sure to click the “check mark” button when you’re done to apply the changes!

      (через Google Translate)
      Используйте кнопку «кисть» в редакторе «Страны» (см. https://imgur.com/5itBMhZ ). После нажатия кнопки выберите страну из списка, для которого вы хотите переназначить территорию, отрегулируйте размер кисти и «нарисуйте» неправильные территории.

      не забудьте нажать кнопку «галочка», когда вы закончите, чтобы применить изменения!

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s