2020-04-25

Egregoria (previously Scale) Devblog #3

If you want to know what Egregoria is about, here's the first post.

Stats

Since the last post, Egregoria got:

  • ~2k "unique" visits on the blog according to OVH (although I suspect lots of them are bots)
  • 42 new stars
  • 157 new commits
  • 11,161 additions
  • 2,798 deletions

Pedestrians

Sidewalks

After reworking the map model, it was time to add pedestrians.
The first step was to add sidewalks and crosswalks for them to walk on. Thanks to the map rework (see last post), I could model a sidewalk just like a driving lane.
Since walking lanes are bidirectional, but driving lanes aren't, I had to rework the ways lanes are traversed and ended up with a model like this. 

pub enum TraverseDirection {
    Forward,
    Backward,
}
pub enum TraverseKind {
    Lane(LaneID),
    Turn(TurnID),
}
pub struct Traversable {
    pub kind: TraverseKind,
    pub dir: TraverseDirection,
}

pub enum ItineraryKind {
    None,
    Simple(Traversable),
    Route {
        cursor: usize,
        path: Vec<Traversable>,
    },
}
pub struct Itinerary {
    kind: ItineraryKind,
    local_path: PolyLine,
}

That way, pedestrians, cars and potentially other ways of locomotions (even trains!) can share the same routing code.

However, pedestrian lanes do not work like driving lanes at intersections, since they can't cross from a road to another one on the other side.
cant cross

So the lanes are sorted by angle and turns are generated, alternating between turns that become crosswalks, and turns that become corners.
However, this raised the expected issue of "holes" appearing when driving turns are not the same as sidewalks turns.

holes

Theses holes appear because e.g. cars coming from the bottom left lane cannot turn left, and thus the turn is not rendered.
One solution would be to render intersections "as a whole" not considering individual turns, but it could make the code much more complicated.

Social forces model

Now that there was something to walk on, I moved on to adding a pedestrian simulation.
I skimmed through literature about pedestrians behavior and saw that the "Social Forces Model" was widely cited and went with this paper from 1998.
The idea is to consider repulsive forces (other pedestrians, obstacles) and attractive forces (objective, family, sidewalks), where most force have an exponential potential, and just run a classical particle simulation.

Here's a picture from their paper showing how a queue of pedestrians emerges from the simple behavior when in a confined tunnel.

confined space

Black dots want to go left and white dots the the right, the size of the dots is proportional to their speed.

And here's my reproduction:

reproduction

As you can see, the same pattern emerges.
I then spent some time tweaking the behaviors to get what I wanted, adding some rules like estimating density and reducing safe space when crowded.

Now that I had pedestrian behavior I just had to add it to the simulation.
This means making them scared of cars, stay on the sidewalks and add a simple 2D model: Head and shoulders with arms going back and forth.

Final look:

pedestrian

Because writing bugfree code is impossible, I messed up my projection code which made pedestrians irresistibly attracted to lane tips, which resulted in "black holes" of pedestrians.

hole

After fixing it, that was it ! I now had pedestrians going around and be happy. :-)

I could also parallelize the code easily, reaching up to 10 FPS with 100k cars and 100k pedestrians going around on a map the size of Paris, all of it running on my i5-7300HQ.

Video

For a more dynamic update, I made a short video resuming my work the past 2 months:

New renderer

Until now, all my rendering was done thanks to the excellent ggez crate, however I wanted to learn more about GPUs and the rendering process to make fancy effects, and also wanted to add a wasm target.

That's why I decided to write my own renderer using wgpu-rs, and thanks to sotrh's "Learn wgpu" tutorial, it only took me a week to get some basic shapes working.

shaders

Triangles and shaders, the base of many great things

WebGPU's goal is to have a clean interface for rendering on the web, so I should eventually be able to build a Rust web client to access Egregoria and not have to mess with Javascript, which is a relief.

What next ?

Next steps will be adding homes and workplaces as a basis of human schedules and city-level behaviors.
It includes fast pathing/routing, cars parking and being used by pedestrians, buildings as part of the navigation model and many small refactors.

Once this work is terminated, I'll have officialy reached the milestone I set in january. 🎉

< Back to list