Search Unity

  1. Welcome to the Unity Forums! Please take the time to read our Code of Conduct here to familiarize yourself with the rules and how to post constructively.

  2. Unity 2022.1 is now available as the latest Tech release.
    Dismiss Notice
  3. Improve your project's performance with our new guide on profiling in Unity.
    Dismiss Notice

Extrapolation Interpolation

Discussion in 'Multiplayer' started by iceshaft07, Feb 24, 2011.

  1. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    Hey everyone.

    Our game heavily relies on a single physics object that bounces around (much like a grenade).

    I am in the process of converting the game over from using UT networking to SFS2.0 networking.

    With a direct connection between the player and server, there wasn't much latency to be concerned about, but now in converting over to SFS2.0, there definitely is. And as I am also improving my networking skills step-by-step, interpolation and extrapolation seem to be the next thing to implement in our game.

    Is there some way to smooth the interpolation and extrapolation? Its a bit choppy right now and I wanted to tighten it up.

    I know I have to use the previous positions of my object to better interpolate / extrapolate the object, but how do I do that factoring in the acceleration of gravity?

    My best guess right now is I'm going to have to do something involving calculus (which is something I'm not very good at).

    I *think* I have to integrate some formula across my known points and use that to predict the curve...

    Any ideas?
     
  2. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    I jumped into the google and wikipedia, what they had was a bit too complicated for my understanding. Humpf!
     
  3. liverolA

    liverolA

    Joined:
    Feb 10, 2009
    Posts:
    347
    got the same problem,in sfs2x fps demo the movement is not smooth enough(even using Extrapolation,there is always a jitter in last position),hope someone give some hints!!
     
  4. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    Weren't there some Valve networking tutorials somewhere (I forget where these were mentioned)? I was wondering if there might have been siome info on extrapolation in those.
     
  5. appels

    appels

    Joined:
    Jun 25, 2010
    Posts:
    2,687
  6. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    After some digging, I found this extrapolation algorithm (called Neville's Algorithm) plus some code to go along with it (thank you for Math majors ;-) )

    I'm going to PHP it, then see how it works in Unity.

    Code (csharp):
    1.  
    2. www.cs.uaf.edu/~bueler/nevM.htm
    3.  
     
  7. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    Appels:
    Hmm-- so maybe my problem is not extrapolation, but rather that I should delay the client game 100ms and work on better interpolation? (On a side not, I believe Neville's Algorithm above works for interpolation as well).
     
  8. appels

    appels

    Joined:
    Jun 25, 2010
    Posts:
    2,687
    thats how Valve treats the issue, seems to work fine.
     
  9. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    Interesting.

    Well, I'm still working on converting Neville's Algorithm to UnityScript, but I will likely approach the situation as you mentioned.

    I'd like to see if Neville's Algorithm is better than just Lerping between two points.
     
  10. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    So I finally got more information on Neville's Algorithm for Interpolation Extrapolation. After finding the right article, I was able to pull this together (per the article, it works-- as far as other data samples, I don't know-- this is hot off the press!)

    This is coded, really, really, really bad and really needs to be worked out a bit. I'm not sure it will compile on iPhone devices, but it is a starting point.

    The data put in there is the data for sines .

    The original article I pulled the information from is here:
    Code (csharp):
    1.  
    2. http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/Fall2004/ceng375/node56.html
    3.  
    Code (csharp):
    1.  
    2. function Awake ()
    3. {
    4.     var vectors : Vector2 [] = (Array(Vector2(10.1,.17537),Vector2(22.2,.37784),Vector2(32.0,.52992),Vector2(41.6,.66393),Vector2(50.5,.63608))).ToBuiltin(Vector2);
    5.    
    6.     Debug.Log(ArrayToString(vectors));
    7.     vectors = SortByCloseness(27.5,vectors);
    8.     Debug.Log(ArrayToString(vectors));
    9.  
    10.     Debug.Log("-----------");
    11.     Debug.Log(NevillesAlgorithm(27.5,vectors));
    12. }
    13.  
    14. function NevillesAlgorithm (newX : float, vectors : Vector2[]) : float
    15. {
    16.     //WICKED COMPLICATED (god damn mathmaticians can't make this easier, can you!)
    17.     //P(i,j) = (x - x(i)) * P(i+1, j-1) + x(x+j - x) * P(i, j-1) / x(i+j) - x(i)
    18.     return P(0,vectors.length-1,newX,vectors);
    19. }
    20.  
    21. function P (i : int, j : int, x : float, v : Vector2[]) : float
    22. {
    23.     if (j == 0)
    24.     {
    25.     return v[i].y;
    26.     }
    27.     var ret : float = 0;
    28.  
    29. //    Debug.Log(i + " " + j);
    30. //    Debug.Log("P("+i+","+j+") = (("+x+"-"+v[i].x+") * "+P(i+1, j-1, x,v)+" + ("+v[i+j].x+" - "+x+") * "+P(i, j-1, x, v)+") / ("+v[i+j].x+"-"+v[i].x + ") = " + ret);
    31.     ret = ((x - v[i].x) * P(i+1, j-1, x,v) + (v[i+j].x - x) * P(i, j-1, x, v)) / (v[i+j].x-v[i].x);
    32.     Debug.Log("P("+i+","+j+") = (("+x+"-"+v[i].x+") * "+P(i+1, j-1, x,v)+" + ("+v[i+j].x+" - "+x+") * "+P(i, j-1, x, v)+") / ("+v[i+j].x+"-"+v[i].x + ") = " + ret);
    33.     return ret;
    34. }
    35.  
    36. function SortByCloseness (xTest : float, inArray : Vector2 []) : Vector2 []
    37. {
    38.     for (x = 0; x < inArray.length; x++)
    39.     {
    40.     for (var y : int = 0; y < inArray.length; y++)
    41.     {
    42.         if (Mathf.Abs(xTest - inArray[x].x) > Mathf.Abs(xTest - inArray[y].x)  x < y)
    43.         {
    44.         var temp2 : Vector2;
    45.         temp2 = inArray[x];
    46.         inArray[x] = inArray[y];
    47.         inArray[y] = temp2;
    48.         }
    49.     }
    50.     }
    51.  
    52.     return inArray;
    53. }
    54.  
    55.  
    56. function ArrayToString (arr : Vector2[]) : String
    57. {
    58.     var temp : String;
    59.  
    60.     for (var i : int = 0; i < arr.length; i++)
    61.     {
    62.     temp += "("+arr[i].x.ToString()+","+arr[i].y.ToString()+") ";
    63.     }
    64.  
    65.     return temp;
    66. }
    67.  
    68. function ArrayToString (arr : float[]) : String
    69. {
    70.     var temp : String;
    71.  
    72.     for (var i : int = 0; i < arr.length; i++)
    73.     {
    74.     temp += arr[i].ToString() + " ";
    75.     }
    76.  
    77.     return temp;
    78. }
    79.  
    Tomorrow, I'm going to work on implementing the above algorithm, as well as setting the delay back 100 ms.

    Liverol, you are welcome to try the the code I posted above-- make sure to let me know how it works :)
     
  11. liverolA

    liverolA

    Joined:
    Feb 10, 2009
    Posts:
    347
    the code works fine,but don't know how to implement this into my network code,waitting for your test and hints!!
    LoL
     
  12. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    Ok--

    well, briefly, what you need to do is build a vector 2 populated with time and the X Y Z values.

    example:
    Code (csharp):
    1.  
    2. //we know where the item is at 10.5 seconds...
    3. var vec : Vector3 = Vector3(2,3,4);
    4. var time : float = 10.5;
    5.  
    6. //we know where the item is at 10.7 seconds...
    7. var vec2 : Vector3 = Vector3(1,2,3);
    8. var time2 : float = 10.7;
    9.  
    10. //lets build some 2D history vectors of X,Y,Z vectors with time
    11. //x history
    12. var xVec : Vector2 [] = [Vector2(vec.x, time), Vector2(vec2.x,time2)];
    13.  
    14. //y history
    15. var yVec : Vector2 [] = [Vector2(vec.y, time), Vector2(vec2.y,time2)];
    16.  
    17. //z history
    18. var zVec : Vector2 [] = [Vector2(vec.z, time), Vector2(vec2.z,time2)];
    19.  
    20. //lets predict where the item will be .2 seconds from now
    21. var newX : float = NevillesAlgorithm(10.9,xVec);
    22. var newY : float = NevillesAlgorithm(10.9,yVec);
    23. var newZ : float = NevillesAlgorithm(10.9,zVec);
    24.  
    25. //predicted position at 10.9 seconds
    26. var predictedPosition : Vector3 = Vector3(newX, newY, newZ);
    27.  
     
  13. iceshaft07

    iceshaft07

    Joined:
    Jul 23, 2010
    Posts:
    293
    Hey-- I got this working. Try this code. It looks like it is a bit better at Interpolation than just Lerping between known points.

    The Spheres are Known Positions (data packets that finally got sent to Client) and the Cubes are predicted positions.

    Attach the script to a camera (in an empty scene) and press run. You should be able to figure it out from there.

    Code (csharp):
    1.  
    2. function Start ()
    3. {
    4. //    var tvectors : Vector4 [] = (Array(Vector4(.17537,0,0,10.1),Vector4(.37884,0,0,22.2),Vector4(.52992,0,0,32.0),Vector4(.66393,0,0,41.6),Vector4(.63606,0,0,50.5))).ToBuiltin(Vector4);
    5. //    Debug.Log(PredictPositionAtTime(27.5,tvectors));
    6.     StartCoroutine(Go());
    7. }
    8.  
    9. function Go ()
    10. {
    11.     var vectors : Vector4 [] = Array(Vector4(0,10,2,0),Vector4(.5,5,3,.05),Vector4(1,0,4,.1),Vector4(1.5,2.5,5,.15),Vector4(2,5,6,.2),Vector4(2.5,2.5,7,.25),Vector4(3,0,8,.3),Vector4(3.5,1.25,9,.35),Vector4(4,2.5,10,.4)).ToBuiltin(Vector4);
    12.    
    13.     for (var time : float = -.81; time < .8; time += .02)
    14.     {
    15.     var pos : Vector3 = PredictPositionAtTime(time,vectors);
    16.     var cube : GameObject = GameObject.CreatePrimitive(PrimitiveType.Cube);
    17.     cube.transform.position = pos;
    18.     Debug.Log("At t=" + time + ", Pos = " + pos);
    19.     yield WaitForSeconds(.25);
    20.     }
    21.  
    22.     for (var x : int = 0; x < vectors.length; x++)
    23.     {
    24.     var temp : Vector3 = Vector3(vectors[x].x,vectors[x].y,vectors[x].z);
    25.     var sphere : GameObject = GameObject.CreatePrimitive(PrimitiveType.Sphere);
    26.     sphere.transform.position = temp;
    27.     }
    28. }
    29.  
    30. function PredictPositionAtTime (time : float, vectors : Vector4 []) : Vector3
    31. {
    32.     var xVec : Array = Array();
    33.     var yVec : Array = Array();
    34.     var zVec : Array = Array();
    35.  
    36. //    Debug.Log(ArrayToString(vectors));
    37.     vectors = SortByCloseness(time,vectors);
    38. //    Debug.Log(ArrayToString(vectors));
    39.  
    40.     for (var x : int = 0; x < vectors.length; x++)
    41.     {
    42.     xVec.Add(Vector2(vectors[x].w,vectors[x].x));
    43.     yVec.Add(Vector2(vectors[x].w,vectors[x].y));
    44.     zVec.Add(Vector2(vectors[x].w,vectors[x].z));
    45.     }
    46.  
    47. //    Debug.Log(ArrayToString(xVec.ToBuiltin(Vector2)));
    48. //    Debug.Log(ArrayToString(yVec.ToBuiltin(Vector2)));
    49. //    Debug.Log(ArrayToString(zVec.ToBuiltin(Vector2)));
    50.  
    51.     var newPos : Vector3;
    52.     newPos.x = NevillesAlgorithm(time, xVec.ToBuiltin(Vector2));
    53.     newPos.y = NevillesAlgorithm(time, yVec.ToBuiltin(Vector2));
    54.     newPos.z = NevillesAlgorithm(time, zVec.ToBuiltin(Vector2));
    55.  
    56.     return newPos;
    57. }
    58.  
    59. function NevillesAlgorithm (newX : float, vectors : Vector2[]) : float
    60. {
    61.     //WICKED COMPLICATED (god damn mathmaticians can't make this easier, can you!)
    62.     //P(i,j) = (x - x(i)) * P(i+1, j-1) + x(x+j - x) * P(i, j-1) / x(i+j) - x(i)
    63.     return P(0,vectors.length-1,newX,vectors);
    64. }
    65.  
    66. function P (i : int, j : int, x : float, v : Vector2[]) : float
    67. {
    68.     if (j == 0)
    69.     {
    70.     return v[i].y;
    71.     }
    72.     var ret : float = 0;
    73.  
    74. //    Debug.Log(i + " " + j);
    75. //    Debug.Log("P("+i+","+j+") = (("+x+"-"+v[i].x+") * "+P(i+1, j-1, x,v)+" + ("+v[i+j].x+" - "+x+") * "+P(i, j-1, x, v)+") / ("+v[i+j].x+"-"+v[i].x + ") = " + ret);
    76.     ret = ((x - v[i].x) * P(i+1, j-1, x,v) + (v[i+j].x - x) * P(i, j-1, x, v)) / (v[i+j].x-v[i].x);
    77. //    Debug.Log("P("+i+","+j+") = (("+x+"-"+v[i].x+") * "+P(i+1, j-1, x,v)+" + ("+v[i+j].x+" - "+x+") * "+P(i, j-1, x, v)+") / ("+v[i+j].x+"-"+v[i].x + ") = " + ret);
    78.     return ret;
    79. }
    80.  
    81. function SortByCloseness (wTest : float, inArray : Vector4 []) : Vector4 []
    82. {
    83.     for (x = 0; x < inArray.length; x++)
    84.     {
    85.     for (var y : int = 0; y < inArray.length; y++)
    86.     {
    87.         if (Mathf.Abs(wTest - inArray[x].w) > Mathf.Abs(wTest - inArray[y].w)  x < y)
    88.         {
    89.         var temp2 : Vector4;
    90.         temp2 = inArray[x];
    91.         inArray[x] = inArray[y];
    92.         inArray[y] = temp2;
    93.         }
    94.     }
    95.     }
    96.  
    97.     return inArray;
    98. }
    99.  
    100. function SortByCloseness (xTest : float, inArray : Vector2 []) : Vector2 []
    101. {
    102.     for (x = 0; x < inArray.length; x++)
    103.     {
    104.     for (var y : int = 0; y < inArray.length; y++)
    105.     {
    106.         if (Mathf.Abs(xTest - inArray[x].x) > Mathf.Abs(xTest - inArray[y].x)  x < y)
    107.         {
    108.         var temp2 : Vector2;
    109.         temp2 = inArray[x];
    110.         inArray[x] = inArray[y];
    111.         inArray[y] = temp2;
    112.         }
    113.     }
    114.     }
    115.  
    116.     return inArray;
    117. }
    118.  
    119.  
    120. function ArrayToString (arr : Vector4[]) : String
    121. {
    122.     var temp : String;
    123.  
    124.     for (var i : int = 0; i < arr.length; i++)
    125.     {
    126.     temp += "("+arr[i].x.ToString()+","+arr[i].y.ToString()+","+arr[i].z.ToString()+","+arr[i].w.ToString()+") ";
    127.     }
    128.  
    129.     return temp;
    130. }
    131.  
    132. function ArrayToString (arr : Vector2[]) : String
    133. {
    134.     var temp : String;
    135.  
    136.     for (var i : int = 0; i < arr.length; i++)
    137.     {
    138.     temp += "("+arr[i].x.ToString()+","+arr[i].y.ToString()+") ";
    139.     }
    140.  
    141.     return temp;
    142. }
    143.  
    144. function ArrayToString (arr : float[]) : String
    145. {
    146.     var temp : String;
    147.  
    148.     for (var i : int = 0; i < arr.length; i++)
    149.     {
    150.     temp += arr[i].ToString() + " ";
    151.     }
    152.  
    153.     return temp;
    154. }
    155.  
     
  14. liverolA

    liverolA

    Joined:
    Feb 10, 2009
    Posts:
    347
    really thanks for the details,still confused to use this in sfs2 fps demo,would you please check the fps demo scripts and convert to
    above algorithm?this should be useful for you too!
    I just attactched the 2 main scripts if you don't download the sfs2x fps demo,this is the Interpolation core scripts!
    Appreciate!
     

    Attached Files:

    Deleted User likes this.
  15. chrustol

    chrustol

    Joined:
    Sep 5, 2012
    Posts:
    2
    iceshaft07 gr8 work
     
    Last edited: Mar 15, 2017
  16. Deleted User

    Deleted User

    Guest

    Thank you so much for this source.
     
unityunity