Welcome ❤️ Coroutine Hell

I’ve been working on a bullet hell game using Rust and WGPU. Right now, it has a main menu and supports shooting bullets at you, but not much else is implemented.

The next step is to implement stage “scripts” instead of having a hardcoded pattern in the game loop and to add support for enemies. Also, to create complex patterns, it’s useful to allow manipulating bullets after they spawn. To handle these, bullet hell devs love coroutines. The venerable Touhou Danmakufu has them, and the Taisei Project keeps a library for it. So what approach will I take?

Don’t use coroutines

This technically works but pretty painful. You have to write state machines controlling behavior manually.

Use stackful coroutines

This needs only some assembly code to switch between stacks and is what the Taisei Project does with their library. My previous project, TDR, also used this approach. The advantage is that you don’t need much language support and that you can use recursion in yielding code. The main drawback is that you have to allocate space for a call stack, which has to be big enough to avoid overflow.

In Rust, you can also run into borrow checker issues, since all tasks will need to modify the game state, even though only one task will be running at a time. You could try to get around it by wrapping the state in a RefCell, but then you have to be careful not to hold a guard to it across a yield, preventing other tasks from accessing it. (Edit 2024-09-19: See note in later section.)

Edit 2024-09-19: Another problem is that in order to destroy a coroutine before it returns, you need to unwind the stack in some way, either by panicking and catching the unwind or by making yielding fallible (and not allowing the code to yield after a previous yield fails). You could ignore the problem and tell people not to hold malloc’d data across a yield, but preventing such problems is part of the point of Rust.

Embed a scripting language that supports coroutines

A popular approach. However, I’d prefer to spend time on other tasks than looking for a scripting language that won’t drain my sanity (or implementing my own), writing bindings to that language, possibly realizing that using f32s in my game code is a terrible idea, and dealing with garbage collection. Also, the gameplay code is tucked into a separate no_std crate to minimize risks to reproducibility, so loading scripts from the asset file will add even more complication.

Use async/await

Rust actually uses coroutines internally to implement async and await. However, this still has the problems with the borrow checker that I previously mentioned.

Use coroutines directly

Rust actually supports coroutines as an experimental feature. The difference from futures is that you can pass information whenever you resume a coroutine, and the coroutine can pass back information when yielding (see for yourself). Instead of letting coroutines keep a mutable reference to the game state, we can pass in a wrapper object on each resumption. To prevent coroutines from holding this object across yields, we require consuming the object to get a ‘yield token’:

#![feature(coroutines)]
#![feature(coroutine_trait)]
#![feature(allocator_api)]
#![feature(stmt_expr_attributes)]

#[derive(Debug)]
#[must_use = "needed to continue interacting with game state"]
pub struct TaskContext<'state, T, A: Allocator = Global> {
    state: *mut T,
    // ... fields omitted ...
}

#[derive(Debug)]
#[must_use = "needs to be yielded to get back a new TaskContext"]
pub struct Wait(NonZeroU16);

impl<'state, T, A: Allocator> TaskContext<'state, T, A> {
    pub fn wait(self, ticks: NonZeroU16) -> Wait {
        Wait(ticks)
    }

    pub fn state(&mut self) -> &mut T {
        unsafe { &mut *self.state }
    }
}

let task = #[coroutine]
    |mut ctx: TaskContext<'_, u64>| {
        *ctx.state() += 1;
        let mut ctx = yield ctx.wait(NonZeroU16::new(1).unwrap());
        *ctx.state() += 2;
        let mut ctx = yield ctx.wait(NonZeroU16::new(3).unwrap());
        *ctx.state() *= 3;
    };

Edit 2024-09-19: This would also be possible with stackful coroutines, but the call stack problem still exists with those, so I think stackless coroutines are the better choice if you language supports them.

A few hundred lines of hideously unsafe Rust code later, I came up with a task manager. I’m publishing the implementation as kcr2.

We still have a few borrow checker issues to wrinkle out: the task manager is naturally a part of the game state, but it needs to borrow the game state to update itself! We can solve this problem using one of two approaches^[1]:

1. Create a struct that contains all of the game state except for the task manager, and include that plus the task manager in the main struct. But I already have nesting with GameState > PersistentGameState (the part that is saved across stages), so including a third nesting level will add more pain (though this can be mitigated by having the outer structs implement Deref I guess).
2. Just make the task manager field be Option<TaskManager<..>> and take the value while it’s being updated. Edit 2024-09-19: This has a slightly higher risk of run-time errors, but it might simplify matters if we had multiple task managers (e.g. a “general stage” manager and a “boss attack” manager) and we had to spawn tasks one one manager while on another, but I don’t think that’s a common occurrence.

Also, communication between different tasks is complicated. The best bet is to use channels (since the game logic is single-threaded, we don’t even need them to be Send or Sync, so they can be a wrapper around UnsafeCell<Vec<T>>), though they’ll need to be wrapped in an Rc. Alternatively, we can provide a function to combine two or more coroutines that want to share some state. Since each task requires a heap allocation, it’s ideal to minimize the number of tasks being created.

What if tasks are enemies?

But hold on; each enemy will have a task attached to it (to control its movement and attacks). What if we tied tasks to enemies? If you want to spawn a task that controls shots after they spawn, create an enemy with no sprite or hitbox!

Here, too, we have problems with the borrow checker: we want to pass access to the game state while we’re updating part of it. Temporarily removing the enemy currently being updated by itself won’t work, since we’re still borrowing the list of enemies. We’ll have to suspend access to the enemy list while updating the enemies, which might be a problem if an enemy wanted to change its behavior based on the presence of other enemies. Simply put, I doubt that this simplification will work out in Rust.

I’m going to stop here for now before I eepify myself further.