Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Deterministic RTS game engine

Discussion in 'Multiplayer' started by Obatztrara, Feb 3, 2012.

  1. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    I think the bottom line is that a fully deterministic simulation can't continue until it knows all of the inputs for the next timeslice. So the most robust way to implement what you're suggesting would be for every client to wait until all input is received from the other clients, for the upcoming tick. You'd need to send tick messages ahead of time to do this without making the game crawl, and the amount would depend on the general latency between the players. It's not out of the question but it does mean that one bad client will slow the whole game down. From what you guys have said about other games, it sounds like some PC RTS games do work that way, and I think this is what 1500 archers was suggesting. Personally though I'd rather go client-server, even if the server is hosted on a client, so the only person whose connection affects the game for everybody is the session host.

    I also find N^2 TCP (or otherwise reliable) connections rather scary...

    Yes - it's rather naively based on realtimeSinceStartup. It tracks when it should update the simulation, and remembers the last time it did it; then when it's placing the sprites, it interpolates based on the new realtimeSinceStartup.
     
  2. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Don't confuse UDP TCP with P2P vs Server.

    With P2P there's absolutely no guarantee you'll save yourself anything like a round trip - in fact the eact opposite can happen!

    For example, if I was to play with my mate up the road from where I live the P2P packet goes like this:

    The request:
    • 50ms down to Brisbane.
    • 50ms up to Cairns [my mate].
    The acknowledgement:.
    • 50ms down to Brisbane.
    • 50ms up to Cairns [me].

    While a server based system should do the following:

    The request:
    • 50ms down to Brisbane. [to server]
    The acknowledgement:.
    • 50ms up to Cairns [me].

    Remembering that a deterministic P2P system is only as good as the worst connection... and you have a lot more connections to worry about!
     
    Last edited: Mar 23, 2012
  3. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    No confusion here, UDP/TCP are network protocols and P2P/ClientServer are architectures describing how clients communicate with each other.

    Yes, but this all assumes you need acknowledgments; it may very well be that you can get rid of most acknowledgments.
     
  4. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Exactly.

    How else can you be sure that everyone has received the correct input at the correct time to allow the deterministic simulation?

    Unless you're thinking of allowing clients to make that decision for themselves:

    Code (csharp):
    1.  if (hasInputFromAllPlayers) NextTick();
    Then you still run into the issue that a single missing packet will stall the entire game. Player Y didn't receive packet from Player X and is waiting [presumably for some sort of timeout before requesting the packet be resent] - while this occurs Players A B C D E F G and X all moved onto the next tick... but can't proceed because Player Y is stalling.

    With a server based system, player Y simply stalls for a couple ticks until it has received the data from the server to allow it to catch up.
     
    Last edited: Mar 23, 2012
  5. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    I wouldn't call it an acknowledgement. In the client-server case, it's more of an echo. In P2P you send your packet and, when the time comes, stall waiting for everybody else's. So let's see what latencies that leads to...

    Suppose A has point-to-point latency of one second to B. When A sends a tick to B, it arrives one second later in real-world time. And suppose it's symmetric, so when B sends a tick to A it also arrives one second later. Suppose there's nobody else in the game, and at some point B waits for a tick from A - so, in real-world time, B's simulation is now one second behind A's. This means that when B sends a tick to A, it is effectively two seconds late. For A to avoid stalling, the machines (or, at least, B) need to be sending ticks two seconds in advance.

    However, if A and B share a common real-world game time, the ticks only need to be sent one second in advance. If you can build in a system whereby A tells B how late its ticks appear to be, relative to A's game time, then B can advance its simulation faster than usual to balance the time difference. This way, if you'll excuse a wild extrapolation to higher player counts, the command latency only needs to be set to the worst point-to-point latency in the network.

    That is assuming that all machines use the same command latency. It is possible that a laggy machine could use a higher latency - I think this also solves the problem, i.e. if there are machines C and D as well, and A, C, and D share low latencies but all experience high latency to B, then A, C, and D can use a low command latency, and B can use a high command latency, and everybody will get a smooth game - but B will experience more delay between clicking and seeing the effect of the click.

    Again, in the client-server case the command latency is not explicit, but for any player it ends up being - more or less - the round trip time to the server. So different players experience different latencies.

    None of this is anything to do with acknowledgements though - that's another kettle of fish. In some designs you could piggy-back the acks on the command stream, but that's just a detail - it doesn't affect the commands themselves, nor - in the case that no packets are dropped - does it affect the player's experience of the game. I think there's a fairly obvious strategy for ensuring the data gets through without experiencing long delays when it does not, but it's not really relevant to the general latency that players perceive.

    Hmm, the more we talk about this the more I want to make a proper reusable engine. :) andorov pointed me to his own engine before, which looks nice. It's hard to get the flexibility and ease of use into a deterministic environment though. At work last year we implemented our own versions of GameObjects, components, prefabs, and so on. I was never convinced it was worth the effort, though, and I think the simulation lost a lot of performance as a result. This time around my simulation is more performance-oriented than object-oriented, and I think that's the only way to get these unit counts to work. For more normal numbers, though, you could probably have the best of both worlds.
     
  6. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Maybe I missed it, but could you explain how you would deal with a dropped packet?
     
  7. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    Sure. For one thing, you could just use TCP - all the data that's sent must be received, exactly once, in order, so it's a pretty good fit. However there are other problems such as NAT negotiation that might make that unappealing, and restoring a dropped TCP connection is another headache. So, using UDP, I'd use a packet format containing:

    • The most recent tick number I've seen from the machine I'm sending to
    • The number of ticks present in this packet
    • For each tick:
      • The tick number
      • Any command data this machine is emitting for that tick number

    So if the newest packet I've received from the target machine told me all its commands up to tick 526, I'd send 526 in the first field. The rest of the packet is just a list of ticks that the target machine might not have seen yet, with command data for each tick. In the last packet I received from the target machine, it told me the most recent tick number it had seen from me - maybe that was 523. The packet I'm sending now, then, will contain all the ticks that I have emitted since then - ticks 524, 525, 526, 527, and 528. I've already sent most of these, but as I don't know that the target machine has received them successfully, I send them all again. Meanwhile, my simulation is running up to and including tick 526, as I don't yet have the data from all other players for tick 527.

    If we tick around for another cycle and I still don't receive new data from this target machine, then my next packet will still say the most recent data I received from it was tick 526, and it will contain duplicates of my tick data for ticks 524, 525, 526, 527, and 528, and also the new data for tick 529. Then I'm stuck because I can't advance my simulation past tick 526 until I receive more data from this target machine. Such is life. While in this state, I probably don't accept new local user input, but I do keep sending regular duplicates of the data up to tick 529 - otherwise there's potential for deadlock.

    So, regarding dropped packets, maybe the packets I sent for ticks 524 upwards all got dropped. That's why the target machine's messages only claim to have received data from me up to tick 523, and its simulation can't tick past that point until it receives the data (so it's not sending new data beyond tick 526 - that is, 523 plus the command lead time). But whenever a new packet does get through, it will provide all of the missing information, so sensitivity to packet loss is quite low - the situation gets resolved easily.

    If ticks occur every 100ms, then when a single packet is dropped it only delays the game by 100ms, until the next packet arrives. The sender doesn't wait for a negative "I haven't seen this" message, so there's no round trip delay there - the source machine resends the data anyway, every 100ms, until it receives a packet from the target machine saying that it has received the data for those ticks.

    I don't think this was a very clear explanation, I'm sorry about that. I don't think there's anything complicated here, but it is hard to explain.
     
  8. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    This thread is turning out to be pretty informative. :D

    I just thought of a "gotcha" with this approach : how would a new player join an existing game that's been running for, let's say, the past 15 minutes? I see two methods :

    1) new client loads initial state and processes all commands/state (let's assume server caches all commands/state) sent within the past 15 minutes at warp speed until it gets to current state, and only then start rendering (obviously not an option)
    2) new client loads "current snapshot" and quickly processes any commands/state issued after snapshot was taken, which means that someone (server most likely) would have to keep its own simulation of the game and provide a "current snapshot" to the new client. this would mean that the server is now no longer simply acting as a router for the clients turn-based-packets, but an active participant by running its own simulation. I guess you would need this no matter what, especially if you want clients to connect as observers (ie. players who don't participate in a match but can observe it).
     
  9. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    Yes indeed, join in progress is tricky.

    You've got the right ideas - pretty much what we were planning at work. You may want to mix the two, so take your time transferring a serialised mid-game state, then catch up by applying whichever ticks have passed since then. But if you're going down the serialization route, you'd better do a good job of it - you must get everything right.

    There are many benefits to having your low level simulation being as lightweight as you can, which is why I've been keen to keep the CPU load per tick in the low millisecond range in the web player I posted. This means I can accelerate time up to 500 frames per second. If my normal tick rate is two per second, that means I can simulate four minutes' worth of gameplay in one second. Catching up to a game that's 15 minutes in would take less than five seconds. Note that the slower your logic tick rate, the faster your accelerated time will appear to go, as well - and the player generally has very little perception of the simulation tick rate, as the view code smooths everything out.

    If you use serialization then yes, you need somebody to provide you with the data. But it doesn't have to be the server - every client has the data you need. There is a trust issue, of course. We were planning to run trusted clients - essentially observers, watching games in progress - and perhaps use those to provide join-in-progress game states. But it's not the only way.
     
  10. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    Most definitely... I realize clients can also serve as a source but for the purposes of the discussion I abstracted this out to a single "server". Trust can be an issue, but the problem I see with having the client take a snapshot is that every time an observer or new player joins in, a client would have to (in addition to running its own game simulation and processing packets) both process the snapshot request and send the data; I may venture a guess that even if this were handled in a most optimized fashion by spreading the load over many frames, it must have some effect on the client and be perceived as lag or severe lag or even a freeze at moments. Perhaps an implementation where each client delivers a piece of the snapshot will help, but that complicates things even further. I think I'm leaning on the server running its own simulation because of exactly this issue : no matter how many players or observers want to join, if they get their snapshot from the server, none of the actual current players should experience any effects from the join process. The biggest problem with having a simulation run on the server, though, is scalability.

    I'm still brainstorming a pure p2p approach though since my game is similar to LoL in its number of players and gameplay.
     
    Last edited: Mar 23, 2012
  11. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    Bear in mind that if the server is serializing out all this data, it's going to have an impact there, and if the server stalls, everybody stalls. :)

    It's hard to spread the load over several frames as you need to snapshot just one frame, and getting the snapshot isn't insignificant. It's not too bad though.

    LoL is perhaps a borderline case, as its unit count isn't excessive. If your interest is in the game rather than the technique then it would be interesting to see how much you can do using andorov's engine for example. I don't really know how complex a game would have to get these days before it would require deterministic simulation.

    At work we had other reasons for being interested in this design for a LoL-scale game - things like cheat prevention and ensuring people don't use content they're not entitled to.
     
  12. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    Not if the clients are pure p2p and the server's silmulation is solely used for joins. :D However, I would rather not have to simulate on the server, so if I can get away with fetching snapshots from the clients I will.

    Yes, this is a problem... perhaps each client can contribute a portion, and send their portion of the snapshot over several turns (I actually meant turns, not frames, in my last post).

    Forget it, my curiosity has been piqued with the deterministic approach, and since it seems to be the right approach I'm up for the challenge. I'm a programmer's programmer, so my interest is in both the game and the technique; I'm excited about the challenges involved in creating a p2p simulation architecture similar to the one implemented in AoE and appreciate the input I've received so far. I'm also very much interested in the security element, since I am well aware of how cheats/hacks negatively affect a gamer's experience of the game (Diablo anyone?). It would seem that most (not all) of these issues are resolved with the entire deterministic approach, but of course there's the big security hole in the fact that you are privy to other user's command 2 turns in advance, so I'll have to figure out how to prevent this once I cross that bridge.

    This seems to be your area of expertise, and I see you frequently mention plans on implementing this at "work"... is this your studio, or a studio you work for? What do you do, and what are you guys working on, if you don't mind me asking?
     
    Last edited: Mar 23, 2012
  13. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    I'm not sure there's much (any?) value in doing P2P with a server as well. If you have the server, I don't think there's any reason to send data P2P.

    I don't think it's a big problem. It only applies in P2P anyway. For me the biggest cheating difficulty with this system is that every client knows all object positions, so things like fog of war could be circumvented client-side in a way that's undetectable.

    I used to work for Disney (http://www.disney.co.uk/disneyinteractivestudios/blackrockstudio/), until last summer when our studio was closed down. For the last four to six months there, I was part of a team designing and prototyping the network infrastructure for a game in preproduction, which itself unfortunately evolved away from being the kind of game that benefits from this structure. In a way, the 16,000 unit demo is my belated rebound from that - wanting to explore the limits of the system, without worrying so much about what the designers actually want to make.
     
  14. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    My thought was that even if we're going pure p2p, a server might be needed in order to provide lag-free snapshots for players/observers who join while game in progress. I would rather do without this though and get the snapshot from the clients and hopefully not have the client(s) incur penalties in the process.

    The whole reason for p2p is you eliminate one leg of the round-trip. In CS you send packet to server, server sends it to everyone; P2P you don't bother with the server and send straight to the clients. In most cases this works well and you come out ahead in the latency game; but as the number of clients increase P2P becomes less attractive until its finally no longer an option.

    It can be a problem since a client can see your moves 2 turns in advance and execute a move to counter yours or profit from it; in other words, I can create a bot that reads your moves and creates perfect play from my end to beat you. And as for fog of war, that's something I've been unable to figure out how to prevent... I don't think any game out there has anything set up to prevent that.

    Awww, that's too bad... but I applaud your efforts in continuing the fight. Even though my game only requires aprox. 10 players, I would love to design a system that supports thousands, and 16,000 would be an impressive feat. This sounds something only client server can accomplish as I don't think that would be possible in p2p at all, though I've heard of p2p mmo's and have no idea how the heck they perform that miracle.

    Do you have an engine in the works? That is, a prototype?
     
    Last edited: Mar 24, 2012
  15. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    You know what... screw it. I'll focus on a CS version, and if I can pull it off within a reasonable time frame I'll create a P2P branch and see how they compare. I'm really psyched to see if I can get a thousand + clients running at once.
     
  16. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    Right, but if you have a server then you should just use it and not do the P2P bit. It's simpler, and the only thing you gain from P2P is not requiring a server.

    The advantage is limited. In client-server, the bot can only respond slightly sooner than a human would, which is not so bad. In P2P, the worst case is when the bot can queue a command for a frame sooner than the one the incoming command will execute on - which is really bad. So in the example I gave earlier, the lagging machine has received data for tick 528 from other players, but hasn't yet sent its own data for tick 527 - so if it's a race (first person to click the powerup wins?) then the bot can jump the queue.

    Probably the best thing to do is not rely on these game mechanics in an RTS-style game. :)

    The reason I mention it is that if you're doing it non-deterministic then a peer can simply not send position updates to other peers when they shouldn't be able to see that unit anyway. That's a fairly simple solution which just can't be done in a deterministic simulation.
     
  17. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    Clients, or units? The engine won't care much which you mean, but the server will need careful design to cope with 1000 connected players. And it's hard to test. :)
     
  18. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Not too bad, but I still can't see how it''s going to be faster.

    My next question is, taking that explanation - how does one send input?

    Remembering, all players must apply the same input at the same tick - and unless you're willing to aggressively roll-back and reapply commands.... how can you be sure that this will occur?
     
    Last edited: Mar 24, 2012
  19. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    Oh you meant unit fog of war... yeah. Nothing prevents hacking the client and seeing the whole map though, and seeing where all the resources are, etc...
     
  20. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    That's the challenge... 16,000 units, 1,000 clients! :p hahaha, I wish! But we'll see what I can manage... though I think uLink was able to host a 1k client demo.
     
  21. vipin123

    vipin123

    Joined:
    Mar 26, 2012
    Posts:
    3
    as I m thinking we should searh it on search engine
     
  22. nerophon

    nerophon

    Joined:
    Aug 8, 2009
    Posts:
    35
    This is a remarkable thread. I'm glad Google appreciates it. Well, it's been a couple of years since the discussion, but I thought I'd throw my recipe into this pot and see if anyone's still listening.

    I've been researching this area for 18 months or so now, and am nearing completion on my first actual implementation, which I am calling Dreamscape. I looked at Starcraft 2 of course, but also of great interest to me was EVE Online. Some of the stuff they built is state-of-the-art even now, and it was written over a decade ago. Props to those guys.

    Anyway, I've opted to cross the Protoss and the Zerg and create a Hybrid monster to take over the galaxy with. The client is written in Unity C# of course, though other clients could appear in the future. The server is stateful, and written in Erlang. For those of you who have never experienced the wonders of the functional language, I must say it changed my life, and can't recommend it more highly, especially for the kind of service this forum considers. But that's a whole other post.

    Dreamscape chooses to model its simulations as systems of actors running turns in lockstep. The implementation has several key tenets:

    1. Deterministic Actor Logic
    This permits massive reduction in bandwidth, as state does not need to be sent around every tick.
    Please note that this does not mean that state cannot be sent, merely that is doesn't have to be for all changes.
    I believe that any decent programmer can make any game using integer or fixed-point mathematics (for the sim-layer) if they try.

    2. Client-Server Simultaneous Simulation
    This permits authoritative state snapshots if and as needed.
    It also empowers worlds with a life of their own... actors can simulate without any sessions being interested in them.
    From a game design perspective, I feel this makes a huge difference.

    3. Causality Compartmentalization
    The server does the usual command routing, but with a subdivision system ("rooms") to limit client exposure if required.
    This permits potentially MMO-scale systems, and supports advanced entities (e.g. room-spanning doom clouds, moving towers, etc.).

    4. Data Never Dies
    Live data is held in memory, both on all clients (given point 3 above) and in duplicate or triplicate on the server-side.
    If a node fails, another node takes over and a new node spins up.
    Moreover, data is versioned, persisted into S3, and as time goes by warehoused in Glacier if desired.
    Imagine an MMO where a lucky player could capture a Temple of Time and turn the whole game back a day! ( >24h cooldown recommended)

    5. Easy to Code
    With formality comes simplicity.
    Actor logic and data classes must be written to strict templates, enforcing robustness and succinctness.
    In the long run, I hope to go further and make these classes so formal they can be interpreted as meta-data, making replays and rewinds possible even between versions, with versioning transparent to players.


    So there is my manifesto! Critiques and questions are most welcome. I hope to have some games running on this thing soonish :)
     
  23. jpthek9

    jpthek9

    Joined:
    Nov 28, 2013
    Posts:
    944
    Hey, I know I'm a little late to the party but I've integrated a deterministic physics engine into Unity. Here's the Reddit thread: http://redd.it/358hl6 . It should be on the asset store in a few days and I'll post updates on that thread.

    It comes with a multiplayer lockstep implementation that works out of the box. The RTS-specific elements will be included in a later release. Unit selections, movement, crowd control, etc. for the multiplayer implementation.
     
    Last edited: May 9, 2015