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 is an upcoming free expansion to (the) Gnorp Apologue in the form a new mode, which will include new talents, mechanics and a different ending.
The Ring
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.
It was the rock all along
The ring is the rock's fault. 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 talent points from 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.
How do you destroy the ring? I'm not telling.
Other news
Before we get into the next section, which will be about optimizing the performance of the ring, I want to quickly mention a couple of things:
- I am not 100% happy with the beta patch. More work has to be done, but Epilogue feels right to prioritize right now.
- I've shifted the road map a bit. Gnorps in Space will be the next focus after Epilogue, but I will talk more about that in the future.
- More hats are coming!
- I got pneumonia from a bacteria called Mycoplasma Pneumoniae, which I thought funny because Mycoplasma is the origin of my handle, Myco. Being knocked out for several weeks was less funny.
- I did an interview about speedrunning (the) Gnorp Apologue with the guys at Board Boosters. You can watch it below.
The technical side of the ring
There's a couple of very exciting things we can do to optimize the performance of the ring. If you're interested in that, keep reading. If not, escape.
The roids
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 a fake orbit, 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 list of four 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 optimization we make, as we do not delete roids outside the maximum X-position and insert new ones--we recycle 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;
}
};
}
Collision
Next, we have to look at collision. The roids will be able to collide with certain game objects, so we need to allow for that. Now, normally we might define the roids as circles 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 collision between circles. That is a benefit as collision detection of circles can be fairly computationally expensive. So roids are circles, but for collision they are considered squares—and so are the objects that they collide with.
Below we can see the function we use to check for collision. Within it, we can see another function, intersects(house, roid), which is a simple function that compares two rectangles against each other. An intersection means collision. As mentioned before, roids are converted into rectangles within the function in order to reduce the computational cost of collision detection.
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.
Checking for intersections can take fair bit of time, as there might be many objects to check against. For example, if we have 100 roids and 10 objects to check against we will have to do 1000 (100 x 10) intersection checks every update.
Height
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 as they are in the sky. (Lower values here mean the roids are higher up in the sky.) 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 far fewer comparisons being made, and that's a job well done. Thanks for reading.
Benchmarking
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.
We set up the benchmark with the following conditions:
- 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 arrive at these numbers, our baseline:
Benchmark: 10k updates, 100 runs. Numbers are the average of 100 runs.
Movement Collision detection # of Collisions Overall time Overall % reduction Baseline 10ms 229ms 22833 239 ms ---
We observe that 95% of the time is spent on collision detection. Reducing that number should then be our focus.
Left and right edges
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 good" 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, because a rectangle where the right edge is less than the left edge of another rectangle can never intersect.
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 the 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()
}
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() < roid.left() {
//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:
Benchmark: 10k updates, 100 runs. Numbers are the average of 100 runs.
Movement Collision detection # of Collisions Overall time Overall % reduction Baseline 10ms 229ms 22833 239 ms --- Sorted 89ms 57ms 23067 146ms 39%
The time it took to check for collisions was significantly reduced, but the time it took for the roids to move was increased by 9x! The increase is due to the time it takes to sort the list, because we need to do that every update as roids might have wrapped around. Overall the change was an improvement, but still—can we reduce the amount of time it takes to maintain the sorted order?
Circular buffer
Sorting lists are expensive. This has to do with moving things around in memory. In our instance, if we have to sort a list like this in ascending order:
[20, 25, 30, 0] -> [0, 20, 25, 30] — The 4th element in the list moves to the 1st position and 3 elements have to shift to the right. 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
roid.position.x -= WIDTH; //We add to the number of rotations we need to do
// in order to maintain the sort
rotations += 1;
}
};
//The list has its "head" rotated to the right in order to
// maintain the sort
list_of_roids.rotate_right(rotations);
}
We implement and benchmark, and our results are:
Benchmark: 10k updates, 100 runs. Numbers are the average of 100 runs.
Movement Collision detection # of Collisions Overall time Overall % reduction Baseline 10ms 229ms 22833 239 ms --- Sorted 89ms 57ms 23067 146ms 39% Circular buffer 9ms 79ms 22969 88 ms 63%
An enormous improvement compared to sorting every update! We took a hit to the collision detection speed, and that has to do with circular buffers being slower to iterate through.
Positional heuristic
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 with the same width. 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 us a roid that we expect to have a similar X-position as the house we may collide with.
There is no guarantee we were right, however! 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 we need to compare with the maximum possible radius of a roid: roid.x + 10 < house.x would mean we have found the point where we will never find roids that we can collide with.
Let's see how it works within the simulation.
Pure heuristic beauty. We can see that very few checks are made, and the benchmark should then show significant improvements.
Benchmark: 10k updates, 100 runs. Numbers are the average of 100 runs.
Movement Collision detection # of Collisions Overall time Overall % reduction Baseline 10ms 229ms 22833 239 ms --- Sorted 89ms 57ms 23067 146ms 39% Circular buffer 9ms 79ms 22969 88 ms 63% Positional heuristic 9ms 10ms 23120 19ms 92%
And indeed it does. We go from 79 milliseconds spent checking for collisions to 10 milliseconds, a rather significant reduction! Optimization! Our positional heuristic is extremely effective at guessing thanks to the properties of the ring.
function assumption(x, number_of_roids) -] Integer {
//We take x and divide it by the ring width
// which gives us the ratio of progress
//We then multiply 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.x + 10 > house.x {
index -= 1
}
//We only check roids from the found starting point
for roid in list_of_roids {
if house.right() < roid.left() {
//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!
}
}
}
Can we do more?
The answer to that question is always yes. But is it worth it? No. Our optimizations are more than enough for what we need, so our time is better spent elsewhere. We did great!
Bonus optimization
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.
Write straightforward code
I made this because I thought it would be fun to show the work that might go into optimizing a game. Normally naïve 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 accommodate any future changes to both desired outcome and desired performance. In other words: Write straightforward code.
While working on a different project a while back, I came across this Sort, sweep, and prune: Collision detection algorithms post about collision detection. A few of the things I apply to optimize the ring I learnt from that post. I drew inspiration of visualizing the collision detection from the post as well.
The end
I'm quite excited to continue the work on Epilogue, and I hope you are looking forward to playing it. Thanks for reading (the) New Gnorp Times #21.