search

Uriopass / Egregoria

3D City Builder without a grid
http://douady.paris/blog/
GNU General Public License v3.0
1.49k stars 51 forks source link

Gridlocks #23

Closed Uriopass closed 3 years ago

Uriopass commented 3 years ago

Currently, cars can get stuck in a 3-way (or more) gridlock since the priority system only looks at couples. So if cars A, B and C each want to let another car go in cycle, a gridlock happens.

This is a very hard problem though, since some global authority (intersection based ? Cluster based ?) Need to be put in place (or maybe not, see comment).

Uriopass commented 3 years ago

I had another idea on how to tackle this.

When a car stops, it displays it's id behind it, then displays the id shown on the car that blocks it. Then, if a car sees it's own ID, it knows there's a cycle (and therefore a gridlock) and goes into panic mode and just drives through everything for a couple of seconds.

There are many ways to make this smoother, but this is the gist, and I'm pretty sure it should work. It shouldn't have any impact on performance too.

Uriopass commented 3 years ago

Implemented in e96cabe1841ec745f4bf83c1b9ba47dc4341eb60 and it works very well :-) here's a video to show the three lock scenario being resolved and a more complicated example where lots of gridlocks appear and are resolved. (thanks github for supporting video!)

https://user-images.githubusercontent.com/5420739/104122307-948bbf00-5344-11eb-8367-e4ae0d6d1db3.mp4

You might probably think that the 3 grid lock is a bit disappointing because they all start at the same time and run over each other. But this is an artefact of the test since they all start stopped at the same time. In a real situation, some car will stop last and break the symmetry and only one car will start before the others.