Search Unity

  1. Calling all beginners! Join the FPS Beginners Mods Challenge until December 13.
    Dismiss Notice
  2. It's Cyber Week at the Asset Store!
    Dismiss Notice

Deterministic RTS game engine

Discussion in 'Connected Games' started by Obatztrara, Feb 3, 2012.

  1. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    First of all, this is my very first post on these forums so yay for that and good day to everybody! :D

    Secondly, as the title suggests I am working on a RTS game, using obviously the unity engine. It is my first attempt at making a game with the engine, but I have programmed in c# before and I study computer science, so the coding is not my biggest concern. What really concerns me is how to implement a working multiplayer mode (the game wont even have much of a singleplayer part). This is why I turn to you guys.

    1) I know the "state of the art" method for RTS games is to create a deterministic game engine, synchronize all players and their input and send only the input over the network, hoping that since everything is deterministic everyone will end up with the same game state.
    Is this concept applicable to the unity engine? Can everything be determinstic? What about for example the Physics?

    2) Does anyone have experience with an engine like this? Any common problems? How did you deal with for example float operations?

    Thanks!
    Greetings,
    Obat
     
  2. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    Hey, and welcome to the forums! Let's dig right into answering your questions.

    1) It's not so much state of the art as the only way to do it properly, I think there is one single RTS game in the past ten years or so that has not done it this way. You can apply this concept to unity, but you're going to have to take a few things into consideration. First up is the physics engine, unitys engine is not deterministic which means you will be limited to use physics for "eye candy", but this is not as big as you think as most RTS games rarely use physics for anything else.

    2) The common problem is really the solution also, making sure that everything stays in sync. It's incredibly difficult, small things can go wrong and the end result/problem wont show up til much later. It's sort of like chaos theory, a single small event can have huge impact on the game eventually.

    There are ways to make floating point math deterministic, but I think the tricks you need to use are things which are not available in C#. There are other ways to get deterministic fractional math which is accurate enough though, it's just a lot of of work.

    I would recommend you to read the incredibly famous "1500 Archers" article on gamasutra: http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_288_network_.php
     
  3. andorov

    andorov

    Joined:
    Feb 10, 2011
    Posts:
    1,061
    I've had some .. uh .. fun... handling these problems in my own RTS project.

    fholm is right in that we are missing some key things to get absolutely deterministic behavior in Unity/C#, but.. as I've found out, all hope isn't lost.

    Some easy things I do is delaying RPC calls in a staggered manner, which ensures that all computers roughly start an action at the same time.

    I also key in a lot more information than just user input. Various points in time, states are also synchronized for units (ie: unit is beginning casting, shooting, etc). This, however, means that I'm sending in a lot more information. Luckily, I'm not programming for 56k dialup connections, and thus can afford to use significantly more bandwidth to exchange extra state information on a per-entity basis.

    I'm not going to get 1500 archers, but I think I can squeeze out 100 units, which is enough... for now. :)
     
  4. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    andorov: Maybe I was unclear in my response, nothing is really missing in Unity. You have everything you need for deterministic math and honestly physics are mostly for eye candy.
     
  5. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Thanks for the fast replies!

    @fholm: I actually stumbled upon that link a few minutes ago, although quite old not much seems to have changed. I will use that as my goto for now.

    @andorov: Great to see that it "can" work! Some technical questions: Do you limit the framerate to the fps of the weakest member of the game? Or just fix it to something everyone can manage? Also, can this be done with the TimeManager of Unity or do I have to control it myself?
    Out of curiosity: Have you added replays to your game? That shouldnt be a problem once the deterministic stuff is done, right?
     
  6. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    You should not limit the FPS itself, this should not be needed on today's computers (as they are more then fast enough). Rendering (FPS) and simulation (input/network logic) should be separate.
     
  7. andorov

    andorov

    Joined:
    Feb 10, 2011
    Posts:
    1,061
    I don't FPS rate my project, but its interesting to note that Starcraft 2 does FPS-limit players if one can't keep up. Also, I have not added replays to my project, and have little desire to do so at this point in time.
     
  8. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    This is not completely true, star craft 2 will stop the simulation due to there being no input from the other player, but this has nothing to do with FPS limiting. It looks like you get "fps drops", but this is really not it, they just freeze the simulation as there is no more input.
     
  9. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Hmm do you think I could use the FixedUpdate Function for my logic network updates? That should make sure that all players have the same amount of update cycles, right?
     
  10. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    Hm, in theory it might seem fine, but the reality is that it becomes a lot more complex , so I would advice against this.

    I can write you a better explanation then "don't do this" tomorrow, gotta take care of the wife now :)
     
  11. Doddler

    Doddler

    Joined:
    Jul 12, 2011
    Posts:
    249
    I remember asking x4000 (from Arcen Games) about it, his AI Wars game is a full deterministic multiplayer game which he ported to unity. I believe he mentioned he was using fixed update to run the game simulation. My understanding is that game commands are scheduled for a future game update tick, and if clients haven't reported their commands (or lack of commands) by the time it comes to execute that tick, the simulation pauses until everyone has caught up. Each game update only occurs every 200ms or so (though you can actively adjust it). That means there's a delay from when you execute commands and when the game responds, but realistically in an RTS you don't really notice that kind of thing.

    As Obatztrara suggests I think you can do it in fixed update but you can't simply rely on everyone running the same number of fixed updates as everyone else, you'll have to manually time the simulation to make sure the different clients are running commands at the right times. If someone's computer is running too slow to meet the current simulation requirements you have to handle the result gracefully rather than desyncing.
     
    Last edited: Feb 3, 2012
  12. andorov

    andorov

    Joined:
    Feb 10, 2011
    Posts:
    1,061
    If one user is under heavy lag, the game prompts the rest with something like "XYZ is slowing down the game," and the simulation of the game won't stop, but it will slow down. I don't believe its limiting frames drawn per second, so I suppose its incorrect to say its limiting FPS, but Its definitely running the simulation loops slower.
     
  13. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    The simulation "slowing" down is exactly what I was talking about, it will not slow down the FPS at all (your game will still render at whatever FPS your computer can squeeze out) - but the simulation will halt/run slower. It will look as if the game is "choppy" as it's not running in full real time due to the slower player. Slowing down the simulation and halting it is pretty much the same thing, if the halting is short enough it will look as if the game "stutters" which is basically what low FPS looks like, so people mix the concepts together.
     
  14. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    @fholm: Looking forward to your explanation, for now I kinda feel like doing it with the FixedUpdate - especially after what Doddler wrote. I can see how there could be a problem in the following scenario though: Lets say my simulation would run at 10 fps (with the graphics as fast as whatever users machine can handle). This forces me to run the physics at 10 fps as well, so if I should ever decide to seriously use them I might be in trouble - since 10fps physics will look very awkward...

    @Doddler: Good to know other people have done this. Thanks for your reply. Of course i would also track the current update number. Packages over the network would probably consist of the input and (currentSimulationCycle + 2) (or so). This would indicate when to run a certain command.
     
  15. Tynan

    Tynan

    Joined:
    Feb 4, 2012
    Posts:
    22
    Thank you for starting this thread; I've been interested in the problem as well. In fact, I'd be surprised if it hasn't been solved several times as well. Does anyone know of any reference implementations we can look at?

    Also, I have a related question.

    It makes sense to me to, say, run the simulation at 10Hz while letting people run their graphics at any speed they want. This way people stay in sync.

    But doesn't that mean that all the gameplay-relevant actors will tick forward at 10Hz, even if the game is re-rendering at 60Hz? I remember this happening back in the Quake 1 days. People would snap through space tick by tick.

    I can imagine how to solve this with some sort of local interpolation, but that sounds very complicated and difficult.
     
  16. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Well, I guess nothing keeps you from implementing different speeds for different aspects of your game: You could run the Input/Network part at 10Hz, the GameLogic/Movement/Whatever at 30Hz and the graphics at whatever speed is possible. That shouldnt break the deterministic part, or am I missing something?
     
  17. Tynan

    Tynan

    Joined:
    Feb 4, 2012
    Posts:
    22
    You know, now that I thought about it a bit more, this makes sense.

    You could run the simulation at 30Hz, which is fast enough to look good. Perhaps camera, particles, and animations would run faster.

    For netplay to work you don't have to run at some really low refresh rate. All that matters is how far in the future you schedule the application of input commands. So you could schedule them 5/30 of a second in the future. As long as your ping is less than that, the game works. The actual update rate of the local sim doesn't matter.
     
  18. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    My [condensed] thoughts regarding deterministic engine:

    Don't do it!

    You cannot use the special flags that force FPM to be deterministic.

    Fixed point maths, at least in my experiments, will give you errors on the simplest things due to rounding. E.g. Divide by 0 exceptions.

    Exceptions

    Possibly using C++ plugins for FPM.

    Game mechanics that can be written exclusively with integer math.
     
  19. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Well, the thing is that I really dont see how I can not do it! :p

    It seems to be the only legit approach to RTS multiplayer games. But yeah, it will probably come down to loosing float precision in favor of less precise integer approximations.

    Also, noobish question: What does FPM mean. *Sigh* My only excuse is that I started last week.

    Progress Update:
    - Input and GameLogic now run at 10 Hz
    - GameObject Logic runs at 50Hz (To prevent movement from being jerky)
    - Graphics run at maximum speed

    All the frequency values can be changed easily at any time.
     
  20. ColossalDuck

    ColossalDuck

    Joined:
    Jun 6, 2009
    Posts:
    3,246
    Fixed point math.

    He just abbreviated it.
     
  21. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Ah lol! That's what im currently working on...
     
  22. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    Actually I meant floating point math in this isntance... but in retrospect that might not have been the best abbreviation attempt.

    WTF [Worse Than Failure].

    WiC is a RTS/RTT.

    You have 16 players, with say 4 units each - that's 64 units.

    Sync position every second ~ 6Kbps.
    Sync rotation every second ~ 6Kbps.
    Fire a round every second ~ 12Kbps.
    etc.

    So the question isn't how is it possible to run a RTS without *complete* determinism - but what are you doing that requires it? Given that most of your game logic should be deterministic, and you remove the majority of Collision Responce, and most of your units move in a fairly predictable [usually slow] manner - you can get away with a surprising number of units without having to rewrite your entire physics engine.

    I mean, I see no reason you couldn't get 500 odd MOVING units to work while using less than <100Kbps. And if you are smart about your syncing [hint - you don't need to send 12 bytes for a position update - you should be able to get away with 2~3 with a little thought] I wouldn't be surprised if you could fit in a fair few more!

    It's important to note that some games that use pure determinism - e.g. SupCom - suck in multiplayer because the simulation always works at speed of the weakest link. By using a more wasteful bandwidth strategy, you take the load off of the clients and can put it on machines that can handle the strain.

    In short - the very same strategy that claims to allow thousands of units often fails to deliver in real world.

    Game logic and rendering should be completely decoupled. As such, that Hz is far too high!


    ------

    Basically what I'm saying is you need to know what you want to make, and then you need to figure out what you are going to make deterministic and what you are going to leave to the imperfect floating point math. You can combine the two in a small myriad of ways - with each combination having its own strengths/weaknesses.

    Generally speaking though collision detection physics need floating point math to work at their best. If you want, you can write your own fixed point math system to replace them - but you'll restricted to a subset of features that you can implement.

    Remember of course, that as a developer one must evaluate risk and time as well as raw performance and features.
     
    Last edited: Feb 5, 2012
  23. andorov

    andorov

    Joined:
    Feb 10, 2011
    Posts:
    1,061
    As NPSF has stated, its not completely bonkers to get an RTS going that isn't entirely deterministic.

    Thats how I've been doing it.

    Since I know my inaccuracies are small, a state sync rate of even 1 per unit per second is more than enough even on laggy (>500ms) connections. I do rely on SOME determinism. The age of empires article discusses techniques used for AOE1.. that was like 10 years ago. Do you really want to make a game with techniques designed for a 300 MHZ processor with 64MB ram and a 28k modem?
     
  24. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    First of all: Game logic and rendering are completely decoupled. It says GameObject logic (= pretty much just movement and animations for now).

    Well I'd like to go down the deterministic route for several reasons.

    1) It's a very solid approach, as proven by countless RTS games, like Starcraft 2 (which I personally take as THE RTS), Age of Empires, etc.

    2) It comes with advantages like an instant replay function (Which is a MUST for the kind of game I have in mind).

    3) The bandwith usage is minimal and doesn't scale with the amount of gameObjects.

    I'm well aware that the OOS error is a total pain and the problem with Floating Point Math is annoying as well, but I think I'll take the risk. Also, this is partly a learning project, so I welcome the challenge.


    On a side note: I don't see a way to sync positions between players without breaking the replay function. Let's say I detect a difference in position between two units. Which one's would I take? Also, if the replay of the game would be seen on a different architecture I can't be sure the same difference would occur at the exact same time. So I might end up not correcting it, which could lead to a completely different game (Butterfly effect).
    If I'm totally wrong on this one, please enlighten me.


    Edit:
    @andorov:
    True, but as said above I believe that would break the replay function, which is a must-have for my game. And yes Age of Empires is old, but theres more than enough newer examples...
     
    Last edited: Feb 5, 2012
  25. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    They should run a FPS, not 50Hz.

    1) Proven C++ games you mean :)

    2) I'd argue that a non-deterministic system would be more effective there. Deterministic system [at least SupCom] require you to runt he entire simulation from beginning to whatever point you wish to see. For a measly 50MB/hr non-deterministic systems can jump anywhere in the simulaiton.

    3) Bandwidth usage is minimal - we live in a day where bandwidth costs ~$10/TB for servers! Say 50MB/hr costs ~ $0.0005 per player hour!


    Good luck. I'm in part playing the devils advocate, part out of failed attempts to get Fixed point math working.

    While I think a great portion of the game can be deterministic, I'd still leave entire sections [such as ray-casting] to the traditional.methods. That said - you've not given us any idea how it's actually going to play - maybe ray-casting isn't needed.

    That's the problem of deterministic engines - they must be 100% accurate.

    With a simple syncing system - it simply doesn't matter if a player is in the wrong position - because they'll shortly receive an update from the Auth Server telling them where they should be.

    Deterministic system:

    Go Left 4. Right 5. ???. Left1. Right 2. Left 6. Where am I? * FYI you start at x = 9 :p

    Sync System:

    x: 5. x: 10. ??? . x: 12. x:14. x: 8. Where am I?
     
  26. andorov

    andorov

    Joined:
    Feb 10, 2011
    Posts:
    1,061
    It wouldn't break the replay function at all because you would record the state-syncs too, and then play those back along with your re-simulation.
     
  27. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    This is not a valid comparison. Especially not bandwidth wise. In a deterministic system you will send the destination, even if will take you 10 seconds to get to it a deterministic system will always take the same path and move locally over it. With a synchronizing system you will have to send the current position 5-20 times per second.
     
  28. fholm

    fholm

    Joined:
    Aug 20, 2011
    Posts:
    2,041
    Also, there is a reason that almost every AAA RTS uses a lock-step system with a deterministic simulation and not a synchronizing system. The former is just superior in every way (a lot harder to build though).
     
  29. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    Close, but no cigar.

    While they both go to the same destination, how they get there is unknown. The deterministic system pretends to be perfect in following the same trend, while the sync system does not.

    So the errors you are going to get are of the type:

    While travelling from A to B, unit X with a range of 3 came within 2.999987 of unit Y for 0.0001s on one machine only. That fluke let unit x fire a round that affect unit Y as such... leading to a desync of the entire game. The butterfly effect.

    With a sync system you keep everything the same - you still go from A to B in a relatively deterministic manner. The difference is that when unit Y fires instead of causing a desync the server merely said 'it did' and tells the clients such.

    Determinism requires every machine to be perfect. Sync simply doesn't care - it accepts errors happen and simply records what actually happened.

    You only have to report key events + a little extra to ensure that there's not much 'snapping'. At the very most I'd expect to see 3hz for units *in action*. Many units spend most of there time doing little-to-nothing - meaning you can shut them down.

    Syncing systems can use deterministic methods - they just don't require absolute accuracy.

    Exactly:

    AAA games with Multi-million budgets, that need the widest target market, many of which where released in the past [slower connections, more expensive bandwidth], written in C++ where you have much finer control...

    None of those things apply to this project.
     
    Last edited: Feb 5, 2012
  30. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Hey, I could be rich! :cool:
     
  31. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Sorry about the doublepost, but I wanted to give a status update.

    Well, I finished my FixedPoint class. It features most operators and I also added a Vector2 and Vector3 class which make use of the FixedPoint class. It all seems to work, and in fact when testing it the performance didnt suffer, actually felt faster than before.

    With that being said, I already decided not to use it. Or in other words I will probably risk Floating Point Operations and make a robust System that can recover/fix OOS bugs.

    Why?

    1) My current version was still not 100% deterministic, I think due to unitys Character Controller, which most likely uses floating point operations. Thats pretty much the first problem. I would have to rewrite a lot of component classes, which would kinda defeat the purpose of using unity, with all its nice components.

    2) Even assuming I would rewrite all component classes which use FPO, I still couldn't be sure that one of the intern backend classes uses FPO. So after days/weeks I might end up where I started.

    3) It's incredibly hard to find out why the result of a FPO is what it is. Sadly between physics, backend classes, my own FixedPoint class and casts there are way too many unknown factors.

    Anywho, here's the final FixedPoint class for anyone interested in this:
    Code (csharp):
    1.  
    2. using UnityEngine;
    3. using System;
    4.  
    5. namespace IntegerFloat
    6. {
    7.     public struct IFloat
    8.     {
    9.         // The float represented as integer
    10.         public long Value;
    11.  
    12.         // This factor determines the quality of the floats
    13.         public const int SHIFT_AMOUNT = 12; //12 is 4096
    14.         public const long FACTOR = 1 << SHIFT_AMOUNT;
    15.  
    16.         public static IFloat iOne = IFloat.Create(1);
    17.  
    18.         #region Constructors
    19.         // Float Constructor
    20.         public static IFloat Create(float FloatValue)
    21.         {
    22.             IFloat iFloat;
    23.             iFloat.Value = (int)Math.Round(FloatValue * FACTOR);
    24.             return iFloat;
    25.         }
    26.  
    27.         // Integer Constructor
    28.         public static IFloat Create(int IntValue)
    29.         {
    30.             IFloat iFloat;
    31.             iFloat.Value = IntValue << SHIFT_AMOUNT;
    32.             return iFloat;
    33.         }
    34.  
    35.         public static IFloat Zero
    36.         {
    37.             get { return IFloat.Create(0); }
    38.         }
    39.  
    40.         #endregion
    41.  
    42.         #region Values
    43.         public float AsFloat()
    44.         {
    45.             return (float)((double)Value / FACTOR);
    46.         }
    47.         #endregion
    48.  
    49.         #region Operators
    50.  
    51.         #region *
    52.         public static IFloat operator *(IFloat one, IFloat other)
    53.         {
    54.             IFloat fInt;
    55.             fInt.Value = (one.Value * other.Value) >> SHIFT_AMOUNT;
    56.             return fInt;
    57.         }
    58.  
    59.         public static IFloat operator *(IFloat aIFloat, int bInt)
    60.         {
    61.             return aIFloat * (IFloat)bInt;
    62.         }
    63.  
    64.         public static IFloat operator *(int aInt, IFloat bIFloat)
    65.         {
    66.             return bIFloat * (IFloat)aInt;
    67.         }
    68.  
    69.         #endregion
    70.  
    71.         #region /
    72.         public static IFloat operator /(IFloat one, IFloat other)
    73.         {
    74.             IFloat fInt;
    75.             fInt.Value = (one.Value << SHIFT_AMOUNT) / (other.Value);
    76.             return fInt;
    77.         }
    78.         #endregion
    79.  
    80.         #region -
    81.         public static IFloat operator -(IFloat one, IFloat other)
    82.         {
    83.             IFloat fInt;
    84.             fInt.Value = one.Value - other.Value;
    85.             return fInt;
    86.         }
    87.  
    88.         public static IFloat operator -(IFloat aIFloat, int bInt)
    89.         {
    90.             return aIFloat - (IFloat)bInt;
    91.         }
    92.  
    93.         public static IFloat operator -(int aInt, IFloat bIFloat)
    94.         {
    95.             return (IFloat)aInt - bIFloat;
    96.         }
    97.         #endregion
    98.  
    99.         #region +
    100.         public static IFloat operator +(IFloat one, IFloat other)
    101.         {
    102.             IFloat fInt;
    103.             fInt.Value = one.Value + other.Value;
    104.             return fInt;
    105.         }
    106.  
    107.         public static IFloat operator +(IFloat aIFloat, int bInt)
    108.         {
    109.             return aIFloat + (IFloat)bInt;
    110.         }
    111.  
    112.         public static IFloat operator +(int aInt, IFloat bIFloat)
    113.         {
    114.             return (IFloat)aInt + bIFloat;
    115.         }
    116.         #endregion
    117.  
    118.         #region ==
    119.         public static bool operator ==(IFloat one, IFloat other)
    120.         {
    121.             return one.Value == other.Value;
    122.         }
    123.  
    124.         #endregion
    125.  
    126.         #region !=
    127.         public static bool operator !=(IFloat one, IFloat other)
    128.         {
    129.             return one.Value != other.Value;
    130.         }
    131.         #endregion
    132.  
    133.         #region >=
    134.         public static bool operator >=(IFloat one, IFloat other)
    135.         {
    136.             return one.Value >= other.Value;
    137.         }
    138.         #endregion
    139.  
    140.         #region <=
    141.         public static bool operator <=(IFloat one, IFloat other)
    142.         {
    143.             return one.Value <= other.Value;
    144.         }
    145.         #endregion
    146.  
    147.         #region <
    148.         public static bool operator <(IFloat one, IFloat other)
    149.         {
    150.             return one.Value < other.Value;
    151.         }
    152.         #endregion
    153.  
    154.         #region >
    155.         public static bool operator >(IFloat one, IFloat other)
    156.         {
    157.             return one.Value > other.Value;
    158.         }
    159.         #endregion
    160.  
    161.         #region <<
    162.         public static IFloat operator <<(IFloat one, int amount)
    163.         {
    164.             IFloat iFloat;
    165.             iFloat.Value = one.Value << amount;
    166.             return iFloat;
    167.         }
    168.         #endregion
    169.  
    170.         #region >>
    171.         public static IFloat operator >>(IFloat one, int amount)
    172.         {
    173.             IFloat iFloat;
    174.             iFloat.Value = one.Value >> amount;
    175.             return iFloat;
    176.         }
    177.         #endregion
    178.  
    179.         #region Sqrt
    180.         public static IFloat Sqrt(IFloat f, int NumberOfIterations)
    181.         {
    182.             if (f.Value < 0) //NaN in Math.Sqrt
    183.                 throw new ArithmeticException("Input Error");
    184.             if (f.Value == 0)
    185.                 return (IFloat)0;
    186.             IFloat k = f + IFloat.iOne >> 1;
    187.             for (int i = 0; i < NumberOfIterations; i++)
    188.                 k = (k + (f / k)) >> 1;
    189.  
    190.             if (k.Value < 0)
    191.                 throw new ArithmeticException("Overflow");
    192.             else
    193.                 return k;
    194.         }
    195.  
    196.         public static IFloat Sqrt(IFloat f)
    197.         {
    198.             byte numberOfIterations = 8;
    199.             if (f.Value > 0x64000)
    200.                 numberOfIterations = 12;
    201.             if (f.Value > 0x3e8000)
    202.                 numberOfIterations = 16;
    203.             return Sqrt(f, numberOfIterations);
    204.         }
    205.         #endregion
    206.  
    207.         #endregion
    208.  
    209.         #region Casting
    210.  
    211.         public static explicit operator int(IFloat src)
    212.         {
    213.             return (int)(src.Value >> SHIFT_AMOUNT);
    214.         }
    215.  
    216.         public static explicit operator IFloat(int src)
    217.         {
    218.             return IFloat.Create(src);
    219.         }
    220.  
    221.         #endregion
    222.  
    223.         #region Misc
    224.  
    225.         public bool IsZero()
    226.         {
    227.             return (Value == 0);
    228.         }
    229.  
    230.         public override int GetHashCode()
    231.         {
    232.             return Value.GetHashCode();
    233.         }
    234.  
    235.         public override string ToString()
    236.         {
    237.             return AsFloat().ToString();
    238.         }
    239.  
    240.         #endregion
    241.     }
    242.  
    243.     public struct IVector2
    244.     {
    245.         public IFloat X;
    246.         public IFloat Y;
    247.  
    248.         #region Constructors
    249.  
    250.         public static IVector2 Create(IFloat X, IFloat Y)
    251.         {
    252.             IVector2 v;
    253.             v.X = X;
    254.             v.Y = Y;
    255.             return v;
    256.         }
    257.  
    258.         public static IVector2 Create(int x, int y)
    259.         {
    260.             return IVector2.Create(IFloat.Create(x), IFloat.Create(y));
    261.         }
    262.  
    263.         public static IVector2 Create(float x, float y)
    264.         {
    265.             return IVector2.Create(IFloat.Create(x), IFloat.Create(y));
    266.         }
    267.  
    268.         public static IVector2 Zero
    269.         {
    270.             get { return IVector2.Create(IFloat.Create(0), IFloat.Create(0)); }
    271.         }
    272.  
    273.  
    274.         public Vector2 AsVector2()
    275.         {
    276.             return new Vector2(X.AsFloat(), Y.AsFloat());
    277.         }
    278.  
    279.         #endregion
    280.  
    281.         #region Vector Operations
    282.  
    283.         #region +
    284.         public static IVector2 operator +(IVector2 one, IVector2 other)
    285.         {
    286.             return IVector2.Create(one.X + other.X, one.Y + other.Y);
    287.         }
    288.        
    289.         #endregion
    290.  
    291.         #region -
    292.         public static IVector2 operator -(IVector2 one, IVector2 other)
    293.         {
    294.             return IVector2.Create(one.X - other.X, one.Y - other.Y);
    295.         }
    296.  
    297.         #endregion
    298.  
    299.         #region SqrMagnitude
    300.         public IFloat SqrMagnitude()
    301.         {
    302.             return (X * X + Y * Y);
    303.         }
    304.         #endregion
    305.  
    306.         #region Magnitude
    307.         public IFloat Magnitude()
    308.         {
    309.             return IFloat.Sqrt(X * X + Y * Y);
    310.         }
    311.         #endregion
    312.  
    313.         #region Normalize
    314.         public IVector2 Normalize()
    315.         {
    316.             IFloat length = Magnitude();
    317.             return IVector2.Create(X / length, Y / length);
    318.         }
    319.         #endregion
    320.  
    321.         #region isZero
    322.         public bool IsZero()
    323.         {
    324.             return (X.IsZero()  Y.IsZero());
    325.         }
    326.         #endregion
    327.  
    328.         #endregion
    329.  
    330.         public override string ToString()
    331.         {
    332.             return "("+ X + ", " + Y + ")";
    333.         }
    334.     }
    335.  
    336.     public struct IVector3
    337.     {
    338.         public IFloat X;
    339.         public IFloat Y;
    340.         public IFloat Z;
    341.  
    342.         #region Constructors
    343.  
    344.         public static IVector3 Create(IFloat X, IFloat Y, IFloat Z)
    345.         {
    346.             IVector3 v;
    347.             v.X = X;
    348.             v.Y = Y;
    349.             v.Z = Z;
    350.             return v;
    351.         }
    352.  
    353.         public static IVector3 Create(Vector3 v)
    354.         {
    355.             return IVector3.Create(IFloat.Create(v.x), IFloat.Create(v.y), IFloat.Create(v.z));
    356.         }
    357.  
    358.         public static IVector3 Create(float x, float y, float z)
    359.         {
    360.             return IVector3.Create(IFloat.Create(x), IFloat.Create(y), IFloat.Create(z));
    361.         }
    362.  
    363.         public static IVector3 Zero
    364.         {
    365.             get { return IVector3.Create(IFloat.Create(0), IFloat.Create(0), IFloat.Create(0)); }
    366.         }
    367.  
    368.         public Vector3 AsVector3()
    369.         {
    370.             return new Vector3(X.AsFloat(), Y.AsFloat(), Z.AsFloat());
    371.         }
    372.  
    373.         #endregion
    374.  
    375.         #region Vector Operations
    376.  
    377.         #region +
    378.         public static IVector3 operator +(IVector3 one, IVector3 other)
    379.         {
    380.             return IVector3.Create(one.X + other.X, one.Y + other.Y, one.Z + other.Z);
    381.         }
    382.  
    383.         #endregion
    384.  
    385.         #region -
    386.         public static IVector3 operator -(IVector3 one, IVector3 other)
    387.         {
    388.             return IVector3.Create(one.X - other.X, one.Y - other.Y, one.Z - other.Z);
    389.         }
    390.  
    391.         #endregion
    392.  
    393.         #region *
    394.         public static IVector3 operator *(IVector3 aIVector, int bInt)
    395.         {
    396.             IVector3 iVector;
    397.             iVector.X = aIVector.X * bInt;
    398.             iVector.Y = aIVector.Y * bInt;
    399.             iVector.Z = aIVector.Z * bInt;
    400.             return iVector;
    401.         }
    402.  
    403.         public static IVector3 operator *(int aInt, IVector3 bIVector)
    404.         {
    405.             IVector3 iVector;
    406.             iVector.X = bIVector.X * aInt;
    407.             iVector.Y = bIVector.Y * aInt;
    408.             iVector.Z = bIVector.Z * aInt;
    409.             return iVector;
    410.         }
    411.  
    412.         public static IVector3 operator *(IVector3 aIVector, IFloat bIFloat)
    413.         {
    414.             IVector3 iVector;
    415.             iVector.X = aIVector.X * bIFloat;
    416.             iVector.Y = aIVector.Y * bIFloat;
    417.             iVector.Z = aIVector.Z * bIFloat;
    418.             return iVector;
    419.         }
    420.  
    421.         public static IVector3 operator *(IFloat aIFloat, IVector3 bIVector)
    422.         {
    423.             IVector3 iVector;
    424.             iVector.X = bIVector.X * aIFloat;
    425.             iVector.Y = bIVector.Y * aIFloat;
    426.             iVector.Z = bIVector.Z * aIFloat;
    427.             return iVector;
    428.         }
    429.  
    430.         #endregion
    431.  
    432.         #region SqrMagnitude
    433.         public IFloat SqrMagnitude()
    434.         {
    435.             return (X * X + Y * Y + Z * Z);
    436.         }
    437.         #endregion
    438.  
    439.         #region Magnitude
    440.         public IFloat Magnitude()
    441.         {
    442.             return IFloat.Sqrt(X * X + Y * Y + Z * Z);
    443.         }
    444.         #endregion
    445.  
    446.         #region isZero
    447.         public bool IsZero()
    448.         {
    449.             return (X.IsZero()  Y.IsZero()  Z.IsZero());
    450.         }
    451.         #endregion
    452.  
    453.         #endregion
    454.  
    455.         public override string ToString()
    456.         {
    457.             return "(" + X + ", " + Y + ", " + Z + ")";
    458.         }
    459.     }
    460.  
    461. }
    462.  
    463.  
    464.  


    tldr:
    I will make everything excluding FPO deterministic and attempt to correct positions/rotations etc on a regular basis. I will also record events like unit deaths, abilities and make sure they are in sync across all players.

    PS: Kudos to you for telling me pretty much I would fail right away NPSF3000, but I just had to try for myself. I know when to admit defeat, though. ;-)
    And I refreshed my memory on shifting...
     
  32. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    Been there done that :p

    If I was to retry a RTS- I'd make an awful lot of it nearly deterministic. For example I'd make the unit position follow a integer coordinate system.

    I figure it'd reduce errors, reduce bandwidth, and make other systems [e.g. path-finding] easier to implement in a deterministic fashion.
     
  33. Tynan

    Tynan

    Joined:
    Feb 4, 2012
    Posts:
    22
    Obatz, I urge you to reconsider.

    I've worked with these sorts of client-server architectures on FPS games and they're nightmarishly complex. They're packed with rules and special cases about relevance and security, and everything has to be coded to work over the network special case.

    With deterministic, you have to follow some rules in your gameplay-relevant code, but other than that it's all taken care of in a single place.

    We should really get x4000 over here to tell us how he did AI War (50,000 units) in Unity.

    Finally, I'll note that 500 units in an RTS isn't that many. Any 4 player Starcraft game will exceed that. I don't know your design, though.
     
  34. Tynan

    Tynan

    Joined:
    Feb 4, 2012
    Posts:
    22
    Obatz, I urge you to reconsider.

    I've worked with these sorts of client-server architectures on FPS games and they're nightmarishly complex. They're packed with rules and special cases about relevance and security, and everything has to be coded to work over the network special case.

    Even recording and playing back games is its own nightmare. Again, you need to deal with a ton of special case stuff, especially if you want the clients to have the recording as well as the server.

    With deterministic, you have to follow some rules in your gameplay-relevant code, but other than that it's all taken care of in a single place.

    We should really get x4000 over here to tell us how he did AI War (50,000 units) in Unity. I'll note that the unit movement in AI War is very jerky; he may just have avoided the Unity movement and physics stuff altogether.
     
  35. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    Given that RTS's are generally lag tolerant, the vast majority of these complications can be ignored.

    And rewrite anything and everything that has anything to do with float

    http://christophermpark.blogspot.com.au/2009/06/optimizing-30000-ships-in-realtime-in-c.html

    Threading. Limited hand-coded physics [no collision detection], tons of optimization, straight line path-finding etc.

    Reread what I said. I was hinting that you'd probably get 1000+ moving units running in surprisingly low bandwidth [less than high quality radio] - e.g. more than sufficient for SupCom, WiC, AoE, Homeworld etc. If you assume your players can burst to 1Mbps [which most of the developed world can] then you could have some real fun :p

    And we haven't even touched culling :p
     
  36. Tynan

    Tynan

    Joined:
    Feb 4, 2012
    Posts:
    22
    So basically, we're saying that you can do this in Unity, but only if you code every line of gameplay logic yourself, including all gameplay-relevant physics, collision, etc?
     
  37. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    Yep.

    That's what AI wars did.
     
  38. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Yeah pretty much.

    Note that I will still attempt to make everything determinstic with the exception of Floating Point Operations.

    I will write some kind of controller class that syncs unit positions on a regular basis (2-3 units per sec, so actually VERY rarely) and manages possible OOS errors.

    It's a learning project, so we'll see. ;-)
     
  39. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    Sounds good :)


    Something to remember is:

    1) Group units.
    2) Hash them.

    Basically you'll have different error rates and types or errors for units fighting, units moving, units idling, buildings, etc. - so detect all errors regularly and log them. That way you know whats going on and can tune your final 'syncing' mechanisms to be just right :)
     
  40. Obatztrara

    Obatztrara

    Joined:
    Feb 3, 2012
    Posts:
    82
    Yep I was thinking something similar.

    I'll get to that once the actual game runs on the photon cloud. Currently working on a very basic matchmaking system...
     
  41. Tynan

    Tynan

    Joined:
    Feb 4, 2012
    Posts:
    22
    Note that you'd have to sync everything about the unit, not just its position.

    For example, if on Client A, Bobby the unit is temporarily slightly further forward than on Client B, and this causes Bobby to be burned by a fire hazard on Client A but not on Client B, you've got a deadly desync. On Client A, Bobby will light up and burn to death while on Client B he'll be puttering around as usual - and that desync will never be corrected.

    Though you likely realized this already.
     
  42. PrimeDerektive

    PrimeDerektive

    Joined:
    Dec 13, 2009
    Posts:
    3,073
    With this whole semi-deterministic system, I would think an environmental hazard like that would be handled authoritatively, and the server would only need to broadcast it when it happens in his simulation.
     
  43. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    I've read the 1500 archers article and was wondering if there was something a bit more "meaty" that goes in-depth.

    I'm also confused about something when they mention lost/dropped packets... I assume you can't just do without a lost packet and the it would need to be re-submitted, because if you drop a packet then you drop a possible command, and if you do that then you are forever out of sync. Therefore, if you do wait for a lost packet (that is, one clients waits for it) then I would assume all the other clients would have to pause as well? Or is this pretty much negated by the fact that your'e essentially buffering 2 turns worth of packets, so you have some leeway here?

    Also, I was wondering if there are any examples of p2p architectures/games that are deterministic; does LoL (leage of legends) do it this way?

    And if you make it deterministic, I assume that if you want to play earlier "recordings" (that is, recordings made with an older version of the game) you would need to have the old version installed as well in order to play it back; correct?
     
  44. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    All communication has to be reliable. Semi-determinism is the worst of both worlds - either do it deterministic, or don't. Semi-deterministic with authoritative state updates from time to time is really pretty much the other way around - authoritative state updates with client-side prediction.

    The server never has to wait for input from a client - it can just carry on without it. The client's input will be applied in the next timeslice instead. So one bad player (bad computer, bad internet connection) shouldn't slow the game down for anybody else.

    If I was writing LoL, I'd do it deterministic. We were doing something similar at my previous employer, with Unity. We used fixed-point maths (custom implementation), and had a system to checksum the entire game state (using serialization and/or reflection, I don't recall - it was meant to be very thorough though). Checksums got sent to the server, which compared them against a trusted client which was shadowing the game; that way we would know who was cheating. AOT on iOS was a particular unknown quantity.

    Although we used fixed point and avoided floating point like the plague, we didn't actually create a test case that demonstrated floating point behaving differently on different platforms - I started doing it, then couldn't think which edge case would cause the problem, at least for basic operations. Square root and trig were the most dubious candidates, but they're easily replaced with deterministic implementations. So, for me this is still an unanswered question, though my tendency is to distrust floating point.

    And yes, if you want recordings to work then you have to either not patch your game, ever, or be very careful about doing it - e.g. lock down the DLL from the first release, and put all patch code in a separate DLL - perhaps a patched copy of the first.

    It's my opinion that if you're going to go down the deterministic route then you must be absolutely anal about it, otherwise you will get stung.

    But I like that kind of thing. :) So in my current game I'm using a DLL compiled in Visual Studio to contain the game logic, which doesn't know anything about Unity. This can then be plugged into different front ends, including a standalone server; I'm considering doing an XNA frontend as well. The Unity front end drives the DLL, looks at the object positions, and constructs a smoothly-interpolated Unity representation of the action. Cosmetic user input is applied directly in the Unity code - things like camera movement, clicking on a unit, browsing stats, choosing what unit type to build at a factory, are all local-only decisions. But when something needs to be done that affects the game state in any way, it has to be sent as a command via the server.

    Anyway, I think this is pretty standard if you're going down this route. We had reasonable success with it last year, until our company closed its doors. My priorities are a bit different now though - I really want to push the number of players and the number of characters in the game, to see how far it can go. I'm also interested in how well this can work on an unreliable network connection, like a 3G link. I think it could work well - even if you lose connection, when you reconnect you can replay the command stream from the last point you got to, so it might be able to recover well, and the system inherently covers up the random latency you get due to higher packet loss on 3G networks.
     
  45. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    Ok, still confused about this detail. Let's say I'm in an RTS like Command and Conquer, and I shoot a missile that is about to destroy an enemy tank factory that is just about to produce a tank. Now a packet is sent out containing my shoot command, and transmitted to all other clients. Everyone except the owner of the tank factory gets that packet. As far as me and everyone else is concerned, the factory has exploded, and no tank is produced. The owner of the factory never received the lost packet with my shoot command and is requesting for it to be resubmitted (I assume it must get all packets), but in the meantime he's produced a tank. Now what?
     
  46. andorov

    andorov

    Joined:
    Feb 10, 2011
    Posts:
    1,061
    This would never happen because every client has to acknowledge all the messages. The TCP protocol is reliable and there are ways to make the UDP protocol reliable as well. If all users do not get the message, the game simulation does not continue!
     
  47. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    You don't send the command packet to the other clients, you send it to the server. The server then puts it in the command queue. At regular intervals, the server sends a "tick" packet to all the clients, including all the queued commands in the packet. The clients receive the tick packet, and when the game time reaches the right point, they apply the commands in order before continuing the simulation. The clients are expecting these regular tick packets from the server, whether they contain commands or not - and a client can't advance its time past the next tick time until it receives the packet from the server, as otherwise it won't know what commands (if any) need to be executed at that point. So if they reach the next tick time without receiving the packet from the server, they stall until they receive the packet. If they later receive tick packets ahead of time, they may run the simulation slightly faster to catch up with "server time".

    The whole system is very asymmetric. Think of it as a unidirectional loop - commands go to the server, the server sends ticks to the game logic on each client, and the game logic state is read by the client's view code for presentation to the user, who makes decisions and issues commands to the server, etc. Data never flows in the other direction.

    Note that when you issue a command to the server, you don't enact it locally - nor do you queue it locally. You just send it to the server, wait for it to bounce back, and only queue it when you receive a response (just like you would for anybody else's commands). You don't need to track it in the meantime, though if you do it can enable you to cover up the latency by applying visual effects to pretend the command is being started - so long as you do this purely in your view code, without modifying the game state.

    Going back to your tank example, it's still possible that a client issues a "build tank" command which, by the time it bounces off the server and back, is now invalid because the factory has since been destroyed. The clients just detect this and silently reject the command; they will all agree that this is the right thing to do, because the simulation is deterministic. At the game logic level, there's no potential for disagreements. So note also that the game logic running on any client is totally agnostic about which player is local. There might not even be a local player.

    I should probably add that this might not completely agree with what's discussed in 1500 archers - it's a while since I read it, so I don't remember exactly what it said. But this is how I think it should be done, and it worked well for us at work last year.
     
  48. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    Thanks for clarifying... this confirms what I asked in my original question which is that the other clients have no choice but to pause. This is all based on a centralized server scheme, and I was wondering if this was possible in p2p. I thought the article mentioned AoE being p2p? If so, how would this be implemented in p2p?
     
  49. George Foot

    George Foot

    Joined:
    Feb 22, 2012
    Posts:
    399
    I wouldn't do strict P2P - I'd have one client run the server. It might be fair to add latency equalizing code in that case. Even with all the traffic routing through a domestic internet connection, it should be OK, because the amount of traffic is really tiny. Still, I don't find this configuration appealing.

    Bear in mind that the server does not need to run the game. It can be totally generic - all it does is receive commands, queue them, and distribute them along with ticks at a regular rate. None of that is game-specific apart from the tick rate, which can be supplied by whoever creates the session. So once you've got the server running, you never need to touch it, no matter what you do to the game. It's very lightweight, easy to set up in any language, any OS, any hosting company. CPU and bandwidth usage are very low on the server, and it's not very sensitive to latency - as we add a bunch of our own anyway.

    For what it's worth, here's a little performance test I made along these lines. It doesn't do any networking yet, but that's fairly trivial to add when the time comes. It's simulating 16,000 characters; limited by vert count as I was too lazy to support multiple meshes. The logic simulation takes about 1ms on my laptop. Pulling the data out of the simulation and into a Unity-friendly format takes a few more milliseconds. These two steps can be performed at a low frame rate though, in general - maybe only a few times per second. Then, every render frame, I interpolate the view data to get a smooth render - taking about 5ms per frame. The overall frame rate, including the render, is hovering around 60fps (16ms). Boosting the logic rate pushes it over, so I guess the rendering is taking about 10ms.

    http://www.gfootweb.webspace.virginmedia.com/Swarms/WebPlayer.html

    Click to move the reds, shift-click to move the blues. Drag to scroll, and use the mouse wheel to zoom. The simulation speed defaults to 50x the speed I actually wanted the characters to move around, because it looks cool and makes nice patterns, but you can turn that down with the slider if you like. The top of the slider is two logic updates per second; the bottom is 200. Zoom in to see the visual smoothing covering up the low logic rates.
     
  50. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    Right, but then it wouldn't really be P2P, we're simply shifting the server to one client. The benefit of P2P is that you save yourself a round trip, and if you implement it with UDP you save yourself all the overhead of TCP; that's some serious latency savings. I'm just starting to research this, so I was wondering if it's possible to implement a deterministic scheme in a P2P architecture, or if anyone sees why it can't be done? I'm going to start seriously thinking about this and do some basic prototyping, so I could use all the wisdom I can get!

    Yes, that makes sense, I didn't think about that... the server need not know a thing, it's simply forwarding data.

    Haha, that's a cool demo! I take it you're interpolating from one turns position to the next turns position over x number of frames?