Procedural map generation (+ Alpha 3.fun testing)
Honorable Knights,
Let's talk about maps today. Maps are fascinating. They can be decorative and inspirational, making us dream of faraway places and the spots that haven't been explored. There may be tigers here.
But before diving into the topic of how maps are made in Knights of Frontier Valley, I'd like to share how the Alpha 3.fun release is going which went out to testers a week ago.
The amount of feedback is absolutely fantastic. I am reading all of it and try to address issues quickly, and it is amazing how much the game has improved in just in a few days. First, of course, there were bug fixes. The game seemed stable before the release, but players have a knack for finding weaknesses in the code right away. Many of them were reported by Alpha tester Eric Hensel - I appreciate his contribution.
64 bugs have been addressed since the release, with a few more on my radar. If anyone is interested in the detailed change list:
https://steamcommunity.com/app/1085830/discussions/0/601897333646473798/?ctp=6
Then there were balancing and QoL improvements. Some opponents are now easier to beat, and the effects of bleeding have been further reduced, to name two examples.
The code now supports displays with an aspect ratio other than 16:9, which seem to be more common than I thought (or the Steam hardware survey would suggest).
There is a new indicator when moving between city quarter maps now, better showing where you are going. Many more things are on my list, mostly about making it clearer just how some of the unique features that you won't find in other games work.
This simple overview makes navigating between city quarters much clearer
But what really blew my mind is that Alpha tester ChavaiotH managed to make the game run smoothly on a Mac, in this case on Apple silicon. We have our first modder! To me it's amazing since the game code includes native libraries compiled for Windows, but it is great. Maybe we are closer to a Mac version than expected. ChavaiotH is also a Patron and I am very grateful for the support.
Testing will continue for another week; then, after a short break, I will jump right into moving towards the next milestone: the public demo. Work on the demo really has already started on the side over the last few days; I designed the story for the demo quest, and new graphics are in the works.
Now on to Maps!
in Knights of Frontier Valley, maps for the world, the towns, dungeons, buildings, and the wilderness all have their own map generator logic and are created differently, so I will talk briefly about each of them.
[h3]World map[/h3]
The world in KoFV is quite large - I once calculated it to be around 138.000 square kilometers big, roughly the size of the country of Greece. If you were to travel across it at a normal walking pace, or even on horseback, it would take a long time.
No one enjoys walking for days to get from one place to another in a game, so time passes much quicker on the world map, and large distances can be covered fast. Since the world map's sole purpose is to get around easier, I often refer to it as the "travel map".
The design intend was to make it so that players could get lost in the wilderness, so you still need to spend some time traveling between places, and you can lose your way if you stray off the roads.
Visuals are abstract on the travel map. It shows grasslands, forests, hills, mountains, cities, dungeons and other points of interest, but intentionally not in very high detail.
You can encounter and talk to other characters there, but real exploration or complex interactions, like combat, happens on any of the detailed local maps desribed below.
The travel map is also the only map that is internally built on hexes - all local maps use squares. This design decision was made with "The Isle of Dread" in mind, one of my favorite D&D tabletop modules.
You can see further from hilltops on the travel map
The world map is procedurally generated, making it look differently in each new game. But what does "procedurally" really mean? First off, it does not mean "random". A map that is completely random will be hit or miss... sometimes, if you are lucky, things might make sense, but in many cases they will not.
"Procedural" means the map is auto-generated, but rather than just randomly placing stuff, the world-builder code follows a set of rules to ensure the map will always make sense. Those include:
Terrain selection:
There are various algorithms to fill a world with areas of different terrain. The one I am using, known as "Cellular Automata", can quickly generate maps with a natural and diverse terrain distribution. Cellular Automata starts by adding "seeds" for hills, mountains, lakes, forests, and other terrain features all over the map. Those seeds then "grow" in a natural manner in different directions, following a specification that dictates things like a forest's maximum size.
The algorithm is very easy to implement and the results look good, but its simplicity also has a drawback: it produces a terrain layout that looks similar all across the world. Unless adding additional logic, there will not be any areas that are particularly forested (or without forests), for example. There will not be any oceans or large mountain ranges that divide areas of the map. It looks good, but is a bit repetitive.
Other terrain algorithms work differently. The Simplex algorithm, for example, does not place forests or lakes on the map. Instead, it generates natural elevation patterns which can then be used to fill the world with fitting terrain features. Water tends to flow downhill, so it would be placed in areas of lower elevation, while forests need water to thrive and will not appear above a certain altitude. Switching to Simplex for more natural-looking world maps is something I have on my to-do list for a later update.
POIs (points of interest):
Points of interest include settlements, dungeons, countryside inns, farms, windmills, and much more. In KoFV, the world builder is making sure settlements are not too close and not too far apart either, and they can be connected with roads (and are not accidentally surrounded by unsurmountable mountains, for example). Dungeons should not be too close to cities, and dwellings of warring factions should have some distance between them. There are many more rules like this.
Pathways (roads and rivers):
Roads should lead around lakes, hills, and mountains and should preferrably not go through dense forests if it can be avoided. This makes roads behave just like a normal character path, which also does those same things. Hence, for placing roads between towns, I am using the same code that also calculates a character's path.
Rivers work slightly differently, as they do not have a specific end point. Where roads and rivers cross, bridges might be placed.
NPCs:
Roaming NPCs on the world map are not placed by the world builder, but their presence is continuously managed by a "wilderness behavior pattern". This behavior pattern is just one of many I developed to control NPC behavior in certain areas or for certain NPC roles. There are patterns for controlling NPC buyers and sellers at the town market, for example. There is one for the town watch, for guard patrols, and for the guards standing in front of the city gate or on top of towers. More behavior patterns are planned for the tavern (controlling the behavior of staff and patrons), residential houses, and more. With more behavior patterns being added to the game, the overall NPC behavior will become increasingly complex, but it is modular and easily controllable.
[h3]Dungeons[/h3]
Dungeon maps are also procedurally generated, but in a very different way. The map maker produces a layout based on the purpose of dungeon rooms, including strorage rooms, cells, underground forges, and many more. Those rooms are connected via hallways in the most efficient manner. While the layout and the contents of a dungeon will look differently in each new game, rooms will always be laid out in a way that those that should be close to each other will indeed be close. There is also a concept of "public" and "private" dungeon areas... one example of a private room would be a treasure room with a locked door, so wandering NPCs cannot help themselves and loot the place before the player gets there.
There are various kinds of dungeons, and they all look differerently and are built using custom code. Natural caves are assembled in a different manner than goblin caves or human underground prisons.
Yes, I know. Undead skeletons should not suffer from tissue damage. It's fixed now.
[h3]Buildings[/h3]
I found that maps of buildings that are created in a fully procedural manner just do not look right. Buildings are very complex, and we all have developed an instinct of spotting something that looks odd here right away. There are walls, doors, windows, stairs, chimneys, furniture, decorative items and more, and trying to place those automatically in a way that looks natural and liveable will require complex generative AI and custom machine learning. Not only would such a project exceed the scope of this game (remember, this is a one-man show), but I also decided a long time ago not to use any generative AI in KoFV whatsoever.
My goal was to present the player building maps with such a large variety that it would appear to be endless. Players are able to enter every building in the game, and they should not feel like they have seen the same room layout and furniture setup elsewhere. But while there should be an endless amount of varieties, those maps should also be human-made to make sure everything is placed logically. How could those conflicting goals be reconciled?
I did the following: using a building map editor I made for this purpose, I created a number of base layouts for every different type of building and each potential orientation it might be placed in the world, and then added procedural logic to make the material of the walls and floors variable. Additionally, the types of furniture you would find in the house, and the container contents, are also variable. So a table would always be at the same spot in houses using the same base layout, but it would stand in a room that might have different walls or floors, and it could be a different type of table and have different things on it. There are more than 160 different base layouts (it took weeks to design them), and together with the procedural variations, now every house in the world looks differently inside.
There are a few buildings in KoFV that are unique and have no procedural variation at all, and those are the taverns. Taverns are the "home bases" in fantasy RPGs, and I wanted the player to feel at home here - a feeling that never really comes up when the map looks differently in each game.
Villas like this are great places for finding loot, if you see the law as just a recommendation
[h3]Cities[/h3]
City maps are the only ones that are not procedurally generated in KoFV. I started with an attempt to also auto-generate those, but quickly found that it is no fun having to look for the general store in every new game. Additionally, medieval towns often had a similar layout (market near the center, stores placed around it, cemetery outside, loud and smelly businesses like smiths or tanners in a separate quarter, and so on). When creating town maps procedurally using that logic, the result would often look quite similar, which defeats the purpose of having procedural maps in the first place.
So I stopped doing it and created all city maps by hand. I made a different map editor for it, and it's fun to use!
Thyle West, known as "The Patch", is not exactly a prime real estate area and should be avoided at night
[h3]Wilderness[/h3]
When combat starts on the world map, the view switches to a local wilderness map where trees, bushes, rocks, and every blade of grass is shown. But the player actually can decide to switch to that view at any time outside combat, too, which can be useful when looking for food like berries or mushrooms, rare plants, firewood, or other useful items nature provides.
Local wilderness maps are procedurally generated, but once objects like trees or bushes on that area are determined, they will always remain there (well, mostly).
Those maps also go by the terrain type found on the travel map, so if you switch to the local map while at the edge of a forest with a mountain nearby, those same terrain features will accurately be placed on the local map at the right spots.
You will be fine, they said. Just stay close to the road, they said. But where did the damned road go?!?
Now you learned everything there is to know about maps in Knights of Frontier Valley! If there are any questions, let me know in the comments.
Until next time,
Martin
Let's talk about maps today. Maps are fascinating. They can be decorative and inspirational, making us dream of faraway places and the spots that haven't been explored. There may be tigers here.
But before diving into the topic of how maps are made in Knights of Frontier Valley, I'd like to share how the Alpha 3.fun release is going which went out to testers a week ago.
The amount of feedback is absolutely fantastic. I am reading all of it and try to address issues quickly, and it is amazing how much the game has improved in just in a few days. First, of course, there were bug fixes. The game seemed stable before the release, but players have a knack for finding weaknesses in the code right away. Many of them were reported by Alpha tester Eric Hensel - I appreciate his contribution.
64 bugs have been addressed since the release, with a few more on my radar. If anyone is interested in the detailed change list:
https://steamcommunity.com/app/1085830/discussions/0/601897333646473798/?ctp=6
Then there were balancing and QoL improvements. Some opponents are now easier to beat, and the effects of bleeding have been further reduced, to name two examples.
The code now supports displays with an aspect ratio other than 16:9, which seem to be more common than I thought (or the Steam hardware survey would suggest).
There is a new indicator when moving between city quarter maps now, better showing where you are going. Many more things are on my list, mostly about making it clearer just how some of the unique features that you won't find in other games work.
This simple overview makes navigating between city quarters much clearerBut what really blew my mind is that Alpha tester ChavaiotH managed to make the game run smoothly on a Mac, in this case on Apple silicon. We have our first modder! To me it's amazing since the game code includes native libraries compiled for Windows, but it is great. Maybe we are closer to a Mac version than expected. ChavaiotH is also a Patron and I am very grateful for the support.
Testing will continue for another week; then, after a short break, I will jump right into moving towards the next milestone: the public demo. Work on the demo really has already started on the side over the last few days; I designed the story for the demo quest, and new graphics are in the works.
Now on to Maps!
Maps
in Knights of Frontier Valley, maps for the world, the towns, dungeons, buildings, and the wilderness all have their own map generator logic and are created differently, so I will talk briefly about each of them.
[h3]World map[/h3]
The world in KoFV is quite large - I once calculated it to be around 138.000 square kilometers big, roughly the size of the country of Greece. If you were to travel across it at a normal walking pace, or even on horseback, it would take a long time.
No one enjoys walking for days to get from one place to another in a game, so time passes much quicker on the world map, and large distances can be covered fast. Since the world map's sole purpose is to get around easier, I often refer to it as the "travel map".
The design intend was to make it so that players could get lost in the wilderness, so you still need to spend some time traveling between places, and you can lose your way if you stray off the roads.
Visuals are abstract on the travel map. It shows grasslands, forests, hills, mountains, cities, dungeons and other points of interest, but intentionally not in very high detail.
You can encounter and talk to other characters there, but real exploration or complex interactions, like combat, happens on any of the detailed local maps desribed below.
The travel map is also the only map that is internally built on hexes - all local maps use squares. This design decision was made with "The Isle of Dread" in mind, one of my favorite D&D tabletop modules.
You can see further from hilltops on the travel mapThe world map is procedurally generated, making it look differently in each new game. But what does "procedurally" really mean? First off, it does not mean "random". A map that is completely random will be hit or miss... sometimes, if you are lucky, things might make sense, but in many cases they will not.
"Procedural" means the map is auto-generated, but rather than just randomly placing stuff, the world-builder code follows a set of rules to ensure the map will always make sense. Those include:
Terrain selection:
There are various algorithms to fill a world with areas of different terrain. The one I am using, known as "Cellular Automata", can quickly generate maps with a natural and diverse terrain distribution. Cellular Automata starts by adding "seeds" for hills, mountains, lakes, forests, and other terrain features all over the map. Those seeds then "grow" in a natural manner in different directions, following a specification that dictates things like a forest's maximum size.
The algorithm is very easy to implement and the results look good, but its simplicity also has a drawback: it produces a terrain layout that looks similar all across the world. Unless adding additional logic, there will not be any areas that are particularly forested (or without forests), for example. There will not be any oceans or large mountain ranges that divide areas of the map. It looks good, but is a bit repetitive.
Other terrain algorithms work differently. The Simplex algorithm, for example, does not place forests or lakes on the map. Instead, it generates natural elevation patterns which can then be used to fill the world with fitting terrain features. Water tends to flow downhill, so it would be placed in areas of lower elevation, while forests need water to thrive and will not appear above a certain altitude. Switching to Simplex for more natural-looking world maps is something I have on my to-do list for a later update.
POIs (points of interest):
Points of interest include settlements, dungeons, countryside inns, farms, windmills, and much more. In KoFV, the world builder is making sure settlements are not too close and not too far apart either, and they can be connected with roads (and are not accidentally surrounded by unsurmountable mountains, for example). Dungeons should not be too close to cities, and dwellings of warring factions should have some distance between them. There are many more rules like this.
Pathways (roads and rivers):
Roads should lead around lakes, hills, and mountains and should preferrably not go through dense forests if it can be avoided. This makes roads behave just like a normal character path, which also does those same things. Hence, for placing roads between towns, I am using the same code that also calculates a character's path.
Rivers work slightly differently, as they do not have a specific end point. Where roads and rivers cross, bridges might be placed.
NPCs:
Roaming NPCs on the world map are not placed by the world builder, but their presence is continuously managed by a "wilderness behavior pattern". This behavior pattern is just one of many I developed to control NPC behavior in certain areas or for certain NPC roles. There are patterns for controlling NPC buyers and sellers at the town market, for example. There is one for the town watch, for guard patrols, and for the guards standing in front of the city gate or on top of towers. More behavior patterns are planned for the tavern (controlling the behavior of staff and patrons), residential houses, and more. With more behavior patterns being added to the game, the overall NPC behavior will become increasingly complex, but it is modular and easily controllable.
[h3]Dungeons[/h3]
Dungeon maps are also procedurally generated, but in a very different way. The map maker produces a layout based on the purpose of dungeon rooms, including strorage rooms, cells, underground forges, and many more. Those rooms are connected via hallways in the most efficient manner. While the layout and the contents of a dungeon will look differently in each new game, rooms will always be laid out in a way that those that should be close to each other will indeed be close. There is also a concept of "public" and "private" dungeon areas... one example of a private room would be a treasure room with a locked door, so wandering NPCs cannot help themselves and loot the place before the player gets there.
There are various kinds of dungeons, and they all look differerently and are built using custom code. Natural caves are assembled in a different manner than goblin caves or human underground prisons.
Yes, I know. Undead skeletons should not suffer from tissue damage. It's fixed now.
[h3]Buildings[/h3]
I found that maps of buildings that are created in a fully procedural manner just do not look right. Buildings are very complex, and we all have developed an instinct of spotting something that looks odd here right away. There are walls, doors, windows, stairs, chimneys, furniture, decorative items and more, and trying to place those automatically in a way that looks natural and liveable will require complex generative AI and custom machine learning. Not only would such a project exceed the scope of this game (remember, this is a one-man show), but I also decided a long time ago not to use any generative AI in KoFV whatsoever.
My goal was to present the player building maps with such a large variety that it would appear to be endless. Players are able to enter every building in the game, and they should not feel like they have seen the same room layout and furniture setup elsewhere. But while there should be an endless amount of varieties, those maps should also be human-made to make sure everything is placed logically. How could those conflicting goals be reconciled?
I did the following: using a building map editor I made for this purpose, I created a number of base layouts for every different type of building and each potential orientation it might be placed in the world, and then added procedural logic to make the material of the walls and floors variable. Additionally, the types of furniture you would find in the house, and the container contents, are also variable. So a table would always be at the same spot in houses using the same base layout, but it would stand in a room that might have different walls or floors, and it could be a different type of table and have different things on it. There are more than 160 different base layouts (it took weeks to design them), and together with the procedural variations, now every house in the world looks differently inside.
There are a few buildings in KoFV that are unique and have no procedural variation at all, and those are the taverns. Taverns are the "home bases" in fantasy RPGs, and I wanted the player to feel at home here - a feeling that never really comes up when the map looks differently in each game.
Villas like this are great places for finding loot, if you see the law as just a recommendation[h3]Cities[/h3]
City maps are the only ones that are not procedurally generated in KoFV. I started with an attempt to also auto-generate those, but quickly found that it is no fun having to look for the general store in every new game. Additionally, medieval towns often had a similar layout (market near the center, stores placed around it, cemetery outside, loud and smelly businesses like smiths or tanners in a separate quarter, and so on). When creating town maps procedurally using that logic, the result would often look quite similar, which defeats the purpose of having procedural maps in the first place.
So I stopped doing it and created all city maps by hand. I made a different map editor for it, and it's fun to use!
Thyle West, known as "The Patch", is not exactly a prime real estate area and should be avoided at night[h3]Wilderness[/h3]
When combat starts on the world map, the view switches to a local wilderness map where trees, bushes, rocks, and every blade of grass is shown. But the player actually can decide to switch to that view at any time outside combat, too, which can be useful when looking for food like berries or mushrooms, rare plants, firewood, or other useful items nature provides.
Local wilderness maps are procedurally generated, but once objects like trees or bushes on that area are determined, they will always remain there (well, mostly).
Those maps also go by the terrain type found on the travel map, so if you switch to the local map while at the edge of a forest with a mountain nearby, those same terrain features will accurately be placed on the local map at the right spots.
You will be fine, they said. Just stay close to the road, they said. But where did the damned road go?!?Now you learned everything there is to know about maps in Knights of Frontier Valley! If there are any questions, let me know in the comments.
Until next time,
Martin