There isn’t much of a connection between Cirque Du Soleil and circular buffers. However, when I look at an animated gif of circular buffers the motion of the read and write heads reminds me of the wall of death. The write head’s ever advancing march over values that were yet to be read, but might never see I/O.
An ongoing video game project of mine is where I experiment with Rust’s features to expand my understanding of the language. When I initially wrote Rasengan, a minimal circular buffer implementation, I had no plans on integrating it into the project. However, recently I wanted to implement a sort of blurred motion streak behind the video game character and Rasengan popped into my brain.
There are several ways to implement a motion streak, and some of them don’t need instantiating new entities.
I’m going to look for ways to do this as a camera effect in Bevy eventually, but it was quite tempting to use Rasengan.
You see, a simple array can be used to store all the information I needed to achieve this. When the character starts moving, at regular intervals its positions can be pushed into an array. At some other regular interval, the values from the array can be read back to render the streak (I use the same sprite, but with lower opacity and color adjustment). As the game runs at 60 fps under normal circumstances, this array can get incredibly large quickly. For instance, if you hold down the right arrow key, you would end up with 5MBs of positions data in the array in an hour.
That doesn’t sound so bad considering the memory that ships with modern computers. For instance the computer I’m using to write this blog post has 18 gigs of RAM. With that said, the video game binary is only 15 Mbs itself, and one hour of gameplay generating a third of that seems awfully wasteful.
As the motion streak is quite short, I only needed to store a handful of previous positions. An array of length 10 can store all the data I was going to need, but continuously writing to the array would end up with an ever increasing size which would require a lot of re-allocations. Once a position has been read, it would never be used again. If only I could re-use the array of length 10.
One solution is to use a queue, I would push a new position into the queue on player move and pop one when rendering the streak.
In Rust, a queue would require a RefCell to create the self referential data structure needed to implement a queue, details of which are out of the scope of this post.
I wanted to allocate all the data on the stack without pointers which could be achieved by using an array. However the frequent (60 frames a second) re-sizing of the array seemed like an unnecessary overhead.
If I could just wrap around a fixed size array and overwrite older values when writing the data, I could achieve similar outcome.
Enter - Rasengan
Yeah I’m aware that it’s a corny reference, fortunately that’s the last you’d have to think about references.
I first wrote Rasengan as a side project to explore const generics and circular buffers in general. My understanding of arrays in Rust was also fuzzy. There are quite a few different data structures that represent contiguous memory: array, slice, and vector.
Vectors are allowed to grow and shrink as needed, but I wanted a constant sized chunk.
Slices are a view into an existing array.
Which leaves us the array: [T; usize].
Usually circular buffers prevent new writes until previous data has been read. Rasengan implements circular buffer with overwrite, which means that once the buffer is completely full (unread data is at capacity), it starts to overwrite the least recently updated values. Which works perfectly for rendering the motion streak as lost frames aren’t a big deal.
Here’s a box diagram detailing how the wraparound overwrite works.
W R
│ │
┌───▼───┬───▼───┬───────┬───────┬─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ ▐▌
│ │ │ │ │ │ ▐▌
└───▲───┴───────┴───────┴───────┴─ ─ ─ ─ ─ ─ ─ ─ ▐▌
▀▀▀│▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀│▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘
└─── Capacity = 4 ──────┘
// buffer has no unread values
read() -> panic("Nothing to read here")
W R
│ │
┌───▼───┬───▼───┬───────┬───────┬─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ ▐▌
│ │ 5 │ │ │ │ ▐▌
└───▲───┴───────┴───────┴───────┴─ ─ ─ ─ ─ ─ ─ ─ ▐▌
▀▀▀│▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀│▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘
└───────────────────────┘
inc(W); write(5); // increment W before writing
w R W
│ │ │
┌───▼───┬───▼───┬───────┬───────┬─ ─▼─ ─ ─ ─ ─ ─
│ │ │ │ │ │ ▐▌
│ 8 │ 5 │ 2 │ 4 │ │ ▐▌
└───▲───┴───────┴───────┴───────┴─ ─ ─ ─ ─ ─ ─ ─ ▐▌
▀▀▀│▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀│▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘
└───────────────────────┘
inc(W); write(2); inc(W); write(4); inc(W); write(8);
w = W % capacity // write with wrap-around
Trail Rendering System
I use the Bevy game engine and its ECS model. Explaining how ECS works is out of the scope of this post, but I’m happy to talk you out of OOP if you’re considering it.
Bevy allows instantiating resources that need to be accessed by systems which is exactly what I needed for storing the positions data. I initialize a Rasengan instance at game launch, and then read and write to it in the trail systems.
Here is the entirely of the trail system.
pub fn trail_position_write_system(
// ECS models usually depend on queries to access different entities
player_transform_query: Query<&Transform, With<Player>>,
// this is the data that I'm writing to and reading from
mut trail_position: ResMut<Rasengan<Vec3, TRAIL_LENGTH>>,
) {
if player_transform_query.get_single().is_err() {
return;
}
let player_transform = player_transform_query.single();
trail_position.write(player_transform.translation);
}
pub fn trail_position_read_system(
mut player_trail_transform_query: Query<&mut Transform, With<PlayerTrail>>,
mut trail_position: ResMut<Rasengan<Vec3, TRAIL_LENGTH>>,
) {
if player_trail_transform_query.get_single().is_err() {
return;
}
let mut player_transform = player_trail_transform_query.single_mut();
if let Some(trail_position) = trail_position.read() {
player_transform.translation = trail_position;
}
}
There’s a minor problem with it though, the system is writing values to the positions data each frame, even when the position doesn’t change. Although Rasengan is not allocating more memory, this still feels unnecessary.
Extending Rasengan with write_unique
I decided to update the api to write only when the system attempted to write a new value. This would prevent unnecessary writes when the game character wasn’t moving.
The Rasengan::write_unique is quite simple, it leverages Rasengan::write but first compares the value at the write head.
impl<T: Copy, const N: usize> Rasengan<T, N> {
...
pub fn write_unique(&mut self, data: T) {
if self.write_ptr == 0 {
self.write(data);
return;
}
let idx = self.write_ptr % self.buf.len();
let last_written = self.buf[idx];
if let Some(last_written) = last_written {
if data != last_written {
self.write(data);
}
}
}
}
There’s another hiccup though. This doesn’t compile.
error[E0369]: binary operation `!=` cannot be applied to type `T`
--> src/rasengan.rs:131:21
|
131 | if data != last_written {
| ---- ^^ ------------ T
| |
| T
The problem here is that Rasengan’s implementation doesn’t have sufficient trait bounds that ensure the concrete type passed to write_unique implements core::cmp::PartialEq.
impl<T: Copy + PartialEq, const N: usize> Rasengan<T, N> {
pub fn write_unique(&mut self, data: T) {
if self.write_ptr == 0 {
self.write(data);
return;
}
let idx = self.write_ptr % self.buf.len();
let last_written = self.buf[idx];
if let Some(last_written) = last_written {
if data != last_written {
self.write(data);
}
}
}
}
I added a second implementation with the PartialEq trait bound for Rasengan and everything was back to normal in the pond.
The reason for adding a separate implementation with an added PartialEq bound instead of adding write_unique to the existing implementation was so that I can still use Rasengan normally without requiring types to implement PartialEq when write_unique is not necessary.