World Generation And You

I am super happy with Revision 40, and how it turned out. We have had only one reported Windows crash that was a true crash, apparently due to very elderly AMD drivers, and a couple of OS X issues (apparently in the OpenGL driver stack for OS X.) The new problem we have, of course, is that people are now able to produce very large colonies. Consequently, we have had some issues where certain parts of the game (stockpile management, work crew menu, jobs menu) start freezing up under the strain. The new UI code that Daniel has been diligently working on should help fix the problems with the job and work crew menus; this has necessitated a complete rewrite of how UI widgets are resized, a job that is labour intensive, gross, and involves rewriting code that I first wrote back in 2001 or so. Still, I’m very happy with Revision 40. So happy, in fact, I took a tiny vacation for… well, for the first time I can remember. It was really, really weird.

Above: artistic depiction of Nicholas' vacation based on description provided.

Above: artistic depiction of Nicholas’ vacation based on description provided.

For Revision 41, we’ve basically gotten two messages. First, there is a large portion of the populace who want to see us doing more work like we did (from a technical side) in revision 40 – continuing to build on and refine the features that are in the game right now, and fixing long-standing issues with things like military units and stockpiles. There is an equally large portion of the populace, some of whom also belong to the first portion, who are desperately after new content. From the perspective of a game developer, you have to push on with new content in early access because, otherwise, it never gets done. Plus, there is a feature cost. The sooner you get a feature started, the easier it is to retrofit the existing code to support the feature.

So, we’re going to try to find a balance for this patch: cleaning up a bunch more outstanding issues, now that stability seems to be taken care of, while also trying to finish more of the systems that need to be done in order for us to get the game done. There are two big, BIG technology pieces that need to go in right now that don’t exist yet, and which we need to deal with with some degree of urgency because the cost of retrofitting the game to support them gets increasingly higher as we continue development. The first of these is multiplayer, which I’m not working on right now. The second one of these is the global world, because – let’s face it – we’ve all colonized New Antipodea and New Sogwood a million times right now, and it’s time to go fail Make The Empire Proud somewhere else!

The overworld in Clockwork Empires needs to do two things:

1. Provide the player with new physical geography to explore – new physical regions, new layouts, new surprises and new mechanisms for generating the surprises. This means also getting a lot of the other biomes in, and our stockpiles of strange and peculiar assets finally placed in game.

2. Provide the player with a way of tracking their global progress in the world from game to game – old colony sites and games that occurred in old colony sites should affect the formation of new colony sites. (“Upfish Soup, who recently survived the collapse of the Old Mushroomhood Colony, has made his way to New Mushroomhood to try and make his fortune.”)

After a couple of days of hacking, I have a working draft of an overworld. The basic operation we use for world generation is the method outlined by Amit Patel here which I believe is also used in Realm of the Mad God. Basically, we generate a bunch of Perlin noise, and we generate a bunch of Voronoi diagrams (a Voronoi diagram, in layman’s terms, starts with a list of points; it then computes, for every point in space, the closest point in your list to that point and partitions space up that way).

We start by generating a large Voronoi diagram for the continents. For a Clockwork Empires map, which is currently 2048 x 2048, we generate a “continental plate” Voronoi diagram with 250 cells on it, and then assign a Perlin noise height value to each of those cells. That indicates whether a plate is above, or below, water. Since Perlin noise is continuous, you get fairly nice smooth islands. To get the world looking how we want to look – after all, the Empire considers itself the center of the world and I see no reason to disappoint it – we have to ensure we generate a large body of water in the center of the world where we will eventually place the Empire. (You can’t set up a new colony on the Empire, for the secrets of the home country are not to be revealed in this particular video game.) Multiplying a second map of Perlin noise, with a fairly high frequency, by these two maps determines whether a given pixel is above, or below, water. This generates an ocean map:

The Ocean Doesn't Want Me TodayWe may also end up with some lakes in the process:

(lakes(Note that these lakes are, quite often, too big; we also shouldn’t let the continential plate affect lake size. So, probably, they should be drawn on top of the existing map using a new Perlin noise pass – but this is a small improvement and it will get sorted out later.)

Our existing biome code expects a number of Voronoi cells as an input; it will then subdivide those Voronoi cells into more interesting things in its own code. We therefore sprinkle 32,000 points across the map, and compute another Voronoi diagram. We then perform two passes of Lloyd Relaxation – we figure out where the center of the Voronoi cell is, and then compute a new Voronoi diagram using that new center as the Voronoi point position. We then sample the ocean map at these points, which has the added benefit of cleaning up those weird lines you see all over the place where a continent edge dominates everything. We then assign biomes based on three things: elevation (defined as “distance from the coast”, which is sort of a hacky metric and is computed using the civilization map code), moisture (defined as “distance from a lake”), and temperature (“distance from the equator.”) This produces our final output (click to enlarge):

terrain_colored_2

There are still a bunch of things we need to do here to tweak the algorithm. You will see, for instance, a couple of lakes outside of beaches, and one absolutely enormous body of water that dominates the southernmost continent. In nature, lakes aren’t actually this large. Still, it looks pretty good for a first pass. The colors are also not final, and were picked by me largely at random (This is why they include such things as the color (0, 255, 255), affectionately known as the Programmer’s Special.) When you select an embark region, you get to scroll around this map and pick a subregion that appeals to you.

We also need to get the map rendering in the correct style again, which is somewhat of an open problem we have yet to sort out.

We also need to add volcanos, because we promised this in a PC Gamer Interview in 2012. Foolishly, I might add.

Here’s another sample generated world:

terrain_colored_anotherone

This one nicely shows off temperature variation. At the bottom of the map, you can see cold areas appearing, whereas there are many exciting deserts located in areas far away from moisture sources.

Eventually, we hope to have other things on the world map such as tracking the influence of other nations, and the causes of your failures, on the world state. If a colony falls to Fishpeople, for instance, it should expand the Fishpeople Influence on the world map.

The second part of this ticket is the maintenance of a global world history, and global world objects. However, we’ll save that for another blog post. I’m not totally sure if this will be in the first experimental build of the Revision 40A stream, and in what form – we’re certainly not going to have all of the new biomes done in short order, so they will probably default to the traditional Antipodean biomes while we start hooking up textures and writing fun new generators and content for areas.

7 Comments

7 Responses to “World Generation And You”

  1. Roshirai says:

    Super exciting! I’ve been waiting for the overworld for quite a while now. 🙂

    { reply }
  2. MailersMate says:

    (awesome) I was wondering when we would start seeing the world map develop

    { reply }
  3. Professorial says:

    what about the koppen classification system?

    { reply }
  4. Unforked says:

    That 2012 PC Gamer interview cemented my interest in the game. I remember thinking how insane you guys must have been for even attempting a game this ambitious. And now its happening!

    I guess the only thing you mentioned then that won’t be in the game is the “urchins”, and I understand the reasoning behind it.

    { reply }
  5. Rob Rendell says:

    Shouldn’t moisture be defined as distance from lake *or ocean*, rather than just lake? You’re already calculating distance to the ocean for elevation, so it would be easy to implement and see how it looked.

    I know that would make moisture directly proportional to elevation when a long way from any lakes, but you lakes seem frequent enough that it doesn’t seem like it would be a problem.

    { reply }
  6. Samut says:

    If you follow the Amit Patel link (and it’s a great read BTW), it determines moisture by distance from fresh water, i.e. lakes. Presumably Gaslamp is following the same rule.

    There is another step mentioned, where wind is calculated to bring moisture in from oceans until it encounters high elevations. That might be something to consider as well.

    { reply }

Leave a Reply

Your email address will not be published. Required fields are marked *