In this lesson, we will build our infinite world generator’s foundations. We will code a virtual base class that each of our world generators will extend.
This base class defines the shared properties and functions to generate and store data regarding the world’s sectors around the player.
The biggest challenge with infinite worlds probably has to do with the computer’s resources.
In other tutorial series, we generated entire levels at once. However, here, our world is infinite. And we can’t generate an endless amount of data on a computer with finite processing power and memory.
Instead, we have to generate a small portion of the world at a time. Because memory is finite, if the player moves far enough, we have to free some of the generated entities to make space for new chunks of the map.
Here’s a solution to this problem. We’ll split the world into a grid and generate or free grid cells on the fly as the player explores the environment.
With such a grid, you can keep using all sorts of generation algorithms, including those you learned in previous chapters.
At least, as long as they’re deterministic. That is to say, if given the same input seed value, they always generate the same patterns. That’s because the player can move away from an area and come back to it later. When that happens, the area gets unloaded and re-generated. And the algorithm should generate it the same way as before.
In this series, we’ve chosen to set the game in space and introduce new techniques like noise generators. These techniques apply to any kind of procedural generation.
Here is how we will make the infinite world algorithm work:
The last point is about performance optimization. We will only generate a handful of sectors at a time to avoid slowing down the game. As we generate a limited number of entities in the demo, the algorithm’s performance shouldn’t be an issue. However, as you add layers and rules to your algorithms, they require more processing power. The easiest way to limit the performance cost is to only generate what you need as the player moves.
We’ll look at the function that helps us lazily generate and free chunks of the world after implementing our first procedural world, in two lessons.
Open a copy of the start project if you haven’t already done so, and create a new script named WorldGenerator.gd. It’s a base class that’ll define some features all of our infinite world generators will build upon.
We start with the class definition and some properties. We need some variables to store the size of sectors, the number of sectors we want to generate around the player, and more.
## Abstract base class for worlds. ## ## Splits the world into `sectors` of a fixed size in pixels. You can think of ## the world as a grid of square sectors. ## Exposes functions for extended classes to use, though the central part is the ## `_generate_sector()` virtual method. This is where you should generate the ## content of individual sectors. class_name WorldGenerator extends Node2D ## When the player moves around the world, we generate sectors only in the ## direction they are moving. And to do so, we think in term of the axis the ## player Is moving along. These two constants represent the X and Y axes ## respectively. enum { AXIS_X, AXIS_Y } ## Size of a sector in pixels. export var sector_size := 1000.0 ## Number of sectors to generate around the player on a given axis. export var sector_axis_count := 10 ## Seed to generate the world. We will use a hash function to convert it to a ## unique number for each sector. See the `make_seed_for()` function below. ## This technique makes the world generation deterministic. export var start_seed := "world_generation" ## This dictionary will store the generated world data for every active sector. ## You can use var _sectors := {} ## Coordinates of the sector the player currently is in. We use it to generate ## sectors around the player. var _current_sector := Vector2.ZERO ## There are some built-in functions in GDScript to generate random numbers, but ## the random number generator allows us to use a specific seed and provides ## more methods, which is useful for procedural generation. var _rng := RandomNumberGenerator.new() ## We will reuse the three values below several times so we pre-calculate them. ## They all relate to sectors and help us define and process our world's grid. ## Half of `sector_size`. onready var _half_sector_size := sector_size / 2.0 ## Total number of sectors to generate around the player. onready var _total_sector_count := sector_size * sector_size ## And this is half of `_total_sector_count`. onready var _half_sector_count := int(sector_axis_count / 2.0)
Next, we define the base functions to generate the world. We’ll run the generate() method below once upon loading the world. This method delegates the work to _generate_sector(), a virtual method where we’ll implement various procedural generation algorithms in the next lessons.
## Generates the world from scratch around the player. ## Calls `_generate_sector()` below for each sector in a grid around the player. func generate() -> void: # We loop over each cell in a grid of size `_total_sector_count` centered on the player. for x in range(-_half_sector_count, _half_sector_count): for y in range(-_half_sector_count, _half_sector_count): _generate_sector(x, y) ## Virtual function that governs how we should generate a given sector based on ## its position in the infinite grid. func _generate_sector(_x_id: int, _y_id: int) -> void: pass
We want to code our world generation algorithm in a deterministic way: when the player returns to a given location, the sector gets generated the same way.
Computers don’t generate truly random numbers. Instead, they produce pseudo-random ones starting with a seed, a root number from which they calculate a sequence of numbers that feel random.
Thanks to this, if we give the program the same seed, we always get the same sequence of numbers in return.
Now, we can’t have only one seed for the entire world: if the player explores far from the starting point, saves, and loads the game again, using the same seed could effectively re-spawn the player at the center of the universe; or recenter the universe around them, depending on how you frame the issue.
A solution to this problem is to generate unique seeds for different parts of the world. And as we’re already looking to split our world into sectors, we’ll generate a unique seed based on their coordinates. That way, each sector will have its unique sequence of pseudo-random numbers and always generate the same way.
To do so, we write a function that produces the same seed given the same input parameters. We start from our start_seed and build a string that includes the sector’s coordinates. Then, we use the String.hash() method to convert it to a unique integer.
## Creates a text string for the seed with the format "seed_x_y" and uses the ## hash method to turn it into an integer. ## This allows us to use it with the `RandomNumberGenerator.seed` property. func make_seed_for(_x_id: int, _y_id: int, custom_data := "") -> int: # We build a string with three templates separated by underscores and use # string formatting to populate them. var new_seed := "%s_%s_%s" % [start_seed, _x_id, _y_id] # We'll use the `custom_data` when we get to the layered world generator. # It'll allow us to add a third dimension of information to the seed: the current layer. if not custom_data.empty(): new_seed = "%s_%s" % [new_seed, custom_data] return new_seed.hash()
Here’s the WorldGenerator.gd script so far, without the comments.
class_name WorldGenerator extends Node2D enum { AXIS_X, AXIS_Y } export var sector_size := 1000.0 export var sector_axis_count := 10 export var start_seed := "world_generation" var _sectors := {} var _current_sector := Vector2.ZERO var _rng := RandomNumberGenerator.new() onready var _half_sector_size := sector_size / 2.0 onready var _total_sector_count := sector_size * sector_size onready var _half_sector_count := int(sector_axis_count / 2.0) func generate() -> void: for x in range(-_half_sector_count, _half_sector_count): for y in range(-_half_sector_count, _half_sector_count): _generate_sector(x, y) func _generate_sector(_x_id: int, _y_id: int) -> void: pass func make_seed_for(_x_id: int, _y_id: int, custom_data := "") -> int: var new_seed := "%s_%s_%s" % [start_seed, _x_id, _y_id] if not custom_data.empty(): new_seed = "%s_%s" % [new_seed, custom_data] return new_seed.hash()