flow/
flow.rs

1//! Crowds finding their way: every agent follows one shared flow field
2//! around walls and through (slow) mud to the goal.
3//!
4//!   `cargo run --release --example flow`
5//!   `AGENTS=200000 cargo run --release --example flow`
6//!   `HEADLESS=1 AGENTS=1000000 TICKS=600 cargo run --release --example flow`
7//!
8//! Mouse: left click moves the goal; drag with the right button to pan,
9//! scroll to zoom. Keys: H shows the distance field, Space pause,
10//! Escape quit.
11//!
12//! Shows: `NavGrid` and `FlowField` (one search shared by every agent),
13//! looked up from `par_for_each`, recomputed when the goal moves.
14
15use ponko::*;
16use serde::{Deserialize, Serialize};
17
18/// World units per grid cell.
19// ANCHOR: constants
20const CELL: f32 = 4.0;
21const MAP: UVec2 = uvec2(320, 180); // 1280 x 720 world units
22const SPEED: f32 = 40.0;
23const MUD: u8 = 6;
24// ANCHOR_END: constants
25
26fn env_number(name: &str, default: f64) -> f64 {
27    std::env::var(name).ok().and_then(|v| v.parse().ok()).unwrap_or(default)
28}
29
30#[derive(Serialize, Deserialize, Clone, Copy)]
31struct Agent {
32    vel: Vec2,
33}
34
35/// The map, the field, and where everyone is going.
36struct Paths {
37    nav: NavGrid,
38    flow: FlowField,
39    goal: Vec2,
40    /// Milliseconds the last `compute` took.
41    compute_ms: f32,
42}
43
44impl Paths {
45    fn set_goal(&mut self, goal: Vec2) {
46        let start = Instant::now();
47        self.goal = goal;
48        self.flow.compute(&self.nav, &[goal]);
49        self.compute_ms = start.elapsed().as_secs_f32() * 1000.0;
50    }
51}
52
53/// Walls in blobs, a few mud patches, and a border, from `seed`.
54fn make_map(seed: u64) -> NavGrid {
55    let mut nav = NavGrid::new(MAP.x, MAP.y, CELL);
56    let mut rng = Rng::new(seed);
57    let mut blob = |nav: &mut NavGrid, cost: u8, r: f32| {
58        let c = vec2(rng.range(0.0, MAP.x as f32), rng.range(0.0, MAP.y as f32));
59        for y in (c.y - r).max(0.0) as u32..((c.y + r) as u32).min(MAP.y) {
60            for x in (c.x - r).max(0.0) as u32..((c.x + r) as u32).min(MAP.x) {
61                if vec2(x as f32, y as f32).distance(c) < r {
62                    nav.set_cost(x, y, cost);
63                }
64            }
65        }
66    };
67    for _ in 0..14 {
68        blob(&mut nav, MUD, 14.0);
69    }
70    for _ in 0..90 {
71        blob(&mut nav, NavGrid::WALL, 6.0);
72    }
73    for x in 0..MAP.x {
74        nav.set_cost(x, 0, NavGrid::WALL);
75        nav.set_cost(x, MAP.y - 1, NavGrid::WALL);
76    }
77    for y in 0..MAP.y {
78        nav.set_cost(0, y, NavGrid::WALL);
79        nav.set_cost(MAP.x - 1, y, NavGrid::WALL);
80    }
81    nav
82}
83
84/// A random walkable point.
85fn walkable_point(nav: &NavGrid, rng: &mut Rng) -> Vec2 {
86    loop {
87        let p = vec2(rng.range(0.0, MAP.x as f32), rng.range(0.0, MAP.y as f32)) * CELL;
88        if nav.walkable(p) {
89            return p;
90        }
91    }
92}
93
94// ANCHOR: steer
95/// Every agent steers along the field; mud slows it down, walls stop it.
96fn steer(ctx: &mut Ctx) {
97    let dt = ctx.dt();
98    let random = ctx.random();
99    // Taken out for the query, which borrows the world, then put back.
100    let paths = ctx.world.remove_resource::<Paths>().expect("paths");
101    ctx.world
102        .query::<(Entity, &mut Transform2D, &mut Agent)>()
103        .par_for_each(|(e, t, a)| {
104            let mut rng = random.of(e);
105            let cell = paths.nav.cell_at(t.position);
106            let slow = cell.and_then(|c| paths.nav.cost(c.x, c.y)).unwrap_or(1).max(1) as f32;
107            let want = paths.flow.direction_at(t.position) * (SPEED / slow);
108            a.vel = a.vel.lerp(want, 0.15) + rng.unit_vec2() * 3.0;
109            // Slide along walls instead of walking into them.
110            let next = t.position + a.vel * dt;
111            if paths.nav.walkable(next) {
112                t.position = next;
113            } else if paths.nav.walkable(vec2(next.x, t.position.y)) {
114                t.position.x = next.x;
115            } else if paths.nav.walkable(vec2(t.position.x, next.y)) {
116                t.position.y = next.y;
117            }
118        });
119    ctx.world.insert_resource(paths);
120}
121// ANCHOR_END: steer
122
123fn setup(ctx: &mut Ctx, agents: usize, texture: Option<Texture>) {
124    let seed = 7;
125    let nav = make_map(seed);
126    let mut rng = Rng::new(seed ^ 1);
127    let goal = walkable_point(&nav, &mut rng);
128    let mut paths = Paths {
129        nav,
130        flow: FlowField::new(),
131        goal,
132        compute_ms: 0.0,
133    };
134    paths.set_goal(goal);
135    ctx.world.reflect::<Agent>();
136    let starts: Vec<Vec2> = (0..agents).map(|_| walkable_point(&paths.nav, &mut rng)).collect();
137    ctx.world.insert_resource(paths);
138    match texture {
139        Some(tex) => ctx.world.spawn_batch(starts.into_iter().map(|p| {
140            (
141                Transform2D::at(p),
142                Sprite::new(tex).with_color(Color::rgb(1.0, 0.85, 0.4)),
143                Agent { vel: Vec2::ZERO },
144            )
145        })),
146        None => ctx.world.spawn_batch(
147            starts
148                .into_iter()
149                .map(|p| (Transform2D::at(p), Agent { vel: Vec2::ZERO })),
150        ),
151    };
152}
153
154fn draw_map(ctx: &mut Ctx) -> impl FnMut(&mut Ctx) + use<> {
155    let (w, h) = (MAP.x as usize, MAP.y as usize);
156    let tex = ctx.create_texture(MAP.x, MAP.y, &vec![0; w * h * 4]);
157    ctx.set_texture_filter(&tex, TextureFilter::Nearest);
158    let mut pixels = vec![0u8; w * h * 4];
159    let mut heat = false;
160    let mut drawn: Option<(Vec2, bool)> = None;
161    move |ctx: &mut Ctx| {
162        if ctx.key_pressed(Key::H) {
163            heat = !heat;
164        }
165        let paths = ctx.world.resource::<Paths>();
166        let goal = paths.goal;
167        if drawn != Some((goal, heat)) {
168            drawn = Some((goal, heat));
169            for y in 0..h {
170                for x in 0..w {
171                    let center = paths.nav.center_of(uvec2(x as u32, y as u32));
172                    let px = match paths.nav.cost(x as u32, y as u32).unwrap() {
173                        NavGrid::WALL => [40, 44, 52, 255],
174                        MUD => [70, 52, 30, 255],
175                        _ => [24, 40, 30, 255],
176                    };
177                    let px = match paths.flow.distance_at(center) {
178                        Some(d) if heat && px[0] != 40 => {
179                            let t = (d / 1500.0).min(1.0);
180                            [
181                                (255.0 * (1.0 - t)) as u8 / 2 + px[0] / 2,
182                                px[1],
183                                (255.0 * t) as u8 / 2 + px[2] / 2,
184                                255,
185                            ]
186                        }
187                        _ => px,
188                    };
189                    pixels[(y * w + x) * 4..][..4].copy_from_slice(&px);
190                }
191            }
192            ctx.update_texture(&tex, &pixels);
193        }
194        ctx.clear(Color::BLACK);
195        let size = MAP.as_vec2() * CELL;
196        ctx.draw_ex(
197            &tex,
198            size / 2.0,
199            DrawParams {
200                scale: Vec2::splat(CELL),
201                z: -10.0,
202                ..Default::default()
203            },
204        );
205        ctx.draw_circle(goal, 8.0, Color::rgba(1.0, 0.3, 0.3, 0.8));
206    }
207}
208
209fn click_to_move_goal(ctx: &mut Ctx) {
210    if ctx.mouse_pressed(MouseButton::Left) && !ctx.mouse_over_ui() {
211        let at = ctx.mouse_world();
212        let paths = ctx.world.resource_mut::<Paths>();
213        if paths.nav.walkable(at) {
214            paths.set_goal(at);
215        }
216    }
217    if ctx.key_pressed(Key::Space) {
218        if ctx.is_paused() { ctx.resume() } else { ctx.pause() }
219    }
220    if ctx.key_pressed(Key::Escape) {
221        ctx.quit();
222    }
223}
224
225fn hud(ctx: &mut Ctx) {
226    let panel = Rect::new(12.0, 12.0, 260.0, 104.0);
227    ctx.ui_panel(panel);
228    let at = panel.min + ctx.ui_style.padding;
229    let agents = ctx.world.query::<&Agent>().count();
230    let ms = ctx.world.resource::<Paths>().compute_ms;
231    let text = format!(
232        "{agents} agents, {:.0} FPS\nfield: {}x{} cells, {ms:.2} ms\nclick: new goal   H: distances",
233        ctx.fps(),
234        MAP.x,
235        MAP.y
236    );
237    ctx.ui_label(at, &text);
238}
239
240fn main() {
241    let agents = env_number("AGENTS", 20_000.0) as usize;
242    if env_number("HEADLESS", 0.0) != 0.0 {
243        let ticks = env_number("TICKS", 600.0) as u64;
244        let mut start = Instant::now();
245        let mut rng = Rng::new(99);
246        let mut field_ms = Vec::new();
247        Game::new("flow", 1, 1)
248            .sim_system(steer)
249            .sim_system(move |ctx: &mut Ctx| {
250                // A new goal every 2 seconds, like a player clicking around.
251                let tick = ctx.sim_tick();
252                if tick % 120 == 119 {
253                    let paths = ctx.world.resource_mut::<Paths>();
254                    let goal = walkable_point(&paths.nav, &mut rng);
255                    paths.set_goal(goal);
256                    field_ms.push(paths.compute_ms);
257                    let avg = field_ms.iter().sum::<f32>() / field_ms.len() as f32;
258                    println!(
259                        "new goal at tick {tick}: field {:.2} ms (avg {avg:.2})",
260                        paths.compute_ms
261                    );
262                }
263            })
264            .run_headless(ticks, |ctx| {
265                setup(ctx, agents, None);
266                start = Instant::now();
267            });
268        let secs = start.elapsed().as_secs_f64();
269        println!(
270            "{agents} agents, {ticks} ticks: {:.2} ms/tick ({:.0} ticks/s)",
271            secs * 1e3 / ticks as f64,
272            ticks as f64 / secs
273        );
274        return;
275    }
276
277    Game::new("Crabby Engine: flow fields", 1280, 720)
278        .sim_system(steer)
279        .system(click_to_move_goal)
280        .system(camera_controls)
281        .system(hud)
282        .run(move |ctx| {
283            let dot = ctx.create_texture(2, 2, &[255; 2 * 2 * 4]);
284            setup(ctx, agents, Some(dot));
285            draw_map(ctx)
286        });
287}
flow/flow.rs

flow/
flow.rs
