Development Update - June 2024

Hey everyone, hope you're doing well. I haven't released any major new features since the last post, but I have been hard at work (and have gone down a few tangents...), so I wanted to show you what I've been up to.

3D Terrain

After the 3D view after the last update (and all the people asking for mountain maps), it made sense to me to work on adding height information to settlements. One of the most common ways to generate a height map is to use perlin or simplex noise.

One immediate challenge is deciding where the height information should be stored. One option is for all of the existing 2D points in the file to become 3D. Another option is to use a separate height map to record the height around the map at a specified resolution. I decided to go with the height map approach, as the first option doesn't work well for the way things are currently stored in the file. For example - a road segment is only two points, so I would record the height at each end, but I wouldn't record the height in the middle of the road without additional processing. Another nice property of a height map is that there is potential for it to be lazy loaded from a seed, so I don't actually need to store it for every settlement, and just create on the fly.

Ok, so we have a height map, now what? The next step for me was to try and have this height map render in the 3D mode, starting off with just a single background texture covering the map. This seemed to go well, and then I tried to show buildings at the correct height. This did not go well...

For some reason, the background wasn't lining up with the height map.

After a fair amount of debugging, I realised that the math working out where the buildings fell on the map was wrong (if I remember correctly, I might have had a +y instead of a -y somewhere). After that was fixed, it now looks like:
Much better! But we're still only using a single background object, not the normal background textures. The nice thing about this background object is that it's easy to have it tessellate (broken up into repeating triangles of a similar size).

Quick background on computer graphics rendering - everything you see is a triangle. The points of the triangle are the positions we can move to create the height. The background object I was using initially was a single plane that had been tessellated to triangles with widths and heights matching the resolution of the height map. Essentially, it looks like this, repeated across the whole map:

To stress how simple it was to get this, it's just a single line of code:

new PlaneGeometry(mapWidth, mapWidth, heightMapWidth, heightMapWidth)

Now, the background textures aren't as nice. By default, they are triangulated into not very even shapes:

If we just update the existing triangle points to use the height from the height map, the middle of these textures don't get any height information. We need to break the shapes up into more regular triangles, ideally lining up with each other to reduce clipping (as the settlement map allows for layering of textures. After that, the triangles look at lot more dense and regular:

Unfortunately, a lot of clipping occurs:

I tried messing around with the tessellation a lot to solve this, but I couldn't find a good way to solve it with the existing parameters, that wouldn't sacrifice too much. I then discovered a way to essentially do polygon math - specifically subtraction (thanks clipper!). This library lets me take one polygon (e.g. one in the background), and subtract another from it (e.g. one on top) to create a new set of polygons. This means I can avoid clipping entirely as I can ensure nothing wil render on top of each other. This also improves performance, as we don't have to render the extra triangles behind the top textures. With this, and updating all the other settlement entities to use the height map, we get something that looks like:

Some clipping still occurs on roads, but it's minimal so I plan to leave that as is. The next steps for the height map generation is to have it respect water bodies - currently rivers/oceans will just render below everything. I also want to handle larger mountains, instead of just the rolling countryside currently supported.

Map Scale

While working on the 3D mode, and height maps, in street view something felt off. All the buildings felt very long to walk beside, especially compared to their height. I thought I had used a 1:1 scale between meters and internal users, so to investigate I added a ruler feature, that lets you click a point on the map and see how far away it is from something else. Turns out, I was not using a 1:1 scale in the x/y axis, just the z axis (so the heights were correct, and the street view height was correct, just not the lengths of buildings). The real scale basically created buildings 3x bigger than they should have been.

After discovering this, I wrapped up the height stuff I had been working on to a working degree, and then pivoted to fix the map scale. I did more research with real world buildings to get a sense of how big different things should be, and then updated the generation parameters. Once this was done, I planned on updating all existing settlements to use the correct scale. Unfortunatelty, the reliablility of the generation algorithm seemed to fall by quite a lot once this was done.

On investigation, it turns out that with the new parameters (which made most buildings smaller, but some larger ones remained the same size), the algorithm was struggling to place the larger buildings into the now smaller lots, and so would regularly give up.

Generation Algorithm Overhaul

Given the challenge of placing large buildings in the lots, I decided to pivot to changing how the generation algorithm works to better handle this - and start planning for other cool features in the future. This is what I'm currently working on, so things here may change.

The current algorithm is essentially:

1. Create the people and determine the buildings we want to place

2. Split the buildings we have into different districts based on the parameters

3. Start placing roads - estimate how much area we need for all the buildings, create roads until we have lots with that area

4. Place districts one by one, each claims a lot and then grows into adjacent ones if possible, placing buildings as it goes.

5. Repeat 3 & 4 until all districts are placed.

Step 4 is the one causing the reliability issue - a district keeps claiming a lot, but it doesn't have room for the current large building (e.g. a temple) - if the district doesn't find a lot after a certain number of attempts, the algorithm gives up.

This also has a bunch of other issues. Currently districts have 'merge' logic in case they end up to small - which happens if a district claims a lot when generating, but then can't grow into any adjacent lots.

This means that some districts may have completely unrelated buildings in them. Part of this also happens as the district groups are created before the roads are placed, so some might have very few buildings.

I'm currently experimenting with a new algorithm:

1. Create the people and determine the buildings we want to place

2. Categorize buildings into different pools for easy access.

3. Place main roads until a large lot is created

4. Pick a district type based on the remaining buildings

5. Give the large lot to that district, let it split it up based on it's parameters, it takes buildings from the pool to fill up the area. Logic can be added here to handle 'landmark' / large buildings - placing them first (which should be easy as it's a large lot), and then generating roads around them.

6. Repeat 4 & 5 until all the buildings are placed.

I hope that this will make the generation more reliable with the new building sizes, as well as result in better overall districts. Importantly, districts are now part of the road generation, so different districts can have different road structures (e.g. an older part of town with random winding roads / vs a newer part with a more regular grid). This could also be extended for special landmark districts, e.g. a cathedral / monestary / castle district, which could place groups of buildings to create a larger complex.

Another thing I'd like to look at are better suburbs - currently, buildings are placed at the border of a lot, surrounded by roads. I'd like to support things like cul-de-sacs, and other road networks that don't require a fully connected graph.

Now, these are all things I'd like to work on - I'm still in the middle of this overhaul, so I can't promise what will make it into the next release, and what will be worked on after that.

Conclusion

As always, thank you for all of your support, it really does mean a lot. If you have any questions or other feedback, let me know!