Welcome to another issue of (the) New Gnorp Times, voted superior to The New York Times in a recently conducted survey (Sample size: 1; Margin of error: ±0%). The topic of today is The Ring, a new mechanic designed for the Epilogue Expansion.

The Epilogue Expansion is an upcoming patch to (the) Gnorp Apologue, which will include new talents, mechanics and a different ending.

If you look above while playing the Epilogue, you will find a number of particles that compose a ring around the planet of the gnorps. The ring is not precious. It is the worst. Not only does the ring reduce the amount of damage and collection the gnorps do through its oppressive presence—it is also hoarding talent points.

Besides further beating up the rock, in Epilogue you also want to reduce the ring integrity in order to get those talent points, increase collection and damage, and ultimately win.

In the base game, during compression events and prestiging, the rock reclaims shards that were ouput. In Epilogue, things are slightly different.

When a compression event occurs in Epilogue, shards fly up and coalesce into more ring particles. This further reduces damage and collection, and makes it harder to collect the talent points of the ring. This downside of compression is intended to allow for a little more strategy about when to compress, but is not meant to be very punishing.

There's a couple of very exciting things we can do in terms of optimization with the ring. If you're interested in that, keep reading. If not, escape.

First of all, the ring particles, or roids as I call them (they are not asteroids or meteors as one might assume (in Gnorps in Space there will be asteroids (no meteors because meteors are defined as objects from outer space that enter the atmosphere of a planet and Gnorps in Space takes place in space (shooting stars are meteors (an asteroid that briefly became a shooting star killed the dinosaurs (except for the ones that evolved to become birds (birds are avian dinosaurs (pterodactyls were not dinosaurs)))))))), fly above the planet of the gnorps at the same velocity. This simple fact allows us to make some cool optimizations. More on this later.

Let's establish a few points to walk through things:

• The ring has no orbit, instead the roids move at a fixed velocity on the X-axis
• When going beyond the maximum X-position, the roid wraps around to the minimum X-position by subtracting the width of the ring
• For this, we define the Width=50, Minimum X-position=0, Maximum X-position=50
• We define the speed as 1, meaning every update the roids move 1 position to the right
• The roids do not collide with themselves

So, assuming a vector, a list of roids, with the following X-positions:

[25, 10, 50, 17]

We update the ring, and end up with this:

[25+1, 10+1, 50+1, 17+1] -> [26, 11, 51, 18] -> [26, 11, 0, 18]

The third roid in the list has wrapped around because it had an X-position greater than the maximum X-position.

This is essentially the first optimzation we make, as we do not delete roids outside the maximum X-position and insert new ones--we recyle them. You can follow individual roids by color in the gif below.

And here is the pseudo-code for the behavior of the roids.

const ORBITAL_VELOCITY = 1; 
const MAXIMUM_X = 50;
const RING_WIDTH = 50;  
function update_roids(list_of_roids) {
    for roid in list_of_roids {
        roid.position.x += ORBITAL_VELOCITY; 
    
        if roid.position.x > MAXIMUM_X {        
            //We found a roid that needs to wrap around
            roid.position.x -= RING_WIDTH; 
        } 
    }; 
}

Next, we have to look at collision. The roids will be able to collide with certain game objects, so then we need to allow for that. Now, normally we might define the roids are spheres with a radius—but objects that orbit around a planet tend to move at terrifying speeds, and therefore we do not need the precision of spherical collision. That is a benefit as spherical collision can be fairly computationally expensive. So the roids are, for collision, considered squares—and so are the objects that they collide with.

Below you will the the function we use to check for collision. The function, intersects(house, roid), is a simple function that compares two rectangles against each other—an intersection means collision.

function check_collision(list_of_roids, house) {
    for roid in list_of_roids {
        if intersects(house, roid) == true {
            //We found a collision!
        }
    }
}

To illustrate the work being done, the gif above pauses on every update and highlights the roids we are checking against. The object we collide against is a house with two gnorps inside. The collision detection function simply goes through the list of roids to find if there is any intersection. This checking can potentially take a fair bit of time, as we there might be many objects to check against. For example, if we have a 100 roids and 10 objects to check agains we will have to do 1000 intersection checks every update.

How can we optimize this? The roids fly above the planet, which means we have knowledge about where they won't be. When the roids are generated, they are given a Y-position that is always under 100. We also know that roids have a maximum radius of 10. Armed with those two pieces of information, we can do this:

function check_collision(list_of_roids, house) {
    if house.y > MAX_RING_Y + 10 {
        //No collision can happen, so we exit this function immediately
        return
    }
    for roid in list_of_roids {
        if intersects(house, roid) == true {
            //We found a collision!
        }
    }
}

Now there are a far fewer comparisons being made, and that's a job well done. Thanks for reading.

Just kidding; life isn't that easy.

At this point in our journey, it's important to establish a benchmark. We need to know the speed at which the computational work is being done in order to take the potential out of "potential improvements". The more you run a benchmark, the more accurate it is. Any good benchmark is also reflective of the real-world conditions: When players run the game.

• Create a list of 1500 randomly positioned roids
• Create a list of 10 randomly positioned houses (the objects the roids collide with)
• Run the movement and collision functions 10000 times
• Repeat the the steps above 99 times

This should give us a fairly accurate benchmark, and we will collect three data points: The time it takes to update the movement of our roids and houses, the time it takes to check for collisions, and the number of collisions. The reason we collect the number of collisions is that we need to make sure that our changes do not alter the results of the collision detection itself—any meaningful change in the number would indicate that something got messed up.

So for every benchmark we run 1 million updates, which is equivalent to running the game for 4.6 hours. And with that, we run the benchmark and arrive at these numbers, our baseline:

Benchmarked 10000 updates 100 times in 23925 milliseconds (24 seconds)
Average time spent up updating roids: 10305 microseconds (10 milliseconds)
Average time spent on collision detection 228954 microseconds (229 milliseconds)
Average # of collisions: 22833

We observe that 95% of the time is spent on collision detection. Reducing that number should then be our focus.

Optimization is all about not doing things. For example one method of optimization is asking an LLM to write (the) New Gnorp Times for me, but that would change the output from "hopefully high-quality" to "definitely artificial", so it would be a bad optimization. We need to find a way to skip work while not changing the outcome.

Let's look a picture I made in paint.

In the picture several roids can be found, and their left edges have been marked with either red or green based on the following comparison: Is the right edge of the house greater than the left edge of the roids? If the comparison is true, there might be a collision: We'll have to do further checking to find out. But if the comparison is false, then a collision is impossible.

The key observation we make here is that if we were to check the roids for collisions according to the order of their left edges, we can skip all remaining collision checking once we hit upon the first roid where right edge of the house is less than the left edge of the roid.

So, every update, after updating the positions of all the roids we also sort them by their left edges. Reiterating upon the above, that allows us to go through the list of roids in the order shown on the picture, and once we find a roid where house.right() < roid.left(), we skip all the remaining roids.

function update_roids(list_of_roids) {
    for roid in list_of_roids {
        roid.position.x += ORBITAL_VELOCITY; 
    
        if roid.position.x > MAXIMUM_X {        
            //We found a roid that needs to wrap around
            roid.position.x -= RING_WIDTH; 
        } 
    }; 

    //We sort the list according to the left edge of the roids
    list_of_roids.sort_by(|roid1, roid2| roid1.left() < roid2.left());
    
}


function check_collision(list_of_roids, house) {
    if house.y > MAX_RING_Y + 10 {
        //No collision can happen, so we exit this function immediately
        return
    }
    for roid in list_of_roids {
        if house.right_edge() < roid.left_edge() {
            //No collision can happen at this point onwards, 
            thanks to our list of roids sorted by their left edges,
            so we exit this function immediately
            return
        }
        if intersects(house, roid) == true {
            //We found a collision!
        }
    }
}

Here's how it looks in our little simulation:

And here is the result of the benchmark:

Benchmarked 10000 updates 100 times in 14676 milliseconds (15 seconds)
Average time spent up updating roids: 89844 microseconds (89 milliseconds), 
Average time spent on collision detection: 56923 microseconds (57 milliseconds) 
Average # of collisions: 23067

The time it took to check for collisions more than halved, but the time it takes for the roids to update has increased tenfold! The increase is due to the time it takes to sort the list. Overall the change was an improvement, but still—can we reduce the amount of time it takes to maintain the sorted order?

Sorting lists are expensive. This has to do with moving things are around in memory. In our instance, if we have a list like this: [20, 25, 30, 0] -> [0, 20, 25, 30], 3 elements have to shift to the right in order to correctly sort the list. The more elements we have to shift, the longer it takes. We have a lot of roids, so it takes quite a bit of time.

Since all the roids have the same speed, we know then that the order of the list never changes except when they wrap around, and when that happens the back of the list simply moves to the front of the list.

This allows us to use a circular buffer to maintain our sort. What that means is fairly simple. It's a list that can rotate its "head", the start of the list. Instead of the actual list changing, it is the starting point of the list that does!

Consider the list of roids here as rotation is applied. The index indicates the order of the list, and we start at 0.     
Roids: [20, 25, 30, 0] -> [20, 25, 30, 0] 
Index: [0,  1,  2,  3]     -> [1,  2,  3 , 0]
The list remains the same, but the starting point changes. 

So, when we go through our list, we start at index 0 and that yields the X-positon 0. That means our sort is maintained!

Upon creation of the roids, they are sorted according to their left edges as usual—but only then! After that, the rotation takes care of the rest.

function update_roids(list_of_roids) {
    rotations = 0;

    for roid in list_of_roids {
        roid.position.x += ORBITAL_VELOCITY; 
    
        
        //We also need to change the wrap-around behavior to make it
        so that roids wrap around based on how we want the list to be sorted 
        (by left edges)
        if roid.left() > MAXIMUM_X {        
        
            //We found a roid that needs to wrap around
            //We add to the number of rotates we need to do
            //in order to maintain the sort
            rotations += 1; 
             
            roid.position.x -= WIDTH; 

        } 
    }; 
    
    //The list has its "head" rotated to the right in order to maintain the 
    sort
    list_of_roids.rotate_right(rotations); 
    
}

Benchmarked 10000 updates 100 times in 8790 milliseconds (9 seconds)
Average time spent up updating roids: 8733 microseconds (9 milliseconds)
Average time spent on collision detection 79173 microseconds (79 milliseconds), 
Average # of collisions: 22969

An enormous improvement compared to sorting every update!

Now, we have another key detail about the belt that we can use to skip even more checking, the coup de grâce of our optimization work: A positional heuristic.

The ring has an even distribution of roids along the X-axis, that is to say that you can expect to find a similar number of asteroids comparing any given bound. The even distribution is due to the way asteroids are generated: They are given a random position between the minium X-position and the maximum X-position of the ring. When you do that enough times, you get a fairly even spread of roids along the X-axis. That allows us to make an assumption about where to start checking within the belt.

Our goal will be to turn an X-position into an index, a number we use to access the list. In order to do that we take the X-position and divide it by the width of the ring. That gives us a number that represents the ratio of progress, which we then multiply with the number of roids in our list. This gives use a roid that we expect to have a similar X-position as the house we may collide with. But there is no guarantee we were right! We need to do some additional work to make sure that we won't miss any collisions, as any misses would invalidate the optimization. In order to that, we go down the list in descending order to find a roid that we cannot possibly collide against. Remember, we sort by the left edges of the roids, so an invalid collision would be roid.x + 10 < house.left(). Why +10? That's the maximum radius of a roid, which means there won't be any roids further down the list that we might collide with.

Let's see how it works within the simulation.

Pure heuristic beauty. In the simulation, you can see that very few checks are made, and the benchmark should then show significant improvements.

And indeed it does. We go from N milliseconds spent checking for collisions to M, a reduction of X%. Optimization! Our positional heuristic is extremely effective at guessing thanks to the properties of the ring.

function assumption(x) -> Integer {
    //We take x and divide it by the ring width
    which gives us the ratio of progress 
    //We then multiply it by the number of roids, 
    which gives us the index of roids with hopefully similar progress
    return round_down((x / RING_WIDTH) * number_of_roids)
}


function check_collision(list_of_roids, house) {
    if house.y > MAX_RING_Y + 10 {
        //No collision can happen, so we exit this function immediately
        return
    }
    
    //We make our educated guess
    index = assumption(house.x); 
    
    //To prevent missing any collisions, 
    we go back down the list to find a roid we can't collide with
    while list_of_roids[index].x + 10 > object.x {
        index -= 1
    }

    //we only check roids from the found starting point
    for roid in list_of_roids[index..] {
    
        if house.right_edge() < roid.left_edge() {
            //No collision can happen at this point onwards, 
            thanks to our list of roids sorted by their left edges,
            so we exit this function immediately
            return
        }

        if intersects(house, roid) == true {
            //We found a collision!
        }
    }
}

The answer to that question is always yes. But is worth it? No. Our optimizations are more than enough for what we need, so our time is better spent elsewhere.

Our view into the game, whatever you can see in the game window, is just a giant rectangle. It would be wasteful to draw things outside the view into the game, so in order to to figure out what is within the view we also apply collision detection: The rectangle representing the screen is checked against the list of roids, and if an intersection occurs we draw the roid in question. This allows us to apply all the optimization work we did in order to also optimize the speed at which we find which roids to draw.

I made this because I thought it would be fun to show the work that might go into optimizing a game. Normally naive implementations of systems are fine most of the time, because computers are extremely fast, especially when using a low-level programming language like Rust (which Gnorp is written in).

What matters the most is if the code is an accurate description of the steps required to accomplish your desired outcome, written in such a way that it can easily accomodate any future changes to both desired outcome and desired performance.