How to calculate vehicle movement ?

Archived discussions related to Transport Empire. Read-only access only.

Moderator: Transport Empire Moderators

User avatar
PJayTycy
Route Supervisor
Route Supervisor
Posts: 429
Joined: 09 Mar 2004 20:30

How to calculate vehicle movement ?

Post by PJayTycy »

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 ?
On holiday from 16/07 till 31/07
User avatar
Hyronymus
Tycoon
Tycoon
Posts: 13233
Joined: 03 Dec 2002 10:36
Location: The Netherlands
Contact:

Post by Hyronymus »

Would it help to add a delay in rendering the world? Like allowing new data to arrive in 2 seconds and start rendering with a 3 second delay (1 additional second for doing maths).
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

Patheticly simple.

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.
User avatar
Steve
Tycoon
Tycoon
Posts: 2085
Joined: 10 Jan 2004 20:19
Location: London
Contact:

Post by Steve »

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?
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

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.
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.
User avatar
PJayTycy
Route Supervisor
Route Supervisor
Posts: 429
Joined: 09 Mar 2004 20:30

Post by PJayTycy »

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 ?
On holiday from 16/07 till 31/07
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

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.
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.
User avatar
PJayTycy
Route Supervisor
Route Supervisor
Posts: 429
Joined: 09 Mar 2004 20:30

Post by PJayTycy »

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.
OK, I'll calculate the +/- necessary bandwith for this (5 frames / second).

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
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

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..
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.
User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Post by Zuu »

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.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
User avatar
Arathorn
Tycoon
Tycoon
Posts: 6937
Joined: 30 Nov 2002 17:10

Post by Arathorn »

Can't the client send the location of the centre of the screen and the diameter of the viewed area (and additionally a viewing angle) to the server?
Grunt
Route Supervisor
Route Supervisor
Posts: 449
Joined: 03 Oct 2003 20:22
Location: Edmonton, Alberta
Contact:

Post by Grunt »

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.)
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

Like grunt said.

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.
Mek
TTDPatch Developer
TTDPatch Developer
Posts: 417
Joined: 13 Apr 2004 13:35
Location: Eindhoven, Netherlands
Contact:

Post by Mek »

uzurpator wrote:Like grunt said.

Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
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?)
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

Mek wrote:
uzurpator wrote:Like grunt said.

Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
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?)
1024X1024 tiled map with 4 texture layers tops at 8 300 000 triangles... Do you _really_ want to display that at once?

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.
Mek
TTDPatch Developer
TTDPatch Developer
Posts: 417
Joined: 13 Apr 2004 13:35
Location: Eindhoven, Netherlands
Contact:

Post by Mek »

uzurpator wrote:
Mek wrote:
uzurpator wrote:Like grunt said.

Client asks for "45x43 tile patch starting at 234:233" and the server sends everything that is there. Simple:)
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?)
1024X1024 tiled map with 4 texture layers tops at 8 300 000 triangles... Do you _really_ want to display that at once?

besides - bandwidth constraints will cut the viewable area but quite A LOT.
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).
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

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.
Attachments
tiles.png
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.
User avatar
PJayTycy
Route Supervisor
Route Supervisor
Posts: 429
Joined: 09 Mar 2004 20:30

Post by PJayTycy »

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.
Attachments
trains_close_far.jpg
(419.71 KiB) Downloaded 317 times
On holiday from 16/07 till 31/07
User avatar
DominionSpy
Tycoon
Tycoon
Posts: 1429
Joined: 03 Oct 2003 23:59
Location: Lancashire, UK
Contact:

Post by DominionSpy »

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 :mrgreen:), 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]
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.
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.

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]
Image
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.
User avatar
uzurpator
Transport Empire Moderator
Transport Empire Moderator
Posts: 2178
Joined: 10 Jan 2003 12:21
Location: Katowice, Poland

Post by uzurpator »

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.
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.

All modern games use this mechanism.

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).
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?

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.
Locked

Return to “Transport Empire Development Archive”

Who is online

Users browsing this forum: No registered users and 1 guest