How to calculate vehicle movement ?
Moderator: Transport Empire Moderators
How to calculate vehicle movement ?
No, this is not about traction formulas etc...
If we play this multiplayer, it is very important to have the same things happening on all computers. Usually this is called "the games are in sync". For most things, this is not so difficult : buildings appearing somewhere, a player laying some track... The only "real" problems that could occur here is if 2 players want to build on the same spot on the same moment, but that can be solved without a lot of trouble.
The thing I'm more woried about is how to calculate train movement on different computers, so trains will behave excatly the same on all pc's, no matter what their frame rate is.
We are likely to have some formula that tells us how fast a train should move, given the current circumstances (ie: current speed, slope, turn, load, ...). Do we then just put the train x pixels further for the next iteration ?
In multiplayer, what do we do if ones computer can't follow? Wouldn't this give problems that trains are not exactly on the same spot on each pc? And imagine a crossing, where 2 trains "enter" in the same iteration, we would need a rigid algorithm that makes sure it's always the same train that gains entrance etc...
I know the Railroad Tycoon series had a lot of trouble with these issues and have never been able to do it right. The games would go out of sync very fast, which meant almost nobody plays them multiplayer. I think it would be good for our project if we think about this now, and find out how it's handled in TTD / openTTD / simutrans / ... and then compare them.
Anybody any idea ?
If we play this multiplayer, it is very important to have the same things happening on all computers. Usually this is called "the games are in sync". For most things, this is not so difficult : buildings appearing somewhere, a player laying some track... The only "real" problems that could occur here is if 2 players want to build on the same spot on the same moment, but that can be solved without a lot of trouble.
The thing I'm more woried about is how to calculate train movement on different computers, so trains will behave excatly the same on all pc's, no matter what their frame rate is.
We are likely to have some formula that tells us how fast a train should move, given the current circumstances (ie: current speed, slope, turn, load, ...). Do we then just put the train x pixels further for the next iteration ?
In multiplayer, what do we do if ones computer can't follow? Wouldn't this give problems that trains are not exactly on the same spot on each pc? And imagine a crossing, where 2 trains "enter" in the same iteration, we would need a rigid algorithm that makes sure it's always the same train that gains entrance etc...
I know the Railroad Tycoon series had a lot of trouble with these issues and have never been able to do it right. The games would go out of sync very fast, which meant almost nobody plays them multiplayer. I think it would be good for our project if we think about this now, and find out how it's handled in TTD / openTTD / simutrans / ... and then compare them.
Anybody any idea ?
On holiday from 16/07 till 31/07
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
Patheticly simple.
Vehicles move just on the server.
Clients only get _positons_ of the vehicles on their viewport.
Vehicles move just on the server.
Clients only get _positons_ of the vehicles on their viewport.
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
But that would mean the vehicles would jump forward with each round of new data from the server, rather than just moving normally.
The server should handle all the collisions and such but the client should be fine with general acceleration and moving of trains. You can always broadcast vehicle positions from the server to the clients every so often, to ensure everything is good.
Given that calculations should be done on the distance travelled and not the frames passed, proper code wouldn't make too much de-syncing anyway?
The server should handle all the collisions and such but the client should be fine with general acceleration and moving of trains. You can always broadcast vehicle positions from the server to the clients every so often, to ensure everything is good.
Given that calculations should be done on the distance travelled and not the frames passed, proper code wouldn't make too much de-syncing anyway?
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
Stev - silly
By a mechanism called movement approximation.
The client knows previous position of the vehicle, and current position of the vehicle.
If the positions are - say 60 ms apart, and the client can draw a whole scene in 20 ms, then the client will create two intermediate frames. Easy - really.
By a mechanism called movement approximation.
The client knows previous position of the vehicle, and current position of the vehicle.
If the positions are - say 60 ms apart, and the client can draw a whole scene in 20 ms, then the client will create two intermediate frames. Easy - really.
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Isn't this very network-intensive?
I thought it might have been possible to find something which is guaranteed to work exactly the same on all computers without the need for very much of these position-messages.
If you want movement approximation, you need to know some positions (at least 1) in advance, so the server would be running a little ahead in time ?
I thought it might have been possible to find something which is guaranteed to work exactly the same on all computers without the need for very much of these position-messages.
If you want movement approximation, you need to know some positions (at least 1) in advance, so the server would be running a little ahead in time ?
On holiday from 16/07 till 31/07
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
The client always needs current frame and next frame - so in effect it always shows the game 1 frame delayed.
If you send 5 frames/second you get 200ms lag, if you send 20 frames you get 50ms lag (+network lag).
So yes - the server runs 1 frame faster.
Ofc - to approximate more you need to send more frames - with say 3 frame approx you get 200ms lag with 20 frames/second.
But franjkly I don't think more then 1 frame approx is needed.
Besides - this model would nicely scale with network speed - even 5 frames/sec to the client will create sensibly looking game if the connection is stable.
And since it is asynchronyous (sp?) it never gets out of sync.
If you send 5 frames/second you get 200ms lag, if you send 20 frames you get 50ms lag (+network lag).
So yes - the server runs 1 frame faster.
Ofc - to approximate more you need to send more frames - with say 3 frame approx you get 200ms lag with 20 frames/second.
But franjkly I don't think more then 1 frame approx is needed.
Besides - this model would nicely scale with network speed - even 5 frames/sec to the client will create sensibly looking game if the connection is stable.
And since it is asynchronyous (sp?) it never gets out of sync.
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
OK, I'll calculate the +/- necessary bandwith for this (5 frames / second).uzurpator wrote:Besides - this model would nicely scale with network speed - even 5 frames/sec to the client will create sensibly looking game if the connection is stable.
Let's say 1000 trains, 2000 road vehicles, 500 ships and 100 planes. All in all, about 3000 vehicles that need new positions.
Now, which data do we need to send ?
=> vehicle ID, probably 32 bit (4 bytes)
=> track ID of current position, probably 32 bit (4 bytes)
=> relative position on track section, probably 8 bit. (1 byte)
So, 9 bytes for each vehicle. For 3000 vehicles this is 27000 bytes. If you take 1024 bytes as max packet size (it could be 576 too), you still need 27 packets.
27kB * 5 frames / sec = 135 kB / sec
Well, that counts me out as a server, as I only have a (theoretical) upload of 192 kbps (24 kB / sec).
Ofcourse, we could compress the data. Maybe don't include the vehicle ID and no relative position on the track. So we only have to send the track ID of each vehicle. That's still 3000 * 4 bytes = 12000 bytes. 12 kB * 5 frames / sec = 60 kB / sec, which is still way too high for my (broadband) upload...
But maybe I'm seeing something wrong here...
On holiday from 16/07 till 31/07
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
Ferfooksake!
You don't send the whole data through the network! You mad or something?
Only the data that the client sees is sent! That may be even 100 vehicles (but usually less - 20, 40 maybe), but not 5000!
With 100 vehicles and 9 bytes/vehicle it is just 0,9 kB/s. And since we send on screen data, we don't need the absolute values - so probably 2 bytes per track and vehicle ID will suffice (or even 1 byte). That will cut the amount of info by helluva lot.
And 100 vehicles is A LOT - you will see that amount very, very rarely..
You don't send the whole data through the network! You mad or something?
Only the data that the client sees is sent! That may be even 100 vehicles (but usually less - 20, 40 maybe), but not 5000!
With 100 vehicles and 9 bytes/vehicle it is just 0,9 kB/s. And since we send on screen data, we don't need the absolute values - so probably 2 bytes per track and vehicle ID will suffice (or even 1 byte). That will cut the amount of info by helluva lot.
And 100 vehicles is A LOT - you will see that amount very, very rarely..
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
How would the server know which positions to send.
The client could tell the server which vehicles that it sees. However how shall the server detect which vehicles that the client does not yet know about, but are about to apear at the clients view area. If the view is a simple 2D rectangle maybe it could be detected on the server, but different clients might have different zoom and different angle etc.
Maybe that could be handeled. I don't know how consuming it would be for the server to check vehicle positions against a 3D Box or something to know which to send.
The client could tell the server which vehicles that it sees. However how shall the server detect which vehicles that the client does not yet know about, but are about to apear at the clients view area. If the view is a simple 2D rectangle maybe it could be detected on the server, but different clients might have different zoom and different angle etc.
Maybe that could be handeled. I don't know how consuming it would be for the server to check vehicle positions against a 3D Box or something to know which to send.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Junctioneer (a traffic intersection simulator)
If the client were to send its current view location (or locations, as we might decide to implement viewer windows in the style of TTD's vehicle boxes) to the server, this would give the server enough information to be able to determine what all was in view of the client.
Grunt
(aka Stephan Grunt, CEO of Grunt Transport Inc. since 1994.)
(aka Stephan Grunt, CEO of Grunt Transport Inc. since 1994.)
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
Like grunt said.
Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
-
- TTDPatch Developer
- Posts: 417
- Joined: 13 Apr 2004 13:35
- Location: Eindhoven, Netherlands
- Contact:
well.. with perspective and such, a client can see the entire map at once, but many items will be too far away to be larger than a pixel, so this would be slightly more complex (i assume we are not just sticking to the isometric view?)uzurpator wrote:Like grunt said.
Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
1024X1024 tiled map with 4 texture layers tops at 8 300 000 triangles... Do you _really_ want to display that at once?Mek wrote:well.. with perspective and such, a client can see the entire map at once, but many items will be too far away to be larger than a pixel, so this would be slightly more complex (i assume we are not just sticking to the isometric view?)uzurpator wrote:Like grunt said.
Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
besides - bandwidth constraints will cut the viewable area but quite A LOT.
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
-
- TTDPatch Developer
- Posts: 417
- Joined: 13 Apr 2004 13:35
- Location: Eindhoven, Netherlands
- Contact:
no, i don't want to display that at once, i was just pointing out that the area displayed will almost never be a nice rectangular patch of tiles (and the smallest bounding box of the tiles will often be way to big).uzurpator wrote:1024X1024 tiled map with 4 texture layers tops at 8 300 000 triangles... Do you _really_ want to display that at once?Mek wrote:well.. with perspective and such, a client can see the entire map at once, but many items will be too far away to be larger than a pixel, so this would be slightly more complex (i assume we are not just sticking to the isometric view?)uzurpator wrote:Like grunt said.
Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
besides - bandwidth constraints will cut the viewable area but quite A LOT.
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
That is easily solvable.
Just divide the map in a larger 'leafs' - say 8x8 vertices. Index them and the client will first approximate the required leafs and request them from the server.
Take a look below.
Red tectangle shows what the client sees - blue squares show leafs (8x8 vertices). The client will ask for those leafs, server will check if those leafs were uploaded to the client (or if they were updated since their last acces by this client) and will send those, which require update.
Just divide the map in a larger 'leafs' - say 8x8 vertices. Index them and the client will first approximate the required leafs and request them from the server.
Take a look below.
Red tectangle shows what the client sees - blue squares show leafs (8x8 vertices). The client will ask for those leafs, server will check if those leafs were uploaded to the client (or if they were updated since their last acces by this client) and will send those, which require update.
- Attachments
-
- tiles.png (5.38 KiB) Viewed 11644 times
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Some things about this:
=> Do you want to view the whole world zoomed out with so much detail ??
No, but I do want to view it without detail. An open-air game like this absolutely needs different levels of detail for the 3D models and the textures of buildings and vehicles.
Ofcourse, the server could answer the client "too many vehicles in current viewport to transmit"
=> What about our separation between core game <=> gui ?
We wanted this to be seperated, so the AI accesses the core game through the same API as the human GUI does. If we implement things like this, the AI will need to have functions demanding positions of trains in a certain area (well, if we want the AI to detect bottle necks that is).
Even if you say this isn't needed for our default gui, because we don't want to enable far-zoom-out, our core game should still be able to work with a gui that does have this feature.
=> How does openttd work in this regard?
One of the first things openttd devs changed was the multiplayer component. I hear it's pretty stable. How does theirs work?
=> CPU / network intensive ?
What needs to be done on the client:
-> determine the area where to display trains. This doesn't need to be the complete view, but only the close-up areas. How difficult this is depends on the GUI, but I don't think it's very problematic. We can use fast sub-optimal solutions here without noticeable problems.
-> movement interpolation
-> drawing the objects (would be needed anyway)
Format to send to the server
-> most cases will be possible to describe by sending the 4 corner points of the area you want to see trains in. These don't have to be the corners of the screen, but are up to the GUI to decide. I think most cases are covered by this trapezoïd, but maybe we might add a circle format too.
-> for individual trains (ie: the small viewports), we can ask for specific data for 1 vehicle. Ofcourse, this would make all other vehicles unvisible in the small viewport. On the other hand, the GUI could just ask for all vehicles visible in that viewport too (using the previous format).
What needs to be done on the server
-> Actual vehicle movement calculation. I don't know how this will be done (although I have a few ideas / possibilities), but this doens't really matter as the server would need to do this anyway.
-> Answering to the client requests.
This might be a little tougher. First it has to find the vehicles inside the viewport, then send them on. We will need a tradeoff here between accuracy - network load, which will be determined by the size of the "larger leafs" uzurpator talks about. I think CPU load will be more important than network load here, so bigger cells (bigger than 8*8) might be the way to go, but that's an easy thing to change in the code. Depending on the way we store the info this might be slow or fast (and memory cheap or intensive).
=> sorry if you feel I "drag on" about this of if you think other issues need to be looked at / discussed first now.
=> Do you want to view the whole world zoomed out with so much detail ??
No, but I do want to view it without detail. An open-air game like this absolutely needs different levels of detail for the 3D models and the textures of buildings and vehicles.
Ofcourse, the server could answer the client "too many vehicles in current viewport to transmit"
=> What about our separation between core game <=> gui ?
We wanted this to be seperated, so the AI accesses the core game through the same API as the human GUI does. If we implement things like this, the AI will need to have functions demanding positions of trains in a certain area (well, if we want the AI to detect bottle necks that is).
Even if you say this isn't needed for our default gui, because we don't want to enable far-zoom-out, our core game should still be able to work with a gui that does have this feature.
=> How does openttd work in this regard?
One of the first things openttd devs changed was the multiplayer component. I hear it's pretty stable. How does theirs work?
=> CPU / network intensive ?
What needs to be done on the client:
-> determine the area where to display trains. This doesn't need to be the complete view, but only the close-up areas. How difficult this is depends on the GUI, but I don't think it's very problematic. We can use fast sub-optimal solutions here without noticeable problems.
-> movement interpolation
-> drawing the objects (would be needed anyway)
Format to send to the server
-> most cases will be possible to describe by sending the 4 corner points of the area you want to see trains in. These don't have to be the corners of the screen, but are up to the GUI to decide. I think most cases are covered by this trapezoïd, but maybe we might add a circle format too.
-> for individual trains (ie: the small viewports), we can ask for specific data for 1 vehicle. Ofcourse, this would make all other vehicles unvisible in the small viewport. On the other hand, the GUI could just ask for all vehicles visible in that viewport too (using the previous format).
What needs to be done on the server
-> Actual vehicle movement calculation. I don't know how this will be done (although I have a few ideas / possibilities), but this doens't really matter as the server would need to do this anyway.
-> Answering to the client requests.
This might be a little tougher. First it has to find the vehicles inside the viewport, then send them on. We will need a tradeoff here between accuracy - network load, which will be determined by the size of the "larger leafs" uzurpator talks about. I think CPU load will be more important than network load here, so bigger cells (bigger than 8*8) might be the way to go, but that's an easy thing to change in the code. Depending on the way we store the info this might be slow or fast (and memory cheap or intensive).
=> sorry if you feel I "drag on" about this of if you think other issues need to be looked at / discussed first now.
- Attachments
-
- trains_close_far.jpg
- (419.71 KiB) Downloaded 317 times
On holiday from 16/07 till 31/07
- DominionSpy
- Tycoon
- Posts: 1429
- Joined: 03 Oct 2003 23:59
- Location: Lancashire, UK
- Contact:
I agree with PJayTycy, we definitely need to have a LOD system with this. The coding team are discussing the architecture of the game which affects this a little. We are looking to keep the data about the game and how that data is represented completely separate (ie the data shouldn't be dependent on a specific viewing method such as 3D/2D/text).
This would mean that when the game is rendering the screen, it only needs enough data to do just that. Data sent might just be the objects in the requested view (a simple ID number would suffice) and their positions. When a client comes to render a frame, it will choose which 3D model and textures to use depending on the distance from the camera.
If a new technology came along that was superior to 3D graphics (like a holographic projection system, say ), then we could create a new rendering system without altering one line of the server code or the communication protocol. Even if we wanted to make a completely text version of it, we wouldn't need to change them .
We could have a system whereby you also specify a resolution of the data to receive back. This could be useful for a minimap overview of the world. The client would request the information for a very large view (from above), but at a low resolution so only the track positions for every kilometer and the vehicle positions to the nearest km, for example. Obviously there is some other information needed, but I hope you get the idea.
[edit]
In most views millisecond differences in data delivery will not be noticable. If the view zooms in close enough to see a jump then the client should request updates more frequently (especially since at that level, the data being sent should be drastically reduced).
[/edit]
This would mean that when the game is rendering the screen, it only needs enough data to do just that. Data sent might just be the objects in the requested view (a simple ID number would suffice) and their positions. When a client comes to render a frame, it will choose which 3D model and textures to use depending on the distance from the camera.
If a new technology came along that was superior to 3D graphics (like a holographic projection system, say ), then we could create a new rendering system without altering one line of the server code or the communication protocol. Even if we wanted to make a completely text version of it, we wouldn't need to change them .
We could have a system whereby you also specify a resolution of the data to receive back. This could be useful for a minimap overview of the world. The client would request the information for a very large view (from above), but at a low resolution so only the track positions for every kilometer and the vehicle positions to the nearest km, for example. Obviously there is some other information needed, but I hope you get the idea.
[edit]
This is a bad idea in my opinion. You are talking about dead-reakoning which involves using information about the game logic. We want to separate that from the rendering completely.uzurpator wrote:Stev - silly
By a mechanism called movement approximation.
The client knows previous position of the vehicle, and current position of the vehicle.
If the positions are - say 60 ms apart, and the client can draw a whole scene in 20 ms, then the client will create two intermediate frames. Easy - really.
In most views millisecond differences in data delivery will not be noticable. If the view zooms in close enough to see a jump then the client should request updates more frequently (especially since at that level, the data being sent should be drastically reduced).
[/edit]
You're saying I'm a Dominion spy, and don't even know it! - Dr. Bashir
That's the Joker in my avatar, not me. No wait it is me.
- uzurpator
- Transport Empire Moderator
- Posts: 2178
- Joined: 10 Jan 2003 12:21
- Location: Katowice, Poland
What game logic info the client needs? It knows that vehicle X was at 42,44 and now it is at 42,45 - obviously it now can create infinite steps from 42,44 to 42,45.DominionSpy wrote:This is a bad idea in my opinion. You are talking about dead-reakoning which involves using information about the game logic. We want to separate that from the rendering completely.
All modern games use this mechanism.
Ok - so If my GE FORCE 10600 GTX PRO TURBO ULTRA can draw the map at 1044 fps in 2048x1536 in full detail in full LOD, x16 AA, x16 aniso - the client should request the data 1044 times/second?In most views millisecond differences in data delivery will not be noticable. If the view zooms in close enough to see a jump then the client should request updates more frequently (especially since at that level, the data being sent should be drastically reduced).
Moreso - the crummy server i play on does just 30 fps. So my geforce will now draw 30 fps, despite the fact that it can do so at 1044 fps?
All art and vehicle stats I authored for TT and derivatives are as of now PUBLIC DOMAIN! Use as you see fit
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Just say NO to the TT fan-art sprite licensing madness. Public domain your art as well.
Who is online
Users browsing this forum: No registered users and 1 guest