How we built a back end system for Uber-like maps with animated cars(blog.maddevs.io)
blog.maddevs.io
How we built a back end system for Uber-like maps with animated cars
https://blog.maddevs.io/how-we-built-a-backend-system-for-uber-like-map-with-animated-cars-on-it-using-go-29d5dcd517a
41 comments
I might be wrong but I think you're sort of confusing the way game multiplayer works for the local player, and for the other players they see.
If we're talking FPS games:
The local player is moved instantly based on their local inputs, and the server will also move them using the same rules. The local player will be corrected in any case where they don't match.
For other players that the local player sees, extrapolation in twitchy multiplayer games like FPSs is notoriously bad as the players are so hard to predict, so usually you have them running e.g. 100ms behind so you can (hopefully, depending on latency) interpolate between two data points from the server instead of trying to guess the future at all. So you still have the "behind real time" problem. The only reason the local player can avoid that is they have the benefit of local inputs. In an Uber sense they are the car.
Obviously that's a problem in games too, because now the player is shooting someone who's behind where they are on the server, so they miss. Latency Compensation fixes that - having the server rewind time to see what the client would have seen. But that won't help the cars-on-a-map problem.
Having said all that, I do agree with your point. Taking a couple of old data points and extrapolating from there should work pretty well for the cars problem. You'll see them snap back when they stop at intersections though.
If we're talking FPS games:
The local player is moved instantly based on their local inputs, and the server will also move them using the same rules. The local player will be corrected in any case where they don't match.
For other players that the local player sees, extrapolation in twitchy multiplayer games like FPSs is notoriously bad as the players are so hard to predict, so usually you have them running e.g. 100ms behind so you can (hopefully, depending on latency) interpolate between two data points from the server instead of trying to guess the future at all. So you still have the "behind real time" problem. The only reason the local player can avoid that is they have the benefit of local inputs. In an Uber sense they are the car.
Obviously that's a problem in games too, because now the player is shooting someone who's behind where they are on the server, so they miss. Latency Compensation fixes that - having the server rewind time to see what the client would have seen. But that won't help the cars-on-a-map problem.
Having said all that, I do agree with your point. Taking a couple of old data points and extrapolating from there should work pretty well for the cars problem. You'll see them snap back when they stop at intersections though.
I find programming games in general, esp FPS, fascinating because their real time requirement is so critical big lag in request/response, dealing with hotspot in code.
Why can't the driver phone be connected to rider via peer to peer. Driver sends position updates to rider in almost real time while occasional batch updates to server.
The fanciness regarding position, why not show a halo like most gps apps showing degree of accuracy?
You could all show a slight tail of previous path to give an idea of direction and speed.
I think the current uber/lyft ui experience is subpar and can be improved.
The fanciness regarding position, why not show a halo like most gps apps showing degree of accuracy?
You could all show a slight tail of previous path to give an idea of direction and speed.
I think the current uber/lyft ui experience is subpar and can be improved.
How do you do P2P? There needs to be an intermediate. You can't just ask the rider to open up some port. They need to subscribe to a channel they both can communicate over, so we are back to the server owned by Uber / Lyft. But I don't think this matters to end-users. As a frequent user, I only care whether the car will arrive on time and whether it is on the opposite side of where I am waiting...
Server can be initial handshake initiator and then p2p can take over. Webrtc already does this.
How about the opposite: Show the car with a nice interpolation using the last two positions, but with an extrapolation arrow with the point located where you think it is now. Then when the system thinks the car is moving fast and it actually comes to a quick stop, it can cut down the extrapolation arrow instead of moving the car icon backwards, and it shouldn't look as weird.
From talking to an uber engineer, he said that it's not fake, it's just delayed.
In my experience, I'd suggest it's delayed something like a month or two...
(Not that I've got a dog in the fight any more, don't forget today's the day to delete Uber!)
(Not that I've got a dog in the fight any more, don't forget today's the day to delete Uber!)
Why would they display a month old data on your home screen? Either it's realtime/delayed by a small amount of time or it's fake.
He told me it was more like 30 seconds.
If you think it's real, go to a big open space where you can see lots of empty roads, and turn it on.
Honestly I think they should do something combining the linear interpolation between data points with acceptance of the delay. Just animate between consecutive received data points, and for the first 15 seconds, replace the car with some animated sprite that visually suggests "your driver is here and is starting to come get you, even though this sprite is staying in the same place".
Thought: the customer's app probably has access to the accelerometers in the phone - maybe use that to trigger the animation of the driver moving off (the assumption that he starts moving in the same direction as he arrived would probably be "good enough". I suspect there's likely to be some reasonable numbers to use as an estimation of how quickly to animate the movement on the map based on accelerometer data and basic assumptions/measurements of how quickly drivers typically move away from a pickup.
Are you completely sure that it is fake?
For those interested, you can build a system like this that tracks sub-second GPS information, and easily scale to 100M+ writes for $10/day with 1KB payload (compare to the 62bytes in the article).
Here is a demo we threw together of it working in real life: https://youtu.be/7ALHtbC9aOM
Here is a prototype of saving 100M+ writes for $10/day: https://www.youtube.com/watch?v=x_WqBuEA7s8
Our sync system: https://github.com/amark/gun
And since we are on the topic, I highly recommend this engineering blog post by Discord on how they scaled up append-only writes in a way similar to how our system does: https://blog.discordapp.com/how-discord-stores-billions-of-m... .
Here is a demo we threw together of it working in real life: https://youtu.be/7ALHtbC9aOM
Here is a prototype of saving 100M+ writes for $10/day: https://www.youtube.com/watch?v=x_WqBuEA7s8
Our sync system: https://github.com/amark/gun
And since we are on the topic, I highly recommend this engineering blog post by Discord on how they scaled up append-only writes in a way similar to how our system does: https://blog.discordapp.com/how-discord-stores-billions-of-m... .
Yes definitely room for improvement. We're pushing at least 8 billion a day through our server.
By the way GunDB looks really cool. Nice!
By the way GunDB looks really cool. Nice!
8 billion a day! That is great! You should write an article and post it. (or if you know the OP you should mention this in the current article). What setup are you using? Thanks - I'd love to learn your tricks.
One thing that always annoys me about the Uber UI is that the oversized cars appear to be moving horribly slowly when they are sometimes actually moving pretty fast. Every time I am waiting for an Uber I find myself wanting to scream at the driver to step on the gas and go at least more than 5 mph which is what it looks like on the UI. The scaling makes it hard to tell the actual speed of the cars and the reasons when they slow down when they actually do slow down. I don't have a good solution to this though. Maybe:
- a car-game-like 3D interface where you can see the view from the driver's seat, moving at the actual sensed speed of the car, with fake (or Street View) scenery whizzing by, so while you are waiting you can see that the driver is actually moving at close to the speed limit.
- render a bunch of other random cars on the road, emulating the actual real-time density of traffic, so if the guy is chugging along slowly I as the user will blame the traffic, not the app or driver
- render rain and snow in the 3D view if that is what is slowing the driver, so I will curse at the weather for creating an unsafe situation and not the driver for going slow
- render ambulances and police cars in the 3D view if a traffic accident is reported, so i will understand that a human is hurt instead of cursing at the Uber app
- show the state of red lights in real time so that when a driver is stopped i know it is for a red light and not lazing around or lost directions. there are enough Uber cars driving around that based on aggregate GPS statistics they should be able to determine the cycle times and phases of every traffic light on major streets.
- a car-game-like 3D interface where you can see the view from the driver's seat, moving at the actual sensed speed of the car, with fake (or Street View) scenery whizzing by, so while you are waiting you can see that the driver is actually moving at close to the speed limit.
- render a bunch of other random cars on the road, emulating the actual real-time density of traffic, so if the guy is chugging along slowly I as the user will blame the traffic, not the app or driver
- render rain and snow in the 3D view if that is what is slowing the driver, so I will curse at the weather for creating an unsafe situation and not the driver for going slow
- render ambulances and police cars in the 3D view if a traffic accident is reported, so i will understand that a human is hurt instead of cursing at the Uber app
- show the state of red lights in real time so that when a driver is stopped i know it is for a red light and not lazing around or lost directions. there are enough Uber cars driving around that based on aggregate GPS statistics they should be able to determine the cycle times and phases of every traffic light on major streets.
>I find myself wanting to scream at the driver to step on the gas and go at least more than 5 mph which is what it looks like on the UI.
sorry but regardless of the UI, does this scenario even make any sense? why would your driver be going extremely slow unless there was a good reason for it? I agree that the UI can be a bit misleading with speed but i think this is a bit much
sorry but regardless of the UI, does this scenario even make any sense? why would your driver be going extremely slow unless there was a good reason for it? I agree that the UI can be a bit misleading with speed but i think this is a bit much
This is an interesting challenge, I'm building something similar for public transport, and the latency in updates tends to make things bad.
On browsers I'm using turf.js to calculate movements and then animate them. I calculate where the bus/train is likely to be in the next 30 seconds, and then send that data through to the user. Then I keep updating the vehicle marker frequently until that 30 seconds time out, or until another update comes in.
I'm struggling to do the same on Android because I haven't found a good turf.js equivalent there.
On browsers I'm using turf.js to calculate movements and then animate them. I calculate where the bus/train is likely to be in the next 30 seconds, and then send that data through to the user. Then I keep updating the vehicle marker frequently until that 30 seconds time out, or until another update comes in.
I'm struggling to do the same on Android because I haven't found a good turf.js equivalent there.
Perhaps React-Native with turf.js will solve this?
Update: Here are React-Native Map components for Android and iOS https://github.com/airbnb/react-native-maps
Update: Here are React-Native Map components for Android and iOS https://github.com/airbnb/react-native-maps
I'm writing the parts of turf that I use in Kotlin for the JVM. Still early work, but I try put in 30 minutes if my tired hours into the project, before I sleep. I'll hopefully have something decent soon enough to make more progress with the vehicles thing.
As you're using public transport might it be worth storing and using basic historical trends to bridge the gaps in data?
When I was in college, I built a tracking system for our campus's bus system. What frequency are your vehicles reporting their location back to your central service? We decided to use the cell network and had no real issues there (the buses would transmit their location every 1 sec).
Hello,
a question about mapping on mobile,
How can one run mobile offline map using OSM with an open source library, their screenshots doesn't contain copyright, so am assuming their own solution.
thank you
thank you
https://openmaptiles.org/docs/mobile/mobile/
OpenStreetMap license requires you to display an attribution though.
OpenStreetMap license requires you to display an attribution though.
You could store tile images locally, similar to Google Maps offline download. App size may be an issue.
See here: http://wiki.openstreetmap.org/wiki/OpenLayers_Local_Tiles_Ex...
See here: http://wiki.openstreetmap.org/wiki/OpenLayers_Local_Tiles_Ex...
What accuracy people care is the car that you have just ordered. The other times when you see a map of cars you can get away 80% of the time using averages
[deleted]
How does one manage sessions for mobile clients when communicating over UDP? Do you just save the client's IP address and address the client by that IP? Are the IPs of mobile devices relatively stable?
[deleted]
You don't need to send the full precision lat/lng in every update. Instead, send only the change in position from the last update (in meters), which you can calculate on the client.
You could also further reduce data by indexing the city into a grid, of, say 1 meter squares, or potentially a hilbert curve would be fun to experiment with.
You could also further reduce data by indexing the city into a grid, of, say 1 meter squares, or potentially a hilbert curve would be fun to experiment with.
Since they use UDP this would not be foolproof
Well of course you need a way to deal with that, you could have a tolerance or tolerated error and then if that gets over a threshold you request the full precision location. Still loads more efficient than sending the full precision every time.
for geoindices why not use redis?
Or Tile38 https://github.com/tidwall/tile38, I want to try it out, it looks awesome
"Also we found challenge near Kremlin where car appeared at airport." /s
Why not PostGIS?
This is an old problem in multiplayer games. The usual solution is that the sending client predicts the position linearly from the last two fixes, and when the actual position differs from the prediction by some constant amount, it sends an update. The receiving end uses the same prediction algorithm, so its positions match the sending end with a maximum error of the same constant amount, (plus some additional error due to lag.) Updates are also sent periodically in case one gets lost, but those are not frequent.
Incidentally, Uber's display of cars on a map on the home screen is totally fake.