We are going to take our noise generation one step further using blue noise.
As we discussed in the course’s introduction, blue noise is a white noise from which you removed the low frequencies. In other words, it’s a sequence of numbers where you favor a large distance between two values in the random series, leading, in our case, to spacing objects more or less evenly. It tends to produce a uniform distribution for positions.
As mentioned in the introduction to noise, the way we think of the different kinds of noises is loose. There is not a canonical algorithm for red or blue noise. Instead, what we are really interested in is how the result looks.
Here, we want our distribution of asteroids to be more uniform and predictable on the map.
We will use a relatively simple algorithm to do so. It has a linear complexity: O(n), meaning that the processing cost scales linearly with the number of generated asteroids.
Another typical and relatively fast algorithm that leads to predictable results is Poisson disk sampling. Its math may be a little more complicated than what we have here, and the algorithm’s probably a bit heavier as it relies on trigonometry. On the flip-side, you can use it to fill arbitrary shapes, like circles and over polygons. Ours works with a grid.
Image courtesy of Jason Davies: Poisson-Disc Sampling generator.
Our blue noise algorithm works like so:
The grid we want to generate, with the margins in question, looks like this.
In purple, you have the sector’s margin, and in dark blue the subsectors. The light blue area represents all the subsectors’ margins merged together.
Let’s duplicate our WhiteNoiseWorldGenerator.tscn scene. The duplicate’s name should be BlueNoiseWorldGenerator.tscn. Open the scene and rename the root node to BlueNoiseWorldGenerator too.
Remove its attached script and attach a new blank script to it.
Let’s open the BlueNoiseWorldGenerator.gd script and get coding.
We use the same code as before to update sectors as the player moves. You can copy the _ready() and _physics_process() functions from WhiteNoiseWorldGenerator.gd (or below).
## Generates a world full of asteroids using blue noise: a noise that is padded ## out so that asteroids are not pushed up against one another but are still in ## random positions inside their sectors. class_name BlueNoiseWorldGenerator extends WorldGenerator export var Asteroid: PackedScene ## The number of asteroids to generate inside of any sector. Affects the number ## of sub-sectors to split the overall sector. For example, a value of 3 will ## split the sector into a 2x2 grid. export var asteroid_density := 3 # From there, the code is the same as in `WhiteNoiseWorldGenerator`. We copy the `_ready()` and `_physics_process()` methods. 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_offset := Vector2.ZERO var sector_location := _current_sector * sector_size if _player.global_position.distance_squared_to(sector_location) > _total_sector_count: 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)
Like before, we need to assign the Asteroid.tscn file to the BlueNoiseWorldGenerator node.
As explained above, we want to split our sector into a subgrid and place asteroids inside of subcells.
We also want the cells to have some margin so asteroids don’t get too close to one another. The higher the margin, the more the asteroids will align, and vice versa.
We define two new exported variables and precalculate the subgrid’s size and several other values, as they don’t change after starting the game.
## We want to add a margin around the sector's border based on this proportion. ## We multiply the sector size by this value to calculate the margin. export var sector_margin_proportion := 0.1 ## We also apply a margin to the subsectors. So we will split the sector into a ## sub-grid, and each cell in this grid will see this margin apply to it. export var subsector_margin_proportion := 0.1 # We generate a sub-grid based on the closest square number that is greater than # `asteroid_density`. # For example, if we want to generate `3` asteroids, we need a 2x2 grid (`3` # cells). If we want `7` asteroids, the grid should be 3x3 (`9` cells). The # calculation below allows us to find that grid size. onready var _subsector_grid_width: int = ceil(sqrt(asteroid_density)) onready var _subsector_count := _subsector_grid_width * _subsector_grid_width # Like before, the values below are ones we will reuse in our procedural # generator, so we precalculate them. # Saving the result of calculations like this saves you a little bit of # performance and can be beneficial when you start to have big loops, as is the # case in procedural content generation. # Here, we calculate the sector and subsector margins, as well as the subsector # size without and with the margin applied. onready var _sector_margin := sector_size * sector_margin_proportion ## The subsector's size before subtracting its margins. onready var _subsector_base_size := (sector_size - _sector_margin * 2) / _subsector_grid_width onready var _subsector_margin := _subsector_base_size * subsector_margin_proportion ## The subsector's final size, with the margin applied. onready var _subsector_size := _subsector_base_size - _subsector_margin * 2
Here is the heart of the generator, the _generate_sector() function.
## Splits the sector into x subsectors with some padding and generates x ## asteroids, picking a new random subsector each time. This results in a ## 'filtered' generation that prevents asteroids from spawning too close to the ## edges or each other. func _generate_sector(x_id: int, y_id: int) -> void: # Like before, we generate a unique seed for the current sector and reset the number series. # Doing so keeps our generation deterministic. _rng.seed = make_seed_for(x_id, y_id) # We use the same seed for the global GDScript random number generator. # This affects the Array.shuffle() method we use below. seed(_rng.seed) # We find the top-left of the sector in world coordinates and apply the sector's margin. var sector_top_left := Vector2( x_id * sector_size - _half_sector_size + _sector_margin, y_id * sector_size - _half_sector_size + _sector_margin ) # We want to generate a grid of subsectors and place at most one asteroid per subsector. # To do so, we generate as many indices as there are subsectors and shuffle the values. var sector_data := [] var sector_indices = range(_subsector_count) # The array class provides a convenient shuffle method to do so. # Note that this shuffles the values in place, so we mustn't assign the result to a variable. sector_indices.shuffle() # With our indices ready, we can generate our asteroids. for i in range(asteroid_density): # We first convert the index of the subsector for this loop iteration into 2D grid coordinates. # These are the subsector's coordinates relative to the subsector grid. var x := int(sector_indices[i] / _subsector_grid_width) var y: int = sector_indices[i] - x * _subsector_grid_width # We then use that to generate a new asteroid inside of that subsector boundary. var asteroid := Asteroid.instance() add_child(asteroid) # See the `_generate_random_position()` function below to see how we generate that # uniform distribution. # We pass the subsector's coordinates to it, as well as the sector's top-left, and # the function generates a position inside that subsector. asteroid.position = _generate_random_position(Vector2(x, y), sector_top_left) # The code below is the same as for the white world generator. # We randomize the object's rotation and scale, and then we save the reference in our # `sector_data` array. 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(subsector_coordinates: Vector2, sector_top_left: Vector2) -> Vector2: # We calculate the top-left and bottom-right of the subsector, applying the `_subsector_margin`. var subsector_top_left := ( sector_top_left + Vector2(_subsector_base_size, _subsector_base_size) * subsector_coordinates + Vector2(_subsector_margin, _subsector_margin) ) var subsector_bottom_right := subsector_top_left + Vector2(_subsector_size, _subsector_size) # And we generate a random position within that small subsector's bounding square. return Vector2( _rng.randf_range(subsector_top_left.x, subsector_bottom_right.x), _rng.randf_range(subsector_top_left.y, subsector_bottom_right.y) )
Depending on the values you pick for sector_margin_proportion and subsector_margin_proportion, you’ll get more or less aligned asteroids.
For our space game, the algorithm should work well with a relatively large sector_size and low asteroid_density count.
When you create procedural maps, the kind of noise or algorithms you should use depends on what you want to create.
All that matters is how the result looks and how the game plays. Sometimes, you will want objects to clump up, and at other times you will want them to spread out. The code should serve that vision.
I recommend to always start by experimenting with simple code, even if your handwritten algorithms are slow. Once the generated world looks the way you want it to be, you can start to look for alternative algorithms and implementation to make it run faster.
With that, you saw two kinds of noise for procedural content generation: white noise, which is unpredictable, and blue noise, which produces more uniform distributions.
Those are the two most used ones for our purposes. There are more colors of noise that we’ll let you explore on your own. RedBlobGames’ introduction to noise is an excellent resource if you want to learn more.
Here’s the complete BlueNoiseWorldGenerator.gd script, without comments.
class_name BlueNoiseWorldGenerator extends WorldGenerator export var Asteroid: PackedScene export var asteroid_density := 3 export var sector_margin_proportion := 0.1 export var subsector_margin_proportion := 0.1 onready var _subsector_grid_width: int = ceil(sqrt(asteroid_density)) onready var _subsector_count := _subsector_grid_width * _subsector_grid_width onready var _sector_margin := sector_size * sector_margin_proportion onready var _subsector_base_size := (sector_size - _sector_margin * 2) / _subsector_grid_width onready var _subsector_margin := _subsector_base_size * subsector_margin_proportion onready var _subsector_size := _subsector_base_size - _subsector_margin * 2 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_offset := Vector2.ZERO var sector_location := _current_sector * sector_size if _player.global_position.distance_squared_to(sector_location) > _total_sector_count: 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) seed(_rng.seed) var sector_top_left := Vector2( x_id * sector_size - _half_sector_size + _sector_margin, y_id * sector_size - _half_sector_size + _sector_margin ) var sector_data := [] var sector_indices = range(_subsector_count) sector_indices.shuffle() for i in range(asteroid_density): var x := int(sector_indices[i] / _subsector_grid_width) var y: int = sector_indices[i] - x * _subsector_grid_width var asteroid := Asteroid.instance() add_child(asteroid) asteroid.position = _generate_random_position(Vector2(x, y), sector_top_left) 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(subsector_coordinates: Vector2, sector_top_left: Vector2) -> Vector2: var subsector_top_left := ( sector_top_left + Vector2(_subsector_base_size, _subsector_base_size) * subsector_coordinates + Vector2(_subsector_margin, _subsector_margin) ) var subsector_bottom_right := subsector_top_left + Vector2(_subsector_size, _subsector_size) return Vector2( _rng.randf_range(subsector_top_left.x, subsector_bottom_right.x), _rng.randf_range(subsector_top_left.y, subsector_bottom_right.y) )