Generating new sectors on the fly

We need to update the world as the player moves through it. Right now, we only have a generate() method. While we could call it every time the player changes sector, we’d be wasting a lot of processing power, regenerating already present sectors.

Instead, we only want to generate sectors as needed. We will consider that the player moves along a given axis, either X or Y (or both), and generate an entire row or column of new sectors in that direction on the fly.

Procedural content generation can be so heavy that you don’t want to calculate what you don’t need. While I wouldn’t recommend optimizing a lot while prototyping, avoiding to regenerate the entire grid of sectors around the player continually is the kind of optimization you would need early on anyway. It doesn’t get in the way of the procedural generation code. So we thought we might as well show you how to implement it from the start.

The function that generates new sectors as the player moves should be on the parent WorldGenerator class because it will benefit all of the infinite procedural world generators.

We will add one method called _update_sectors() that will call another method twice, _update_along_axis(). This second method will walk along one axis and free or generate a row or column of sectors perpendicular to that axis.

For example, if the player moves to the right, we’ll add a new column of sectors on the grid’s rightmost and delete the leftmost column.

The _update_along_axis() function below works both for the X and the Y axes, so you have to wrap your head around the logic that makes it work for those two cases.

Open the WorldGenerator.gd script and add the following functions.

## Updates generated sectors around the player based on `difference`, a cell
## offset.
## The difference is in grid coordinates. It tells us which neighbor sector the player entered.
func _update_sectors(difference: Vector2) -> void:
    # We call `_update_along_axis()` twice, once for each axis.
    # The function returns if the `difference` is irrelevant.
    # But calling it twice would make the code work in the edge case the player moved
    # diagonally and we need to generate both a row and a column of sectors.
    _update_along_axis(AXIS_X, difference.x)
    _update_along_axis(AXIS_Y, difference.y)


## Travels along an axis and a direction, erasing sectors in the perpendicular axis that are too far
## away from the player and generating new sectors that come into this range.
func _update_along_axis(axis: int, difference: float) -> void:
    # If the player isn't moving along that axis, that is, if the `difference`
    # is `0`, we don't have anything to generate along that axis, and we return
    # early.
    if difference == 0 or (axis != AXIS_X and axis != AXIS_Y):
        return

    # We're going to use the `difference` argument in calculations below to determine the sectors to
    # generate and delete.
    # Depending on the direction the player is moving, we need to correct for the calculations
    # below.
    # When `difference` is positive, we end up in situations where sectors aren't erased or added on
    # time. This value is there to catch those cases.
    var axis_modifier := int(difference > 0)
    # We extract the `_current_sector`'s row or column depending on the axis we want to walk.
    var sector_axis_coordinate := _current_sector.x if axis == AXIS_X else _current_sector.y
    # We calculate the coordinate of the row or column of the new line of sectors to create.
    var new_sector_line_index := int(
        # Here, notice how we use `axis_modifier`. If the player is moving right or down, we need to
        # subtract `1` to the `_half_sector_count` to get the new sector's coordinate along that
        # axis.
        sector_axis_coordinate + (_half_sector_count - axis_modifier) * difference + difference
    )

    # We find the range of coordinates of the row or column *perpendicular* to the
    # axis we're updating.
    # We want to generate and delete new sectors in this range.
    var other_axis_position := _current_sector.y if axis == AXIS_X else _current_sector.x
    var other_axis_min := other_axis_position - _half_sector_count
    var other_axis_max := other_axis_position + _half_sector_count

    # We generate a new entire row or column perpendicular to the axis along which we're moving.
    # The values `new_sector_line_index` above and `other_axis_coordinate` together represent the
    # coordinates of a row or column of sectors.
    for other_axis_coordinate in range(other_axis_min, other_axis_max):
        var x := new_sector_line_index if axis == AXIS_X else other_axis_coordinate
        var y := other_axis_coordinate if axis == AXIS_X else new_sector_line_index
        _generate_sector(x, y)

    # We then want to delete the row or column on the opposite end of the grid.
    # To do so, we calculate the corresponding line of sector's coordinate along the axis we're walking.
    var obsolete_sector_line_index := int(new_sector_line_index + sector_axis_count * -difference)

    # We erase the entire row or column that's farthest from the player.
    for other_axis_coordinate in range(other_axis_min, other_axis_max):
        # We first calculate each sector's coordinates as a Vector2 as that's how we indexed them in
        # the `_sectors` dictionary.
        var key := Vector2(
            obsolete_sector_line_index if axis == AXIS_X else other_axis_coordinate,
            other_axis_coordinate if axis == AXIS_X else obsolete_sector_line_index
        )

        # We free all asteroids in this sector and remove the corresponding key.
        if _sectors.has(key):
            var sector_data: Array = _sectors[key]
            for d in sector_data:
                d.queue_free()
            var _found := _sectors.erase(key)

    # And now we're done updating the world, we update the `_current_sector`.
    if axis == AXIS_X:
        _current_sector.x += difference
    else:
        _current_sector.y += difference

Next, we need to update the WhiteNoiseGenerator class. We will track the player’s position and, if they move too far away from the current sector, call _update_sectors() and update the grid position.

We’ll do this in _physics_process(). Open WhiteNoiseGenerator.gd and add the following code to it.

onready var _player := $Player

# We use the physics process function to track where the player is in the world
# and generate new sectors as they move away from existing ones.
func _physics_process(_delta: float) -> void:
    # Every frame, we compare the player's position to the current sector. If
    # they move far enough from it, we need to update the world.
    var sector_location := _current_sector * sector_size
    if _player.global_position.distance_squared_to(sector_location) > _total_sector_count:
        # Our function to update the sectors takes a vector to offset. As the
        # _player can be moving left, right, up, or down, we store that
        # information in our sector_offset variable.
        var sector_offset := Vector2.ZERO
        sector_offset = (_player.global_position - sector_location) / sector_size
        sector_offset.x = int(sector_offset.x)
        sector_offset.y = int(sector_offset.y)

        _update_sectors(sector_offset)
        # We also update the grid position to encompass the active sectors. We
        # don't need to redraw the grid, so we move it using the provided
        # function.
        _grid_drawer.move_grid_to(_current_sector)

Above, we calculated the squared distance between the player’s position and the sector. Doing so is faster than using the Vector2.distance_to() method.

This is because the distance between two points a and b is sqrt(pow(b.x - a.x, 2) + pow(b.y - a.y, 2)). Calculating the square root of a number is computationally intensive. If we calculate the squared distance, we remove the square root, and the calculation becomes much faster. It may not matter in a small game, but if you need to calculate distances often, you’ll want to compare squared distances.

With those changes, if you try the game again and keep moving, you will notice that new sectors keep appearing: the world never ends.

With that, you already have your first infinite world, even though it’s a bit simple. But you have the foundations in place already and can build upon them.

In the next part, we’ll work on the blue noise generator.

Code reference

Here are the complete WorldGenerator and WhiteNoiseWorldGenerator scripts.

Starting with WorldGenerator.gd.

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


func _update_sectors(difference: Vector2) -> void:
    _update_along_axis(AXIS_X, difference.x)
    _update_along_axis(AXIS_Y, difference.y)


func _update_along_axis(axis: int, difference: float) -> void:
    if difference == 0 or (axis != AXIS_X and axis != AXIS_Y):
        return

    var axis_modifier := int(difference > 0)
    var sector_axis_coordinate := _current_sector.x if axis == AXIS_X else _current_sector.y
    var new_sector_line_index := int(
        sector_axis_coordinate + (_half_sector_count - axis_modifier) * difference + difference
    )

    var other_axis_position := _current_sector.y if axis == AXIS_X else _current_sector.x
    var other_axis_min := other_axis_position - _half_sector_count
    var other_axis_max := other_axis_position + _half_sector_count

    for other_axis_coordinate in range(other_axis_min, other_axis_max):
        var x := new_sector_line_index if axis == AXIS_X else other_axis_coordinate
        var y := other_axis_coordinate if axis == AXIS_X else new_sector_line_index
        _generate_sector(x, y)

    var obsolete_sector_line_index := int(new_sector_line_index + sector_axis_count * -difference)

    for other_axis_coordinate in range(other_axis_min, other_axis_max):
        var key := Vector2(
            obsolete_sector_line_index if axis == AXIS_X else other_axis_coordinate,
            other_axis_coordinate if axis == AXIS_X else obsolete_sector_line_index
        )

        if _sectors.has(key):
            var sector_data: Array = _sectors[key]
            for d in sector_data:
                d.queue_free()
            var _found := _sectors.erase(key)

    if axis == AXIS_X:
        _current_sector.x += difference
    else:
        _current_sector.y += difference

And WhiteNoiseWorldGenerator.gd.

class_name WhiteNoiseWorldGenerator
extends WorldGenerator

export var Asteroid: PackedScene
export var asteroid_density := 3

onready var _grid_drawer := $GridDrawer
onready var _player := $Player


func _ready() -> void:
    generate()
    _grid_drawer.setup(sector_size, sector_axis_count)


func _physics_process(_delta: float) -> void:
    var sector_location := _current_sector * sector_size
    if _player.global_position.distance_squared_to(sector_location) > _total_sector_count:
        var sector_offset := Vector2.ZERO
        sector_offset = (_player.global_position - sector_location) / sector_size
        sector_offset.x = int(sector_offset.x)
        sector_offset.y = int(sector_offset.y)

        _update_sectors(sector_offset)
        _grid_drawer.move_grid_to(_current_sector)


func _generate_sector(x_id: int, y_id: int) -> void:
    _rng.seed = make_seed_for(x_id, y_id)

    var sector_data := []
    for _i in range(asteroid_density):
        var asteroid := Asteroid.instance()
        add_child(asteroid)

        asteroid.position = _generate_random_position(x_id, y_id)
        asteroid.rotation = _rng.randf_range(-PI, PI)
        asteroid.scale *= _rng.randf_range(0.2, 1.0)
        sector_data.append(asteroid)

    _sectors[Vector2(x_id, y_id)] = sector_data


func _generate_random_position(x_id: int, y_id: int) -> Vector2:
    var sector_position = Vector2(x_id * sector_size, y_id * sector_size)
    var sector_top_left = Vector2(
        sector_position.x - _half_sector_size, sector_position.y - _half_sector_size
    )
    var sector_bottom_right = Vector2(
        sector_position.x + _half_sector_size, sector_position.y + _half_sector_size
    )

    return Vector2(
        _rng.randf_range(sector_top_left.x, sector_bottom_right.x),
        _rng.randf_range(sector_top_left.y, sector_bottom_right.y)
    )