2020-06-23

Egregoria (previously Scale) Devblog #4

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

Stats

Since the last post 58 days ago, Egregoria got:

  • ~1.2k unique visits
  • 17 new stars
  • 141 new commits
  • 7,806 additions
  • 7,236 deletions

New renderer

The renderer/front-end was entirely rewrote and moved from ggez to wgpu + winit.
I worked on it until there was enough to draw the same things as the original renderer, but didn't go further since actual features needed work too.
I learned a lot about how to fit I/O and graphics together, and how GPUs works.
I now understand shaders and the whole graphical pipeline better, which I hope will result in beautiful roads in the future once I take the time.

This rework also produced its share of graphical bugs which I love, here's a few samples:

Leaking traffic lights

Windows XP solitaire nostalgia

Octopus roads

I also have to link to sotrh's wgpu tutorial since it's the best place to start if you want to learn it.

Curved roads

Until now, all roads were straight and turns were curved.
This was very simple and practical but not very realistic, and made me do huge intersections to imitate curved roads.

So I took the time to implement a home-made smart cubic Bézier curve flattening algorithm. It works by locally approximating the curvature using the derivative and 2nd derivative, and making a step forward based on the tolerance. Which, in code, looks like this:

fn step(curve: &Bezier, t: f32, tolerance: f32) -> f32 {
    let curvature = curve
        .derivative(t)
        .normalize()
        .perp_dot(curve.derivative_2(t))
        .abs()
        .sqrt();
    (tolerance / curvature).min(0.15)
}

This is probably too simple, and I could have used lyon's flattening algorithm, but it works, is fast and lyon is a big dependency I don't want right now.

I also had to learn how to split a Bézier curve into 2 Bézier curves, which is surprisingly elegant!
A good schema is worth a thousand words:

L2 and L3 are the control points for the first part of the curve if splitted at L4, and R2 and R3 are the control points for the second part.

Result

Beautiful curved roads !

For the moment, only one curve is allowed between two intersections (in gray), but multiple curves roads will be possible in the future.

If you follow a bit, you'll notice that the hole problem from post #3 was solved by filling the intersections with concrete.

Parking

Cars are nice to drive around, but they also need a place to park.
I started to use Github projects as a Kanban board, and split the task into 3 parts:

  1. Parking spots generation, managed by the Map.
    This was pretty trivial, parking lanes are generated which remember some evenly spaced spots on it.

  2. Parking spots reservation and queries i.e. "I want to park near here, where is the closest available spot?".
    The procedure will look for near parking lanes based on actual turns just like if you went to your destination and then start to look for spots, then it will reserve that spot so no one else can park there.

  3. Park registration and animation for cars.
    It isn't a full realistic parking motion yet, just went with a Bézier curve from the car position into the spot. It can be updated later but it works.

Once this was all implemented, cars could go around and park everywhere!

Pathfinding

Implemented A* pathfinding for cars and pedestrians using the pathfinding crate.

I had a bit of a challenge since I consider a lane as a node and turns as edges to optimize a bit, so the edge case of "I want to go from a lane to the same lane but behind me" can be a bit tricky.
I solved it by making a dummy start which has the same neighbors as the start but isn't the start. That way even if start = end, dummy_start ≠ end.

flat_spatial

I've recently learned to embrace open source, opening some PRs on different Rust projects.

But I had never released a crate and wanted to know the process a little bit. So I extracted what I thought was a useful data structure into a crate:
flat_spatial

flat_spatial is a crate dedicated to dynamic spatial partitioning structures that are not based on trees (which are recursive) but on simple flat structures such as a grid/hashmap of cells.
Using grids or other flat structures makes for very fast updates (constant time) and even fast queries, provided they are adapted to the structure.

DenseGrid is the structure used by cars to query their neighbors, it's an array of cells on a grid containing points that can be moved or deleted without reallocating the whole structure (as is common with kd-trees).

Here's a schema from the documentation:

If you have a suggestion or a problem and you think about using it, please file an issue as I'm very open to extending the crate.

What next ?

Next steps will be adding homes and workplaces, with humans going to work and coming back using their cars or their feets.

Building generation and integration into the navmesh should take some time and be worthy of the next blogpost.

I'm also planning on trying to integrate sound/music, but the situation with winit 22 + rodio on windows is a bit scary at the moment.

< Back to list