Frozen Fractal : Development blog

Around The World, Part 30: Making better waves

Fri, 27 Mar 2026 00:00:00 +0000

I previously blogged about how I’m modelling and rendering water waves in the game, but that was in the previous incarnation on a sphere. I’ve finally ported that over to the current version, and made some considerable improvements along the way. People told me it looks good, and I tend to agree. Let’s dive in!

Reflections

Even if a water surface is perfectly still, you can still tell that it’s water. This is because of how light interacts with it: part of the light passes through (transparency), and part of the light is reflected. Let’s tackle reflection first.

Since the water surface is mostly reflecting stuff that is also on screen (distant coasts), screen-space reflections seem like the way to go. Godot significantly improved its SSR algorithm in version 4.6, so we now get this without writing any shader code:

That’s nice; it already looks pretty watery. However, real water is also transparent. I want some transparency in the game too, so the player can see and interact with nearby underwater objects like fish.

And here we hit a problem: Godot’s built-in material supports screen-space reflections, but not at the same time as transparency. So I’ll have to do the work myself and write a shader.

It’s just a fairly standard raymarch that inspects the depth buffer and returns the local colour when it hits something. However, because it’s meant for horizontal water surfaces, I can pull a few tricks: when hitting the side of the screen, rather than fading out like a normal SSR shader would because there’s no data, the raymarch just reverses direction. This means we still have reflections near the edges of the screen, even if they’re not quite correct.

You can see that my implementation is not as great as Godot’s built-in one, most notably because it doesn’t use Hi-Z. But in practice, the water surface won’t usually be this smooth, and the artifacts are no longer noticeable.

It took me forever to figure out how to get the reflected colour to combine properly with albedo and shadows, but the answer turned out to be very simple: Godot shaders have a dedicated output variable just for this, called RADIANCE.

Though it may be hard to see in the above screenshot, there’s also a bit of transparency going on already.

Ripples

Before we start moving the water surface physically, let’s add some of that nice glittering that real water has. This is caused by small ripples (capillary waves) randomly disturbing the smooth surface.

In my implementation, they won’t be travelling a particular direction; it’s just a bit of seamless Perlin noise used as a normal map:

The trick to make this look good in motion is to have multiple layers of this noise (I use 4), each with a random offset, and add them together. The layers are faded in and out over half a second, and when a layer’s opacity reaches zero, its offset is assigned a new random value. By setting the phases of the layers 90 degrees apart (360° / 4), we make sure that the total amplitude of the sum of the layers remains constant.

To fit in with my pixelated-textures art style, I’m using nearest-neighbour sampling on the noise texture. The result speaks for itself:

Sorry, your browser does not support embedded videos.

See? I told you the reflection artifacts wouldn’t be a problem!

A wave

Now let’s add some bigger motion to the water surface. Actual water waves follow a trochoidal motion, where each point on the surface describes a circle:

Source: Wikipedia by Kraaiennest, CC-BY-SA 4.0

In the previous version of the game, I decided not to do this, but to only move the vertices of the water mesh up and down. I thought I had a good reason for this:

It looks good, but it has a significant drawback: the water surface is no longer a simple height field. In other words, given a coordinate in the world, it’s very hard to compute what the water height at that point is. And we’ll need that computation later, when we want the ship to float on the surface and move in response to it.

This is nonsense! If the ship is floating on the water, and the water is moving sideways, the ship should move sideways along with it!

So let’s implement proper trochoidal motion, for a single sine wave at first (that is, a sine for the vertical motion and a cosine for the horizontal motion).

Sorry, your browser does not support embedded videos.

The “texture” that the water surface gets from the normal map really helps sell the horizontal motion.

Waves and wind

The game will have a dynamic weather system, so the waves will have to react to the wind. On a stormy day, we’ll have big waves, and on a calm day the waves will be small.

And they will never be simple sine waves; there’s always more going on. The real ocean surface is, essentially, a sum of sine waves, each with its own amplitude and wavelength, travelling at its own speed in its own direction.

It turns out there’s a deep rabbit hole of theory and measurements about this, but eventually I found the Pierson-Moskowitz spectrum to be perfect for my needs. It allows me to calculate the wave frequencies that occur at a given wind speed; from that I can compute their propagation speeds; and from those two follow their wavelengths. For the amplitude, I’m using another model, which gives me the significant wave height at a particular wind speed. The significant wave height is defined as “four times the standard deviation of the surface elevation”, and with some statistical gymnastics I’m able to make the sum of an array of sines match that standard deviation.

I thought I’d need to resort to manual inputs to get some artistic control over all this, but no, the outcome of the model is pretty convincing already.

Here’s what that looks like at a moderate gale of 15 m/s, which is around 29 knots or 7 Bft:

Sorry, your browser does not support embedded videos.

Changing wind speed

During gameplay, the wind speed can change at any time, though the change will always be gradual. How do we deal with this? We cannot simply update the wavelength of our existing sine waves, because the water surface would appear to contract or expand horizontally.

In the previous version, I solved this by not changing the sines at all, but rather fade them in and out over time. Whenever a sine would expire and a new one would take its place, it would check the wind speed and set up its parameters to match. It worked, but it was a bit difficult to experiment with, because every change would take 30-60 seconds to propagate. Fade the waves any faster, and the changes would be too visible.

So in the new version, I came up with another algorithm. It’s still based on fading sine waves in and out, but now, the set of sines is completely fixed. Each of them has a fixed wavelength and a direction, which we can plot in polar coordinates:

Each dot represents a single sine; the farther from the center the dot is, the larger its wavelength. The blue dots indicate active sines, that is, those that align with the current wind speed. The size of the dot is relative to that sine’s amplitude. So in the above image, the wind is blowing west to east, activating the waves that travel to the right. Because the wind speed is 15 m/s and I’ve accounted for wind speeds up to 35 m/s (hurricane speeds, 12 Bft), the biggest waves are barely active at all.

This lets me change the wind speed quickly in the Godot editor or the game’s debug panel, and the water surface is updated instantly to match. While tuning the various parameters, this saved me a lot of time.

Breaking waves

This is all fine for deep water, but in shallow water, waves behave differently. As they approach the coast, they slow down and grow taller, until they break and topple into a flatter shape.

This is difficult to model accurately, but I’ve made a rough approximation of the process:

Sorry, your browser does not support embedded videos.

Essentially, what I’m doing is flattening the circular motion into an ellipse, making it taller and narrower the shallower the water is relative to the wavelength. This effect needs to remain somewhat subtle, otherwise the sum-of-sines tends to go haywire at higher wind speeds, causing the water surface to turn inside out and intersect itself.

Foam

At higher wind speeds, the wind causes foam to form on the water surface. Let’s add that! I happened to be in the Dutch coast town of Scheveningen during strong winds, so I used the opportunity to take some reference photos from the famous pier:

The foam is far from uniform; it tends to form “tendrils” that slowly fade away. To mimic that, cellular noise works best:

Another observation is that there’s no such thing as “a little foam”; it’s either there (white) or not there (transparent). We can do that by thresholding the noise texture. Of course we’ll add a little bit of smoothing to the threshold to make the transition between foam and not-foam less jarring.

And where should we put the foam? It tends to form at the crest of waves, and then fades out gradually until the next wave comes along. However, since we’re doing a sum of many sines, what exactly is the “crest”? I compute that by summing up all the phase vectors of the waves, multiplied by their respective amplitudes. This gives me a phase vector that more or less follows the biggest sines, but doesn’t discount the small ones entirely either. And the angle of that vector tells me where in its cycle that combined wave currently is: at the crest, falling, at the trough, or rising. With some simple arithmetic we can make foam density increases quickly as a wave crest approaches, then make it gradually fall off towards the trough.

And in the end, how does it look?

Sorry, your browser does not support embedded videos.

I think that looks perfectly adequate for a one-person indie game. On to the next thing!

Around The World, Part 29: One year in

Sat, 14 Feb 2026 00:00:00 +0000

Exactly one year ago this Valentine’s Day, I started development on Around The World. Let’s look back on the past, but more importantly, look forward at what’s still ahead.

“Wait,” you ask, “haven’t you been at this for far longer than one year?” Yes, that’s true. The first post in this series was published in November 2023, over two years ago. But the code repository of that project was called aroundtheworld4, so clearly there is even more untold history here. Let’s dive in!

Iteration 1: tectonics, mostly

The first repository, simply called aroundtheworld, was started in 2019. The idea of the game was already on my mind, but mostly it was an excuse to play around with procedural world generation. I never got around to even start on gameplay, but the tectonic plate simulation made for some pretty satisfying videos:

Sorry, your browser does not support embedded videos.

The bright parts are continental crust, the dark parts are oceanic crust, and the colours are determined based on the plate. Note that a tectonic plate isn’t either oceanic or continental; it can contain both types of crust attached to each other. Each tectonic plate is modelled as a set of discs of radius r, and the rule is that two discs may never overlap.

A birds-eye view of the algorithm:

Generate discs on a sphere using Poisson disc sampling. For r = 0.01 radians, this gives about 43000 points.
Generate 12 random tectonic plates, each with a type (continental or oceanic), a height above/below sea level, a centroid on the sphere, and a velocity (axis + angle).
Assign each disc to the nearest plate center. To make plate edges less straight, add a random offset to each disc before looking up the nearest plate centroid. The random offset comes from a couple octaves of 3D simplex noise.
For each time step:
- Move all discs according to the velocity of the plate they belong to.
- Detect collisions between discs. If two discs overlap, then one of the two survives. Which one depends on crust type and height/depth: oceanic crust subducts underneath continental crust and disappears; deeper oceanic crust subducts under less deep; and for continental/continental collisions we flip a coin.
- Colliding discs also apply a force to the plate, causing colliding plates to slow down relative to each other.
- Adjust the height/depth of the surviving disc: subducting oceanic crust pushes up continental crust to form coastal mountains; colliding continental crust also forms mountain ranges.
- To create new crust near divergent boundaries, we just run another round of Poisson disc sampling, spawning new discs near existing ones. The crust type and height/depth here also depends on the existing point, to create ocean ridges and rift valleys.

Although it was fun to work on and to look at, I eventually realized that this approach was not suitable for a game: it was too slow, and gave me too little control over the output. So within the same repository, I started on a new approach that was mostly just layers of noise. It got as far as a basic height map:

Sorry, your browser does not support embedded videos.

The approach you see here survives to this day:

Generate random jagged Voronoi regions called “subplates”.
Accumulate these into actual plates.
Divide each plate into a continental and oceanic part (either of which may be empty).
Determine plate velocities based on adjacent plates (e.g. oceanic crust is pulled under continental crust).
Generate features like mountain ranges and rift valleys along plate boundaries.
Add simplex noise to make the rest of the terrain interesting as well.

As you can see at the end of the video, I took some effort to match the distribution of heights on the actual Earth. Not really necessary for the game, but a good check that my work made some kind of sense.

The video doesn’t show the flight_view or map_view tabs because they seem to be broken in the latest version, but here’s an old screenshot of the uplift map:

The map shows the boundaries of tectonic plates, their velocities, and the resulting uplift (mountain creation) along plate boundaries.

This project started in 2019 using Godot Engine version 3.1, and eventually got upgraded all the way to Godot 4.0. It used Rust and gdnative (later gdextension) for the high-performance bits. I abandoned it in January 2023.

Iteration 2: an actual game

In September 2020, a fortunate thing happened. It was the time of the 10th Alakajam, a small game jam community similar in format to Ludum Dare, that I’ve been involved with from the beginning. To celebrate the 10th instalment, there wasn’t just one theme, but three: maps, ships and chaos.

Guess who had been spending years thinking about a game involving at least maps and ships? To cover the chaos theme, I was hoping that procedural generation would help me out there. So I created a new repository, aroundtheworld2, and started work using Godot 3.2.

Making this game in a weekend was wildly ambitious, because my original plans were for a project that would take at least months to make. But I distilled it down to the essentials: you control a ship in a procedurally generated world, in which you have to find your way using maps. You can buy maps with gold, which is obtained by trading. You can also buy upgrades to sailing speed and view range. To add time pressure, you can only carry provisions for 10 in-game days of sailing; if you run out, you die. If you manage a complete circumnavigation and came back to your home port, you win. Somehow I pulled it off: it was a complete game!

The game came in 2nd place overall (out of 24 entries), and the feedback from fellow jammers was very positive, with several people suggesting I develop it further:

As a base for a longer solo project this seems very solid.

I know I will keep returning to play this game, and would love to see if it could be expanded post-jam

I see no reason why this could not be a paid-for game.

I would really like to see the post-jam version of this when it is released.

I was so happy to see that a full release is finally in the works, and I’ll be buying it for sure when you finish.

You can play this version online if you like. By sheer coincidence, random seed 0 gives you a good starting situation.

Iteration 3: Bevy, briefly

In April 2022, I started aroundtheworld3, still using Rust but this time using the Bevy engine. I think the reason was that I was dissatisfied with the quality of the Godot-Rust integration at the time, and I thought that a code-first approach would be a better fit for this project. I also may have been infatuated with the ECS (Entity-Component-System) architecture that Bevy uses.

Bevy was still fairly immature at that point, so it took a long time to figure out how to do anything. I liked Bevy and still do, but it just wasn’t ready yet to build this project on. I may also have been missing the ease of development that an editor like Godot brings, especially for building GUIs.

This incarnation was abandoned in the same month that it started, with only 622 lines of code written. All it did was show a sphere mapped with some simplex noise:

Sorry, your browser does not support embedded videos.

Iteration 4: Godot and C#

In April 2023, I seem to have decided to go with mature and trusted technology again. That meant the Godot engine. However, the Rust bindings still weren’t as great as they are today, and I knew that GDScript wouldn’t have the performance to do what I needed, so I opted for C# instead and started aroundtheworld4. Next to GDScript, this is the only other language that Godot has official support for, so I assumed it would be stable and solid. And it was!

The blog posts from part 1 all the way through part 21 were produced with this version, so I don’t need to say much about it here. Suffice it to say that I got some basic gameplay and trading going, in a 3D spherical world with a top-down camera.

However, I found that C# did not grow on me like I hoped it would. This is very subjective, and if I were working with it in a salaried job I wouldn’t even complain about it. However, if I’m going to sustain development on this game for months or years, it’s important that I keep up my motivation — and C# just tended to drain it. Because C# is a strongly typed language so “I could always refactor it easily later”, I racked up a fair bit of technical debt. Furthermore, working with a spherical world meant fighting the engine every step of the way. Moreover, the Godot-Rust bindings had improved a lot in the meantime.

All this eventually led to the decision to start over. I described my reasons more fully in part 22.

Iteration 5: back to Rust

That brings us to the project I am working on today, aroundtheworld5, started on 14 February 2025. This time, I decided to tackle the technically hard parts first, so I would have a solid foundation upon which to build the game.

This approach seems to be paying off: I now have a robust multithreaded implementation of LayerProcGen, some speedy noise functions, a procedural world generator whose output I can control to a sufficient degree, a floating origin to keep precision issues at bay, and on-the-fly chunk generation so we don’t have to generate the entire world in detail. Many of the procedural algorithms were ported over from the C# version, with some improvements along the way. Although there is always room for refactoring and cleanup, I still feel reasonably good about the codebase.

I could not have done any of this nearly so well without the experience of the previous implementations!

Where to next?

I also have more of a project plan than before, with the first three milestones fully mapped out. Milestone 1, “solid technical foundation” was achieved in November 2025. This allows me to focus now on Milestone 2, “core gameplay”. The aim is to implement all features from the Alakajam version, so we have a complete game loop:

Camera controls — done.
Ship controls — in progress. Still not decided whether it should be point-and-click or WASD.
Buying and viewing maps — mostly done. The UI could use some improvement.
Trading — not yet started.
Provisions — not yet started.
Some basic upgrades — not yet started.

Considering that the remaining items are things I implemented before in a single weekend, completion of this milestone shouldn’t take too much work.

I’m also cherry-picking some fun items from Milestone 3, “looking good”, to keep my motivation up. Good-looking visuals are also important to generate some early buzz about the game. Nobody gets excited about grey boxes! Here’s a teaser, showing some recent progress on waves and water rendering:

The long term

This one-year anniversary is also a good moment to reveal my plans for the full game, so I’ve set up a dedicated page for it. That text can eventually be used for a dedicated website, and onto the Steam page and other storefronts (I will definitely sell it on itch.io, and hopefully GOG as well if they’ll have me.). Go check it out!

Around The World, Part 28: Scaling up

Fri, 12 Dec 2025 00:00:00 +0000

Even though the in-game world is fairly small compared to Earth, I want it to feel big. Part of that is being able to see things that are far away.

For context: by now, I have settled on a third-person “chase camera” rather than a top-down view. It feels so much more immersive, and makes the gameplay (in particular, matching up maps to your surroundings) more interesting as well.

Remember that my world is now a flat plane that wraps around, rather than an actual sphere. However, it would be great if we could still make it look like a sphere, so that distant lands would gradually appear over the horizon. Mountains would be visible from a greater distance, so that the terrain actually matters beyond just the shape of the coastline.

Until now, I’ve been using a view distance of 5 km. That’s still a lot compared to other open-world games! But a landmass at 5 km does not look very far away, because it’s so big. For gameplay purposes, it would be good if view distance could be increased to about 25 km. Otherwise, the part of the world that the player can see is too small compared to the maps, and they won’t have anything to orient themselves by.

How does it work out if we just look at the geometry? My planar planet is 512 km wide, so let’s pretent that’s the circumference of a spherical planet. Its radius would then be 83 km. Terrain generation is scaled down relative to the real world, so that the tallest mountain is about 2500 m high. Assuming a ship of up to 25 m tall, the mountain’s peak will be visible over the horizon from 22 km away. That’s pretty close to the 25 km I figured out above, so I decided to sail with these numbers for now: let’s fake a planet radius of 83 km.

We now have some problems to solve.

World wrapping

To actually be able to sail around the world, you need to be able to sail off the west edge and reappear at the east edge, and vice versa. That’s easy enough to implement with some modular arithmetic applied to the ship’s coordinates. However, any nearby objects and terrain must also exhibit the same wrapping: if you are near the west edge of the world, you should be able to see across it, so anything near the east edge would have to be moved near you as well. This, too, can be implemented with some modular arithmetic.

However, it would have to be applied to every object in the game individually. That’s tedious at best, and bad for performance at worst, so I came up with the solution of parenting every object to a 2×2 km chunk. Only the chunks are moving around; their children just come along for the ride. The node hierarchy looks like this:

Here’s an example of how a nearby NPC ship would become visible, even though it’s all the way on the other side of the map in world coordinates:

The chunks themselves take care to move their children to adjacent chunks whenever they cross a chunk boundary, so the code of individual objects doesn’t need to care about the chunking at all.

Floating origin

As before with the spherical world, we’re going to run into floating-point precision issues. Godot by default uses 32-bit floats for object and vertex positions, which have only 23 bits of precision; at 512 km from the origin, the distance between two successive floating-point numbers is about 6 cm. The official recommendation in the Godot docs is not to go beyond 8 km for a 3D third-person game, and not beyond 64 km for any 3D game.

I started out hoping that this wouldn’t be an issue, but it turns out to be real: far away from the world origin, the ship started jittering weirdly, and the sails started jittering relative to the ship. A solution was needed.

Building Godot with 64-bits precision is possible, but adds a lot of overhead: now every vector and matrix in the game uses twice the memory, including the large procedurally generated terrain meshes. Would that be a problem? Not necessarily, but it turns out there’s now an easier solution.

Since we’re moving chunks around anyway, we can implement a floating origin system there as well. Just before rendering a frame, the chunk containing the player’s ship is moved to the global origin (0, 0), and all other chunks are positioned relative to it:

This ensures that every object we care about remains close to the global origin, where floating-point precision is sufficient. As long as none of the code assumes that global coordinates (relative to Godot’s global origin) are the same as world coordinates (relative to the north-west corner of the world map), this works great: the jitter is gone.

Planet curvature

Let’s take a look at how we could implement a fake planet curvature. In particular, I want distant objects to gradually sink below the horizon.

This could be done in a vertex shader: simply compute the distance to the camera (measured on the horizontal plane), calculate how far downwards the vertex should move, and move it:

The drawback is that this shader would need to be applied to every object in the world, meaning I would have to use custom shaders everywhere and couldn’t benefit from Godot’s built-in materials anymore. Tedious! Another drawback is that the visible meshes would no longer align with their physics shapes, which becomes relevant if we want to do object picking (e.g. clicking on the peak of a distant mountain to set a course towards it).

But I had an idea I wanted to try. Now that we have chunks, maybe we could pull the chunks themselves downwards, and have all their children come along for the ride?

My first attempt was to introduce some skew. In 3D games, the position and orientation of an object is usually represented as a matrix, and mine is no different. Godot uses 3×4 matrices: a 3×3 part to represent rotation and scale, and a 3x1 part for translation. But rotation has 3 degrees of freedom, and scale has another 3, so that means that we have 3 more degrees of freedom we can play with to make the chunk align (somewhat) with the sphere. Because chunks are in the y = 0 plane and are neither rotated nor scaled, the matrix looks like this, where tx, 0, tz is the translation vector (the chunk’s position):

 1 0 0 tx
0 1 0 0
0 0 1 tz

If we want to move points within the chunk only on the vertical axis (y), depending on their position in the xz plane, we have two components rx, rz we can play with, as well as ty:

 1 0 0 tx
rx 1 rz ty
0 0 1 tz

My idea is then as follows: modify these variables rx, rz, ty in such a way that the chunk’s corners end up on the sphere. Because we have 4 corners and only 3 variables, this is impossible; instead, we do it only for the 3 corners that are closest to the camera, and let the 4th end up where it will. It’s hard to draw in 3D, but in 2D you can see the idea better:

Every object inside these chunks will end up skewed as well, but because the effect is slight, this shouldn’t be visible.

Here’s how it looks when I modify the curvature in real time:

Sorry, your browser does not support embedded videos.

At lower curvatures, it’s quite effective!

However, there’s a problem with this approach that might not be obvious at first: physics. The built-in Godot Physics engine is well known to be bad at anything except pure translation and rotation; it doesn’t even support scaling. The newly integrated Jolt engine is better in this regard, but it draws the line at skewing, and starts emitting a lot of errors if a physics shape like a cylinder has any skew introduced to it.

So, let’s try something so stupid that it couldn’t possibly work: do not skew chunks at all, but just move them on the vertical axis, like this:

Amazingly, at small curvatures such as I’m using, this works just fine and the visual difference compared to skewing is not even noticeable. You might think it would introduce visible cracks between terrain chunks, but no: because farther chunks are moved farther downwards, the cracks are always hidden behind nearby terrain. It’s a keeper!

Terrain LODs

Now that we have the ability to make stuff gradually appear over the horizon, we need some stuff that actually will gradually appear over the horizon. With a ship of 25 m tall, even though the horizon itself is (surprisingly) only 2 km away, we can see tall mountains at a distance of 25 km. So a draw distance of 5 km is not nearly enough anymore.

It’s easy enough to increase this value in the configuration, but this increased the amount of terrain by a factor of 5² = 25, and tanked the frame rate. Some quick math shows that, at the terrain resolution of 8 m that I’m using, the 50×50 km patch of terrain around the player consists of 39 million triangles, and this is too much for my GPU.

Fortunately, we don’t need that many triangles, because on distant terrain they’re smaller than a pixel. It’s time to introduce a LOD (level-of-detail) scheme to our terrain: render nearby terrain at full detail, but reduce the number of triangles on terrain chunks farther away.

A classic problem with this are seams, or cracks, between adjacent terrain meshes of a different LOD. It’s often just a few pixels, but it’s still quite visible especially in motion. Here, I tweaked some values to make the problem more visible:

There are various solutions. The most elegant is to introduce special bits of mesh to cover the cracks, which are only made visible when the two adjacent terrain chunks are currently displayed at different LODs. Due to all the different edge cases (pun wholeheartedly intended), it’s surprisingly fiddly to get this right.

Fortunately there’s a simpler method, which is to simply add a ‘skirt’ of quads that hangs down from the edge of each chunk:

The normals on the skirt are copied from the adjacent vertices, so they receive the same lighting, and it won’t look as if there’s an actual small cliff there. And with that, the crack is gone:

This should also cover up any cracks caused by moving chunks vertically, though I haven’t spotted any so far.

Impostors

The trees I added in the previous post make a huge difference to the believability and sense of scale of the terrain. It would be sad if they couldn’t be rendered up to a large distance.

However, as it currently stands, being near a rainforest will drop the framerate to about 40 fps; the tree meshes take 15 ms to render. Since I want this game to run well on potato hardware, it should run at around 150-200 fps on my mid-range Radeon RX 7600 card, meaning a frame budget of only 5-7 ms.

The standard trick is to not render full meshes at a large distance, but rather pre-render the mesh into a texture from various points of view, and then just render a single quad with the texture applied: an impostor.

Godot doesn’t have support for impostors built in, but adding tooling inside the editor is really easy, so I built this quick and dirty impostor baking scene:

Sorry, your browser does not support embedded videos.

It iterates through all the tree meshes at 8 different angles, and renders each to a suitably sized viewport through an orthogonal camera (to simulate an infinite distance). Each orientation is rendered twice: once to capture colour and alpha, once to capture normals. The textures have pretty low resolution, but that’s fine, because they’re never viewed up close anyway:

These are then applied directly to the impostor quad, depending on the viewing angle:

Sorry, your browser does not support embedded videos.

This increased the frame rate from 40 fps to about 130 fps. There’s some more low-hanging fruit that will improve the frame rate further, so this is fast enough for the time being.

All together now

Let’s see all of the above in action while the player sails towards a remote island: the distant terrain, planet curvature, and tree impostors. I’ve edited the video for brevity, because it ran over 3 minutes; one of the biggest game design challenges will be to make sure the player has something to do during these long voyages.

Sorry, your browser does not support embedded videos.

The transition from impostors to real geometry is still fairly noticeable, probably because the impostors cast a smaller shadow. But it’s plenty good enough for now.

Around The World, Part 27: Planting trees

Fri, 28 Nov 2025 00:00:00 +0000

In the previous post, I determined what kind of vegetation should grow where in my procedurally generated world. Now it’s time to actually plant those plants!

As I mentioned last week, I figured out a list of tree species that belong to each “plant functional type” in the BIOME1 system. I made sure to get a set of distinctive-looking trees, so now it was time to fire up Blender, dust off my modelling skills (such as they are) and create some low-poly tree models and an assortment of other plants:

Most of the game takes place at sea, so you won’t often see these models up close. By keeping the polygon count very low, I’m hoping I can render a large enough number of trees without having to resort to impostors. The tallest tree in the back (tonka bean) has only 44 triangles. The simplest plants are just distorted octahedra, with only 8 triangles.

The grasses are generated with Blender’s geometry nodes and are actually way too detailed, with up to 500 triangles each, but I’m not sure I’ll be keeping them anyway. If I do, a handful of intersecting textured planes would be a better implementation.

Inputs

Recall that we have a fairly coarse map of biomes, and that each biome corresponds to a set of plant functional types, each of which contains some plant species. So that indirectly gives us an occurrence map for each species, containing 1.0 where the plant can occur and 0.0 where it can’t.

However, that map only has a resolution of 1×1 km. We don’t want our forest boundaries to be big straight-edged squares, so we’ll have to add some detail to this. In the previous post, I used domain warping to distort the boundaries, because I didn’t want to blend between biome terrain colours. Let’s apply the same trick here, using the same domain warp, so that the plants nicely follow the biome boundaries.

On top of that, I want some artistic control over how often each species appears. For example, in tropical rainforest, most of the visible trees are part of the canopy, but the canopy is occasionally pierced by even taller, so-called “emergent” trees, like the tonka bean we saw above. These should be rarer than the other species, so I’ll give each species a base “occurrence rate”, to be evaluated relative to the other ones in its biome.

And on top of that, not every square meter of land should be covered by trees, even in biomes where they can grow. In nature, factors like soil quality and grazing animals keep areas of land open. This differs by biome: tropical rainforest should have near 100% coverage, but colder or dryer biomes will have less. I’ll mimic that using a single layer of simplex noise, and give each biome a threshold value between 0 and 1. Plants can only grow where the value of the noise is below the threshold.

In the end, this gives me two functions, which can be evaluated at any point in the world:

Coverage amount: what is the probability of a plant growing here?
Relative species frequency: if there is a plant here, how likely is it to be of a particular species?

Placement

First off, we don’t want plants to overlap. Maybe in a dense forest, the trees will intersect a little bit, but never by too much. So I’ll assign each species a radius, and declare that the discs defined by these radii must never overlap. This also gives some artistic control; for example, by setting a large radius, we could create a “loner” tree species that doesn’t grow near others.

However, remember that the terrain is generated in chunks (of 1×1 kilometer, like the biome map, but this is a coincidence). When placing plants in one chunk, we cannot refer to trees in the neighbouring chunks, because those might not have been generated yet. If we force generation of neighbouring chunks, we run into a chicken-and-egg problem, because they’ll require their neighbours, and so on. And yet, we have to prevent trees from overlapping.

A simple approach is rejection sampling: pick a uniformly random point inside the chunk, choose a plant species for it, and if there is room for that plant, spawn it there. But then, how would we prevent overlaps with plants from other chunks? We could avoid placing plants near chunk edges, keeping their entire disc inside their own chunk, but then we’d get weird straight paths along chunk edges where no plants grow.

Grid placement

A more suitable approach would be to place plants in a grid (ideally a hex grid, but squares are a bit simpler to work with). Each grid cell contains the center of at most one plant, whose species and position within the cell are computed deterministically from the hash of the cell’s global coordinates. Here sketched on single chunk containing a 3×3 grid for two species:

species “green” has a small radius and a relative probability of 1
species “blue” has a large radius and a relative probability of 0.5

Of course, plants will end up overlapping, so we’ll have to prune them. To do that, my first thought was to hash the coordinates of their cells, and keep only the plant with the largest hash. We can then “predict” where plants will spawn in the neighbouring chunks, and deal with overlaps that way. With some fictional two-digit hashes, it could look like this:

However, this has an ordering dependency: suppose plant A overlaps with B, and B overlaps with C. The hashes are ordered as A > B > C. If we handle the overlap A-B first, then B is pruned and C can continue to exist. But if we handle the overlap B-C first, then C is pruned. I didn’t notice this problem until drawing the above image! For instance, the plant with hash 02 could only continue to exist because 43 and 46 were pruned first, since they in turn were dominated by 93 and 88 respectively.

We could impose some fixed ordering for handling overlaps, such as left-to-right, top-to-bottom, but it’s not clear how that would work across chunk boundaries. There might be an entire chain of overlaps running across a chunk, meaning information could “travel” across many chunks, most of which we haven’t generated yet. This would make placement depend, at least a little bit, on chunk creation order – something I’d rather avoid.

On top of that, there is another fundamental problem with this approach: it creates a bias towards smaller plants. Imagine we use a grid of 1×1 meter squares, a shrub has a radius of 1 meter, and a tree has a radius of 10 meters. A potential tree will then overlap with many shrubs, and the probability that it’ll “win” over all of them is near zero. We could try adjusting the relative probabilities to compensate, but I’m not sure how that should work when more than two species are in play.

Rather, since we already applied the relative spawn probabilities of each species, from now on each candidate should have an equal probability of spawning. And… I have no idea how to achieve that.

Rejection sampling

So maybe I should use rejection sampling after all? Pick a random point inside the chunk, pick a species for it, and if there are no overlaps, spawn a plant of that species there. But this runs into the exact same problem! Even if the tree and the shrub are configured with equal probabilities, the tree has a larger radius, and therefore a smaller probability of actually fitting in between the already spawned plants.

Maybe we should spawn larger plants first? But this won’t work either: if two species have equal probability and nearly equal radius, the slightly larger one will dominate.

Maybe we should adjust the spawn probability by radius, or by surface area, to make larger plants more likely to spawn? This should fix the balancing issue – and in fact it should even work with the grid-based approach – but now a large tree with a small probability will create a great many candidates, most of which will be rejected. With rejection sampling, this would kill performance, and with the grid placement, it would occupy most grid cells with plants that will never spawn, and thus not achieve maximum density.

Maybe we could select a plant species first, according to its relative probability, and find a suitable place for it second? Then we could keep searching until it fits somewhere. However, what do we do if we can’t fit it in anymore? To keep the relative frequencies of all plants, we’d have to abort the loop, otherwise we’ll just keep spawning only smaller and smaller plants to fill the gaps, upsetting the balance. But if we do abort the loop, it might mean we haven’t achieved maximum density: a single failed attempt to fit in a large tree would mean that the entire chunk would not be as densely covered as it could be. Another issue is that we can’t select a plant species without knowing the biome, and the biome depends on the location within the chunk.

Iterative methods

Maybe we could iteratively improve our plant placement to converge to the desired balance, while also keeping density. Let’s call this “acceptance sampling”: pick a point, pick a species based on that point’s biome, unconditionally place that plant there, then prune everything it overlaps with. Repeat until satisfied.

However, this has the same problem of imbalance: though large plants now have the right probability of spawning, they instead have a disproportionately large probability of being pruned. We could increase their spawn probability to compensate, but then they’d often spawn only to be pruned shortly afterwards, leaving a gap in coverage. And that’s not even considering how this would work across chunk boundaries.

Turning down the difficulty

This is a much harder problem than I thought at first. I don’t think it’s fundamentally impossible to solve; if you have any ideas, let me know! But I have to avoid wasting even more time on it, so for now, I’m adjusting my requirements: overlapping plants are okay and I’m not going to keep that from happening.

To ensure somewhat even coverage, I’ll still use the grid approach. Now the grid spacing becomes all-important, since it directly determines how many plants will be placed and how much overlap there will be. I’ll have to find some compromise so that large trees don’t overlap too much, while the distance between small plants doesn’t get too large either.

This nicely avoids any problems at chunk boundaries as well, since we don’t need to account for overlaps with plants from neighbouring chunks.

With all that, I’m getting decent results. Here are some patchy coniferous forests interspaced with shrublands:

And a tropical rainforest:

Remaining issues

There are a few more issues to resolve. First, it looks weird if plants grow on sheer cliff faces:

To fix this, I just computed the gradient of the local terrain, and reject the plant if it tries to spawn on a location that’s too steep for that species. This is configurable per species, so that smaller shrubs can still spawn on steep slopes, where big trees couldn’t grow. This helps:

Here’s another issue that needs to be solved:

The white houses represent a port town, and of course it shouldn’t be overgrown like that. We could prevent plants spawning wherever buildings have already spawned, but we can do better: typically, humans will cut down trees for firewood, so there should be some clearing around the port itself.

Thus, my solution is to assign each port an inner and outer radius. Within the inner radius, no plants can spawn at all; the probability is 0. Between the inner and the outer radius, the plant spawn probability smoothly increases towards 1. This is multiplied with the base spawn probability for plants, which is already a noisy function, so we shouldn’t get a hard-edged perfectly circular clearing around the port.

Let’s see how that looks:

Much better!

Performance

At the start, I wrote:

By keeping the polygon count very low, I’m hoping I can render a large enough number of trees without having to resort to impostors.

How is that working out? Not great, unfortunately. On this densely forested archipelago, the trees bring the framerate down from 132 fps to 75 fps:

It gets worse on flat continents, which have even more trees and also more overdraw, even though most of the trees are hidden behind other trees. The framerate goes down to 45 fps on those.

These numbers would be fine if I were testing on a low-end machine and wasn’t planning to add more stuff, but at this stage of development I should be aiming for about 150-200 fps to keep this game playable on potato hardware as well. So it’s clear that I will need to implement impostors after all. But that’s for some other day!

Around The World, Part 26: Biomes

Fri, 26 Sep 2025 00:00:00 +0000

I should be working on gameplay, but I got tired of looking at drab grey terrain, so I decided to beautify it first by adding some vegetation. In a way, this is in line with my plan to add a solid technical foundation for the game before stacking too much gameplay on top, because I’m not sure that the hardware will be able to render all those trees in a huge open world.

Let’s take a look at our starting point:

(That mountain village is placed a bit unrealistically, but I’ll tackle that later.)

You probably don’t remember from a post almost two years ago, but I already implemented generation of temperature, wind and precipitation patterns, and inferred the local climate from those. That was still in C# on a spherical world though, so I dutifully started porting it all to Rust on a flat world. In the end, I got my algorithms to produce a nice climate map using the Köppen-Geiger scheme, like before:

This map uses a common colour scheme, same as Wikipedia. Here’s the real world for reference:

Source: Wikimedia Commons, CC-BY 4.0

You can see that my attempt is far from perfect – in fact, it’s worse than what I got previously in my C# implementation. This is mostly because I simplified wind patterns, and I haven’t added noise to rain distribution yet either. But looking at the coasts (which is what the player will see), I think we’ve got good variety, which is the most important thing.

The next step was to map Köppen climate classes like “temperate oceanic climate” (Cfb) and “cold-summer Mediterranean climate” (Csc) to a set of trees and plants that could plausibly grow there. And that’s where the real trouble began.

To Köppen or not to Köppen

I had originally chosen the Köppen-Geiger scheme because, and I quote myself:

Köppen designed the system based on his experience as a botanist, so his classification is based on the vegetation we encounter in each climate class. That aligns perfectly with my goals.

So logically, these climate classes should cleanly map to particular biomes, right? I never checked this before, so I checked it now…

… and it’s false.

An awesome Wikipedia user has created the following map of the Earth’s biomes:

Source: Berkserker on Wikimedia Commons, CC-BY-SA 3.0

These are biomes I can work with; even if I don’t manage to find any data sources, names like “dry steppe and thorn forest” contain enough information to start drawing something plausible. So the question is: how does this compare to the Köppen map? Which Köppen climate zones map to which biomes?

Of course, being a programmer and map nerd, I wasn’t going to determine this by hand. So I figured out by trial and error that the above map was using the Robinson projection, used GDAL and QGIS to reproject the Köppen map into Robinson as well, aligned the two to the best of my abilities in GIMP, and then wrote some Python code to tally the corresponding pixels in each map. Note that the alignment isn’t perfect, so there will be some noise in the results, especially for Köppen zones that cover only a small part of the world. I’ll paste the full results here in case somebody has a use for it, but don’t bother reading the whole thing:

Af 89.0% tropical rainforest, 8.2% subtropical evergreen forest
Am 84.4% tropical rainforest, 6.3% grass savanna
Aw 29.0% dry forest and woodland savanna, 23.2% tropical rainforest, 23.0% tree savanna, 14.8% monsoon forests and mosaic, 5.7% grass savanna
As 100.0% monsoon forests and mosaic
BWh 44.1% xeric shrubland, 21.1% arid desert, 20.5% semiarid desert, 5.9% dry steppe and thorn forest
BWk 39.3% xeric shrubland, 25.3% dry steppe and thorn forest, 12.8% arid desert, 11.4% montane forests and grasslands, 5.5% semiarid desert
BSh 25.3% grass savanna, 22.8% tree savanna, 19.7% dry forest and woodland savanna, 17.9% dry steppe and thorn forest, 4.8% temperate steppe and savanna
BSk 57.8% temperate steppe and savanna, 10.2% dry steppe and thorn forest, 9.1% Mediterranean vegetation, 9.0% montane forests and grasslands, 6.3% xeric shrubland
Csa 63.9% Mediterranean vegetation, 14.5% temperate steppe and savanna, 11.8% temperate broadleaf forest
Csb 29.1% Mediterranean vegetation, 24.7% montane forests and grasslands, 24.1% temperate broadleaf forest, 9.2% dry steppe and thorn forest, 5.2% temperate steppe and savanna
Csc 38.5% Mediterranean vegetation, 30.8% temperate broadleaf forest, 30.8% montane forests and grasslands
Cwa 44.6% dry forest and woodland savanna, 19.4% temperate broadleaf forest, 14.1% monsoon forests and mosaic, 11.2% subtropical evergreen forest, 3.5% montane forests and grasslands
Cwb 32.3% montane forests and grasslands, 24.6% subtropical evergreen forest, 13.0% dry forest and woodland savanna, 12.2% temperate steppe and savanna, 8.8% tree savanna
Cwc no matches
Cfa 42.6% temperate broadleaf forest, 25.7% subtropical evergreen forest, 20.7% temperate steppe and savanna, 5.8% dry forest and woodland savanna
Cfb no matches
Cfc 62.5% taiga, 37.5% temperate broadleaf forest
Dsa 30.3% dry steppe and thorn forest, 29.8% montane forests and grasslands, 28.7% temperate broadleaf forest, 6.2% temperate steppe and savanna
Dsb 76.3% montane forests and grasslands, 13.5% dry steppe and thorn forest, 4.8% temperate steppe and savanna
Dsc 52.2% tundra, 36.0% taiga, 9.9% alpine tundra
Dsd 50.0% alpine tundra, 25.0% tundra, 25.0% taiga
Dwa 82.4% temperate broadleaf forest, 17.5% temperate steppe and savanna
Dwb 46.8% temperate broadleaf forest, 23.0% taiga, 16.3% temperate steppe and savanna, 13.7% montane forests and grasslands
Dwc 61.6% taiga, 17.9% alpine tundra, 15.4% montane forests and grasslands
Dwd 83.0% taiga, 16.0% alpine tundra
Dfa 55.2% temperate steppe and savanna, 44.7% temperate broadleaf forest
Dfb 46.3% temperate broadleaf forest, 44.1% taiga
Dfc 65.9% taiga, 29.3% tundra
Dfd 71.9% taiga, 26.1% tundra
ET 46.0% tundra, 44.8% montane forests and grasslands
EF 83.9% ice sheet and polar desert, 15.2% tundra

The thing that you should be looking at is the first percentage on each line. For example, Köppen class Af is covered for 89% by tropical rainforest – fine, we can just always plant tropical rainforest there. But the majority of climate zones aren’t nearly so clear cut; for example, what to make of BSh (hot semi-arid)? One quarter of it is covered by grass savanna, almost a quarter by tree savanna, and several other biome types as well.

At this point, I concluded that Köppen’s scheme did not fit my purposes as well as I had assumed, so I started looking at alternatives. And that’s when I was reminded of a blog post by the always extremely thorough World Building Pasta: Beyond the Köppen-Geiger Climate Classification System, Part I: Extensions and Alternatives. In it, Pasta describes several alternative climate classification systems with their pros and cons.

BIOME1

The system that caught my attention was the BIOME1 model by Prentice et al., 1992 (PDF). This model fits my purposes very well, because it directly talks about plant types and in which climates they might grow, and offers a very data-driven approach to find out. The core of the paper is this one table:

For example, this says that the plant type “cool-temperate conifer” can grow in areas where the minimum temperature is at least −19 °C, the maximum temperature does not exceed 5 °C, there are at least 900 growing degree-days in a year, and the α coefficient is at least 0.65. Let’s unpack this one by one.

Temperatures Tc and Tw are straightforward; Prentice et al. use the monthly average here, which I have readily available from my simulations.

Growing degree-days are also easy to compute, but might warrant some explanation. The idea is that plants do not grow below some particular temperature, here taken as 5 °C, and they grow faster the higher the temperature goes. So to approximate the total amount of growth in a year, for each day we take the number of degrees above the 5 °C threshold, and add those up across the days in a year. For example, a 21 °C day is good for 21 - 5 = 16 growing degree-days, and a 2 °C day doesn’t contribute any growing degree-days at all. Some plants can start growing above 0 °C already, which is what the GDD₀ column is for.

The Priestley-Taylor coefficient α is a bit more complicated to determine. Prentice et al. describe an iterative algorithm that models moisture storage in the soil, but I used a simpler approach: α = precipitation / PET, where PET is the potential evapotransipiration computed using the outdated, but simple, Thornthwaite equation. I compute α separately for each month (assuming 10 in the case where PET is zero, because this empirically gave better results than 1), then take the average over the year.

Finally, there’s the column “D”, the dominance class. This is needed because, even if a plant type could technically grow in a particular climate, other plants are better adapted and will outcompete it. This is why, for example, we won’t see any conifers in tropical rainforest. The rule is: if any plant type with a particular dominance class can grow in a particular climate, all other types with higher-numbered dominance classes are excluded. Plants with the same dominance class can coexist though! This model is simple, straightforward, wrong, and oh so useful to me because it’s easy to implement and efficient to evaluate.

With the list of plant types in hand, the BIOME1 model also specifies how to map these to biomes:

So the biomes are computed from the plants that can grow, rather than the other way round. Since I only want to plop down some plants, you might wonder why I’d bother with biomes at all. There are two reasons: one, I’d like to plot these on a map so I can compare it to the paper; and two, I want to assign different colours and textures to the base terrain depending on the biome.

Here’s the output computed by Prentice et al. themselves:

And, using the same colour scheme, here’s mine:

Again, it’s far from perfect, but this is clearly because of my simplistic climate model and not because of my implementation of the BIOME1 model. Most importantly, all classes are represented here.

Now, not to repeat my previous mistake with the Köppen model, I checked beforehand whether I could find a list of specific plant species for each of these biomes. That more or less worked by patching together various sources, and validating using the amazing Map of Life whether their occurrence actually corresponds to that biome. In the end, I have a list of 2-3 distinct and characteristic species for each plant type, and since most biomes contain more than one plant type, this should give a decent impression of biodiversity on my world.

Colouring terrain

Actually modelling, placing and rendering those plants is for a future blog post, because this one is getting plenty long already. So I’ll tackle the terrain colours first. I manually assigned each biome a plausible colour, and then mapped it to the terrain using the above biome map:

It works exactly as designed! We’re looking at cool mixed forest (yellowish green), cool conifer forest (blueish green), tundra (yellowish) and ice/polar desert (white) here. This makes sense, because this island is situated at 56° north, and should have a climate comparable to the Hebrides off the coast of Scotland.

But maybe, just maybe, real biomes don’t have such straight and hard borders? Actual biomes blend into each other. Interpolating between biomes is tricky though, because they are discrete classes. I could instead interpolate the output colours, but I think it would look more natural to add some domain warping using simplex noise instead:

Better. Never mind that the snow line no longer corresponds properly to height; snow is something I’ll tackle later.

One cheap trick to make every terrain instantly look much more varied is to have nothing grow on steep slopes, so let’s expose grey rock underneath:

Finally, terrain near the waterline will not be overgrown, or at least not by the same type of plants, because of tides and spray from the salty sea. So let’s expose the bare rock there too:

The effect is subtle from this perspective, but it helps ground the terrain much better, and also makes the underwater bits less unnaturally green. (Underwater biomes and vegetation is something that should be handled separately, if needed.)

Notice how there’s not a single texture in sight. I’m not great at drawing textures, and I hate UV unwrapping, so I’m trying to get away with a mostly texture-free art style in this game. We’ll see more of that style when I finish modelling my arboretum.

Around The World, Part 25: Placing ports

Sun, 21 Sep 2025 00:00:00 +0000

In the previous post, I promised to start placing some ports in our procedurally generated world. That turned out to be a bit more work than I expected.

First off, what are our requirements?

Ports must be on a coast.
Two ports must not be too close to each other.
Ports must be distributed around the world, according to some distribution that I can configure.
Ports must be reachable by sea (do not put them on the shore of a lake).

As with terrain generation, my approach has two “levels”: the global and the local. The code decides the location of all ports in the world on the global map first, so that we can later create quests that involve ports that are very far away.

(By the way, right now I’m talking only about ports, but besides harbour towns there could also be other points-of-interest on the coast, such as shipwrecks and buried treasure. Those have the same requirements, so they will be a straightforward extension later.)

Global placement

Recall that we previously figured out where the coasts are in our global map. We know the height of the terrain at each grid point, which can be either above or below sea level. We say that a grid cell is “coast” if some of its corners are above, and some are below sea level, coloured light blue here:

Those cells will be candidates for containing a port. (Lakes have already been detected and filtered out at this point; they are classified as land instead.)

To guarantee an even distribution of ports around the world, you might think that we could just put all coast cells in a list, and randomly pick elements from that list. However, that would only guarantee even distribution along coastlines, not spatially. If we have a very wrinkly coastline (think fjords), it will contain a much higher density of ports than straight coastlines!

The solution I came up with is to divide the global map up into grid squares:

Each of these squares will contain at most one port. For each square, we first check if it contains any coast at all; if not, we skip this square. If it does contain some coast cells, we pick the most “desirable” one; desirability is measured as the number of land cells within some radius of the port. This promotes spawning of ports at the end of sheltered bays, and discourages spawning of ports on tiny islands. The most desirable coast cell becomes the candidate port for that grid square.

Next, all candidates are assigned a sample weight according to their latitude, fed through a curve that I can specify:

So ports at the equator have a weight of 0.5, around 30° latitude the weight goes up to 1.0, sloping all the way down to 0.0 in the polar regions. The shape of the curve is my best guess at realism, considering habitability, but I might well need to tweak it for gameplay balancing purposes later. We then select a fixed number of candidates according to this weight:

(The icons are very small; zoom in to see them.)

For each of these ports, we also randomly select a population, also according to some distribution. I think I’ll later replace this by discrete size classes (hamlet, village, town, city, metropolis) but this’ll do for now.

Smooth sailing so far!

Local placement

In the previous post, I was very happy because I’d found a solution to the port placement problem, by using a modified diamond-square algorithm. In short, if all four corners of a diamond or square are below sea level, the center is assigned a value below sea level as well, and vice versa.

This works perfectly to preserve the “nature” of each cell in the global map: land, sea or coast. However, it does not guarantee that all coast is reachable – I encountered fun situations like this:

The red and green lines here mark out the edges of global map cells, whose corners have their heights taken from the global height map; everything in between is generated using diamond-square. As you can see, the cell containing (most of) the port has one corner that’s ever so slightly below water, so this cell is a coast cell, and the algorithm correctly decided to spawn a port there.

However, the cells connecting it to the sea are also coast cells, so there are no constraints on the heights inside those cells, apart from the corners. In this case that terrain is fairly high, creating a tiny lake completely surrounded by hills; not a great spawn point for our intrepid fleet of player ships.

At first I thought I could solve this by forcibly lowering the center of the port’s cell, pulling the neighbouring cells down along with it. But no:

This created a second tiny lake, but diamond-square still decided to block off the route to the sea.

A second attempt had me force the height of the entire quadrant connected to the sea corner, and you can guess how that worked out:

This problem took me way too long to figure out, but once I did, the solution seems obvious: we need to enforce connectivity between grid points. To be precise: if two adjacent corners of a cell are both below sea level, the local terrain generator must ensure that there is a path by sea between the two. So I ended up forcing the terrain to be sea along entire edges, and that works great:

(For now, I’m ignoring both the width and the depth of this forced “channel”. The depth does not currently matter to gameplay; any place where the terrain is below sea level is accessible. The width can easily be extended by also forcing a minimum depth on cells adjacent to the edge.)

Now that I had this functionality of forcing minimum and maximum height of particular points, I also used it to force the height of the middle point to be at least zero. Usually this will cause some of the adjacent terrain to be above zero, creating some land for the port buildings to spawn on. The port is then always spawned right in the middle of the cell, without any local adjustments needed. Much simpler!

The player’s ship will also need to be spawned near one of these ports. I previously had a complex dance at game startup to figure out where to spawn it, because even corner points wouldn’t necessarily be connected to open sea, but we couldn’t know until we started generating local terrain around the player, which we couldn’t do until we had placed the player. Now that chicken-and-egg problem is gone too: we simply pick a corner of the port’s cell that is below sea level, and the local terrain generator will guarantee a path from there to open sea.

Spawning buildings

You’ve already seen how the ports currently look, using this ~~placeholder~~ absolutely stunning model of a building I created in Blender:

The radius in which buildings are spawned depends on the port’s population. Right now, the algorithm simply picks a uniformly random angle and distance from the center, and plops a building down at that point. This causes the building density in the centre to be greater, which is actually a feature – but really, this entire algorithm is a placeholder as well, until I have time to come up with something better.

That’s it for port placement… for now. I’m sure I’ll revisit this topic in the future, because there are more things I want to implement: a fair spatial distribution of small vs. large ports (larger ones having more services), a local language and culture, proper building placement in sensibly-looking districts, influence on the local vegetation, and maybe even non-placeholder building models as well. For now though, I should be turning to gameplay, but I might actually tackle some eyecandy first. We’ll see.

Around The World, Part 24: Local terrain

Mon, 23 Jun 2025 00:00:00 +0000

Now that we have a plausible looking height map for the entire world, it’s time to zoom in and see what the terrain looks like up close.

I did this before, when I was still working on a sphere. I started out this time using the same approach, but the implementation I ended up with this time is quite different.

Let’s start by simply interpolating the global height map using bilinear interpolation:

The overall shape is plausible, but the terrain is way too smooth and obviously made of squares. I could fix the squares by using a more advanced interpolation method, but that would only make the smoothness worse. So I turned to my usual solution…

More noise

Adding some octaves of simplex noise gives a much better result:

This is the minimum amount of noise necessary to hide the sharp creases at the cell edges. However, there is a problem. Consider this much flatter terrain:

What happens if we add simplex noise to this?

Whoops! That doesn’t look realistic, and it’s also not going to be fun to navigate. The problem is that the simplex noise is now too strong, compared to the low height of the terrain.

I tried several different approaches to solve this:

Compute the slope of the global height map, and using that to modulate the amplitude of the local noise. Steeper regions get more noise, flatter regions get less. It worked, to some extent, but the effect was hard to control.
If the input height before noise is close to zero, modulate the noise to be close to zero as well. This had the unwanted effect of keeping the coastlines exactly straight, as in the situation without any noise.
Compute the distance to the nearest coastline, then modulate the noise based on that. The problem with that is, that the nearest coastline could be far away in some ungenerated chunk, and we’d still end up creating tons of islands in shallow water.

So none of these approaches was satisfactory.

Prelude to ports

The worst problem is that the simplex noise would arbitrarily move, add or remove coastlines. This is going to be a problem once we start placing port cities for the player to visit. In the global map, we classify each cell as land, sea or coast based on the terrain height at the four corners:

If all corners are above sea level, the cell is land.
If all corners are below sea level, the cell is sea.
If some corners are above sea level and some are below, the cell is coast.

Using orange for land, dark blue for sea and light blue for coast, the map around the above area looks like this:

Ports will be placed on this map only in coast grid cells, which should make them accessible from the sea. However, if simplex noise raises that cell fully above sea level or lowers it fully below, where will the port go? Or what if the noise creates a land barrier in the sea surrounding the port, making it inaccessible?

I initially tried to work around this by generating some extra local terrain around the current chunk, and creating the port in a suitable location once all surrounding local terrain was available. My use of the LayerProcGen algorithm made this pretty easy! Again it worked, to some extent, but it remained impossible to give any hard guarantees. On sufficiently tricky terrain, there would still be cases where no coastline could be found for the port to be placed, and it would end up landlocked or floating. (A city on water could still be a cool feature every once in a while; consider Venice. But a landlocked city being picked as a quest destination would be distinctly uncool.)

What I really needed was a way to guarantee that a coast cell in the global map would remain a coast cell in the local map, with a coastline bordering on the sea. It took me way too long to realize that this would happen automatically if I kept the height of all four corners the same as in the global map, and only filled in the intermediate terrain. Ideally, land should also remain above sea level and sea should remain below. And I know just the algorithm for that! It’s fast, flexible, simple to implement, and predates simplex noise by about two decades! Enter…

Diamond-square

The diamond-square algorithm is explained in many places around the web, so I’ll only give a brief summary.

We start with an array (height map) in which only the corner points have a known height. These points form a single square.
For each square, fill in the center value as the average of its four corner values, plus some random value. This produces diamonds, and is therefore called the “diamond step”.
For each diamond, fill in the center value as the average of its four corner values, plus some random value. This produces squares again, and is therefore called the “square step”.

An illustration should make this clearer:

Source: Christopher Ewin via Wikimedia Commons, CC-BY-SA 4.0

(I think the naming is confusing. The step operating on squares should be called the “square step”, and the step operating on diamonds should be called the “diamond step”. Oh well.)

On the edges, we only get half diamonds (i.e. triangles); the fourth corner is outside of the initial square. We can deal with those using LayerProcGen again: generate the neighbouring chunks as well, then read from those.

Let’s see how this looks when applied to our steep coast:

Okay, it’s rough now, and the creases are gone. What happens to the flatter coast?

Well, it’s rough now too — but still a mess of islands, no better than our previous approach! What gives?

Random tweaking

The key is in the part “some random value” that I handwaved in the algorithm description. The terrains above were produced with uniformly random values between -100 and +100 meters, which is halved on each iteration of the algorithm. (It’s actually multiplied by √½ after the diamond step, and again by √½ after the square step.) This means the amplitude of the noise is the same on rough terrain as on smooth terrain, so we haven’t really gained much yet, compared to simplex noise.

However, we now have a convenient place to tweak the randomness dependent on the input. For instance, we could pick a random value uniformly between the minimum and the maximum of the height at the four surrounding points. This way, we could never get any local maxima or minima where previously there were none.

In my case, I chose to compute the standard deviation of the surrounding four heights, and express the randomization strength relative to that standard deviation. For example, if the four corners are at heights 1.0, 2.0, 3.0 and 4.0, then the average is 2.5 and the (biased) standard deviation is about 1.12. Setting the strength factor to 1.0 would result in a center point between 1.38 and 3.62, which is safely in between the minimum and maximum. If the surrounding corners are at heights 1.0, 1.0, 1.0, 4.0 instead, then the central point would be between 0.45 and 3.05; you can see it shifts down along with the average, and it can go below the minimum and above the maximum.

How does this look when applied to the previous terrain?

I think this already looks far more interesting and realistic than the uniformly noisy previous attempt. The terrain is much more varied; there are clearly delineated steeper and flatter areas now. But the most important test of this algorithm: how does it fare on flat terrain?

Marvellous! Notice how we are getting only small bumps in the terrain now, and how the coastline has become more jagged and interesting, but the overall shape of the coastline has been preserved.

There is one thing that still bothers me, though. All coast cells are guaranteed to have some combination of land and water, but land cells aren’t guaranteed to contain only land, and sea cells aren’t guaranteed to contain only sea. In some cases, this could still cause land to form in sea cells off the coast, blocking access to the port. Ideally, I’d like to keep all terrain in sea cells below sea level, and in all land cells above sea level. Fortunately, that’s now very easy to do: if all four corners are below sea level, limit the range of allowed random values to be below sea level as well, and vice versa. It didn’t visibly change the test terrains we were looking at, but I’ll trust that it does the right thing.

All this together gives me an ironclad guarantee that coast cells will always contain a suitable spot to place a port, and the port will always be accessible from the sea!

Future work

Instead of a uniformly random height change, it would be interesting to experiment with other random distributions, such as the normal (Gaussian) distribution. I’m putting that on the backlog because it’s not a priority right now, and easy to change in isolation later.

Since I have an erosion algorithm, it would be cool to apply that after diamond-square, to make the result more believable. I have actually gotten that to work, and it looks a bit better. The trouble is that erosion messes up all guarantees about coast/land/sea cells again. I might be able to fix that by locally raising or lowering the terrain after erosion, to restore those guarantees… but that’s something to tinker with later. For now, I’m keeping erosion turned off.

For the next post, after all this talk about preparing the terrain for placing ports… let’s place some ports!

Around The World, Part 23: Hydraulic erosion

Fri, 06 Jun 2025 00:00:00 +0000

As I mentioned last time, I’m currently working on a full rewrite of the game, with a focus on building a solid technical foundation first. But because much of that is boring work, I allowed myself a fun side quest: hydraulic erosion.

In nature, erosion is a hugely important factor in shaping landscapes. And arguably the most significant form of erosion is hydraulic erosion, that is, erosion by flowing water. It results in typical branching folds in the landscape:

Credit: OutcropWizard via Wikimedia Commons, CC-BY-SA 4.0

Just so we’re on the same page, I’ll first describe my understanding of the hydraulic erosion process. Rain falls on the ground and flows downhill. It combines to form streams, which merge to form rivers, which merge into bigger rivers, until the water eventually flows into the sea. Along the way, it wears down the terrain that it flows over, lowering it. These loose rocks, pebbles and grains of sand, collectively known as sediment are carried downstream. Where the terrain flattens out, the water flows less quickly, and the carried sediment settles down on the bottom, increasing the height of the terrain there.

It’s difficult to recreate the effects of hydraulic erosion directly through equations, although this amazing Shadertoy by Felix Westin does a very impressive job, at the expense of being pretty complicated. Instead, most people resort to some kind of simulation of the erosion process over multiple time steps, simulating water flow, sediment pickup and deposition, and evaporation. Those simulations can get pretty complex and time consuming, so I thought: maybe there’s a simpler way?

Attempt 1: blurosion

It’s always worth starting out with “the simplest thing that could possibly work”. Because it’s simple, it doesn’t take much time to implement, and it may be good enough. Even if it isn’t, it’ll teach you something valuable.

With that in mind, I tried the following idea. The steeper the terrain is, the faster the water will flow, and thus the more sediment it will carry downhill. So here’s the simplest possible erosion algorithm I could think of: for each grid cell, find its lowest neighbour, and compute the difference in height. Reduce my own height by some fixed fraction of that difference (erosion), and increase the neighbour’s height by the same amount (deposition). Repeat this a couple of times.

For example, suppose the current cell’s height is 12, its lowest neighbour has height 4, and we’ve configured the erosion strength at 25%. The height difference is 8, so we’ll want to move 25% × 8 = 2 units of material. The current cell’s height then becomes 12 - 2 = 10, and the neighbour’s height is increased to 4 + 2 = 6.

Let’s try it on this height map, which is mostly just simplex noise with some tectonic boundary effects on top:

And here’s the result after some iterations of the above algorithm:

It looks like I just invented a rather slow blur algorithm instead. Not quite what I’d hoped for. In fact, it’s very similar to the thermal erosion algorithm I described over two years ago and apparently forgot about!

But why didn’t it produce these typical ridges and valleys? Here comes the lesson: hydraulic erosion is, in some sense, self-reinforcing. If by random chance a slight valley forms, it’ll collect slightly more water from its surroundings, causing it to erode more quickly, and becoming more pronounced, which will cause it to collect even more water, and so on. In technical terms, the amount of erosion that happens to a point is strongly dependent on the drainage area of that point, which is the total area that’s upstream from that point. My simplistic idea did not capture that.

Attempt 2: simulation

Looking at the literature, I quickly found a well-known paper by Xing Mei et al., Fast Hydraulic Erosion Simulation and Visualization on GPU. I’m not running my algorithms on the GPU at the moment, but that doesn’t matter; the algorithm works equally well on a CPU and can easily be parallelized.

Mei models water flow as a column of water on top of each terrain cell, connected to its neighbours by virtual pipes. Water flow through these pipes is simulated, which results in a flow velocity field. The sediment transport capacity is then calculated for each cell, depending on the slope and velocity. Sediment is then picked up or deposited to bring the amount of dissolved sediment towards this target capacity. Finally, sediment is moved (advected) through the flow velocity field.

The images in the paper aren’t very impressive, which may in part be due to limitations of the algorithm. Several people have taken the ideas and built upon them, for example Dylan Mcleod et al. in Interactive Hydraulic Erosion Simulator and Lan Lou in Terrain erosion sandbox in WebGL. Those people do get good results, so I knew it was possible.

However, I failed to get good output from Mei’s algorithm. I’m not sure why – maybe my implementation had bugs, maybe the combination of (about ten) parameters was wrong, but I always got weird artifacts at best, and numerical instability at worst. Here’s the best result I managed to get:

It does show branching patterns, but they have a strong tendency to be strictly horizontal or vertical, which gives a very artificial look. You may need to zoom in to see it.

There may have been ways to fix this, but the algorithm was already complex enough. So I started shopping around for something less complicated, but still sophisticated enough to do what I wanted.

Attempt 3: stream power law

While stumbling around, I found the blog post Simulating worlds on the GPU by David A Roberts. In it, he mentions the stream power law, which is a very simple empirical equation that models how quickly terrain erodes:

E = K * A^m * S^n

where

E is the rate of erosion,
A is the drainage area,
S is the slope,
K, m and n are constants.

A simple equation just two inputs, drainage area and slope, and only three parameters to tune (maybe just two because n should be about twice as large as m) – but it still involves that all-important factor, the drainage area. Did I hit gold?

Slope is easy enough to compute; it’s just the length of the gradient vector. However, how do we find the drainage area? This is where I found another paper, by Schott et al. (2002), Large-scale terrain authoring through interactive erosion simulation. They do a lot of work that I’m not interested in here, but also happen to present an algorithm to approximate the drainage area iteratively. It’s rather simple:

Set the drainage area of each cell to 1.
Repeat for some number of iterations:
- Set the drainage area of each cell to 1 (the cell itself) plus the drainage area of all neighbouring cells that drain into the current cell (i.e. that have the current cell as their lowest neighbour).

This will eventually converge to the true drainage area, but we can stop it sooner if we want.

A complication is that the drainage area depends on the shape of the terrain, and erosion will change that shape. So I decided to iteratively erode the terrain based on the stream power law in the same loop that also updates the drainage area.

Does it work?

It still has directional (horizontal/vertical) artifacts, but it’s getting somewhat acceptable.

However…

As you can see, the algorithm produces a large number of inland lakes below sea level. There are also many higher-up regions that are completely surrounded by higher terrain. These are known as endorheic basins, and are quite rare in nature. The way I understand it, there are two reasons for this. Firstly, they would fill up with water, which carries sediment, eventually raising the basin floor until the point where it is no longer a basin. And secondly, because the water eventually overflows the edge of the basin, it will start carving out a path for the basin to drain into, turning it into a regular lake with an outflow, and eventually maybe just a riverbed.

It makes sense that the algorithm produces basins, because they have a large drainage area, causing their bottom to sink. What the algorithm fails to capture, though, is that the stream power law only applies to flowing water, and the water in a basin is standing still.

I considered various approaches of detecting basins, and then either filling them or carving a way out, but decided that it would be too fiddly to get right, and possibly also too slow. Time for another tack.

Interlude: a better starting point

I decided to turn off the hydraulic erosion algorithm for the moment, and apply some long-wanted improvements to what I already had. This is basically just a rehash of previous stuff that I implemented in C# on a sphere, but now done in Rust on a plane.

Firstly, we know that water runs downhill and eventually reaches the sea. So, very broadly speaking, the closer to the coast a point is, the more water it receives, the more it erodes, and the lower it tends to be. So I computed the shortest distance to the coast at every point, mapped this through a configurable curve, and applied that to the terrain as a starting point:

Of course, for various reasons, the coast isn’t equally steep everywhere. So let’s use some low-frequency simplex noise to modulate the distance by, before mapping it to a height:

That’s better. Now we have steep coasts, as well as flat regions that reach farther inland (hello Netherlands!).

Next up was to improve the noise. What I had previously was just some octaves of simplex noise, which I’d hoped to make more interesting through the erosion algorithm:

(On top of the simplex noise, you’ll also notice some mountain ranges added by tectonic boundaries, which I blogged about extensively before.)

Inspired by the article on value noise derivatives by Inigo Quilez, I modified the noise according to a simple idea: mountains have steeper slopes, and also more rugged terrain. In terms of simplex noise octaves, this translates to: if the gradient of the noise is larger, subsequent smaller octaves of noise get bigger amplitude. I implemented a configurable curve so I can control this effect, which I call “slope dependent amplitude”:

With this curve applied, we can see that flatter regions become smoother, and steeper regions become rougher:

It makes the terrain much more varied and interesting.

Because the slope is apparently not continuous, it also results in some weird artifacts in the form of straight lines… but I have an old trick up my sleeve: domain warping. If we modify the input point of the noise by yet another layer of noise (or rather two, one for x and one for y), those straight lines get broken up nicely, and the overall terrain becomes even more interesting:

This could almost pass for something produced by erosion, without needing an actual erosion algorithm, but I wasn’t satisfied yet. There was one more idea I wanted to try.

Attempt 4: droplets

So far, I’ve only talked about grid-based erosion algorithms. But there is another category, one that is at least as popular: particles. The idea is to simulate rainfall one “droplet” at a time, tracing its path downhill, picking up and depositing sediment as it moves over the terrain. Do that for enough random droplets, and you get quite a convincing landscape. For a more thorough introduction, check out the amazing video Coding Adventure: Hydraulic Erosion by Sebastian Lague. It’s so good I’ll just embed it here:

However, there is one major drawback to this approach: it’s relatively slow. To get some decent results, you need to simulate many thousands of droplets, each for several dozen time steps. Because each droplet affects the terrain in random places, it’s hard to parallelize this across multiple cores, and it’s also not very friendly to CPU caches.

Another drawback is that a droplet can affect the terrain far away from where it’s initially spawned. This makes it difficult to apply erosion to individual terrain chunks, something I’ll want to do later.

For these reasons, I initially didn’t consider using such a droplet algorithm. But maybe I could take some ideas from it, and from the grid-based methods, and come up with some hybrid approach that combines the best of both worlds? It turns out that I could.

The idea is as follows. Instead of spawning one droplet at a time and simulating it, we’ll spawn all droplets simultaneously. And not just anywhere: we spawn exactly one droplet in each grid cell. And this remains the rule throughout the simulation; each grid cell contains exactly one droplet:

This allows us to track the droplets’ positions not in a flat, 1D array, but in a 2D array aligning exactly with the height map itself. For each droplet, we track:

the position as a floating-point number (rounding this down to the nearest integers gives the grid index)
the speed at which it’s moving, starting out arbitrarily at 1 (notice that this isn’t really related to movement, and is more a measure of kinetic energy)
the size (starting out at 1)
the amount of sediment it’s carrying (starting out at 0)

Next, we compute the terrain height at each droplet’s position using bilinear interpolation, as well as the gradient of the terrain. The gradient points uphill, so we want to move the droplet in the exact opposite direction. Regardless of its speed, we always move it over a distance of exactly 1 grid step. This guarantees that it’ll either remain in its current cell, or at worst in one of the 8 neighbouring cells:

We don’t yet move the droplet’s data into the new grid cell at this point!

Next, we compute the terrain height at its new position. Subtracting the previous height gives us a height difference, i.e. how much the droplet has moved downwards (or, sometimes, upwards). We use this to calculate the droplet’s sediment carrying capacity, which is the product of the height difference, speed, size and a configurable parameter, the sediment capacity factor.

If the droplet can carry more sediment than it currently does, it picks some up from its previous location, lowering the terrain there, but never by so much that it would turn a downhill slope into an uphill one – erosion never does that. Conversely, if it carries more sediment than it can, it deposits some at its previous location, again never turning an uphill slope into a downhill one. The height change is applied to the terrain through bilinear interpolation, depending on the droplet’s position within its cell.

Next, we update the droplet’s speed depending on how far it moved downhill, and we evaporate some of its water (multiply its size by something like 0.95).

Now comes the secret sauce! We have updated each droplet’s position, but this means that some droplets (most, in fact) will have left the grid cell in which their data is stored:

This leaves some cells overcrowded, with up to 9 droplets in them! My solution is to merge these droplets into one:

We average the position and speed, weighted by the size of the original droplets, but of course we sum up the sizes and sediments without weighting.

Droplet movement also leaves some cells empty. One solution is to just spawn a new droplet with size 0 (essentially no droplet at all) in those cells. Another solution is to implement steady rainfall: in every time step, always spawn a small droplet in every cell. This is slightly more elegant because we don’t need to check for division by zero, and is the approach I ended up with.

If you want to know the details, I’ll refer you to Sebastian Lague’s implementation on GitHub. Though my data structures and outer loops are different, the equations are pretty much the same. Though I do think Sebastian’s code has some bugs…

And now the moment you’ve been waiting for: let’s see if it works!

It’s clear that the algorithm does what it should do, that it doesn’t introduce strange artifacts or numerical instabilities, and most importantly: that the result looks great! And it takes only 20 iterations, running in less than 1.5 seconds for a 2048×1024 map.

As a finishing touch, I made the erosion strength dependent on tectonic region to randomly get more or less eroded terrain depending on location. The final result:

Erosion strength is also dependent on latitude to get more hydraulic erosion towards the poles, resulting in more fjord-like structures on coastlines there (zoom in to see them).

In nature, fjords occur on terrain closer to the poles because it was once covered in ice and therefore subjected to glacial erosion. Which… I should probably not be getting into right now.

Around The World, Part 22: Dropping the ball

Mon, 12 May 2025 00:00:00 +0000

I’ve done something that common wisdom in software development says you should never ever do: I started over. Let me explain why. This might get a bit technical…

Stumbling around

Progress on the game had been rather slow for a few months. This was in part due to lack of time, but it was also because of the code itself, and my feelings about it. I was getting increasingly annoyed by the fact that everything is harder on a sphere. The spherical shape of the world permeates every aspect of the code, from procedural generation to physics to navigation to rendering. It meant I had to develop bespoke solutions everywhere. Even if each of those solutions individually didn’t take up a lot of time, it was starting to add up, but I was nowhere near done dealing with this. And because the world geometry is so invasive, it’s hard to get rid of it without at least a partial rewrite.

I also realized that I don’t like C#. I started out using it because I needed something more performant than GDScript, and also because I wanted a statically typed language to keep the codebase maintainable. C# is supported as a first-class citizen in Godot, and I had a little prior experience with it (though outdated), so it seemed the obvious choice. Even though I’d never been particularly fond of the language, I figured it would let me get the job done, and the language might grow on me.

It did the opposite. Working in C# on the game, while using Rust for contract work, made me realize that I just like Rust much better. Despite Rust’s reputation of being hard to learn, the core language is actually simpler than C#, with fewer features that work together better. Moreover, C#’s documentation turned out to be mediocre at best – exceedingly verbose, but often failing to mention important details. Language features like inline arrays, which can be a huge performance boost in tight loops, are incompletely specified and the specification is still in draft after the feature has shipped. And the API docs don’t even consistently use a fixed-width font for code!

A third factor that was holding me back was the migration away from my custom ECS, which I never completed because I wanted to continue working on features. The codebase was messy and needed a significant amount of tedious work to get back to a good state. I would even get the occasional segmentation fault – something that should have been impossible using a managed language. (This very same error happened later with Rust as well, and turned out to be something that I thought was thread safe in Godot not actually being thread safe, so C# isn’t to blame here. But I didn’t know that at the time.)

All this was making me rather demotivated. If this were paid contract work, I would just power through, but for a hobby project that I’m doing for fun, it’s killing. If the fun is gone and unlikely to come back soon, the project is as good as dead.

Rust + GDScript = profit?

I eventually decided that the effort I was spending on the spherical world shape wasn’t worth it, considering that the improvement to gameplay would be small at best. I would be better off with a rectangular world, wrapping around at the east and west edges – essentially, a cylinder. But it was hard to make this happen without rewriting significant parts of code, and the game would not be runnable while I was working on this migration. It was an all or nothing affair.

Also, the landscape has shifted since I started working on this incarnation of the game about two years ago. For one, the Rust bindings in the form of the godot-rust library have matured, and are quite stable and usable these days. On top of that, static typing in GDScript continues to improve, with features like typed dictionaries being added to close the gaps.

All these factors led me to the decision that a clean start would be a good idea. I started working on this on Valentine’s day this year, using Rust for the heavy lifting, and GDScript for glueing everything together. So far, this has been a productive combination, playing off each language’s strengths: Rust is performant (or rather, gives the programmer full control over performance) and scales well to complex codebases, whereas GDScript is quick to iterate on, and interfaces well with the engine.

State of the world

Since I didn’t want to end up with a messy codebase once again, I spent the past three months working on a solid technical foundation. This effort is about halfway, but I want to finish it before building out more gameplay and content on top of it. That said, I couldn’t resist adding some nice new procedural generation features while porting, most notably erosion – but that’s still incomplete at this point, and warrants a blog post all of its own.

Here’s a screenshot of the current state of things:

Procedural generation at the global scale is mostly done, with only tectonic hotspots and polar ice caps remaining on the list. Adding local noise and erosion to each chunk still needs to be done as well, as you can see from the grid artifacts. Other main missing features are ports and maps, both so essential to gameplay.

I’m holding off on porting my fancy water shader until I figure out the art style, since painterly rendering turned out to be a non-starter. I think it’s going to be something more low-poly.

But I do now have a nice interactive in-game world map viewer, which is a huge help for inspecting and debugging:

Because this tooling is written in GDScript, it’s really easy and actually fun to quickly throw something like this together. Previously, I had built such tooling as an editor add-on. Having it in the game allows for interaction with the game itself, such as showing the ship’s position on the map, and right-clicking to teleport the ship to another location.

And since the world is no longer spherical, the map is actually accurate and not distorted anywhere. (You might have noticed that the world wraps around north/south as well. It was just easier to code this way, and it won’t matter once I add impassable ice sheets to the poles.)

With this reduction in scope, maybe, just maybe, a third-person 3D perspective is back on the table? I haven’t decided yet…

Around The World, Part 21: Visibility

Tue, 04 Feb 2025 00:00:00 +0000

In a game focused on exploration, we need to have a way to decide what the player can and cannot see. With a first-person or third-person 3D view, visibility comes for free: anything below the horizon, and anything behind something else, is not visible. With a top-down perspective, we need to do some more work.

Visibility

Here’s the test scene I’ll be using:

Please ignore the black areas in the corners, which are due to a bug in my camera calculations that I’ll fix later. The player’s ship is in the centre, but it’s so small it’s barely visible. I’ll have to look into that later too.

The simplest way to restrict visibility is to limit the camera zoom, so you simply cannot zoom out farther to see more. Since the view is always centered on the player’s ship, this effectively limits how far they can see. However, because the screen is typically not square, this restricts visibility more in the vertical direction than the horizontal; also, the amount of restriction would depend on the screen aspect ratio. Rather, we want some kind of circular visibility.

Of course, this is not a new problem, and games have been solving it at least since the early real-time strategy games like Dune II:

The areas not visible to the player are simply rendered in black here. More precisely, in RTS games, areas unexplored by the player are rendered in black, but that’s not what I want for my game. I’ll just make everything black that isn’t currently visible.

Thanks to my newly gained experience with Godot’s compositor effects, it’s relatively simple to implement this:

However, this restricts visibility to a circle at the horizon. Wouldn’t it be fun if, just like in a first-person view, things farther away than the horizon would also be visible, if they were tall enough, such as mountains and volcanic islands? So let’s add that! Using some vector algebra and trigonometry, it’s not too hard to compute whether a given point is above or below the horizon:

And… that’s cool, but there is a problem. The calculations are based on a typical carrack of the time, with a lookout standing in the crow’s nest 25 meters above the water level. The equation to compute the distance to the horizon is easy to derive using Pythagoras’s theorem:

d = sqrt(2*R*h + h²)

where R is the radius of the planet and h is the height above sea level. (If h is small relative to R, we can omit the h² term.) With our planet being 1% the size of Earth, this puts the horizon at 1.8 km away. That is, we can see the surface of the ocean up to 1.8 km away, but may be able to see taller things beyond that.

Let’s say that a mountain can be at most 10 km tall. (The tallest mountain on Earth, Mount Everest, stands at 8.8 km.) The tip of such a mountain would then be visible from almost 39 km away! That means it would be very far outside our little horizon circle; you’d have to zoom out until the horizon circle occupies only a fraction of the screen, before you can spot that mountain in the distance. And the game would have to generate and render terrain at huge distances to make this work.

Fortunately, when scaling down the planet to 1% the size of Earth, I also scaled terrain heights down to 10% size. (This should of course also have been 1%, but that would reduce mountains to mere hills in comparison to the ship.) So actually, our mountain is at most 1000 meters tall. This makes it visible from about 13 km away, which is already better, but still a lot compared to our 1.8 km horizon radius.

So it’s time to cheat, and scale down terrain height only in the visibilty calculations. But by what factor? Let’s take it from the other side: from how far away do we want a 1 km tall mountain to be visible? We can make this value configurable directly for the game developer (me), and have the game code figure out the right scale factor. If we set the distance to a reasonable 5 km, that works out to a maximum mountain height of 81 meters, i.e. a scale factor of 0.081 on top of the 10% we have already:

That seems a bit too tame, but maybe these mountains aren’t actually very tall; I haven’t checked. At least now I have a meaningful value to adjust. (And in the remainder of this post, you’ll see that I did adjust it.)

Blue is the new black

Even though you can’t go far wrong with black, it looks rather dull, especially if a large portion of the screen is filled with it. In reality, you would see the sky above the horizon. So how about using the sky colour instead of black?

As it happens, during my excursion down the third-person rabbit hole in the last post, I wrote some shader code to compute sky colours and atmospheric scattering. So I can reuse that here – it hasn’t been in vain after all!

First, let’s compute the sky colour just above the horizon, and use that instead of black. This is a good opportunity to show off the day-night cycle as well, which has been in the game forever:

Sorry, your browser does not support embedded videos.

I think this looks fairly good, but I also added some debanding noise after capturing this video.

(You’ll notice that it’s not completely dark before sunrise and after sunset. That’s because there is also a moon, which is currently always full, and whose position is not overridden by the debug controls.)

Aerial perspective

When looking at a distant object, such as a mountain, you’ll notice that it appears blueish and washed out. This phenomenon is called, somewhat confusingly, aerial perspective. The washing out happens because the light from the mountain is partially absorbed and scattered before it reaches your eye. The blueish tint is caused by light from the sun being scattered into the line of sight; light towards the blue end of the spectrum is more prone to scattering.

Godot has fake aerial perspective built in, but the problem is that it works from the point of view of the camera, where we want it to work from the point of view of the ship. There’s no way to override that, so we have to build our own. Fortunately, with the sky shader, all the pieces are already there, so it’s just a few lines of code:

It adds a nice sense of distance. Because of the 1% planet scale, I had to strengthen the effect by a factor of 30 to make it look like this. Realistically that should have been a factor of 100, but that turns out to be too strong.

Shadows

Godot offers shadow rendering by default, but I had to tweak the values quite a bit to make them work well at these scales. They make a big difference:

To wrap things up, here’s a video of exploring a bay in the early morning:

Sorry, your browser does not support embedded videos.

I do see some problems already, such as that the aerial perspective effect is also applied at full strength in shadows, where inscattering should be less. I’m not yet sure how to fix that, so I’ll leave it at this for now. The game still looks better now than it did this morning!

Around The World, Part 20: Two steps forward, one step back

Wed, 25 Dec 2024 00:00:00 +0000

Work on the game has been slow due to lack of time, but worse, I’ve let it drift off in the wrong direction. I need to be more careful about scope creep. But first, let’s talk about the progress that I am happy about.

No more ECS

In a previous post, I described my newly written entity-component system (ECS). I had some reasonable arguments for structuring the game as an ECS, most notably that it’s not possible to add functionality to all Godot nodes, regardless of type. You’d need multiple inheritance for this.

I did mention the workaround of putting the functionality onto a child node, but that’s a fairly heavyweight solution. However, does that matter in practice? Perhaps not. Moreover, I’ve found another approach: put the nodes into a group, and have a separate node that applies some operation to all nodes in that group. This only works for code, not for data, but it turns out I don’t need that – I initially wanted to store a 64-bits node position, but storing a 32-bits position relative to the floating origin works just as well.

And my ECS came with a number of drawbacks. Adding new node-based entities now required me to add code in five different files:

Define a component to hold the data.
Create a scene to represent the entity in the scene tree.
Implement a system to work on that data and sync the changes to the scene.
Register the system to be executed every frame.
Register the scene to be added to the tree whenever the component is added.

This was just way too cumbersome, for little benefit. With Godot’s node-based approach, I’d only need the scene and a script, and the link between the two is automatically managed.

And because all the values were tucked away in components and systems in pure C# code, I lost the ability to modify scene properties in the editor while the game is running. I didn’t realize at the time how useful that feature is.

Another argument for using an ECS was that it would simplify the implementation of saving and (especially) loading. I now realize that isn’t true. Yes, streaming a bunch of components from disk using some predefined serialization format is easier than reconstructing a scene tree from (e.g.) a JSON object. However, after loading those components, I’d still need to reconstruct that scene tree anyway. The work is just moved into the systems that update nodes from components, but it still needs to be implemented.

So in the end, I decided to throw out the ECS and port everything back to a more customary Godot scene tree. Everything? No, there were a few key benefits that I wanted to keep.

First, there’s dependency injection. Systems allowed injecting resources and queries into their constructors, and this really helped to decouple the code. Since we’re now doing nodes again, I wrote a very simple Injector node, which is triggered whenever a node is added to the scene tree. It uses reflection to scan the new node for any fields with the [Inject] annotation, and provides them with values from an array of pre-registered injectable objects. Functionally it’s almost the same as Godot’s singletons, but makes the dependency more explicit, which I like.

Second, there’s the global event bus. I haven’t actually implemented this yet, and maybe I won’t need to, but I’m definitely keeping it in mind.

LayerProcGen

Earlier this year, Rune Skovbo Johansen alias runevision released LayerProcGen, a principled framework for procedural generation of infinite worlds. My worlds aren’t infinite, but they are big enough that we can’t generate and store them in their entirety, so the same principles apply. The idea is that procedural generation happens in layers, and each layer is generated in chunks as usual. Each layer can only depend on the layers below it, but it can request chunks from a larger area so that it has some context to work with:

Source: the LayerProcGen documentation, licensed under MPL 2.0

I realized that I was essentially already doing some of the things LayerProcGen helps with, but in a more ad-hoc way. So I decided it would make sense to switch over to this framework. I couldn’t use Rune’s code directly even though it’s in C#, because it assumes a flat world (curse those spheres!). Fortunately, the implementation isn’t rocket science so I just wrote my own.

I now have layer-by-layer, chunk-by-chunk generation working, distributing the work over several threads to speed it up. The game looks exactly the same as before, but the code is better organized and easier to build on top of.

Around this point, I got sidetracked a bit.

Full 3D

I’d previously settled on 3D rendering, but with a mostly top-down camera:

On a whim, with my newly found powers of editing the scene tree while the game is running, I moved the camera away from the top-down perspective, and put it in a third-person perspective behind the ship. And it looked… rather nice. Oh dear.

This screenshot doesn’t even have any land in it, but it already has a much more immersive feel than the top-down view. It would also add interesting gameplay elements, such as distant coasts actually being less clearly visible, and having to do more work to match your surroundings to a ~~map~~ chart.

I figured that we have a full 3D scene already, so it shouldn’t be too much work to use this perspective instead of top-down, right? So down the rabbit hole I went, not realizing how deep it was.

Sky

We can now see the sky, and it looks rather drab and boring – not even properly blue. Indeed, that’s the best you can get with Godot out of the box, so I had to write my own sky shader. I did that, implementing a pretty standard path tracer with single scattering, which made sunsets about 100× prettier:

It automatically works with moonlight too:

Aerial perspective

Okay, we now have some atmospheric scattering going on, but it’s only applied to the sky and not to any other objects:

The faraway islands are still a harsh green, rather than fading into the distance. Fortunately, Godot has a checkbox to add some fake aerial perspective, which mimics the effect of light scattering into the ray between the camera and the distant mountains. This instantly made the scene look much better:

The effect is fake and might be limiting later once I start adding fog, but it’s better than nothing. Good enough for now.

Painterly rendering

With this new third-person perspective, the low-poly ship model contrasted weirdly with the highly detailed waves and terrain. I already had a solution in mind for that. There weren’t any cameras in the Age of Sail, so much of what we know has come to us in the form of paintings. So wouldn’t it be cool if the game looked like an oil painting as well? I’d been planning to apply a post-processing filter to do just that.

I looked around in the literature, and found that there are essentially two ways to make images look like paintings. On the one hand, there are filters that modify the image in some clever way, so that the result looks somewhat like brush strokes. On the other hand, some techniques create and render actual brush strokes. The challenge with that is temporal coherence: we render 60 frames per second, but we don’t want entirely new brush strokes to appear every frame, because that would cause way too much flicker.

The anisotropic Kuwahara filter by Kyprianidis et al. is of the first category, which is easier to implement, so I wanted to try it first:

This YouTube video shows an implementation in TouchDesigner, applied to some drone videos of a mountainous landscape, and it looks absolutely gorgeous (skip ahead to 1 minute):

I got most of the way through implementing this, using Godot’s new compositor effects and compute shaders, when I realized that this rabbit hole was too deep. The somewhat naive, but still GPU-based implementation was taking almost 100 milliseconds per frame; I’d need to get it down to 3-4 ms to still run smoothly on older hardware. And some bug was causing it to look more like a bad JPEG than a painting.

And even if I fixed the bugs and somehow made it 30 times faster, this filter might still not achieve the look I’m looking for, because the input doesn’t have nearly as much detail as a photograph or video. This filter is essentially about removing detail, where I might be better off with something that adds detail instead, i.e. individual brush strokes, with all the temporal stability issues that that entails.

Thump! Thump!

Alice felt that she was dozing off, when suddenly, thump! thump! down she came upon a heap of sticks and dry leaves, and the fall was over.

At this point, I belatedly realized that going full 3D wasn’t as quick and easy as I’d originally estimated. The sky shader needed more work to get rid of the green horizon. The painterly rendering was the kind of stuff that academics build entire careers on, but without it, I’d need to craft more detailed models. And on top of all that, I only have clear skies so far – I haven’t even begun to implement real-time, dynamically changing clouds yet.

It was becoming clear that I would have to cut scope, and put the camera back where I had planned it. I even considered going to 2D entirely, but that would essentially mean starting from scratch and wasting even more time. Instead, let’s climb back out of this hole to the surface, take a breath of fresh air, and forge ahead with what I’ve got already.

Why my apps will soon be gone from the Google Play Store

Fri, 06 Sep 2024 00:00:00 +0000

The first real money I ever made from game development was on Android. It was in 2013, when Android was still the underdog compared to the iPhone, and was being touted as a great platform for developers. I’d taken two weeks to build Patchy, a retro arcade game revamped for touch controls, and published it on the Google Play Store without any hassle. Since then, I’ve also published Twistago, Rocket Mail, Bigcanvas, Radio Nul and Papageno.

With each next app, the bar for publishing kept getting higher. At some point, Google started publishing developers’ full company address on the store alongside the app. That’s fine for a professional company, but quite problematic for a solo indie developer who works from home, especially if the app or the developer is even remotely controversial. I worked around it at the time by just putting the name of the town instead of the full address, which is only right morally, but not legally.

The technical requirements also kept going up. To publish an update to an app, it has to target the latest API version, which goes up once or twice a year. Each API update comes with a slew of deprecations, and breaking changes to the already inscrutable build system. And even if you don’t want to update the app, Google will eventually start hiding apps from users if the app doesn’t target some minimum API version. This means you can’t just publish an app and leave it at that; it’s several days of work per app per year to keep up with the latest rug-pulls from Google. Again this is no problem for a company for whom the app is their core business, but bad news for indie and hobbyist developers who just want to make something cool, put it out there, and move on to the next project.

And then, there’s the latest increase in publishing requirements, the straw that broke the camel’s back, which made me decide to abandon the Google Play Store altogether.

The new rules

The original announcement just mentioned that organizations will need to provide a D-U-N-S number. It was possible to choose your own deadline, so I set it as far in the future as I could. Now that deadline, 5 November, is getting close, and I can start the verification process. The email, however, makes it clear that they want much more than a D-U-N-S number:

What you need to provide to verify

a D-U-N-S number for your organization
If you don’t have a D-U-N-S number, request one at no cost from Dun & Bradstreet now. This process can take up to 30 days, so we recommend requesting a D-U-N-S number immediately. Learn more about requesting a D-U-N-S number

a phone number and email address for Google Play users to contact you

a phone number and email address for Google to contact you

an official document to verify your identity

an official document to verify your organization

There is only one of these items that I don’t have a problem with.

The D-U-N-S number is only needed if your Play Store publisher account is for an organization, not an individual. But I’m registered as a sole proprietor, so the rule applies to me. You can look up your company’s D-U-N-S number, but the form doesn’t (currently?) allow selecting any country except the US. Dun & Bradstreet’s partner in the Netherlands, Altares, does allow me to look up my own company, but charges 15 € for the privilege of seeing my own data, including my own D-U-N-S number, which they’ve apparently already assigned when I registered with the Chamber of Commerce. If I didn’t already have one, I don’t see a way on their website to request one either, even though the FAQ mentions that you can (for a fee, of course).

While that may be just some paperwork and a small expense, the next requirement is more insidious: “a phone number and email address for Google Play users to contact you”. I’m fine showing an email address, but I absolutely do not want my phone number to be available to anyone on the internet. (Even for phone calls. But remember that a phone number is used for much more than phone calls these days.) And that’s just me, a privileged hetero white cis dude who is unlikely to be the target of harassment or doxxing.

The requirement “a phone number and email address for Google to contact you” is the only one that sounds benign to me, although I have yet to see Google trying to contact small-fry developers like me by phone, instead of just reaching for the algorithmic ban hammer if I cross any line.

An “official document to verify your identity” would presumably be a scan or photo of my passport. Now, I have reasonable confidence in the security of Google’s systems, but this is something very sensitive and can easily be abused if it fell into the wrong hands. And why is it necessary? I’ve done business with many other companies, where a lot more money was changing hands than I’m getting from my Play Store apps, but they never asked for my passport. Why does Google?

Those other companies also never asked for “an official document to verify your organization”. Presumably this is a document I can request from the Chamber of Commerce to the tune of another 9 €, but again I’ve never had another company ask for this when doing business with them.

In conclusion

I sort of understand why Google is doing all this. It’s partly legal requirements (especially EU), partly an attempt to reduce spam and malicious stuff. Some of it might even be in the best interest of the end user.

Larger companies have the resources to deal with all this, and for personal accounts the rules are much more lenient. Sadly, there has been little consideration for sole proprietorships like mine, which fall somewhere in between: bound by the same rules as big companies, but without the means to play by them.

And this is why I’m just going to let my Play Store developer account expire. Starting on 5 November, you won’t be able to install any of my apps anymore. Most of them were not actively maintained anymore, but they still worked, because the Android operating system itself is actually pretty good at backwards compatibility.

Even though there was little remaining interest in my older apps, it makes me sad that people won’t be able to use them anymore. The one I’m most sad about, though, is Papageno, an unfinished side project about bird sounds that I haven’t worked on for three years, but keeps popping into my mind as something I’d really like to finish some day. Maybe it could be in the form of a web app. We’ll see.

Around The World, Part 19: Constructing languages

Fri, 09 Aug 2024 00:00:00 +0000

I’m having a bit of an “off” day today, so let’s do something fun, even if it’s rather low priority for the game: generating foreign languages.

The idea is that the player starts out in a region where they speak the local language, which will be represented as English (or some other real-world language, if the game ever gets translated). However, as the player ventures out and discovers new civilizations, they’ll run into a language barrier. Text like quest descriptions and gossip will be shown in incomprehensible gibberish instead, until the player’s character learns the local language, or hires someone to translate. At that point, the foreign text is partially or entirely replaced by English. Of course, I don’t want to use real-world languages in my fictional world, so: we need an algorithm to produce languages!

A more immediate reason to write a language generator is for naming cities, seas, coasts, islands and the like. Right now, city names are just drawn from a list of real-world ports, which is a bit weird at best.

Prior work

A fairly well known generator for place names is due to Martin O’Leary. He has a great description on his website, and published the source code on GitHub.

I’ve experimented with O’Leary’s algorithm in the past, but I was never entirely happy with the results. One problem might have been that I was trying to do two things at once:

Generating languages
Generating words in a generated language

Repeatedly, I ran into the problem that as I added more diversity to words within a language, each language became less distinctive and recognizable, resulting in a uniform soup of words.

But a more fundamental issue was that generated words looked too artificial to me, which is probably due to the rigid phoneme structure that the algorithm uses. So instead, I’ll start with a more classic approach.

Markov chains

Unlike Martin O’Leary’s generator, a Markov chain needs to be created from input data, for example a large amount of text. If we feed it English text, it’ll generate words that look more or less like English (or, in many cases, are English). Since we don’t have any text in a language we haven’t yet generated, this sounds useless, but bear with me – I have some Ideas.

For our purposes, you can think of a Markov chain as a table that contains, for each combination of preceding letters of some fixed length, the probability distribution of the letter that follows. For example, one row in the table could look like this:

...
ba | 50% d, 20% g, 10% r, 10% t, 10% y
...

This particular table is based on counting trigrams, i.e. combinations of three letters. In this case, the trigrams bad, bag, bar, bat and bay were encountered in the input text. The left column contains the leftmost two letters of the trigram, and the right column indicates how frequently each next letters was encountered. There are special indicators for start-of-word and end-of-word, which can be treated just like other letters.

Creating the chain

To produce the Markov chain, we need some input data. I want a diverse set of languages, so after some searching, I settled on the UDHR corpus, which contains the Universal Declaration of Human Rights translated into 372 languages. This text is rather short: only 1783 words in English. For a normal Markov chain word generator, this would be pretty limiting. But for my Ideas, it shouldn’t matter.

Here’s the full table for the English version, if we count bigrams (combinations of two letters):

^ | a 270, t 256, o 168, i 101, r 96, s 96, e 93, h 92, f 89, p 82, b 69, w 58, c 57, d 43, n 41, m 32, l 27, u 21, g 17, j 7, v 4, k 3
a | n 174, l 128, r 93, t 92, s 68, c 30, $ 20, m 17, v 16, g 16, i 13, d 9, w 9, b 8, y 7, u 2, f 1, p 1, k 1
b | e 52, l 18, y 13, i 7, a 5, o 4, j 4, s 3, u 2, r 1
c | l 45, o 43, e 43, t 38, h 32, i 30, a 19, $ 12, u 10, r 9, c 5, k 5, y 1
d | $ 181, e 45, i 34, o 23, u 15, a 12, l 3, s 3, v 2, g 2, r 2, y 1, h 1
e | $ 363, r 144, n 106, d 84, s 66, c 51, v 40, l 39, e 38, a 32, m 23, t 21, q 16, i 13, f 12, p 7, x 7, o 6, g 3, y 3, k 2, b 1
f | $ 98, r 39, o 31, e 16, u 16, a 11, f 9, i 4
g | h 61, $ 33, e 22, a 12, n 10, r 8, i 8, u 4, s 3, o 3, t 1
h | e 174, a 75, i 60, t 56, $ 36, o 25, u 14, r 3, m 1, y 1, n 1
i | n 135, o 109, t 92, g 71, s 69, c 66, e 25, m 24, v 22, a 22, l 19, r 14, f 8, d 6, b 6, p 5, z 4, $ 1, h 1
j | u 6, o 5, e 4
k | $ 7, i 4, e 3, s 3, n 1
l | $ 120, e 74, l 55, i 47, a 29, y 23, o 15, d 12, t 8, u 7, f 4, v 2, s 2
m | e 49, a 30, i 23, $ 21, o 17, s 17, p 13, m 8, b 7, u 4
n | $ 171, d 142, t 83, a 59, e 58, g 41, i 34, c 34, s 32, o 24, y 19, j 4, h 2, n 2, u 2, l 2, m 2, k 1, v 1, f 1
o | n 189, $ 97, f 95, r 94, m 48, u 36, t 35, c 22, p 19, l 13, d 9, o 8, s 8, y 7, g 6, w 6, v 6, b 4, i 2, h 1, k 1
p | r 43, e 43, l 16, o 12, u 11, a 8, i 6, m 4, $ 4, p 3, t 1, s 1
q | u 16
r | e 128, i 100, $ 85, t 53, y 53, o 43, a 42, s 25, d 11, n 11, m 9, r 8, v 6, b 5, g 5, k 5, u 4, f 4, p 4, c 4, l 2, h 2
s | $ 214, e 47, t 46, h 33, o 32, s 24, u 16, i 15, a 11, p 11, c 9, l 3, d 2, r 1, y 1
t | h 199, i 161, $ 121, o 90, e 75, y 37, a 35, s 33, r 24, l 11, u 10, t 5, w 1, m 1
u | n 42, r 29, m 17, a 17, l 16, t 16, c 14, s 11, b 9, d 6, i 6, p 5, g 4, e 3, f 1
v | e 76, i 10, a 8, o 5
w | h 22, i 18, o 12, $ 10, e 6, a 5, n 2
x | i 2, p 2, e 2, $ 1
y | $ 127, o 31, m 3, r 1, w 1, l 1, s 1, i 1
z | a 3, e 1

I’m using ^ to indicate the start of the word and $ for the end of the word.

Generating words

Now let’s generate a word using this table, picking the most likely letters each time:

From the start-of-word indicator ^, the most likely next letter is a.
From a, the most likely letter is n, forming an.
From n, the most likely letter is $, so we are done.

Indeed, an is a rather common English word. If we had started with t instead, can you see where we are most likely to end up?

Now let’s write some code to automate this process, and also randomly select the next letter according to the weighting, instead of just picking the most common one. Here are 10 words produced by the table above:

no
ofessinyoory
tofen
thal
frtitopof
as
eraricolalees
con
berthigior
derthirghtiredendacorouly

… Okay. Not exactly English. What if we use trigrams instead of bigrams? The table is too large to show in full, but here’s some output:

and
the
beitradefoull
mation
ance
weedomine
in
artion
torights
a

Better. Four of those are actual English words, the rest look like parts of words glued together, but that’s fine. Let’s try it on some more languages. I’ve added capitalization and punctuation manually.

Language	Generated sentence
Dutch	Dat van welken eeft sond overwel echijn hetzen stikerrichtens opvolkel.
Spanish	Que la hagará destaral mérionesu plese humad nal humanacionalgual pentodada.
Finnish	Tei kaiskosa ja ja mihmisteettä arti la ja liseen ja.
Serbian	I člata privo poranjudje zemljšavo mednosti ste i ovešanda ne.
Zulu	No kuzwenhlama iswakekhelulundle nomba basivikathwazo olokwayimigazilele isizinke isizwe wona nombenza.
Chinese	育方他努所普照定家任.

Looks quite reasonable to me. I don’t think I’ll use non-Latin-based alphabets, but it’s neat to see that the algorithm correctly inferred that Chinese words mostly consist of a single character.

(Fun fact: DeepL translates the generated mock Chinese text as “The United States of America is the only country in the world that has a universal mandate for the protection of human rights.” So my code, in all its simplicity, is already on par with modern LLMs when it comes to hallucinating! But the sentence is clearly ambiguous, because Google instead translates it as “He strives to make the best use of his talents and to fulfill his family responsibilities”… Chinese is as wonderful as it is mysterious to me.)

The first Idea

Now, how do we get from these Markov chains for real languages to Markov chains for generated languages, that don’t really exist? Here, my Idea is to not create a Markov chain of letters, but of letter classes: vowels and different types of consonants. When generating words, we substitute each class with a letter from that class. This should reduce the resemblance to the input text, and hopefully combine the strengths of Martin O’Leary’s algorithm (pronouncable, plausible words) with those of Markov chains (natural word structures).

I’ll start with these letter classes, grouped roughly using my very limited knowledge of phonetics:

Label	Letters
V	vwf
M	mnñ
T	td
P	pb
L	l
S	szjščćž
K	ckq
G	grhx
A	aeiouyáéíóúàèìòùâêîôûäëöüï

Linguists will recoil in horror at this table: I’m assuming a 1:1 correspondence between spelling and pronunciation here, which is very wrong in general. But since the generated languages will be fictional, nobody will know how to pronounce them anyway.

Now before we create the Markov chain from our input text, we first replace each letter in the text by its class label. This yields a much shorter table, which hopefully captures the word structure (phonotactics) of the input language. For English:

Preceding	Following
AA	M 176, T 53, L 43, G 29, S 24, $ 22, K 11, P 11, V 10, A 2
AG	A 168, $ 86, G 79, T 64, M 30, S 25, P 11, V 10, K 9, L 2
AK	A 81, L 39, T 36, G 23, $ 14, K 10
…
^S	A 50, G 30, T 14, P 4, L 3, K 2
^T	G 160, A 139
^V	A 93, G 58
^^	A 653, T 299, G 205, P 151, V 151, S 103, M 73, K 60, L 27

Of course, the quality of generated words is pretty hard to judge now:

GAPSAMKA
GAAT
AMT
TG
PGA
AVALTAM
TGALAALA
VAGA
AGAGTA
AVAL

To map these class labels back to actual letters, we use the occurrences of letters in the source language as weights. For example, in English, ‘e’ is the most common vowel, so it’ll have the largest probability of being chosen if class ‘A’ is encountered.

GAPSAMKA -> repsancu
GAAT -> hiet
AMT -> unt
TG -> dr
PGA -> pha
AVALTAM -> evaltom
TGALAALA -> thiloela
VAGA -> vere
AGAGTA -> ehirda
AVAL -> owel

It certainly doesn’t look like English anymore, but it does look somewhat like a real language.

Can we still distinguish our input languages from each other?

Language	Translated sentence
English	Hepsanco ongs ofe pa ren rot reco beind elesois ba.
Dutch	Hovt fheegerelinoden ta vigste den sen en vaen ieetin iam.
Spanish	Pocrancoenicin proenpracon depdaruehosunil lo ensdes inena ne si o por.
Finnish	Sehviltaan jolnaisee soin ara aos vili alli votu takaon ioldervyte.
Serbian	Jvhća ci dake ejan tgutzeni jve prapag o jen avirlosovo.
Zulu	Zeantahla aselolalu na omgulinpe ekgemte nha ezujwezini oswancywy la wuntgokuto.

We still get some the double vowels typical of Dutch and Finnish, and the rhythm of the Spanish words also seems familiar. English is all over the place, but that’s fair, considering it’s something of a bastard language.

However, I’m not thrilled about phrases like “pocrancoenicin proenpracon depdaruehosunil”. Those are altogether too many long words in a sequence.

Word lengths

Fortunately, I don’t want to generate entirely random sentences; I want to “translate” English into these generated languages. That lets us use the original English sentence structure as a basis, which doesn’t have such word sequences. So let’s start with a famous English sentence:

It is a truth universally acknowledged, that a single man in possession of a good fortune must be in want of a wife.

For each word, we’ll generate a word in our target language that has the same length. I’m just doing this brute-force by generating words until one of the right length comes up (allowing a little leeway if this takes too many attempts):

Language	Translated sentence
English	Dr bo en fenec tholerefend fritemyh, tach mah peamni tga uh hisedehtaos na li arer treseut, roun he ri thes en jer er.
Dutch	Ge in ca aweri everdied entermekgtih, tico en ainven ofd hol ollosejhan di av bisn injalto, acht an an folj in in eint.
Spanish	Ra lu ó cecom cenpinamenete esórvecre, dede o dochoi dos ce laprecopiál ta e ale vinstaz, heho se ne con la am lasal.
Finnish	An os tä kakina parsikejta kiimeittevyson, esin ke käatan han nos tiklunnäsvyn hoam te etun ehdanta, ahten ta ut naat on dän keyn.
Serbian	I an i jvono drjulmarlen epstiti, nuvo u ojonsu sui vo sugide na i ali miluvok, slodo a eno nina si ta pidu.
Zulu	Le wu ki inhu ecazikekelwy kwytshakhabu, ongo eo akwale eenwu na unbhedhutvi kwy mu okga aswoche, aswa ma nha ano esi awo langi.

In real languages, of course, word lengths are not the same between languages. Some, like Greenlandic, are famous for their long words – the longest Greenlandic word in our input text is “suliffissaaruttoornaveersaartitaanissamut” at 41 letters. Other languages might consist mainly of shorter words. The distribution of word lengths is a significant part of each language’s characteristic look and feel.

To incorporate word length into our generator, we’ll start by tallying how often each word length occurs in the input text:

Now, rather than just drawing random samples from this distribution, I would prefer that short words in the input sentence remain short in the translation, and long words remain long. So we want to somehow “remap” word lengths from English to Greenlandic. We can do that by looking at quantiles. For example, say we want to know the appropriate word length for the translation of the 5-letter word “truth” into Greenlandic. First we calculate: what proportion of English words are shorter than 5 letters? Let’s say it’s 30%. We then generate a word such that (roughly) 30% of Greenlandic words are shorter than that word. Let’s see if it works:

Language	Translated sentence
English	Dr bo en fenec tholerefend fritemyh, tach mah peamni tga uh hisedehtaos na li arer treseut, roun he ri thes en jer er.
Dutch	Ren sen ca tikgap werivelcanekeahenbeg entermekgtih, hienr ep oevenr eem ofd jirveredelazde rie lat vejn eateewd, vomjm wra ran oafel nen vom hemhe.
Spanish	Ra lu ó irduro cenpinamenete intesteea, qorda o dochoi baro on pehtelicil ne a toin dadroccóe, aserud la am tyine de i upah.
Finnish	Syan enui an eramion attinellodaselu ogtemkoättistima, seenoin ha sästaetta allaäte han tiklunnäsvyn hoam suen joenjam pätassaltta, ehdanta ahten oon teunnat naat on oulten.
Serbian	I an i iparat šadodisamevnu majbesnapejte, nuvo o ikasta jrinto ti etnujanajesi šo a potća bravirač, nina in am žlijo ku a moko.
Zulu	Nahle mhulule inhu ecazikekelwy mzamhaputhakwuna kwytshakhabu, enhylali lola oaudhule ajekwonka ikacge asuwezwumgle aakula axlu emebagte nokuthenpha, iswucusu lelolu bosanga kvemhike nhalu awo ecalwenhu.

It seems to do the trick. In particular, mock Finnish and mock Zulu have become considerably more representative of their origins.

Supercalifragilisticexpialidocious

Oh, did someone say Greenlandic? Alright, let’s have it:

Language	Translated sentence
Greenlandic	Tiaqarnit inatenraaotila unat eijsataluunmuit alitiunimniasagsuritriluanakait qaemnetirsinasasesuitugsiitaissi, tinmgofvaimalli senuq pernuiffainmiinaqqanmaq iittiuvfaqkit qaniaremi inmappamnainnainniqalluat pississok pasat uppagaiteautaanulit ugniqissannassinnut, anmriunnatsiniq anuitirtaq pasat turanissiinmut tiavfakirat mutit pasjanikiaraaq.

However, there’s a subtlety that I’m ignoring here: languages with long words typically pack more meaning into each single word. For example, the aforementioned “suliffissaaruttoornaveersaartitaanissamut” appears to mean “protection against unemployment”, so it does the work of three English words all by itself. Even then, Greenlandic is relatively verbose: the entire Universal Declaration of Human Rights text contains 58% more characters than its English counterpart.

I don’t want to get into such merging of words, but I do want to scale the word length back a bit, so that on average a generated Greenlandic word is 58% longer than the original English. It seems to work – words are still long, but no longer outrageously so:

Language	Translated sentence
English	Dr bo en fenec tholerefend fritemyh, tach mah peamni tga uh hisedehtaos na li arer treseut, roun he ri thes en jer er.
Greenlandic	Akanit kalla mi tigninnik eessutnakusinngat isunalilliirutonamu, aronnrit ania taqirfuk umagtat qigat tiqalarirnililli pasat taq pissutet anuitirtaq, anaila inniat mutit nakugeemut tiutat tiak samakcali.

The second Idea

For each input language, we now have:

a Markov chain for letter classes,
the probability of each letter within each letter class,
the distribution of word lengths.

The second Idea is that we can mix and match these between languages. For example, this could produce a language with the rhythm of Italian, the letters of Turkish, and the word lengths of Greenlandic.

For that to work well, we need some more languages in the mix. So I hand-picked over 30 languages that can reasonably be rendered in an extended Latin alphabet, trying to cover a broad spectrum of language families as based on this website. For Abkhaz, Arabic, Chinese, Greek, Japanese, Russian and Ukrainian, I used the uroman Python package and cleaned up the output manually.

After implementing the random mixing and matching, we have over 50,000 possible fictional languages. We can now also make each language generate its own name!

Language	Origin	Translated sentence
Sashhomuz	Abkhaz + Hani + Uzbek	Ae ti es eshi uaahahu uhutalido, aee yi dgoq ydeo cho onashulexds aqx ti aaio ilaqhu, ojny yim din oshi ea eb eliq.
Drli	Hakha Chin + Serbian + English	Me um i orto rmokinraoldo domrmir, nuk or rnoika ćai lo rmecno li i lavr kaimok, airr li li duuk ng a nrad.
Lotolis	Hungarian + Russian + Finnish	Nic mon vo elazuro otelidenecmeoll satihasapamily, bolicc a zsosihen tisnyn sa kudisetereht kit i viledes yllantaho, osatsyk ilu lin ssen lin suh ventab.
Brvah	Irish + Turkish + Uzbek	Ir eys ü ardrem ırseedheas ütarrriihsethıç, krin ğü ketril bian emi bıekrenhse hkr t iıne ereeh, beıl lyn bra anti rus an fart.
Nespasto	Quechua + English + Lithuanian	Osfes hoam as asllenam cicremaocope cieuacoscillis, llasko to vifehonto toenes com boscaaetetu tece os ronuma nanacal, cenan min cobi moiene es cona llince.
Mahgi	Edo + Xhosa + Kurdish	Ei ao en wanfan nege agpanvan, kan e kaghe ohaen ni ohaqho kgy e uxeu inwigpo, uabe su ta awbe no u inwen.
Tahiwk	Hani + Huasteco + Kikongo	Má nal jac baaik piulnákkoil noaanák, cyal bé céewik caaw ka jilpa bá bi pyjyl maéwc, lakhha ia la táawk i sa lakjek.

I like it! These languages are fairly plausible, yet reasonably distinctive.

It would be possible to mix even harder, for example by choosing each character class from a different language, or by constructing a new Markov chain from the trigrams of multiple languages merged together. But I’ll leave it at this for now.

Place names

Now that we can generate languages, and words within each language, it’s a small step to produce names of cities. Most of the time, these will be single words, but sometimes we’ll want to generate a composite name like “Dar es Salaam” or “The Hague”. I did have to impose a limit of 20 letters for this not to get out of hand.

Language	Origin	Generated city names
Sashhomuz	Abkhaz + Hani + Uzbek	Znexkha, Aiylolo, Omyiheop, Yeyhi, Amimeh, Esunsou, Aihegai-Amuihui, Ieno-Ilejhe, Om-Osamimaala, Ipshi
Drli	Hakha Chin + Serbian + English	Rlenkrim, Tiasojal, Krot-Mre-Ninta, Kgaor-Denrkan, Liolla, Kaomrtir, Diulrni, Kop Jijela, Nintumr, Zoldin
Lotolis	Hungarian + Russian + Finnish	Zsynintak, Zzihoga, Sayhek, Venkiom, Sasso, Va-Valtosas, Ellak, Zssat, Nentos, Tok-Kolehik
Brvah	Irish + Turkish + Uzbek	Rcrtriymta, Us-Rımtram, Kht-Iaimy, Ahkitr, Iıhfarb, Bhaapha, Deutr, Leene, Lianmü, Etr-Rğenna
Nespasto	Quechua + English + Lithuanian	Sebayni, Ogane, Lloes, Cintoe-Ates, Ebeshiscoe, Lenes, Comeno Sas Cafpeo, Cgoon-Llonim, Mynocanaj, Chinemim
Mahgi	Edo + Xhosa + Kurdish	Goaemwon, Idymnwyna, Fewon, Unnwun-Iwboe, Ovonwan, Uluhu, Agaunkufu, Aewba, Hhum Nizukheke, Igei-Iwenfaunae
Tahiwk	Hani + Huasteco + Kikongo	Jsal, Siak-Cáwk, Nekkawc, Xial, Kakyw-Naek-Keaow, Aac Lácáyl, Baol, Aí Keuw, Jakbail Taw Naáktak, Jjylcea

I can just imagine the player finally learning Sashhomuz in the city of Aiylolo, only to be confounded when the next city over, Sayhek, turns out to speak Lotolis instead…

Around The World, Part 18: Charting the seas

Wed, 24 Jul 2024 00:00:00 +0000

Maps will be an important part of the game. Let’s take a look at how we can draw those!

By “maps”, I don’t mean your usual in-game map, which is always there in the corner of the screen, tracks your position and orientation, knows all parts of the world, and is never wrong. No, I’m talking about the kind of maps that sailors in the age of discovery actually used: sketchy, partly based on hearsay, woefully incomplete, often just plain wrong, and with no built-in GPS to tell you where on the map you are.

In the real world, it takes a lot of effort to remove incompleteness and wrongness. In our perfect computer-generated world, it takes effort to add them. So let’s first try to come up with a complete and correct map instead.

(Aside: if you like reading about procedural map generation, I can highly recommend Here Dragons Abound by Scott Turner. Scott’s map generator does way more than I can ever hope to achieve, and he blogs about it in detail.)

Maps? Maps?!

Actually, using the word “map” is not quite right at best, and almost blasphemy at worst. The correct term is “chart”. NOAA’s National Ocean Service is almost condescending towards maps:

A chart is used by mariners to plot courses through open bodies of water as well as in highly trafficked areas. Because of its critical importance in promoting safe navigation, the nautical chart has a certain level of legal standing and authority. A map, on the other hand, is a reference guide showing predetermined routes like roads and highways.

Nautical charts provide detailed information on hidden dangers to navigation. Maps provide no information of the condition of a road.

Here’s an example of a typical chart. This one was drawn by Johannes Jansson around 1650:

It’s a good example of the style I’ll be aiming for.

Charting the coast

We have a height map of our world, so the easiest way to produce a topographical map (and yes, this is more like a map than a chart) is to apply a colour scale to these heights:

It’s start, but it’s still a far cry from Jansson’s beautiful work. Our height map focuses on the land, whereas nautical charts usually had very little detail on land; only features that are helpful in navigation were drawn. So let’s start by detecting coastlines from the height map using a marching squares algorithm. Drawing the coastlines on a nice parchment-like texture:

Okay, that looks more like it. But without prior knowledge, it’s hard to distinguish land from water. The old charts address this in several ways:

Shade either land or sea, often only along the coast. Or shade both with a different colour.
Draw rhumb lines (those criscrossing compass lines) only on the sea.
Place city labels only on land.

I’d like my charts to have some variety, so I’ll implement at least the first two. Because I’m detecting contours as closed loops anyway, it’s easy to give each landmass its own distinct colour:

It’s more readable, but perhaps a bit over the top. How about shading only near the coast? This requires me to implement a distance transform, which thankfully is well documented (Meijster, Roerdink, Hesselink, 2002):

That looks a lot more professional. Let’s also add a windrose network to fill up all that empty space:

Lakes

We still have a small problem:

The coastline detector detects every transition between land and water, including ones inside a continent. These are lakes, and would historically not have been included in a coastal survey. More importantly, they make the chart look cluttered and aren’t reachable by the player anyway.

Fortunately, it’s easy to detect whether a polygon is a lake or a coastline, because one will be oriented clockwise and the other counterclockwise, so we can just get rid of them:

Unfortunately, this leaves us with another problem, because the land colouring is based on the original land/sea matrix, so it isn’t aware that we removed some polygon outlines. A second, smaller problem is that islands inside lakes are still drawn; see the yellow spot just above the ‘k’ in ‘Gdansk’.

A more robust approach is to fill lakes in the land/sea matrix, effectively replacing them by land before we trace the coastlines. Let’s classify as a lake every water area that’s fully surrounded by land. This does mean that lakes touching the edge of the chart won’t be removed, but we’ll deal with that later. It nicely gets rid of lake polygons, islands inside lakes, and land colouring in one fell swoop:

That’s looking a lot cleaner.

Ports

So far, I’ve been using a tiny placeholder icon to represent cities:

Surely we can do better. Somebody by the name of Zarkonnen recently published a great asset pack of map icons extracted from a 1688 German map:

The city icons are probably too big and detailed for our purposes, but the town icons fit nicely:

However, their placement leaves something to be desired. The icons currently overlap the coastline too much, showing half the city in the water.

Right now, the icon sprite is centered on the location of the city. However, the icon is quite a bit bigger than the actual city would be on the chart, causing it to stick out into the sea. Let’s try moving each icon a little in each of 8 directions, and pick the one that gives the greatest overlap with land. To make it clear what’s happening, I added some debug drawing:

This shows the actual city location in red, and the candidate icon positions in blue. The green rectangle indicates the portion of the icon that we try to keep on land. The algorithm seems to be doing a reasonable job. It sometimes puts the icon in a slightly misleading position (most notably Zeebrugge), but this does not seem to happen a lot, and in-game we can just blame it on the chart author!

Name labels

You may already have spotted the other problem: the city name labels also overlap coastlines, and each other. Let’s tackle that next.

In general, this is a hard problem to solve, because every adjustment you make to the placement of a single element might cause it to overlap other elements, which would then also need to be moved, which might have a cascading effect. The aforementioned Here Dragons Abound started with a force layout algorithm to solve this, but eventually switched to simulated annealing. That’s a rather big hammer though, so I’ll try something simpler first.

First, I’ll give each label a few possible placement positions, and check which of those gives the least amount of overlap with the coastlines:

Additionally, there is a weight factor assigned to each of the placements, to give some preference to the label being put to the right of the icon, instead of to the left, above or below.

This algorithm makes a valiant attempt to avoid coastlines, but it doesn’t yet avoid overlap between labels. For that, we can simply add previously drawn labels to the area that should be avoided:

You can see that the Qingdao label has moved to make room for Jubail. I’m not happy with the outcome yet, but with a smaller font size, hopefully such problems won’t occur frequently. So let’s increase the chart’s resolution, meaning all icons and labels get smaller:

That’s starting to look presentable. In the game, the player will be able to zoom in on these charts, so I’m not worried about drawing text at very small sizes.

I’m sure I’ll revisit chart drawing in the future, wherever the gameplay demands it: mountains, trade goods, hazards, names of regions and coastal features, and of course the mysterious X that marks the spot.

Around The World, Part 17: World generation in the prototype

Thu, 27 Jun 2024 00:00:00 +0000

The code repository in which I’m developing Around The World is called aroundtheworld4. That might make you wonder: what happened to the first three? Today, let’s take a look at aroundtheworld2.

This was the version I made in 48 hours for the Alakajam game jam, and the only one that has been publically released. I’ve been referring to it on this blog as “the game jam prototype”. You can play it in your browser right now, which I would recommend, but you don’t have to take my word for it. (I’m not sure it fully works on mobile, so use a computer with a mouse if you can.)

In this post, I’ll explain the procedural generation of the world in that game. This is an updated version of an article I wrote earlier on the Alakajam website.

Generating the world map

In this early version, the world wasn’t a sphere; rather, it wrapped around left and right, and the poles were inaccessible, so it was technically a cylinder. Here’s the end result:

The world size is 300×150 tiles; each pixel in this image represents one tile. I chose 300 because it gives some margins when displaying the map at the 320×200 resolution of the game. I chose the 2:1 ratio because it’s how an equirectangular projection of a sphere (like the Earth) is usually displayed, with one degree of latitude being the same size on the map as one degree of longitude.

Water depth is shown on the maps as four shades of blue, but in-game you can’t see depth; only one tile sprite is used for all water. This is because I had plans to make your ship run aground if you tried to enter shallows, so you had to use maps to avoid that. I’m glad I never got round to that, because it would probably have been too hard! But the different shades looked pretty on the maps, so I kept them.

The base of the world generation is, as you might have guessed, simplex noise, powered by Godot’s OpenSimplexNoise class. We can configure, among others:

the number of octaves: fewer octaves for a smoother result, more octaves for a more jagged result;
the period: a larger period gives larger continents

To make it wrap, we need to call get_seamless_image to create a 300×300 image, then crop it to 300×150. The result is an image with monochrome pixel values between 0 and 255. Most of the values are around 128. We are going to interpret these values as a height map, larger values being higher.

Filling the oceans

If we simply used 128 as the threshold to decide between water and land, about half the map would be water and half would be land, and it almost certainly wouldn’t be circumnavigable! So in the code I have a variable WATER_FRACTION, which lets me tweak what portion of the map should be water. In the end I set it to 0.75, which is slightly more than the 71% of our own planet, but always resulted in at least one possible route around the world in my tests, so I didn’t bother to actually code a check for this. This means there are probably seeds that are unwinnable!

To figure out the desired water level, the code first loops through all pixels and creates a histogram, counting how often each of the 256 values occurs:

[ 0] 0
...
[126] 1894
[127] 2645
[128] 3642
[129] 3528
[130] 2974
[131] 1490
...
[255] 0

Then it runs through this array, adding each value to an accumulator. When the accumulator exceeds the desired number of water pixels, which is 300×150×0.75 = 33750, we have found our water level. Let’s say it’s 130 for this example.

Adding ice caps

Now we need to create the poles, because the top and bottom of the map must not be traversable (this world is a cylinder, after all). To do this, a bias is added to the height of each pixel, where the bias depends on the y coordinate like this:

bias = 255 * pow((abs(2 * y / 149 - 1) - 1) * 10 + 1, 3)
if bias > 0:
pixel += bias

Formulas like this are a very powerful tool in procedural generation, but they’re harder to read than they are to write (drawing graphs on paper helps!). Yet it’s built from a few basic primitives, so let’s break it down from the inside out:

y is between 0 and 149, inclusive. So y / 149 is between 0 and 1, inclusive.
Multiply by 2, subtract 1, to get it between -1 (north pole) and 1 (south pole).
Take the absolute value to get it between 0 (equator) and 1 (either pole).
Subtract 1 again to get between -1 (equator) and 0 (pole).
Multiply by 10 (a configurable constant which decides the size of the poles) to get between -10 (equator) and 0 (pole).
Add 1 to get between -9 and +1.
Raise to the power of 3 because it looked nicer that way? I forget.
Multiply by 255 to make sure that we get a bias of 255 on the poles, which guarantees that they’ll be impassable.

Colouring the map

Next, the colours are assigned. Level 130 has a height of 0 above water level, so we say that this is the beach (yellow). The three levels above this (131, 132, 133) become light green, the next three become middle green, and so on. A similar thing happens for negative heights, which are below water. As an exception, if the pixel is near the poles (y close to 0 or to 149), it becomes ice (blueish white), but we add the height to y to avoid a sharp horizontal line between ice and non-ice. The result is that inland ice occurs farther from the poles than coastal ice, which makes sense because the ocean has a warming effect. Ice is not just cosmetic but also serves a gameplay purpose: it lets the player know that they are getting close to the pole and will be blocked if they go much farther in that direction.

Placing ports

That’s it for the terrain. Now let’s place the ports. There are up to 100 of them. I searched the web for a list of seaport names and found an Excel sheet with over 100 names, which I cleaned up a bit and copied into my code. (In jams especially, I often don’t bother opening files or parsing data, I just turn the data into a literal that can be pasted directly into a script. JSON in particular is valid source code in several languages!)

For each of the 100 ports, first we generate a random x, y coordinate pair as our starting point. If it’s land, it might be landlocked: too bad, try again! If it’s sea, we start a random walk. Each step, we move one pixel north, south, east or west. If it’s now on land, it must be coast because it was previously water. We’d like to place our port here, but first we check if there’s already another one within 4 tiles. If not, we place it, otherwise we give up and try again. If we haven’t found land after 75 steps, we give up and try again from a different starting point, up to 100 times. As an exception to avoid lots of polar cities (which would be unrealistic and might also be game-breaking), we also abort when we get close to the poles.

Adding port inventory

Finally, the port’s inventory is decided. One random cargo type is picked as supply (with 2-7 units) and two different ones are picked as demand (at twice the regular price). We need to make sure that these are all unique, because it makes no sense to both supply a good and demand it. Your first intuition might be to pick a random type until you’ve found one that’s not used yet, but there’s an easier way: simply create an array of all possible types, shuffle it, and pop items off of it. For large arrays and small numbers of samples, this is obviously rather inefficient, but for small arrays it’s fine, and it makes the code a lot easier to write.

As to equipment, in 60% of cases, a map of random size is offered for sale; in 40% of cases, one of the three powerups is offered. (In the game, you might encounter ports without any equipment. This is because when you buy the Binoculars, any Binoculars in other ports are upgraded to Telescopes, and when you buy the Telescope, all remaining Telescopes are deleted.)

Wrapping up

As the very last step, the game decides what your starting port is going to be. This is not simply a random port! I wanted to make the player start in the “easiest” part of the map, so I added some code that counts for each port how many ports are within 15 tiles distance from it. The port with the most such neighbours becomes the starting port, and the player’s ship is placed in the middle of an adjacent sea tile.

And that’s it! I hope you enjoyed the read; now go and play the prototype if you haven’t already! I’ll be back in the next post with more updates on the new, in-progress version of the game.

Around The World, Part 16: A matter of scale

Tue, 18 Jun 2024 00:00:00 +0000

All else being equal, I prefer games (and books, and movies) to be realistic, rather than making things up on the spot. But of course, all else is rarely equal. Today, I’ll be taking away some of the realism of my procedural world generator to accommodate gameplay.

The trouble

Douglas Adams might have written:

Earth is big. You just won’t believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think it’s a long way down the road to the chemist’s, but that’s just peanuts to Earth.

Planet Earth has a radius of 6371 km, a circumference of about 40,000 km. (That’s no coincidence: the metre was originally defined as 1/10,000,000th of the distance from the pole to the equator over Paris.) The first expedition to sail around the world was Magellan’s, and took this route:

Source: Wikimedia Commons by Sémhur and Uxbona, CC-BY-SA 3.0

A 15th-century carrack like the ones Magellan used would be about 25 metres long and 25 metres tall:

Replica of the carrack (nao) Victoria, the first ship ever to circumnavigate the world. Source: Wikimedia Commons by Gnsin, CC-BY-SA 3.0

At sea, standing in the crow’s nest of such a ship on a clear day, the horizon would be about 20 km away. But interesting things like ships and islands are tall, and you’d be able to see them beyond the horizon as well, so let’s say your maximum view distance is 50 km. Those are the numbers I originally plugged into the game.

However, remember that I chose to show the world from a top-down, bird’s eye perspective. When fully zoomed out, at a common resolution of 1920×1080, one pixel on the screen would be about 50 metres in the world. The ship would just be half a pixel! You’d need to zoom in by a fair amount until you can even see that it’s actually a ship.

It gets worse.

Magellan’s fleet took about three years to circumnavigate the world, averaging less than 2.5 km/h. I’m aiming for a single run of the game to take about three hours instead, so I’m compressing time by a factor of 10,000 (8,760 for the pedants, but this isn’t an exact science). To accomplish that, the player’s ship would need to move at a speed of 25,000 km/h — that’s 20 times the speed of sound, and well on its way to escape velocity towards outer space. In a single second, you’d be traversing 7 km. For a half-pixel ship, that would certainly look like ludicrous speed. I’m not trying to build Kerbal Sea Program here!

The solution

I’m going to have to shrink the world. A lot. After some tinkering with a ~~spreadsheet~~ highly advanced game design tool, I figured I’d make the world scale 1:100. A 400 km circumference might sound small, but it’s still much bigger than most open-world games, so there’s plenty of space for adventure. This takes care of a factor of 100 out of that 10,000. (Somebody on Mastodon suggested I should just scale up the models instead, but it amounts to the same thing. Keeping the models scaled 1:1 makes authoring easier.)

I also decided to significantly speed up the ship. Magellan’s fleet may have averaged 2.5 km/h, but under optimal conditions, they would have been doing about 7 knots, or 13 km/h. That means the 25 m ship would travel its own length in 7 seconds. I tried this in the game, and it feels really, painfully slow. Instead, I ended up with a ship that can do 90 km/h, which is pretty ludicrous for a sailing vessel, but feels right in the game. This takes care of another factor of 7 out of that 10,000.

That leaves a factor of about 15 still to be dealt with. For that, I’ve just added some buttons to speed up time. These will be necessary anyway: carefully navigating along a coast calls for a slower rate than crossing an ocean. At a 25× speedup, movement looks obviously fast, but not ludicrous.

At a world scale of 1:100, a view range of 50 km would allow you to see all the way across the Atlantic ocean. Clearly that would take the fun out of discovery, and would make maps pointless. So I reduced the view range to 1 km; not scaled all the way down, but enough to make it feel constraining.

Scaling the heights

But now, major terrain features like mountains are much too small. An 8 km tall mountain like Mount Everest would stand only 80 m tall, which would be only a minor hill compared to the 25 m tall ship.

So we’ll have to scale up those “minor” topography features, keeping them closer to their real-life size, while retaining the “major” features like continents at 1:100 scale. Fortunately, I had seen this coming and kept all the scaling factors in the procedural generation easily configurable.

Without further comment, here are some pictures of the state after about a day of tinkering:

The new world scale has some advantages. Remember that the global world map is generated on a 6×512×512 quad sphere. A single grid cell used to be about 20 km in size, so any small-scale features like rivers and barrier islands could not be generated at this level, and would have to be produced with more limited “local” functions like simplex noise. After downscaling, a grid cell is only 200 m (1/10th of the player’s view circle), so adding such features at the global level becomes feasible. I’ll have to see how much time I want to spend on that.

Another advantage is that I no longer need double-precision floating point maths. A single-precision float has a precision of 3.8 mm at the surface of our 1:100 world, which turns out to be sufficient.

Around The World, Part 15: Making waves

Fri, 31 May 2024 00:00:00 +0000

I’ve been investing a lot of effort in the generation of plausible land. But the game is all about sailing, so most of the screen will be filled with water, not land. It’s time to take that smooth blue plane that served as the sea, and make it look better!

The rendering of the water will largely be done in a shader. Godot shows changes to shader code live in the editor itself, but it doesn’t hot-reload modified shaders into the running game. So to shorten the feedback cycle, I created a little test scene in Blender and imported it into Godot:

This also reveals the carrack that I modeled earlier. For reference: it’s about 25 meters long.

Sines

If you’re even slightly mathematically inclined and you think of waves, you think of sines. So let’s start with that: a single sine wave, moving along the water. I’m using the very same mesh data as for the terrain to also render the water surface, but with a vertex shader that moves the vertices up and down. The wave propagation speed is determined from its wavelength a simple formula: frequency = sqrt(gravity * 2 * pi / wavelength). This is only valid in deep water, but I’m using it for shallows too. Here’s the result (I’m too lazy to create videos of every step, so you’ll have to make do with static images):

The effect is… underwhelming. Part of the reason is that the mesh normals aren’t modified: they still point straight up. This affects things like shadows and reflections.

Fortunately, it’s easy to compute the derivative of a sine wave, which can be used to compute the gradient, which in turn can be used to compute the normal.

I’m doing all this in the fragment shader, so it’s done finely per pixel rather than coarsely per mesh vertex. This will make a big difference in visual quality later on, when we add finer details.

Transparency

The shape of the waves is not yet great, but there’s a more pressing problem: this blue sheet doesn’t look like water, but more like a corrugated solid surface. It lacks the transparency and reflections that are characteristic of real water.

Real water gets more opaque the deeper it gets, because more and more light is absorbed along the way to the bottom and back up again. We can emulate that: since we’re reusing the terrain mesh to render the water, each vertex already knows the local water depth from its y coordinate. So let’s use that to create exponential attenuation:

Note that this is only an approximation, because it’s not the water depth that matters, but the length of the path that the light takes towards the bottom. If you’re looking at an oblique angle, that path might be (much) longer than the actual depth. But we’re not using very oblique angles in this game, so the approximation works well enough.

However, because shallow water is now almost fully transparent, it’s difficult to see where the water ends and the land begins. In reality, there would be some foam caused by breaking waves. We can easily add that: wherever the water depth (including wave height) is less than 1 meter, render the water as opaque white:

The surf definitely does not look amazing. It could do with a bit of texture and randomization. But it’s not awful and it serves the gameplay purpose, so it’s good enough for the moment.

Wave shape

As I discovered while I was working on this, there is a lot of scientific literature on waves. One thing that immediately becomes clear: ocean waves are not sines. A better model is the so-called trochoidal wave or Gerstner wave:

Source: Wikipedia by Kraaiennest, CC-BY-SA 4.0

As you can see, each surface particle doesn’t just move up and down; it actually moves in a circle. It’s tempting to have our mesh vertices play the role of surface particles, and move the vertices horizontally as well as vertically. It looks good, but it has a significant drawback: the water surface is no longer a simple height field. In other words, given a coordinate in the world, it’s very hard to compute what the water height at that point is. And we’ll need that computation later, when we want the ship to float on the surface and move in response to it.

So we’re going to settle for an approximation. The very first chapter of the very first GPU Gems book describes one way to do this: shift the sine wave vertically to be between 0 and 1, raise it to some power, then shift it back. (Note that the web rendering of the book is slightly broken: the π symbol is missing from some equations.) A power of 2 looks good to me:

Calculating the derivative is slightly more involved now, but it’s still just high school calculus. We can vary the exponent to make the waves look more or less pointy, but higher exponents flatten the valleys too much, so this model is not perfect. I can always revisit it if needed.

More waves

The corrugated solid look is gone, but the waves still look extremely straight and artificial. Real ocean waves are affected by all sorts of random processes, so they aren’t so regular. We’ll take another page out of the GPU Gems book, and add four such waves together, with different amplitudes, wavelengths and speeds – and most importantly, moving in slightly different directions. They add up to a much more irregular surface:

It may not be immediately clear from these static images, but the interaction between waves and land does look rather weird. Basically, there isn’t any: the waves simply pass through the land and disappear. In the above image, you can see a relatively tall wave cutting a straight path through the islands.

In reality, waves tend to get taller in shallow water:

Source: Wikipedia by Régis Lachaume, CC-BY-SA 3.0

However, that by itself will only make the problem worse. There’s another effect at play which counteracts the growing waves: when they get too tall, they break and topple forwards. Breaking waves are more difficult to model, so I don’t want to go there for the moment. Instead, I’ll just reduce the amplitude in shallows, all the way down to zero at the waterline:

That gives a much calmer and more convincing look, especially in motion. The definition of “shallows”, by the way, is also in the literature: water is considered shallow if the depth is less than half the wavelength. This means that shorter waves will travel farther towards the waterline before getting extinguished.

Fine details

We’re getting there, but a real ocean surface doesn’t stop at a sum of just four waves. There are also waves of much shorter wavelengths running around and interfering with each other, giving water its characteristic sparkling and shimmering reflections:

Source: Pixabay by jingoba

Since we’re having fun summing powers of sines anyway, why not sum some more, adding shorter and shorter waves to the mix? The effect is… not quite what I was hoping for.

Due to the smaller wavelengths, there are clearly visible repeating patterns now. The same actually happens for the larger waves as well, but it’s not visible in this small-scale test scene.

Can we fix this with more sine waves? Only up to a point, as it turns out. After over an hour of tinkering with parameters, I got somewhat better results:

I might eventually have to throw in some simplex noise. What’s holding me back is a limitation in Godot: even though the simplex noise algorithm makes it trivial to compute the gradient of the noise alongside the actual value for little to no cost, Godot only exposes the value and not the gradient.

On a sphere

Did I mention that everything is harder on a sphere? This includes waves.

First off, the y coordinate of a vertex is no longer equal to the height of the terrain. We could do a calculation using the vertex position, but remember that I’m using a floating origin, so this is harder than it seems. Instead, I’m just passing the terrein height (negative for water depth) in a custom vertex attribute.

A more subtle problem is how to represent waves. Imagine a single wave all the way around the equator, travelling north. At the equator, all looks good, and the wave crests will look nice and parallel. But the farther north you go, the more they are distorted; at the north pole, the waves would seem to converge inwards from all around you!

A related problem, which also applies to flat planes, is: how to adjust the waves when wind speed changes? We can’t just change the wavelength of an existing wave, because as GPU Gems mentions: “Even if it were changed gradually, the crests of the wave would expand away from or contract toward the origin, a very unnatural look.”

But GPU Gems also has a solution: individual waves live only for a limited amount of time, fading in at the start of their lifetime and out at the end. “Therefore, we change the current average wavelength, and as waves die out over time, they will be reborn based on the new length. The same is true for direction.”

This also solves the problem of distorted waves on the sphere: as long as the player moves slowly enough that new waves are born around their point of view, they’ll never get to a point where the waves appear to converge or diverge significantly.

Anyway, after getting all that sorted out, the water renders nicely in the game:

(This might be the first screenshot I’m sharing of the game itself! Please ignore the ugly HUD. It’s all placeholder.)

I’m well aware that it doesn’t look great yet. But at least it appears… watery?

Around The World, Part 14: Floating the origin

Thu, 11 Apr 2024 00:00:00 +0000

In the previous post, we got to see our generated world at close range. This revealed some precision problems that I knew I’d need to deal with eventually, but had been putting off for a rainy day. Now I could ignore them no longer.

The trouble with floats

Godot uses single-precision floating point numbers throughout the engine. I’ll call them “floats” for short. These numbers are stored in 32 bits. In order to allow both very large and very small values, these 32 bits are split into a mantissa and an exponent:

Source: Wikimedia Commons by Tanner, CC-BY-SA 3.0

The mantissa (“fraction” in the above image) stores the actual digits of the number, and the exponent indicates where the decimal (binary) point goes. The consequence is that floats don’t have the same precision throughout the number line: the larger the number, the larger the step becomes between two consecutive numbers that can be represented.

This is fine for most games, where the world is small. But as it turns out, a planet the size of the Earth is actually not small. At Earth’s radius, 6371 km from the center of the planet, 32-bit floats have a precision of about 0.38 meters. It’s a kind of grid that every object will be snapped to, and any movement will have to take place in increments of this step size. And this grid isn’t nicely aligned with the planet surface either, so sideways movement will often also cause the object to move up or down at the same time.

For most of the game, this amount of precision is actually still fine. I don’t plan to generate terrain triangles smaller than a few meters, and at that size any rounding problems will mostly be invisible. But for movement of the player’s ship, the lack of precision is an issue. It seems to jitter as it moves around. (“Ship?”, you say? Yes, I have been working on gameplay systems behind the scenes as well. More about that later!)

Non-solutions

Naively, you might think that we can just change the units of the scene to something smaller, like millimeters instead of meters. This doesn’t work because the numbers just get bigger – the digits of each number remain the same, the only thing that changes is the location of the decimal point in between them. Instead of a precision of 0.38 meters, you now have a precision of 380 millimeters.

A working solution would be to use 64-bit floating point numbers, or “doubles”, instead. For games at the scale of the galaxy, this still isn’t enough, but at Earth scale it’s plenty: a double has a precision of 53 bits, allowing for a precision of nanometers at the planet’s surface.

Godot actually supports using doubles instead of floats throughout the engine. There are a few reasons why I chose not to go this route. First, because it requires recompiling the engine from scratch – actually pretty easy for me, but a bit of a chore. Second, because it’s a fairly recent addition and probably not widely used, so I would expect to encounter bugs. And third, because it’s an all-or-nothing deal: everything in the engine will then work with doubles. This means that basic types like Vector3 suddenly take up twice as much memory, which also means that mesh vertex data takes twice as much memory and twice as long to upload to the GPU. SIMD instructions can only process half as many doubles as floats simultaneously, so CPU efficiency also suffers.

So, in the end I once again chose to make life difficult for myself, and implemented a hybrid solution.

Floating the origin

The key idea, which games like Kerbal Space Program also use, is that floating-point numbers actually are very precise — as long as you don’t stray too far from the origin. So, what if instead of having the origin at the center of the planet, we just put it where we need it to be? Instead of moving the player through the universe, we move the universe around the player. Things far away from the player still won’t be precisely positioned, but they’re so far away that we don’t care. (This idea goes back at least as far as 1984, to the original Elite game on the BBC Micro. This amazing website by Mark Moxon explains how that – and all the rest of that game – works in extreme detail.)

In fact I get to cut some corners here. Because doubles are precise enough for my needs, I can just store each object’s position in 64-bit double precision relative to the world origin. When it’s time to render the frame, I convert this to a 32-bit float relative to the player, for consumption by the Godot engine. This way, all my game logic remains in global coordinates, making it easier to work with. Because these are discrete game objects, not big arrays of vertices, the added CPU and memory overhead should be minimal.

However… now I need to put this 64-bit position on every object in the world. And that’s a whole new can of worms.

Components

Godot’s architecture is heavily based on object-oriented principles, and inheritance in particular. So if you need to have some functionality on every object, regardless of its position in the class hierarchy, you’re out of luck. You’d have to add it to the root Node3D class, but this is part of the engine itself and cannot be modified. (Granted, Godot is open source, you can in fact modify the engine. But I’d prefer to keep using the official builds, so I can easily keep up to date with the latest version.)

Fortunately, Godot’s node system is also very flexible. You can define the additional functionality as a separate node, which is attached as a child to every node that needs it. The new node is a kind of pluggable “component” that you can reuse wherever you need it. This article by GDQuest demonstrates that approach.

However, it never felt quite right. You often need to interact with the sub-node that stores the position, which is tedious, error-prone and slow. What if the node isn’t there, or has been renamed, or if there are multiple? Something that should be trivial (looking up a value on an object) turns into a pile of error handling.

There’s also the matter of memory efficiency. Once I’d started using such pluggable components, it made sense to consistently use them for everything. Tracking the health of an entity? A node. The speed? A node. The current camera focus? Another node. Most of these nodes contain very little data; a few numbers, maybe 16 bytes at most. Some are just markers that don’t store any data at all. But a Godot node by itself is a pretty heavyweight object: it stores a name, parent and owner pointers, a list and a hash map of children, a hash map of signal connections, a list of groups, a bunch of flags, stuff related to networking… hundreds of bytes all together, and all that for storing a few bytes of data.

An alternative approach is to have these pluggable components as plain C# objects, and put these in an array or in individual fields directly on each object. This is what I’d been doing so far. But it was a weird hybrid between Godot node scripts and pluggable objects, and it started to grate on me. It was time to go all the way and turn this into an ECS.

The ECS

ECS stands for entity component system, and it’s a popular pattern in some game development circles. The concept is explained very well in many other places, so I won’t rehash that here. Suffice to say that I chose to write my own, because it’s so fundamental to my game that I’d like to have full control over its features and implementation. And, as long as you don’t need squeeze out every last drop of performance, it’s not all that hard; it took me about a week fulltime to develop and port the existing game code over.

Here’s what it does, in a nutshell. This is going to get rather technical and requires some knowledge of C# and Godot to follow, so if you’re just here for procedural generation and/or pretty pictures, feel free to tune out.

Entities are identified by 64-bit integers. Entity IDs are never reused, but 64 bits are enough to ensure that they won’t run out. Components can be any C# type, including structs and Godot nodes. The overarching World class stores each component in a separate hash map, keyed on entity ID.

Central to the World is an event bus. Events can be any C# type, and objects can subscribe to events of a particular type. Systems are classes that subscribe to one or more events, by implementing the IEventHandler<E> interface. The World itself fires events when components are added and removed. Note that systems don’t implement a dedicated Process(float delta) method called every tick; instead, there is a Process event that they can subscribe to.

Additionally, there are “resources”, which are singleton objects keyed on their type. My procedural generation services are added to the World as resources, so that systems can access them. There is a simple dependency injection mechanism based on reflection, whereby systems can request resources through their constructor. (The new primary constructors introduced last November in C# 12 are great for this!) The event bus and the World itself are also injectable in that way, to allow systems to send events and to create/destroy entities.

Systems typically affect entities in the world through queries, which are also injectable. They are represented by the IQuery<...> interface, where the ... indicates one or more components to query for. The IQuery interface extends IEnumerable, which lets the system iterate over all matching entities and components and manipulate them in whatever way needed.

Right now I’ve only implemented “and” queries, where all requested components must be present. The actual iteration is implemented in the World in a rather simple way: the hash map of the first component is iterated over in its entirety, and for each entry, the hash maps for the other requested component types are probed to see if they’re all present. (If this were a general-purpose library, I would at least iterate over the hash map of the rarest component instead of the first, which is more efficient. But because I’m writing both the ECS and the game, I know which component is rarest, and I just list that first.)

The upshot of all this is that I no longer have node spaghetti. Everything is beautifully decoupled, there is very little boilerplate, and I feel much more comfortable and secure adding new functionality. Here’s an annotated example:

// Class components are mutable, struct components are not, because
// I failed to find a way to return structs by reference instead of value.
// So these have to be classes.
class Position { public Vector3 Value; }
class Velocity { public Vector3 Value; }

// Using the primary constructor to inject the query.
// The World takes care of constructing it and passing it in.
class MovementSystem(IQuery<Position, Velocity> query) :
 IEventHandler<Process>
{
 public void Handle(Process processEvent) {
 foreach (var (position, velocity) in query) {
 position.Value += processEvent.Delta * velocity.Value;
 }
 }
}

// Add this to the world (somewhere in the main function).
world.AddSystem<MovementSystem>();
world.BuildEntity()
 .Add(new Position())
 .Add(new Velocity())
 .Done();

To integrate this ECS with Godot, I added a few special components and systems. There is the InTree component, which contains a Godot Node. The InTreeSystem listens for ComponentAdded<InTree> and ComponentRemoved<InTree> events, and adds/removes the corresponding node from the component into Godot’s node tree. Additionally, there is a generic system called NodeAddSystem<C> that takes a scene path in its constructor, and automatically instantiates that scene whenever a component of type C is added to an entity. The idea here is that I don’t want to store any data on Godot nodes directly, because nodes are difficult to save and load. Instead, data flows only one way: from components to nodes.

End of story

Okay, that’s enough talk about implementation details. I hope this makes it clear why I haven’t been posting any pretty pictures lately. I’ll try to make sure to have some more in the next post!

Around The World, Part 13: Zooming in

Mon, 25 Mar 2024 00:00:00 +0000

As mentioned in the previous post, the player will never see our procedurally generated world all at a glance. They’ll be much closer to it, and seeing only a small part at any given time. Let’s see how we can go from coarse, global world maps to something that will actually look good at close range!

Here’s a map of one of our generated worlds:

The map is based on a quad sphere with six faces of 512×512 pixels. At Earth scale, that works out to about 20×20 kilometers per pixel. (I’m not certain that my world will actually be Earth-sized, because it might be too much work to fill such a big planet with enough interesting content — but I want to keep that option open for now.)

How far can the player see? It depends how high above sea level they are: the higher up you are, the farther away the horizon is. Looking at some references, ships of the Age of Sail were no taller than 25 meters. We can then use this calculator to find that the horizon is about 20 km away. Taller objects like mountains and other ships can be seen beyond the horizon, and in theory Mount Everest could be seen from as far as 361 km away if it were on the coast, but I’ll settle for 50 km as an upper bound.

That means that the player could see about 2.5 “world pixels” in any direction — at best:

Clearly, the current world resolution is not quite enough!

Making a mesh of things

I haven’t settled on any particular art style yet, but it’s a safe bet that we’ll need a 3D mesh of the terrain. And if I settle on a low-poly style, it would be nice if that mesh looked good even if you can distinguish individual triangles.

The quad sphere is great for the generative algorithms and simulations I’ve been doing so far, because it lets us pretend that we’re working with squares. But a mesh that the GPU can render is made up of triangles instead. We can split each square into two triangles, but they would not be nice equilateral triangles, so the mesh would not look so beautiful.

Now it’s time to remember what I wrote previously:

But the subdivided icosahedron might make a comeback once we start building meshes!

Indeed, an icosahedron is made of 20 equilateral triangles, and we can subdivide each of these triangles recursively into smaller triangles to get an approximate sphere with almost exactly equilateral triangles:

Source: Wikimedia Commons by Tomruen, CC-BY-SA 4.0

GPU’s don’t much like individual triangles though; they like triangles in large batches. So instead of subdividing each face of the icosahedron into 4 triangles, we subdivide it into 64×64 triangles. At each corner, we interpolate the original quad sphere height map to get the height at that corner. This gives us our first approximation of a terrain mesh:

Clearly this is no better than what we had before. But the beauty of it is, that we can subdivide each face into 4 smaller triangles, and generate a 64×64 triangle mesh for each of those. And we can repeat this procedure indefinitely to get finer and finer meshes, as needed.

If we did that for the whole world, it would take far too much memory and computing power. So we generate meshes only for the part of the world that’s visible, at the proper subdivision level to make it look detailed enough. No matter how far we zoom in, the number of visible triangles, and therefore the amount of work that needs to be done, is more or less the same. Nice!

Now those chunky pixels from before resolve into something much smoother:

Whoops, that’s a little too smooth. That makes sense, because the original large-scale world map simply doesn’t have this amount of detail.

Adding fine details

What we need here is our trusty friend simplex noise to add some smaller features. Remember that this noise is added during the generation of meshes, so it doesn’t need to be computed for the whole world. The drawback is that we can’t easily use any fancy algorithms like erosion simulation, which require information from nearby points; each mesh vertex must be computable independently of all the others. So at this scale level, we’re limited to relatively simple algorithms.

The noise is scaled such that the largest (lowest frequency) octave is roughly the size of one pixel in the global world map. That gives us this:

That’s looking better already, but most coastlines end up looking like this instead:

Unlike the steep volcanic island we looked at above, this is a coastline with a much shallower slope, where the noise adds way too many small islands and inlets. This is because the noise amplitude is the same everywhere, but what looks good on mountains is way too rough for lowlands. In real life though, not all terrain is equally rough.

Modulating the noise

What we need is a system that adds more noise in areas where we’d expect rough terrain, such as mountainous areas, and less noise in smoother terrain like lowlands. We already have a system to add height based on tectonic forces, which is how we create mountain ranges, so let’s bolt it onto that. Let’s also add noise to hotspot volcanoes. Our previously messy coastline now looks much smoother and resolves into an isthmus:

Meanwhile, our hotspot volcano remains pleasingly rough:

The noise itself could be improved, though. Right now it’s just 4 octaves of simplex noise layered on top of each other. While working on the large-scale terrain, I noticed that ridge noise looks much better: the valleys between the ridges almost look like rivers, resembling the effect of hydraulic erosion (something we don’t simulate). Seen here at an angle to better show the relief:

Here I also lowered the frequency (increased the scale) of the noise to span several pixels in the world map. This seems to be better for tying those disparate pixels together.

On mountain ranges, the noise looks perhaps a bit too uniform:

Warping the domain of the ridge noise using three octaves of yet another simplex noise fixes this nicely, making the result look pleasingly irregular:

As you can see in the corners, there’s also something wrong with my calculation of the visible area. We seem to be missing some terrain meshes here. I’ll fix that later.

To wrap up this post, let’s add a simple water surface. The same subdivision algorithm is used as for the land, but I just apply a height of zero everywhere, and use a different material for rendering. When a triangle is entirely covered by land, we don’t need to generate any water mesh and vice versa, but if a triangle is only partly covered by water, we need to render both so we get nice sharp coastlines.

Some pretty islands:

An interesting-looking bay:

It’s obvious that more work is needed. For example, you can still see some artifacts of the underlying square grid, and the coastlines are much too smooth here. But we’re getting there!

Around The World, Part 12: 2D or not 2D

Tue, 19 Mar 2024 00:00:00 +0000

So far, I’ve been talking about generating a world at a very large scale for the game. But the aim of the game is exploration, so the player will rarely, if ever, get to see the entire planet at once. Which raises the question: what will the player see?

The game jam prototype that started it all looked like this:

Its visuals were designed to mimic the EGA era, with low resolution and a limited colour palette. A top-down two-dimensional view perfectly fit into that. Of course, it’s also easier to build, which made it the obvious choice for a 48-hour game jam.

However, this prototype took place on a rectangular map that wraps around at the left and right edges – essentially a cylinder. This made it possible to represent it as a grid of square tiles. The full game that I’m working on now will take place on an actual sphere, where such a thing is not possible.

Making it 2D?

I’ve thought long and hard if I could use some kind of hack to use an entirely flat 2D view in the new game as well. Then I could use pixel art, which is relatively quick to produce. If the player only sees a small part of the world at the same time, surely it’s possible to flatten that to a plane without too much distortion?

And yes, this is possible. But it’s not enough. Even if we have zero distortion at the player’s location, distortion inevitably increases towards the edges of the view. That’s still fine, except that the player can move towards these edges, and far beyond them. As the player moves further away from their starting point, distortion would inevitably increase. What should happen then?

One option is to reproject when the distortion becomes too large. At that moment, the center of the projection would again snap to the player’s position. This would lead to jarring jumps, where the entire world suddenly appears to change around the player. That’s clearly not awesome, and we want this game to be awesome, right?

I could try to hide those jumps in some artificial way, e.g. by showing a fullscreen end-of-day summary at the end of every in-game day. But I’m worried that this would interrupt the flow of the game.

To entirely get rid of these sudden jumps, we could instead reproject continuously. The location of the player is always used as the center of the projection, so it has zero distortion, and the edges of the view are never distorted too much. So now we have a system that, in real time, transforms a 3D scene into a 2D image. Does that sound familiar? At this point, we have essentially reinvented a 3D rendering engine.

Making it 3D?

After this realization, I wondered if I should go all-in and make the game fully 3D. After all, wouldn’t it be awesome if you viewed the world from a first-person perspective, standing on the deck of your ship and seeing a strip of long-awaited land appearing from the haze on the horizon? This would make the game much more immersive.

I have even been tinkering with this in another early prototype:

Sorry, your browser does not support embedded videos.

The prospect is extremely tempting even now, but I have to be realistic: I’m just one guy doing game design, coding and artwork, and I have neither the time nor the skills to model 3D objects to the detail needed to make this work.

Also, from a gameplay perspective, it might make the game very difficult: this third-person camera makes it very hard to match the shape of a coastline to what you see on a map. Of course navigators needed to deal with this in real life too, but they used a sextant to take painstaking measurements. Also, they could draw on years of experience and even then sometimes got it wrong. Not something I’d want to inflict on my players!

Middle ground

So we have to use 3D, but we don’t want a first or third person perspective. The sensible remaining option is to use a top-down perspective, but rendered using 3D meshes and models.

I was initially worried that this would look very bland and boring. You would just see the deck of the ship, with some narrow lines across it representing the beams and sails. Trees would look like circles, buildings would look like squares. Even 2D games from the previous century would rarely do this; rather, they would have some oblique perspective baked into their sprites:

SimCity Classic (1994)

Oddly, it wasn’t until I bought the newly released Pioneers of Pagonia, a real-time strategy game by the makers of the old Settlers games, that I saw the extremely obvious solution:

Pioneers of Pagonia, screenshot by the developers

The camera used in modern RTS games like this could work for me as well: a mostly top-down view, but with the camera tilted slightly from the vertical. This would show objects slightly from the side, giving a better sense of their shape, while still letting me get away with low-detail, low-poly 3D models because the camera never gets too close.

Also, it saves me from having to procedurally generate and render good-looking skies and clouds, which would be a rabbit hole that I would absolutely love to go down, but would keep me busy for months.

As a bonus, the circle of viewable area is squashed into a wide ellipse, better fitting the aspect ratio of a PC screen.

So, that’s what we’re working with. In the next post, let’s see what our generated worlds might look like from this perspective!