Building an Infinite World, Part 1

April 19th, 2015 - No Comments

An idea that was kicking around in my head, going back as far as a few years ago while I was still working at Rancon, was the idea of a empire game with an infinite world to explore.

Rather than be a traditional 4X game where you have a world pre-generated for you and a selection of AI to fight over, you would start with your city in the middle of a country, and gradually unveil the fog of war. Ever increasingly stronger barbarians would spawn outside of your explored borders, beating a path to your cities, forcing you to construct additional cities to bulwark your empire, advance your technology, and fight onwards out from there.

After ProcJam last year I started kicking about ideas for world generators again, and after playing a lot of Endless Legend and Civilization: Beyond Earth, I’ve found myself thinking about this nascent project more and more. So with some time spare and a burning need to reacquaint myself with Unity, I figure I should get to building it.

Ground Rules

Hardest task on this list is I need to build an infinite world generator. So, first I need to outline a specification on what I’m trying to generate.

  • The idea that you’re taking over a world one country at a time means we’ll want to generate non-uniform shapes to use as Regions. A region I envisage being the size of… oh let’s say Skyrim, or Stranglethorn Vale, or any arbitrary interesting, large location made up of multiple settlements, an expanse of wilderness and a predominant climate. As the player explores the map (through whatever means… explorer units they control, their own avatar, whatever), new regions are created as a player leaves the edge of whatever has been currently generated.
  • We’ll spit everything out onto a Hexagonal Grid. Because I want to build a game with Hexes. This one may well be just due to playing Endless Legend a lot, but hexagons are popping up more often in 4X games. Ideally however, I’d like to make something that 80% of it can be taken and put into any kind of system; square grid based, hex based or even a non-gridded structure.
  • Since we’re in 3d thanks to Unity, let’s go the whole hog and make use of that third dimension. We’ll assign our normally two dimensional hex grid a discrete height value for each of their hexes; and for pathfinding purposes you can travel from one hex to another if it’s the same height, or within one of the current height. We’ll assume you can’t go *under* a hex, as cool as that would be
  • Regions will be bordered either by impassible mountains, oceans, or by other regions; the aim will be to make these mostly impassible borders the norm so that the player has the opportunity to set up choke points to defend each area.
  • Then we’ll set out to make each region pretty. Assign it a climate, some sensible rivers, villages, pre-existing castles, dragons.
  • I should be able to scale the output of the engine down so that it *could* run on a device of my choosing. This one is a low priority, but having this compile on my now aging iPad3 would be a feather in my cap.

There’s a bit of research that’s been done on these infinite worlds, and a few publicly available papers on the topic. Foremost resource for generating pretty continents these days is from the systems programmer of Realm of the Mad God’s Amit P, who’s written up a comprehensive guide to building a procedural island using Voronoi Diagrams that forms the jumping off point for my build. With Amit’s implementation, however, I would be limited to islands with mountains in the middle; I’m aiming for something a bit less orthodox.

Time for a ground up implementation then…

Chunking Out a Region

Lets presume that, for however many hexagons I plan to pack into a region, a fixed number in a square (let’s say, for arguments sake an 8×8 square of 64 hexagons) forms a Chunk (Minecraft has certainly given us a very fixed lexicon on how we describe our world generation). This chunking will come in useful later when it comes to rendering batches of 64 hexagons at a time, but can also serve as a prime unit as our “minimum region size”. Ideally, a single chunk region would be representative of a small county, while a region with thirty to forty of these squares will be our pre-ordained ideal Skyrim sized space to roam about in.

Sixty four hexagons arrayed in an 8x8 grid; a Chunk

This is a Chunk of hexes. They took me an inordinately long time to make due to unfamiliarity with Maya LT and (for reasons in a later blog post) had to be done thirteen times.

These chunks then become a building block for plotting out a region; at any given border, a region can be started, and grown out from there one chunk at a time to an arbitrary size. The method I eventually chose to build these regions out with was a variation on a Koch Snowflake (specifically, the Quadflake);

  1. Start at a given point y on the grid (normally where we’ve just entered), a direction (top, left, right, bottom, or from the center), and an arbitrary value n based on the rough size of the region we want to build.
  2. Grow a rectangle out from point y of width and height n in the given direction. Fill each integer point on this rectangle with a Chunk.
  3. Identify the top, left, right and bottom edges of these rectangles. For any given point z on these edges that is not already making contact with a pre-existing chunk, repeat steps 1 through 3 from point z with n -1, until n = 0, in the relevant direction.
  4. Bundle all the Chunks created in this fashion, and declare it as a new region.
  5. For any area of space on the edge of the region bounded either at the corner or edge by five or more chunks, add this “orphaned” area as a new Chunk to the region. This will reduce the number of 1 x 1 regions eventually built by smoothing out the region perimeters
Koch Snowflake demonstration diagram

An example of the recursive function used to define regions (where number of recursions, in this case, was 3); the algorithm runs from red to blue, extending a new square from each edge recursively (from top clockwise to left). Purple chunks were added in as the “orphaned” cels with five or more existing neighbours

This is all so far, so good… if all we wanted was a uniform series of squares on a grid. Next post, we’ll be looking at splitting these regions up with some Voronoi diagrams…

  Work  

Leave a Reply

Name

E-Mail