World generation in Around The World 0

thomastc • 3 years ago on 10th Alakajam! entry  Around The World

"But thomastc, how is the procedural world in your latest Alakajam entry generated?" asked no-one ever. But since you're here, I might as well tell you. 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.

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.

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

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.

That's it for the map. 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 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.

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

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 game if you haven't already!

Comments (0)

Login to comment