Before moving on to the next lesson, let’s cover Utils.gd, our library of utility functions for this series.
We regularly use this idea of independent or library scripts. These are scripts that don’t inherit from built-in classes and where we declare all functions as static. By giving it a class name, we can directly call Utils.function_name() instead of creating an instance of the class. This makes the script a container for reusable functions.
Create a new GDScript file and save it as Utils.gd with the following content:
class_name Utils const UNCERTAINTY := 0.01
We covered the UNCERTAINTY constant before. We use it for calculations with floating-point numbers that cause rounding errors. We use it instead of the built-in function is_equal_approx() because we deal with large differences.
Next, we define two functions for generating uniform random numbers in a circle and an ellipse. We will use these to spawn and position many rooms randomly in a circle before letting the physics engine pushing them away from one another, and away from the circle’s center.
We use trigonometry and polar coordinates to calculate these values. We won’t cover the mathematics here, but you can find a detailed explanation for these functions on StackOverflow.
static func get_rng_point_in_circle(rng: RandomNumberGenerator, radius: float) -> Vector2: return get_rng_point_in_ellipse(rng, radius, radius) static func get_rng_point_in_ellipse(rng: RandomNumberGenerator, width: float, height: float) -> Vector2: # Get a random number in [0, 2PI]. var t := 2 * PI * rng.randf() # Adding two random numbers allows us to get a uniform distribution of points in the ellipse. var u := rng.randf() + rng.randf() # Calculate a random factor in [0, 1]. var r := 2 - u if u > 1 else u # Calculate the coordinates of the point in the ellipse. return r * Vector2(width * cos(t), height * sin(t))
The next function converts from a 1D index to a 2D vector coordinate given a grid width. We saw this function in the first chapter. We use it to convert two nested for loops into a single one.
static func index_to_xy(width: int, index: int) -> Vector2: return Vector2(index % width, index / width)
The next function, is_approx_equal(), tests for equality between two 2D vectors. Our version takes the error parameter, an absolute value for our error margin. That’s unlike the built-in Vector2.is_equal_approx() that calculates a tiny error margin, and that won’t work for our algorithm.
# Tests for approximate equality between two `Vector2`, allowing you to specify an absolute # error margin. static func is_approx_equal(v1: Vector2, v2: Vector2, error: float = UNCERTAINTY) -> bool: return abs(v1.x - v2.x) < error and abs(v1.y - v2.y) < error
We called our function is_approx_equal() because there’s already a built-in global function called is_equal_approx() which compares floats.
The last utility function, mst(), implements Prim’s algorithm for computing a Minimum Spanning Tree (MST) graph given a list of points.
A minimum spanning tree is the smallest number of edges that connect all vertices of a mesh, taking into account the weight or length of its edges. If you take the center of each room as a vertex, the algorithm gives us the minimum number of paths or corridors we need to connect all of them.
For a break-down of the algorithm, please refer to the linked article. We encourage you to go over the break-down in the link by following along with the code below.
# Calculates the Minimum Spanning Tree (MST) for given points and returns an `AStar2D` graph # using Prim's algorithm. static func mst(points: Array) -> AStar2D: var out := AStar2D.new() # Start from an arbitrary point in the list of points out.add_point(out.get_available_point_id(), points.pop_back()) # Loop through all points, erasing them as we connect them. while not points.empty(): var current_position := Vector2.ZERO var min_position := Vector2.ZERO var min_distance := INF for point1_id in out.get_points(): # Compare each point added to the Astar2D graph # to each remaining point to find the closest one. var point1_position = out.get_point_position(point1_id) for point2_position in points: var distance: float = point1_position.distance_to(point2_position) if min_distance > distance: # We use the variables to store the coordinates of the closest point. # We have to loop over all points to ensure it's the closest. current_position = point1_position min_position = point2_position min_distance = distance # Connect the point closest to `current_position` with our new point. var point_id := out.get_available_point_id() out.add_point(point_id, min_position) out.connect_points(out.get_closest_point(current_position), point_id) points.erase(min_position) return out
We store the graph stored as an AStar2D object designed to store and manipulate graphs. It’s mainly used for pathfinding using the A* algorithm, hence the name. But the graph API is generic enough to use it even if we’re not interested in graph search directly.
To follow along the linked article on Prim’s algorithm, you’ll need to know some of the AStar2D API. Here are the relevant parts:
AStar2D.add_point(int id, Vector2 position, weight_scale=1.0): takes three parameters, an ID and the point itself and an optional weight scale. AStar2D keeps track of points with the help of IDs.AStar2D.connect_points(int id, int to_id, bool bidirectional=true): connects two points, referenced by the given IDs, with an edge. The connection is bidirectional by default, allowing movement in both directions.AStar2D.get_available_point_id(): generates the next unused ID for us so we don’t have to track it manually.AStar2D.get_point_position(int id): returns the 2D-vector position of the point with the given ID.AStar2D.get_points(): returns all points as an array.This concludes our coverage of the Utils.gd library script. In the next part, we’ll go over the main scene and start putting things together.
Below you can find the entire contents of Utils.gd for quick reference.
class_name Utils const UNCERTAINTY := 0.01 static func get_rng_point_in_circle(rng: RandomNumberGenerator, radius: float) -> Vector2: return get_rng_point_in_ellipse(rng, radius, radius) static func get_rng_point_in_ellipse(rng: RandomNumberGenerator, width: float, height: float) -> Vector2: # Get a random number in [0, 2PI]. var t := 2 * PI * rng.randf() # Adding two random numbers allows us to get a uniform distribution of points in the ellipse. var u := rng.randf() + rng.randf() # Calculate a random factor in [0, 1]. var r := 2 - u if u > 1 else u # Calculate the coordinates of the point in the ellipse. return r * Vector2(width * cos(t), height * sin(t)) # Tests for approximate equality between two `Vector2`, allowing you to specify an absolute # error margin. static func is_approx_equal(v1: Vector2, v2: Vector2, error: float = UNCERTAINTY) -> bool: return abs(v1.x - v2.x) < error and abs(v1.y - v2.y) < error # Calculates the Minimum Spanning Tree (MST) for given points and returns an `AStar2D` graph # using Prim's algorithm. static func mst(points: Array) -> AStar2D: var out := AStar2D.new() # Start from an arbitrary point in the list of points out.add_point(out.get_available_point_id(), points.pop_back()) # Loop through all points, erasing them as we connect them. while not points.empty(): var current_position := Vector2.ZERO var min_position := Vector2.ZERO var min_distance := INF for point1_id in out.get_points(): # Compare each point added to the `Astar2D` graph # to each remaining point to find the closest one. var point1_position = out.get_point_position(point1_id) for point2_position in points: var distance: float = point1_position.distance_to(point2_position) if min_distance > distance: # We use the variables to store the coordinates of the closest point. # We have to loop over all points to ensure it's the closest. current_position = point1_position min_position = point2_position min_distance = distance # Connect the point closest to `current_position` with our new point. var point_id := out.get_available_point_id() out.add_point(point_id, min_position) out.connect_points(out.get_closest_point(current_position), point_id) points.erase(min_position) return out static func index_to_xy(width: int, index: int) -> Vector2: return Vector2(index % width, index / width)