In this article we will be discussing an alternative approach to Bevy’s Schedule system that uses timers to encapsulate and schedule game logic, and how this system can be implemented on top of Bevy without any changes.
The question of how to implement sequential processes in game engines has a long and storied history. The most basic approach is to use a step function that contains all of the game logic. A typical step function might look as follows:
struct World { /* ... */ }
impl World {
pub fn step(&mut self) {
collect_input(self);
update_positions(self);
resolve_collisions(self);
other_logic(self);
}
}Effectively, this is how Bevy works. It has a Schedule structure that contains an ordered list of “stages” which are executed one after another. Running all of the stages once completes a “step”:
pub struct Schedule {
stages: HashMap<String, Box<dyn Stage>>,
stage_order: Vec<String>,
/* ... */
}
impl Schedule {
pub fn run_once(&mut self, world: &mut World, resources: &mut Resources) {
for name in self.stage_order.iter() {
let stage = self.stages.get_mut(name).unwrap();
stage.run(world, resources);
}
}
}This is a perfectly acceptable method for structuring games. However, when adding the element of time, this structure becomes less than elegant. Let’s consider what Bevy recommends doing if we would like to have a process run every two seconds:
struct GreetTimer(Timer);
fn greet_people(
time: Res<Time>, mut timer: ResMut<GreetTimer>, query: Query<&Name, With<Person>>
) {
// update our timer with the time elapsed since the last update
// if the timer hasn't finished yet, we return
if !timer.0.tick(time.delta_seconds()).just_finished() {
return;
}
for name in query.iter() {
println!("hello {}!", name.0);
}
}
impl Plugin for HelloPlugin {
fn build(&self, app: &mut AppBuilder) {
// the reason we call from_seconds with the true flag is to make the timer repeat itself
app.add_resource(GreetTimer(Timer::from_seconds(2.0, true)))
.add_startup_system(add_people.system())
.add_system(greet_people.system());
}
}A few issues stand out here in this approach:
- The timer is not automatically tracked by Bevy, requiring the greet_people system to tick the timer every entry.
- As a consequence of the previous point, the greet_people function will be entered even if the timer has not elapsed, which is not as efficient as we would like.
- The timer is based on real-time, which means that it can be off by some amount of time.
- Timers are resources and thus extracted by type, which means we have to strategically couple them if we want more complicated behavior. This point is addressed in the next section.
A grenade (in a video game) is an item which after a set amount of time performs an action and despawns itself. Let’s analyze how we would implement this currently in Bevy.
Our grenade needs to be able to despawn an entity in our ECS after a set amount of time, so therefore it is composed of a Timer and Entity id:
struct Grenade {
timer: Timer,
entity: Entity,
}In order to efficiently dispose of our Grenade’s timer and entity id after the timer has elapsed, we need to store them in a data structure that allows for fast removal of any item. Therefore, the simplest effective data structure to make our “Grenades” resource is a linked list:
struct Grenades(LinkedList<Grenade>);There are ways to make this more efficient, such as structuring the linked list such that the first entry is the timer that is next to run, and all subsequent timers refer to how much time after the first has run. However, and this is the fundamental point of this article, the problem of efficiently designing this data structure is the exact same as efficiently designing a scheduler for arbitrary timers. Therefore, let us continue with this example.
Our system for exploding the grenades is as follows:
fn explode_grenades(
commands: &mut Commands,
time: Res<Time>,
mut grenades: ResMut<Grenades>,
) {
let elapsed = time.delta_seconds();
let mut curr = grenades.0.cursor_front_mut();
loop {
let exploding = if let Some(ref mut curr) = curr.current() {
if curr.timer.tick(elapsed).just_finished() {
true
} else {
false
}
} else {
// No more items left in the list.
return;
};
if exploding {
let Grenade { entity, .. } = curr.remove_current().unwrap();
// Curr now points to the next entry.
// Despawn the entity and perform whatever other action is required.
commands.despawn(entity);
} else {
curr.move_next();
}
}
}This is quite a bit of code for an implementation that is not very efficient, and as noted above this is basically because we are implementing an ad-hoc system scheduler. More efficient designs for these are much more involved. This leads us to the question: how can we design a system to efficiently handle any type of timer?
In a game engine, the most basic unit of time is a single discrete update to the game state, known commonly as a tick. Ticks are related to real-time in some ratio, some common ratios being 60 to 1 second or 120 to 1 second. Other common tick rates are 64 to 1 second or 128 to 1 second.
You will notice that these numbers do not match up necessarily with common refresh rates of monitors, which are usually 60 or 144 hertz. The number of refreshes to the display the game engine does is called the frames per second, or more commonly known as the FPS. The FPS is often times equal to the tick rate, but as we will explain later this can often be detrimental.
It is important that games have a consistent tick rate during a single game session and that units of time in game are expressed in terms of ticks and not real-time. Because tick rates are ratios to real-time, it is possible to express any real-time value as a number of ticks, and vice versa. However, when real-time values are used as timer values instead of tick values, inconsistencies in clocks can lead to the same real-time values varying by some number of ticks.
This might not seem like much of an issue, and for a lot of video games it can be argued that it is not. However, for competitive games this effect can be devastating. It is fundamentally important to eliminate variables that a player cannot influence unless these variables are explicitly random. For example, Street Fighter would be far less competitive of a game if hitboxes lingered for a random number of frames. It might not ruin the competitive aspect of the game but it would be an incredible source of frustration for players.
As another example of the importance of basing timers in game-time and not real-time, consider what happens if a tick lasts much longer than it is expected to, such as from network lag. Now any timer based on real-time no longer relates to ticks, and network lag can affect the game logic.
Basing game logic on ticks also allows for games to be reproducible. Recording the input given at each tick effectively creates a replay that allows us to recreate game state at any time. This is incredibly important for many competitive games on a wide spectrum of game play, from Street Fighter to Counter Strike.
It might not seem like this is an issue for single player games, however I would argue it’s just as important for two reasons. First, allowing for replays to be captured makes it much easier to debug your game during development. Secondly, even single player games can be competitive, with speed running becoming more and more popular it behooves you to make your game as consistent and reproducible as possible. Your speedrunners will thank you.
There are plenty of times in which real-time effects are desirable and therefore real-time timers are useful, such as effects in single player games that are determined by a real amount of time and not an amount of time spent during a game session. For everything else, tick based timers should be used.
We redefine a Timer to be a Bevy Stage that is executed after a certain amount of time and is discarded. Notice that the Timer includes a mutable reference to a TimingWheelHierarchy instead of just the world. We will get into that later.
/// An object that runs once, modifies the world, and then is destroyed.
pub trait Timer: Any {
fn wakeup(
self: Box<Self>,
schedule: &mut TimingWheelHierarchy,
world: &mut World,
resources: &mut Resources
);
}One of the most efficient data structures for executing timer is called a hierarchical timing wheel (insert reference here). An implementation of this with respect to our timer implementation is provided here. This implementation uses const generics, however it can be implemented just as easily with a fixed constant.
Keep in mind that there are almost certainly better ways to implement this.
struct TimingWheel<const MAX_INTERVAL: usize> {
current_tick: usize,
ring: [Vec<Box<dyn Timer>>; MAX_INTERVAL],
}
impl<const MAX_INTERVAL: usize> Default for TimingWheel<{ MAX_INTERVAL }> {
fn default() -> Self {
let mut empty = MaybeUninit::<[Vec<_>; MAX_INTERVAL]>::uninit();
let p: *mut Vec<Box<dyn Timer<World>>> = unsafe { mem::transmute(&mut empty) };
for i in 0..MAX_INTERVAL {
unsafe {
p.add(i).write(vec![]);
}
}
TimingWheel {
current_tick: 0,
ring: unsafe { empty.assume_init() },
}
}
}
impl<const MAX_INTERVAL: usize> TimingWheel<{ MAX_INTERVAL }> {
/// Insert the timer into the wheel.
fn schedule(&mut self, ticks: usize, timer: Box<dyn Timer>) {
let index = (self.current_tick + ticks) % MAX_INTERVAL;
self.ring[index].push(timer);
}
/// Return all the timers that execute on the current tick, and more the clock
/// forward one.
fn tick(&mut self) -> Vec<Box<dyn Timer<World>>> {
let timers = mem::take(&mut self.ring[self.current_tick]);
self.current_tick = (self.current_tick + 1) % MAX_INTERVAL;
timers
}
}
#[derive(Default)]
struct TimingWheelHierarchy {
/// One frame at 120 fps.
level_0: TimingWheel<64>,
level_1: TimingWheel<64>,
level_2: TimingWheel<64>,
level_3: TimingWheel<64>,
// TODO: Add more levels (if you want to).
}
impl TimingWheel {
/// Schedule a timer to occur after the given number of ticks have elapsed.
pub fn schedule(&mut self, ticks: usize, timer: Box<dyn Timer>) {
let level = if ticks == 0 {
0
} else {
(63 - ticks.leading_zeros()) / 6
};
match level {
0 => self.level_0.schedule(ticks, timer),
1 => self.level_1.schedule(ticks >> 6, timer),
2 => self.level_2.schedule(ticks >> 12, timer),
3 => self.level_3.schedule(ticks >> 18, timer),
_ => panic!("timer interval too long"),
}
}
pub fn tick(&mut self) -> Vec<Box<dyn Timer>> {
// Surely there is a better way to do this.
let mut timers = Vec::<Box<dyn Timer>>::new();
if self.level_0.current_tick == 63 {
if self.level_1.current_tick == 63 {
if self.level_2.current_tick == 63 {
timers.extend(self.level_3.tick());
}
timers.extend(self.level_2.tick());
}
timers.extend(self.level_1.tick());
}
timers.extend(self.level_0.tick());
timers
}
}With this new structure, we can redefine App in terms of timers. In this implementation we are omitting the Runner for the sake of brevity.
pub struct App {
pub world: World,
pub resources: Resources,
pub schedule: TimingWheelHierarchy,
}
impl App {
/// Schedule a timer to be run after some number of ticks have elapsed.
pub fn schedule<T>(&mut self, after: usize, mut timer: T) -> &mut self
where
T: Timer + 'static,
{
self.schedule.schedule(after, Box::new(timer))
self
}
/// Schedule a timer to run immediately.
pub fn now<T>(&mut self, timer: T) -> &mut self
where
T: Timer + 'static,
{
self.schedule.schedule(0, Box::new(timer));
self
}
/// Run the simulation forever.
pub fn run(&mut self) -> ! {
loop {
let timers = self.schedule.tick();
for mut timer in timers {
timer.wakeup(
&mut self.schedule,
&mut self.world,
&mut self.resources
);
}
}
}
}Stages in Bevy run once every game tick. By passing the schedule to wakeup, we now have a way to replicate that behavior with timers: a “pass” (or Bevy Stage) is a timer that reschedules itself upon wakeup:
pub trait Pass {
// Default to 1 to run every tick.
const RUN_EVERY: usize = 1;
fn wakeup(
&mut self,
world: &mut World,
resources: &mut Resources
);
}
impl Timer for T
where
T: Pass + 'static,
{
fn wakeup(
self: Box<Self>,
schedule: &mut TimingWheelHierarchy,
world: &mut World,
resources: &mut Resources
) {
let mut timer = *self;
<Self as Pass>::wakeup(&mut timer, world, resources);
app.schedule(Self::RUN_EVERY - 1, timer);
}
}Now let us consider implementing grenades with this new timer system. Now, grenades are no longer an resource and thus may be created and inspected independently. Additionally, their time is expressed in game ticks instead of real-time units.
struct Grenade {
entity: Entity,
}
impl Timer for Grenade {
fn wakeup(
self: Box<Self>,
_: &mut TimingWheelHierarchy,
world: &mut World,
_: &mut Resources
) {
let Grenade { entity } = *self;
// Despawn the entity and perform whatever other action is required.
world.despawn(entity);
// Timer is automatically destroyed here.
}
}Although we can replace stages outright with timers, it would be just as useful to supplement stages with timers. This can be done by making the TimingWheelHierarchy a resource.