Open Worlds

Open-world games are great, like World of Warcraft and Grand Theft Auto 5, where exploration is as entertaining as the quests/missions. The main disappointment with these two games is that the worlds have boundaries; a traveler continually moving east will eventually hit a boundary, instead of returning to the start position like a real planet. What would be involved with creating virtual worlds without these boundaries?

A Visual Demo

Below is an interactive visual guide of the processes to be explained in this blog post. It begins with a single, blank Chunk which is then assigned height values that correspond to colors. In the next steps the neighboring Chunks are discovered and eventually the entire world is assembled.

Considerations

There are several concerns that present themselves when attempting to solve this challenge -

  • loading a very large world entirely into memory may not be reasonable, the size of the world could be limited by the available memory
  • creating a very large world by hand would be a bottleneck in development, designing every world by hand would limit the number of projects a developer could work on
  • one world per game might not be enough, game design might require an entire universe of many worlds and that they be dynamically generated
  • for multiplayer games, transferring planet data over the network could be very expensive for large worlds
  • the worlds should be interesting, they should have geographic features such as seas, beaches, plains and mountains

There are several resources on the web that describe ways to procedurally generate terrains using methods such as Perlin noise but these approaches are not suitable for the constraints described here. Perlin noise methods don't readily stitch together at the edges; they do a great job of generating heightmaps but stitching them together requires the extra work of interpolating with at least 3 other heightmaps. Subsections of the world should be queryable without computing neighboring subsections.

This blog post describes an algorithm that may be suitable to solving these problems. The methods described are not suitable for all games, they will not have the diversity and minute details found in worlds designed by hand; this should be considered as a starting point and that other concepts will likely need to be added.

Described below are the attributes of this design -

  • a world is generated using a numeric value, the seed. This is very useful in networked games, as a world can be reproduced on all clients by transferring only the seed value
  • a Pseudorandom Number Generator is used to generate a repeatable sequence of values
  • a world has a height and width, it is not infinite
  • the world is divided into chunks that can be requested individually without loading the entire world or neighboring chunks
  • chunks are created with x/y position, width and height, and corner values. The rest of the cells in the chunk are defined with bilinear interpolation
  • bicubic interpolation is used to stitch these chunks together to form the entire world
  • the world is not a sphere, it is a 2 dimensional plane that would map to a torus if it were to be to projected as a 3D structure. This can be an advantage to 2D games that have minimaps as it will not suffer from distortion as a spherical map would

In the end, the generated data is just a heightmap. These heights are used to describe individual tiles and determine if they will be a part of an ocean, beach or mountain.

Linear Interpolation

At the heart of this is method is linear interpolation. It's useful for generating intermediate values between two heights. Below is a visual demonstration of this concept, the left and right cell colors are provided and the 3 values in between are computed. The colors can be changed to observe how intermediate values are derived.

Linear interpolation is 1-dimensional and not readily useful for creating worlds, two dimensions are required for practical use.

Bilinear Interpolation

Individual chunks are 2-dimensional arrays and are created by defining their height and width and providing the height values of their four corner edges. These four heights are generated using a seed value and their x/y coordinates in the world. In this way corner values are generated in a deterministic manner without computing neighboring chunks. Once the corner values are defined, intermediate tile heights are discovered by using bilinear interpolation, creating a sequence of heights that ease between corner values.

Bicubic Interpolation

Once the chunks are generated, they must be stitched together to form the world. Neighboring chunks are generated using their x/y coordinates, allowing them to be independent of their neighbors. Every chunk has a neighbor, there are no edges to the world.

Below is a demo of a simple world created using this method. Determining sea and land is a simple matter of comparing the height to a cutoff value, anything below it is sea. The edges of the map also align with each other.

See it in action

This is a very simple and small world created in a 3D environment. Moving through the world is possible using the mouse. Observe that moving continually in a direction will lead back to the starting location.

Here's a spherical world that uses the same pattern generator.

Another example in 2D, a simple game that has been developed which uses this method.


Update June 12, 2016 - Added the terrain-generator pen near the top of the post to help readers get an idea of how the process works, in a visual way.

Update June 26, 2016 - Replaced previously added pen with terrain-generator-css which uses CSS transitions and seems to be slightly faster on some computers.

Update June 29, 2016 - Again, replaced previous pen, this time with terrain-generator-canvas which uses Canvas and is much smoother.