flock_parallelism/

flock-parallelism.rs

//! A flock of butterflies, each butterfly's next position and heading read from the
//! previous tick's own neighborhood by the three rules of a flock:
//! separation, alignment and cohesion.
//! The flock is kept in cell order: one array of positions and one of
//! each butterfly's velocity, sorted by the cell of a box each butterfly lies in,
//! with the start of every cell beside them. A tick steers each cell's butterflies
//! against the cells around it, each cell its own task on the workers the
//! engine builds at startup, with nothing configured for it, and then
//! sorts the next arrays into cells again by one counting pass. The
//! flock's center, which the camera turns about, is summed by the chunked
//! fold that `mirage_engine::rayon`'s own docs show, so it reads the same
//! bits at any worker count.
//!
//! `cargo run --example flock-parallelism`. The camera holds no controls of its own:
//! it turns about the flock's center for the whole run. A panel names the
//! pool's own workers, offers three flock sizes and times the last tick. A
//! checkbox sets the same step to run one cell after another, so the tick
//! time shows the parallel run's own gain.

use core::f32::consts::{PI, TAU};
use core::ops::Range;

use mirage_engine::prelude::*;
use mirage_engine::rayon::{self, prelude::*};

/// Flock sizes the panel offers, ascending.
const FLOCK_SIZES: [u32; 3] = [1_000, 10_000, 40_000];
/// Flock size the example starts at: [`FLOCK_SIZES`]'s middle value.
const DEFAULT_FLOCK_SIZE: u32 = FLOCK_SIZES[1];

/// Cubic meters of the flock's own sphere given to each butterfly, so the
/// flock's density is the same at every size in [`FLOCK_SIZES`].
const WORLD_VOLUME_PER_BUTTERFLY: f32 = 3.0;
/// Meters between the ground and the bottom of the flock's own sphere.
const FLOCK_CLEARANCE: f32 = 4.0;
/// How far past the flock's own sphere [`Cells`]' own box reaches, as a
/// fraction of the sphere's radius, so a butterfly turning back at the bound
/// keeps a cell of its own.
const BOX_MARGIN: f32 = 1.25;

/// Meters within which a butterfly reads a neighbor's heading and position for
/// alignment and cohesion; also the side of one cell of the box.
const NEIGHBOR_RADIUS: f32 = 3.0;
/// Meters within which a butterfly steers away from a neighbor.
const SEPARATION_RADIUS: f32 = 1.3;

/// Steering acceleration scales, in 1/second, each rule's own vector is
/// multiplied by before it is added to a butterfly's velocity.
const SEPARATION_WEIGHT: f32 = 2.5;
const ALIGNMENT_WEIGHT: f32 = 1.2;
const COHESION_WEIGHT: f32 = 1.6;
/// Steering acceleration scale, in 1/second, that turns a butterfly back toward
/// the center once it leaves the flock's own sphere.
const BOUND_WEIGHT: f32 = 4.0;

/// The slowest and fastest speed a butterfly holds, in meters/second.
const MIN_SPEED: f32 = 3.0;
const MAX_SPEED: f32 = 7.0;

/// The butterfly's own source, next to the other example assets, the root
/// node the source names it under, and the image inside it the wings are
/// drawn with, read grey so a tint colors it.
const BUTTERFLY_SOURCE: &str = "examples/assets/butterfly.glb";
const BUTTERFLY_ROOT: &str = "Butterfly";
const BUTTERFLY_SKIN: &str = "butterfly-skin";
/// The tints the flock's butterflies are drawn in, one per butterfly by
/// its own integer-hash, over the grey skin; past `1.0`, since the grey
/// skin is darker than the color it stands in for.
const TINTS: [Color; 6] = [
    Color::rgb(1.8, 1.0, 0.3),
    Color::rgb(0.6, 1.0, 1.8),
    Color::rgb(1.8, 1.6, 0.5),
    Color::rgb(1.7, 1.7, 1.6),
    Color::rgb(1.7, 0.45, 0.55),
    Color::rgb(1.3, 0.7, 1.7),
];
/// How many times the model's own size a butterfly is drawn at: the model
/// is a quarter meter across, so the flock's are a meter and more.
const BUTTERFLY_SCALE: f32 = 5.0;
/// Flaps per second of a butterfly's own `Fly` clip, at the middle of the
/// spread below.
const FLAP_RATE: f32 = 2.5;
/// How far the flap groups' rates spread about [`FLAP_RATE`], as a fraction
/// of it from the slowest group to the fastest.
const FLAP_RATE_SPREAD: f32 = 0.6;
/// The three waves a group's flap rate rises and falls by, each a depth as
/// a fraction of the rate and the seconds one wave takes: a butterfly flaps
/// more and then less by turns, and the three waves never line up.
const FLAP_WAVES: [(f32, f32); 3] = [(0.35, 1.7), (0.3, 4.3), (0.25, 11.0)];
/// How many flap groups the flock shares, each with a rate that rises and
/// falls and a phase of its own: every butterfly belongs to one, so a frame
/// poses the clip this many times, never once per butterfly.
const FLAP_GROUPS: usize = 24;

/// The ground plane's side length, in meters, far enough that its edge
/// meets the horizon from the camera's height.
const GROUND_SIZE: f32 = 4000.0;
const GROUND_COLOR: Color = Color::rgb(0.4, 0.31, 0.25);

/// The sun's direction, low enough that the flock's shadow lands on clear
/// ground beside it.
const SUN_DIRECTION: Vec3 = Vec3::new(-0.8, -0.55, -0.5);
const SUN_COLOR: Color = Color::rgb(0.95, 0.92, 0.85);

const SKY_ZENITH: Color = Color::rgb(0.15, 0.22, 0.42);
const SKY_HORIZON: Color = Color::rgb(0.7, 0.48, 0.34);
const SKY_NADIR: Color = Color::rgb(0.2, 0.16, 0.14);
const SKY_LIGHT: f32 = 0.65;
/// The sky's own color under the horizon, so a butterfly's own underside and
/// the ground reflect light from the sky instead of reading black.
const SKY_GROUND: Color = Color::rgb(0.42, 0.34, 0.28);

/// The camera's height above and distance from the flock's center, each a
/// fraction of the flock's own radius, so the view frames every size.
const CAMERA_HEIGHT_FRACTION: f32 = 0.45;
const CAMERA_DISTANCE_FRACTION: f32 = 2.2;
/// How far above the flock's center the camera looks, as a fraction of
/// the flock's own radius, so the flock sits below the panel.
const CAMERA_AIM_LIFT_FRACTION: f32 = 0.25;
const CAMERA_FOV: f32 = 75.0;
/// Radians the camera turns about the flock's center per second.
const CAMERA_ANGULAR_SPEED: f32 = 0.08;

/// Butterflies a chunk of [`Butterflies::center`]'s fold sums at a time, so the sum
/// reads the same bits at any worker count.
const CENTER_CHUNK_SIZE: usize = 1024;

const PANEL_PADDING: i8 = 8;

meshes! { enum Shape { Butterfly, Plane } }

/// The one sky this game draws, a gradient set each frame.
#[derive(Catalog, Clone, Copy, Debug, Eq, Hash, PartialEq)]
enum Sky {
    Day,
}

impl Skyboxes for Sky {
    fn build(&self, _assets: &Assets) -> SkyboxData {
        match self {
            Self::Day => SkyboxData::gradient(SKY_ZENITH, SKY_HORIZON, SKY_NADIR)
                .lit_by(SKY_LIGHT)
                .with_ground(SKY_GROUND),
        }
    }
}

#[derive(Catalog, Clone, PartialEq, Eq, Hash)]
struct Butterfly;

/// The one clip a butterfly is posed by, named as the source names it.
#[derive(Clip, Clone, Debug, PartialEq, Eq, Hash)]
enum ButterflyClip {
    #[clip("fly")]
    Fly,
}

impl Mesh<NoParts, ButterflyClip> for Butterfly {
    fn build(&self, assets: &Assets) -> MeshData<NoParts, ButterflyClip> {
        assets
            .model(BUTTERFLY_ROOT)
            .with_texture(greyed(&assets.texture(BUTTERFLY_SKIN)))
    }
}

/// `skin` with every texel at its own grey level, its alpha kept, so a tint
/// colors it whole.
fn greyed(skin: &TextureData) -> TextureData {
    let pixels = skin
        .pixels()
        .chunks_exact(4)
        .flat_map(|texel| {
            let [red, green, blue, alpha] = [texel[0], texel[1], texel[2], texel[3]];
            let grey =
                (0.2126 * f32::from(red) + 0.7152 * f32::from(green) + 0.0722 * f32::from(blue))
                    .round() as u8;
            [grey, grey, grey, alpha]
        })
        .collect();
    TextureData::rgba8(skin.size(), pixels)
}

/// What one butterfly looks like: the flap group that poses it and the tint
/// it is drawn in, both its own for the whole run.
#[derive(Clone, Copy, Default)]
struct Kind {
    flap: u8,
    tint: u8,
}

impl Kind {
    /// The kind butterfly `index` is given, by its own integer-hash.
    fn of(index: u32) -> Self {
        Self {
            flap: (hash(index, 4) % FLAP_GROUPS as u32) as u8,
            tint: (hash(index, 5) % TINTS.len() as u32) as u8,
        }
    }
}

/// A machine of one state, holding the flap at the phase it is given: one
/// machine per flap group poses every butterfly of that group.
#[derive(Clone, Copy, Eq, PartialEq, Debug)]
enum FlapState {
    Flapping,
}

impl AnimationStates for FlapState {
    type Clip = ButterflyClip;
    type Input = f32;

    fn entry() -> Self {
        Self::Flapping
    }

    fn motion(&self, phase: &f32) -> Motion<ButterflyClip> {
        Motion::scrubbed(ButterflyClip::Fly, *phase)
    }

    fn next(&self, _phase: &f32, _at: Progress) -> Option<Transition<Self>> {
        None
    }
}

/// The phase flap group `group` holds `flown` seconds into the run: the
/// flaps its own rate has run, spread about [`FLAP_RATE`] by
/// [`FLAP_RATE_SPREAD`], the rate rising and falling by [`FLAP_WAVES`] at
/// the group's own offsets, from the group's own start. The count is the
/// sum of the rate over the seconds `flown`, taken whole rather than tick by
/// tick, so no step adds up an error.
fn flap_phase(group: usize, flown: f32) -> f32 {
    let share = group as f32 / FLAP_GROUPS as f32;
    let rate = FLAP_RATE * (1.0 + FLAP_RATE_SPREAD * (share - 0.5));
    let waved: f32 = FLAP_WAVES
        .iter()
        .enumerate()
        .map(|(wave, &(depth, period))| {
            let angular = TAU / period;
            let offset = hash_unit(group as u32, 6 + wave as u32) * TAU;
            -depth / angular * (angular * flown + offset).cos()
        })
        .sum();
    (rate * (flown + waved) + share).fract()
}

/// The sphere the flock is bound to: its center, held above the ground by
/// [`FLOCK_CLEARANCE`], and its radius, sized so each butterfly has
/// [`WORLD_VOLUME_PER_BUTTERFLY`].
#[derive(Clone, Copy)]
struct World {
    center: Vec3A,
    radius: f32,
}

impl World {
    fn for_flock(count: u32) -> Self {
        let radius = (count as f32 * WORLD_VOLUME_PER_BUTTERFLY * 3.0 / (4.0 * PI)).cbrt();
        Self {
            center: Vec3A::new(0.0, radius + FLOCK_CLEARANCE, 0.0),
            radius,
        }
    }
}

/// The box of cells the flock is kept in: cubes [`NEIGHBOR_RADIUS`] across,
/// `side` to an axis, from `least` on every axis.
#[derive(Clone, Copy)]
struct Cells {
    side: usize,
    least: Vec3A,
}

impl Cells {
    /// The box over `world`'s sphere and [`BOX_MARGIN`] past it.
    fn covering(world: World) -> Self {
        let reach = world.radius * BOX_MARGIN;
        let side = ((2.0 * reach) / NEIGHBOR_RADIUS).ceil().max(1.0) as usize;
        Self {
            side,
            least: world.center - Vec3A::splat(reach),
        }
    }

    /// How many cells the box holds.
    fn count(self) -> usize {
        self.side * self.side * self.side
    }

    /// The cell `position` lies in, held inside the box on every axis.
    fn of(self, position: Vec3A) -> usize {
        let scaled = (position - self.least) / NEIGHBOR_RADIUS;
        let most = (self.side - 1) as f32;
        let x = scaled.x.clamp(0.0, most) as usize;
        let y = scaled.y.clamp(0.0, most) as usize;
        let z = scaled.z.clamp(0.0, most) as usize;
        (x * self.side + y) * self.side + z
    }

    /// `cell` and every cell beside it, at most 27, inside the box.
    fn around(self, cell: usize) -> impl Iterator<Item = usize> {
        let side = self.side;
        let z = cell % side;
        let y = (cell / side) % side;
        let x = cell / (side * side);
        let span = move |at: usize| at.saturating_sub(1)..(at + 2).min(side);
        span(x).flat_map(move |cx| {
            span(y).flat_map(move |cy| span(z).map(move |cz| (cx * side + cy) * side + cz))
        })
    }
}

/// The flock: every butterfly's position and velocity in cell order, where each
/// cell's butterflies start, and the arrays the next tick is written into.
struct Butterflies {
    cells: Cells,
    /// Where each cell's butterflies start, and one more for the end of the last.
    start: Vec<u32>,
    position: Vec<Vec3A>,
    velocity: Vec<Vec3A>,
    /// Each butterfly's kind, in the same order.
    kind: Vec<Kind>,
    next_position: Vec<Vec3A>,
    next_velocity: Vec<Vec3A>,
    next_kind: Vec<Kind>,
    /// The cell each butterfly of the next arrays lies in.
    next_cell: Vec<u32>,
}

impl Butterflies {
    /// `count` butterflies scattered through `world`'s sphere, each with a level
    /// heading at [`MIN_SPEED`], sorted into cells.
    fn scattered(count: u32, world: World) -> Self {
        let cells = Cells::covering(world);
        let count = count as usize;
        let mut swarm = Self {
            cells,
            start: vec![0; cells.count() + 1],
            position: vec![Vec3A::ZERO; count],
            velocity: vec![Vec3A::ZERO; count],
            kind: vec![Kind::default(); count],
            next_position: Vec::with_capacity(count),
            next_velocity: Vec::with_capacity(count),
            next_kind: Vec::with_capacity(count),
            next_cell: Vec::with_capacity(count),
        };
        for index in 0..count as u32 {
            let radius = world.radius * hash_unit(index, 0).cbrt();
            let inclination = hash_unit(index, 1) * PI;
            let azimuth = hash_unit(index, 2) * TAU;
            let position = world.center
                + Vec3A::new(
                    radius * inclination.sin() * azimuth.cos(),
                    radius * inclination.cos(),
                    radius * inclination.sin() * azimuth.sin(),
                );
            let heading = hash_unit(index, 3) * TAU;
            let velocity = Vec3A::new(heading.cos(), 0.0, heading.sin()) * MIN_SPEED;
            swarm.next_position.push(position);
            swarm.next_velocity.push(velocity);
            swarm.next_kind.push(Kind::of(index));
            swarm.next_cell.push(cells.of(position) as u32);
        }
        swarm.sort();
        swarm
    }

    /// One tick of `dt` seconds: every cell's butterflies steered against the
    /// cells around it into the next arrays, on the engine's workers or one
    /// cell after another, then the next arrays sorted into cells again.
    fn step(&mut self, dt: f32, world: World, sequential: bool) {
        let Self {
            cells,
            start,
            position,
            velocity,
            kind,
            next_position,
            next_velocity,
            next_kind,
            next_cell,
        } = self;
        let flock = Flying {
            cells: *cells,
            start,
            position,
            velocity,
            kind,
        };
        let mut out = CellOut::split(&flock, next_position, next_velocity, next_kind, next_cell);
        let steer = |(cell, out): (usize, &mut CellOut<'_>)| flock.steer(cell, out, dt, world);
        if sequential {
            out.iter_mut().enumerate().for_each(steer);
        } else {
            out.par_iter_mut().enumerate().for_each(steer);
        }
        drop(out);
        self.sort();
    }

    /// Sorts the next arrays into the current ones by cell: a count per
    /// cell, a running total, and a placement in order, so the result reads
    /// the same at any worker count.
    fn sort(&mut self) {
        self.start.iter_mut().for_each(|start| *start = 0);
        for &cell in &self.next_cell {
            self.start[cell as usize + 1] += 1;
        }
        for cell in 0..self.cells.count() {
            self.start[cell + 1] += self.start[cell];
        }
        let mut fill = self.start.clone();
        for (index, &cell) in self.next_cell.iter().enumerate() {
            let at = fill[cell as usize] as usize;
            fill[cell as usize] += 1;
            self.position[at] = self.next_position[index];
            self.velocity[at] = self.next_velocity[index];
            self.kind[at] = self.next_kind[index];
        }
    }

    /// The flock's center: positions summed in fixed chunks and then
    /// folded in order, the fold that `mirage_engine::rayon`'s own docs
    /// show, so it reads the same bits at any worker count.
    fn center(&self) -> Vec3A {
        if self.position.is_empty() {
            return Vec3A::ZERO;
        }
        let sum: Vec3A = self
            .position
            .par_chunks(CENTER_CHUNK_SIZE)
            .map(|chunk| chunk.iter().copied().sum::<Vec3A>())
            .collect::<Vec<Vec3A>>()
            .into_iter()
            .sum();
        sum / self.position.len() as f32
    }

    /// Every butterfly's position, velocity and kind, in cell order.
    fn each(&self) -> impl Iterator<Item = (Vec3A, Vec3A, Kind)> + '_ {
        self.position
            .iter()
            .zip(&self.velocity)
            .zip(&self.kind)
            .map(|((&position, &velocity), &kind)| (position, velocity, kind))
    }
}

/// The flock as one tick reads it: the current arrays and the cells they
/// are sorted by, shared by every cell's step.
struct Flying<'a> {
    cells: Cells,
    start: &'a [u32],
    position: &'a [Vec3A],
    velocity: &'a [Vec3A],
    kind: &'a [Kind],
}

impl Flying<'_> {
    /// The butterflies of `cell`, as a range of the arrays.
    fn range(&self, cell: usize) -> Range<usize> {
        self.start[cell] as usize..self.start[cell + 1] as usize
    }

    /// Steers every butterfly of `cell` by separation, alignment and cohesion
    /// against the butterflies of the cells around it, and back toward the center
    /// once it leaves `world`'s sphere, writing the next state into `out`.
    fn steer(&self, cell: usize, out: &mut CellOut<'_>, dt: f32, world: World) {
        let mut around: [Range<usize>; 27] = core::array::from_fn(|_| 0..0);
        let mut near_count = 0;
        for near in self.cells.around(cell) {
            around[near_count] = self.range(near);
            near_count += 1;
        }
        let around = &around[..near_count];

        for (at, index) in self.range(cell).enumerate() {
            let position = self.position[index];
            let velocity = self.velocity[index];
            let mut separation = Vec3A::ZERO;
            let mut heading_sum = Vec3A::ZERO;
            let mut position_sum = Vec3A::ZERO;
            let mut neighbors = 0u32;

            for near in around {
                for other in near.clone() {
                    if other == index {
                        continue;
                    }
                    let offset = position - self.position[other];
                    let squared = offset.length_squared();
                    if squared > NEIGHBOR_RADIUS * NEIGHBOR_RADIUS || squared <= f32::EPSILON {
                        continue;
                    }
                    if squared < SEPARATION_RADIUS * SEPARATION_RADIUS {
                        separation += offset / squared.sqrt();
                    }
                    heading_sum += self.velocity[other];
                    position_sum += self.position[other];
                    neighbors += 1;
                }
            }

            let mut steering = separation * SEPARATION_WEIGHT;
            if neighbors > 0 {
                let share = 1.0 / neighbors as f32;
                steering += (heading_sum * share - velocity) * ALIGNMENT_WEIGHT
                    + (position_sum * share - position) * COHESION_WEIGHT;
            }
            let from_center = position - world.center;
            if from_center.length() > world.radius {
                steering -= from_center.normalize() * BOUND_WEIGHT;
            }

            let next = velocity + steering * dt;
            let speed = next.length().clamp(MIN_SPEED, MAX_SPEED);
            let next_velocity = next.normalize_or_zero() * speed;
            let next_position = position + next_velocity * dt;
            out.position[at] = next_position;
            out.velocity[at] = next_velocity;
            out.kind[at] = self.kind[index];
            out.cell[at] = self.cells.of(next_position) as u32;
        }
    }
}

/// One cell's share of the next arrays, written by that cell's step alone.
struct CellOut<'a> {
    position: &'a mut [Vec3A],
    velocity: &'a mut [Vec3A],
    kind: &'a mut [Kind],
    cell: &'a mut [u32],
}

impl<'a> CellOut<'a> {
    /// The next arrays split into one share per cell of `flock`, in cell
    /// order, each as long as that cell's range.
    fn split(
        flock: &Flying<'_>,
        position: &'a mut Vec<Vec3A>,
        velocity: &'a mut Vec<Vec3A>,
        kind: &'a mut Vec<Kind>,
        cell: &'a mut Vec<u32>,
    ) -> Vec<Self> {
        let count = flock.position.len();
        position.resize(count, Vec3A::ZERO);
        velocity.resize(count, Vec3A::ZERO);
        kind.resize(count, Kind::default());
        cell.resize(count, 0);
        let mut out = Vec::with_capacity(flock.cells.count());
        let mut position = position.as_mut_slice();
        let mut velocity = velocity.as_mut_slice();
        let mut kind = kind.as_mut_slice();
        let mut cell = cell.as_mut_slice();
        for at in 0..flock.cells.count() {
            let len = flock.range(at).len();
            let (own, rest) = position.split_at_mut(len);
            position = rest;
            let (own_velocity, rest) = velocity.split_at_mut(len);
            velocity = rest;
            let (own_kind, rest) = kind.split_at_mut(len);
            kind = rest;
            let (own_cell, rest) = cell.split_at_mut(len);
            cell = rest;
            out.push(Self {
                position: own,
                velocity: own_velocity,
                kind: own_kind,
                cell: own_cell,
            });
        }
        out
    }
}

/// An integer-hash of `seed` and `salt`.
fn hash(seed: u32, salt: u32) -> u32 {
    let mut x = seed ^ salt.wrapping_mul(0x9E37_79B9);
    x ^= x >> 16;
    x = x.wrapping_mul(0x7FEB_352D);
    x ^= x >> 15;
    x = x.wrapping_mul(0x846C_A68B);
    x ^= x >> 16;
    x
}

/// `hash`, scaled to `0.0..1.0`.
fn hash_unit(seed: u32, salt: u32) -> f32 {
    hash(seed, salt) as f32 / u32::MAX as f32
}

/// The load a player chooses: how many butterflies the flock holds, and whether
/// the step below runs one cell after another instead of on the engine's
/// workers.
struct Settings {
    flock_size: u32,
    sequential: bool,
}

impl Default for Settings {
    fn default() -> Self {
        Self {
            flock_size: DEFAULT_FLOCK_SIZE,
            sequential: false,
        }
    }
}

struct Flock {
    settings: Settings,
    applied_flock_size: u32,
    world: World,
    butterflies: Butterflies,
    flaps: [Animator<Butterfly, FlapState>; FLAP_GROUPS],
    /// Seconds the ticks have run, which paces the flap.
    flown: f32,
    last_tick_ms: f32,
}

impl Flock {
    fn init(_ctx: &mut InitContext<'_, Self>) -> Result<Self, Error> {
        let settings = Settings::default();
        let world = World::for_flock(settings.flock_size);
        Ok(Self {
            applied_flock_size: settings.flock_size,
            butterflies: Butterflies::scattered(settings.flock_size, world),
            settings,
            world,
            flaps: core::array::from_fn(|_| Animator::new()),
            flown: 0.0,
            last_tick_ms: 0.0,
        })
    }

    /// Rebuilds the flock where the chosen size changed since the last
    /// frame.
    fn apply_settings(&mut self) {
        if self.settings.flock_size == self.applied_flock_size {
            return;
        }
        self.world = World::for_flock(self.settings.flock_size);
        self.butterflies = Butterflies::scattered(self.settings.flock_size, self.world);
        self.applied_flock_size = self.settings.flock_size;
    }

    /// The camera at `elapsed`, turning about `center` at
    /// [`CAMERA_HEIGHT_FRACTION`] and [`CAMERA_DISTANCE_FRACTION`] of the
    /// flock's own radius, looking [`CAMERA_AIM_LIFT_FRACTION`] above it.
    fn camera(center: Vec3, world: World, elapsed: f32) -> Camera {
        let angle = elapsed * CAMERA_ANGULAR_SPEED;
        let eye = center
            + Vec3::new(
                angle.cos() * world.radius * CAMERA_DISTANCE_FRACTION,
                world.radius * CAMERA_HEIGHT_FRACTION,
                angle.sin() * world.radius * CAMERA_DISTANCE_FRACTION,
            );
        let aim = center + Vec3::Y * world.radius * CAMERA_AIM_LIFT_FRACTION;
        Camera::new(View::look_at(eye, aim), Projection::perspective(CAMERA_FOV))
    }

    fn draw_ground(ctx: &mut FrameContext<'_, Self>) {
        ctx.draw(
            Plane
                .at(Transform::from_scale(Vec3::new(
                    GROUND_SIZE,
                    1.0,
                    GROUND_SIZE,
                )))
                .material(Material::lit(GROUND_COLOR).roughness(0.9)),
        );
    }

    /// Every butterfly at its own scale, turned to face its velocity, posed
    /// by the flap machine of its own group and tinted its own color.
    fn draw_butterflies(&self, ctx: &mut FrameContext<'_, Self>) {
        for (position, velocity, kind) in self.butterflies.each() {
            let rotation = Quat::from_rotation_arc(Vec3::Z, Vec3::from(velocity).normalize());
            ctx.draw(
                Butterfly
                    .at(Transform::from_scale_rotation_translation(
                        Vec3::splat(BUTTERFLY_SCALE),
                        rotation,
                        Vec3::from(position),
                    ))
                    .posed(&self.flaps[usize::from(kind.flap)])
                    .material(Material::lit(TINTS[usize::from(kind.tint)])),
            );
        }
    }

    /// The load controls, the pool's own worker count, and the last tick's
    /// own cost.
    fn panel(&mut self, ctx: &mut FrameContext<'_, Self>) {
        let workers = rayon::current_num_threads();
        let tick_ms = self.last_tick_ms;

        ctx.ui(|ui| {
            egui::Frame::new()
                .fill(egui::Color32::from_gray(24))
                .inner_margin(PANEL_PADDING)
                .corner_radius(f32::from(PANEL_PADDING))
                .show(ui, |ui| {
                    ui.label(format!("workers {workers}"));
                    ui.horizontal(|ui| {
                        for size in FLOCK_SIZES {
                            ui.radio_value(
                                &mut self.settings.flock_size,
                                size,
                                format!("{size} butterflies"),
                            );
                        }
                    });
                    ui.checkbox(&mut self.settings.sequential, "sequential update");
                    ui.separator();
                    ui.label(format!("tick time {tick_ms:.2}ms"));
                });
        });
    }
}

impl Game for Flock {
    type Meshes = Shape;
    type Sounds = NoSounds;
    type InputActions = NoInputActions;
    type Skyboxes = Sky;
    type SurfaceStyles = NoSurfaceStyles;
    type PostEffects = NoPostEffects;

    fn tick(&mut self, ctx: &mut TickContext<'_, Self>) {
        let dt = ctx.dt().as_secs_f32();
        let start = Instant::now();
        self.butterflies
            .step(dt, self.world, self.settings.sequential);
        self.last_tick_ms = start.elapsed().as_secs_f32() * 1000.0;

        self.flown += dt;
        for (group, flap) in self.flaps.iter_mut().enumerate() {
            ctx.animate(Butterfly, flap, &flap_phase(group, self.flown));
        }
    }

    fn frame(&mut self, ctx: &mut FrameContext<'_, Self>) {
        self.apply_settings();

        let center = Vec3::from(self.butterflies.center());
        let elapsed = ctx.elapsed().as_secs_f32();
        ctx.set_camera(Self::camera(center, self.world, elapsed));
        ctx.set_skybox(Sky::Day);
        ctx.light(Light::directional(SUN_DIRECTION, SUN_COLOR).shadow());

        Self::draw_ground(ctx);
        self.draw_butterflies(ctx);
        self.panel(ctx);
    }
}

fn main() {
    run(
        Config::new("Mirage: flock parallelism")
            .with_size(1280, 720)
            .with_assets([BUTTERFLY_SOURCE]),
        Flock::init,
    );
}