Extrapolation Interpolation

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?

 

I jumped into the google and wikipedia, what they had was a bit too complicated for my understanding. Humpf!

 

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

 

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.

 

http://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

 

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.  

 

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

 

thats how Valve treats the issue, seems to work fine.

 

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.

 

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

 

the code works fine,but don't know how to implement this into my network code,waitting for your test and hints!!
LoL

 

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.  

 

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.  

 

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!

 

iceshaft07 gr8 work

 

Thank you so much for this source.