Advertisement

a better way to interpolate between positions?

Started by January 24, 2005 08:19 PM
25 comments, last by leonobr 20 years ago
Quote:

"lets all execute the command at time T, or if T has passed, lets catch up"


That's how most RTS games do it; I've seen that in at least StarCraft and Warcraft III. Actually, those games will even suspend gameplay if a player has a ping greater than the command delay ("Waiting for player..." message) because they require everyone to be in sync at all times.

The draw-back, for the game that you're describing, is that the immediate feedback won't be there for the player -- jumping back and forth to dodge bullets might be an un-satisfying experience with this command delay.

Quote:

how could we be sure that we actually only wait that exact amount of time


I suggest stepping all of your world physics at the same rate, say 25 times a second (every 40 milliseconds). Measure time in steps, rather than milliseconds. When you receive a command for a specific step, put it in a queue. Each time an object is stepped, it de-queues and executes all commands that are queued for the current (or any previous) time step.

Rendering can still run faster than the physics rate; see mindcontrol.org for a description.
enum Bool { True, False, FileNotFound };
@ nice coder

i really dont understand what your trying to describe. time is already synchronized on all machines. i dont really want the client to tell the server his own velocity, because otherwise it will be easy to make yourself super fast and speed through everything. also, theres no reason to send textures or anything like that, or anything like telling the client what he can see, since the client already knows what he can / cant see, and for now no textures are dynamic..

@hplus

yes, i had read something that RTS's do this in Terranos (sp?) article. also, i think you might be right. seeing a ping ms delay in your own movement might get pretty annoying..

do you think theres any reason that i should be getting jerky movement from the other method? or do you think im screwing up somewhere in the code? ive been at it for a while and im just not sure what im doing wrong. the client clicks and starts moving at half his speed. when he gets his position, he only sets his physical position to this. the render position starts moving closer to this over time untill it catches up.. for the most part, im only seeing jerky movement when i hold down the mouse and continually click to move somewhere. if i click to move, stop at my dest, click to move again, etc, it appears to be smooth.. also, i dont allow the player to click to move untill hes already gotten his last movement ack AND hes no longer interpolating his render position, so im not sure what the problem is...

also, i had this plan where i could set some sort of "minimum latency" time, which i wanted to include into this system. kind of like the RTS style, but a little different. basically, i would just add to the timestamp the server sent a client. then, i would wait that long to execute the movement. e.g..

-client requests to move.
-server gets request. he waits 40 MS to execute the command. he then sends to al l clients including the guy who requested to move the current time + 40 MS as the timestamp

in this case, all clients who have > 80 ping will see a 40 MS reduction in their reaction times. so if you had 300 ping, reactions would appear to take 110 MS instead of 150 MS. if you had 50 ping, then it would really be like you had 80 ping, but thats not a big deal.. however, im not sure how i could implement this system if the client starts immediately moving when he clicks..

thanks again.
FTA, my 2D futuristic action MMORPG
Advertisement
ok, i figured out why it is jerky when i click to move while already moving.

the problem is this (this is hard to explain, so bear with me)


- on the clients machine, he is at 5,5 and moving to the right. at this exact time, him and the server are completely in sync. they both have the same position.

- the client clicks to the left of him to move, and then he _immediately_ starts moving at half speed towards where he clicked. so now the client is at 5,5, but heading to his left. then he tells the server "i clicked at X,Y, i want to move there". now, during the time from this exact moment untill the server gets this message, the server is still moving him to the right. when he gets the message, he then sends to the client "here is your position". the reason why they are off is because of what i just described, the server was moving him in his old direction for ping/2 MS, so they are out of sync..

now, there is a simple solution to this, but it is insecure. the client says "i clicked at X,Y and the time is T". the server gets this, finds out how long ago T was, and then "back-tracks", by moving the player at his negative velocity for T's worth of distance. now, him and the client have the exact same position (well, actually the player is off at this exact time, since the player is moving at half speed towards his dest). however, when i do it like this, then there is not much of a jump, and movemeny is actually pretty decent even with 300 ping. at 600 ping its kind of tedius though, because most of the time your moving at half speed if you hold down the mouse..

anyway, is there a beter way to do this? i *could* just use ping/2 instead of a timestamp, however, this just plain sucks. the movement is pretty choppy doing it like this..

if you think about it though, what vulnerabilities does this really open me up to? if they spoof a smaller timestamp, then they just wont back-track as much, and at worst, they wont back-track at all. all this will do is give them choppy movement (right?). if they spoof a timestamp which is too big, then they will back-track a lot. i think this has more serious vulnerabilities, since they would be able to make themselves "jump" backwards i think. i could maybe log if someone sends a timestamp > there biggest recorded ping more then say 10 times in a minute, and if so then i kick / ban them i guess..

also, i still dont know what im doing wrong with the interpolation. it actually looks better with no interpolation.. i must be screwing up bad somewhere, but cant figure out where..

thanks again.
FTA, my 2D futuristic action MMORPG
Could it also be the case that you have more than one movement command outstanding at the same time? So first you click on position A, then start moving there, then click on position B before the server has started moving you towards A, then server-A arrives, and your guy gets told to go to another position again, then server-B arrives, and your guy gets told about the actual destination.

Another issue would be that, as you say, on the server, the player is still moving towards the old goal, so the starting position for where you clicked towards the new goal will be different on the server, compared to the client. This can be hidden using interpolation, although not completely -- it's hard to figure out whether you're just ultra-sensitive to small issues, or whether your code is likely screwed up at this point.

If you know what the RTT is, you could delay the execution of a command by RTT/2, and then start executing the command, at full (not half) speed. This would be a trade-off between latency and interactivity, and it would probably interpolate better. In fact, there's a whole continuum between the three variables of "snap" and "accuracy" and "cheatability" where you have to find a sweet spot.

An alternative movement strategy would be for the server to tell the client "I think you are HERE and you should move to THERE at time T+X". On the client, you always know where you're supposed to move to, and what time you're supposed to get there. On the client, you actually run a different simulation than on the server, that just tries to get to point T at time T+X from wherever the character has previously been drawn. This makes the aiming of bullets harder, of course -- but it fixes the rendering jump, and won't allow for cheating.

Because of the latencies involved, there isn't any simple perfect solution that disallows cheating, always shows you where the server thinks you are, and never snaps, unless you go down the time dilation path we did with Diphy in the OLIVE platform. You'd be better off licensing that from us rather than trying to re-invent that from scratch, though :-)
enum Bool { True, False, FileNotFound };
Quote:
Original post by hplus0603
Could it also be the case that you have more than one movement command outstanding at the same time? So first you click on position A, then start moving there, then click on position B before the server has started moving you towards A, then server-A arrives, and your guy gets told to go to another position again, then server-B arrives, and your guy gets told about the actual destination.


when the user clicks and sends the packet, i set a bool "waiting for movement ack" to true. the user cannot click anywhere else to move unless this is false. it gets set to false when the player gets the "ok here is your position" packet from the server. also, i dont even let the user click to move untill his render position has "caught up" to his physical position,

Quote:

Another issue would be that, as you say, on the server, the player is still moving towards the old goal, so the starting position for where you clicked towards the new goal will be different on the server, compared to the client. This can be hidden using interpolation, although not completely -- it's hard to figure out whether you're just ultra-sensitive to small issues, or whether your code is likely screwed up at this point.


well, for now i have the client timestamp the packet to prevent this. its not exactly secure though, but im not sure how badly it can really be exploited...

Quote:

If you know what the RTT is, you could delay the execution of a command by RTT/2, and then start executing the command, at full (not half) speed. This would be a trade-off between latency and interactivity, and it would probably interpolate better. In fact, there's a whole continuum between the three variables of "snap" and "accuracy" and "cheatability" where you have to find a sweet spot.


ok, i just tried this, but it seems to be more jumpy then moving at half speed. im using the clients average ping / 2. for the times that it was accurate though, it definetly looked a lot nicer then moving at half speed. i couldnt even notice a delay in the reaction really.

Quote:

An alternative movement strategy would be for the server to tell the client "I think you are HERE and you should move to THERE at time T+X". On the client, you always know where you're supposed to move to, and what time you're supposed to get there. On the client, you actually run a different simulation than on the server, that just tries to get to point T at time T+X from wherever the character has previously been drawn. This makes the aiming of bullets harder, of course -- but it fixes the rendering jump, and won't allow for cheating.


wouldnt this look bad though when bullets started missing people but they took damage, or a bullet hit but nothing happend, etc? or do you think it wouldnt be that noticable?

anyway, i really dont know what im doing wrong with the interpolation. i thought i had figured out what the problem was, but thats not even the problem. i was thinking that maybe the line that goes from my render position to my physical destination was at a different angle from the line that goes from the render position to the physical position. another thing that kind of supported this was that when checking if render pos was < 1 unit away from physical pos using the distance formula like in your example, sometimes that would never trigger and i would be permanantly interpolating. i had to switch to using the dot product for it to trigger every time. anyway, i tried fixing that by making "render_xvel/yvel" variables, and each frame i would (re)calculate the render velocity based on the render position and physical position, so i sort of "heat seaked" to my destination.

however, even this doesnt look right. it still actually looks better with no interpolation [lol]. with the interpolation, the movement is jerky, almost like im moving backwards for a second. im gunna try to get this right and if not ill post some code or something. its probably just some really stupid mistake somewhere that i cant spot out for some reason..

thanks again.
FTA, my 2D futuristic action MMORPG
Are you assuming that the player keeps his old velocity until something changes it?

If so, one way to make it work, is to delay the player's movements, but build it into the game, sound & animations.

I did this in Start Wars : Rebellion. We had 2 players, player a owned his ships & player b owned his. When you clicked on a ship, and then clicked on a command or a destination, it would say 'Executing Maneuver, Sir' or something, and then after about a second, the ship would start turning & moving.

This worked within the game b/c they were large ships, and you wouldn't expect them to move on a dime. The upside of this was that I could keep in lockstep, even during packet loss or delay and still have no perceptible lag.

For your game, if you have humanoid characters, you would use animations to convey some start up time to each movement. Like say your character was running, when you hit fire, your character has to slow down and raise the rifle, which is a non-trivial movement that takes a little while. Slowing down will reduce the possibility that other players are out of sync. Also, it could be an interesting gameplay tradeoff.

If you switched directions, your character would slide to a stop, then lumber off in the other direction.

This way, you don't change your speed or direction until the server has OK'd it, and the change has a minimum time built in, designed to cover the round-trip latency.

The other characters could appear to react quicker than your character, because the the player wouldn't see the first half of their direction change. If you wanted everyone to appear in synch, then you would delay all movements by 1.5 the round trip latency of the most lagged player.

Advertisement
Also, I'm sure you saw it the first time around, but I'd like to again point out the Zen of networked character physics thread. It's good, and has source.
enum Bool { True, False, FileNotFound };
Ok. im taring my hair out, and i cant take it anymore [grin]. im going to post my code and hopefully someone is nice enough to scan through it, and can maybe find my mistake. please note: this is the code for when i have a "render velocity" which i re-calculate each frame. i have not been doing this the whole time, its just the last thing that i tried. otherwise, i would just move my render position at my physical velocity x 1.2.

all of this code is used inside the Player class. first, let me say some members of the class.

xPos, yPos - this is my physical position
render_xpos, render_ypos - this is my render position

xVel, yVel - this is my physical velocity
render_xvel, render_yvel - this is my render positions velocity

current_dest_x/y - this is my destination, where i am moving towards, where the player clicked on

Collision_Mediator::Attempt_To_Move() - this received a Player instance, a time, and a velocity. it then tries to move that player at the given velocity * given time. this function can receive either seconds or milliseconds, and if it receives milliseconds, it turns it into seconds.

first, this is the function i call when i get a message from the server saying "ok, your good to move. this is your position, and this is the time". then i call this function sending it that data. basically, this function first sets my render position to my current physical position. then it sets my physical position to what the server says. then it jumps my physical position to make up for lost time.
void Player::Movement_Request_Accepted(Uint32 timestamp,float x,float y){	//DONT FORGET! OUR INTERPOLATED POSITION STARTS HERE, AT OUR CURRENT X/Y!	if(!Math::Float_Equal(x,xPos) && !Math::Float_Equal(y,yPos))	{		render_xpos = xPos;		render_ypos = yPos;		interpolating_render_position = true;	}	//set our new position (before making up for lost time)	xPos = x;	yPos = y;	//// calculate slope	xVel = current_dest_x - (xPos);//+(w/2));	yVel = current_dest_y - (yPos);//+(h/2));	//find the distance between the target the and shooter	float diff = sqrt(xVel*xVel + yVel*yVel);	// normalize and set velocity	float invlen = 1.0f/diff;//((float)dy*dy + dx*dx);		xVel *= (invlen*200);	yVel *= (invlen*200); 	const Uint32 dt = RakNetGetTime() > timestamp ? RakNetGetTime() - timestamp : 0;	//if there was a dt (this should always be true except rarely when there is 0 ping)	if(dt > 0)	{		 	    Collision_Mediator::Attempt_To_Move(this,dt,xVel,yVel);	}//end if(dt > 0)		render_xvel = xPos - render_xpos;	render_yvel = yPos - render_ypos;	float diff2 = sqrt(render_xvel*render_xvel + render_yvel*render_yvel);	float invlen2 = 1.0f/diff2;	render_xvel *= (invlen2*225);	render_yvel *= (invlen2*225);}


then, each frame, i have a function called Player::Update() which i call. Player::Update() contains the following code, in this order:

first, i allow the player to click to move, and send the request to the server. here i also start moving at half my speed.
	if( (systm->Get_Input().Mouse_Down(3) || systm->Get_Input().Mouse_Still_Down(3) )		&& RakNetGetTime() - last_time_moved > MOVEMENT_DELAY 		&& !waiting_for_movement_ack && !interpolating_render_position)// && !movement_todo.pending)	{		//mouse x/y		int mx,my;		SDL_GetMouseState(&mx,&my);		//if they clicked on their view (e.g. not on the HUD)		if(mx >= 0 && mx < VIEWWIDTH && my >=0 && my < VIEWHEIGHT)		{						if( !( Math::Float_Equal(xPos, mx+scroll_x) && Math::Float_Equal(yPos, my+scroll_y) ) )			{				current_dest_x = mx + scroll_x;				current_dest_y = my + scroll_y;				// calculate slope				xVel = current_dest_x - (xPos);//+(w/2));				yVel = current_dest_y - (yPos);//+(h/2));				//find the distance between the target the and shooter				float diff = sqrt(xVel*xVel + yVel*yVel);				// normalize and set velocity				float invlen = 1.0f/diff;//((float)dy*dy + dx*dx);								xVel *= (invlen*100);				yVel *= (invlen*100);				Network_Mediator::Send_Movement_Request(current_dest_x,current_dest_y);//(movement_todo.dest_x,movement_todo.dest_y);				waiting_for_movement_ack = true;			}			last_time_moved = RakNetGetTime();						}	}


next, i increment the render position to move closer to the physical position
(IF we are interpolating!). i also check to see if render has caught up to physical..
	if(interpolating_render_position)	{		render_xvel = xPos - render_xpos;		render_yvel = yPos - render_ypos;		float diff = sqrt(render_xvel*render_xvel + render_yvel*render_yvel);		float invlen = 1.0f/diff;		render_xvel *= (invlen*225);		render_yvel *= (invlen*225);				float x_inc,y_inc;				x_inc = (render_xvel * timer.Time_Passed);		y_inc = (render_yvel * timer.Time_Passed);		render_xpos += x_inc;		render_ypos += y_inc;		//now if our render position has caught up to our physical position		float cntr_x = render_xpos;// + (w/2);		float cntr_y = render_ypos;// + (h/2);				//if( Math::Float_Equal( Point::Length( Point( xPos+(w/2),yPos+(h/2) ) - Point( render_xpos+(w/2),render_ypos+(h/2) ) ), 1.0f ) )		if(Point::Length(Point(xPos,yPos)-Point(render_xpos,render_ypos)) <= 1.0f)/*		if(((cntr_x-xPos)*(xVel*1.2f) + (cntr_y-yPos)*(yVel*1.2f) ) >= 0.0f)*/				{			//we stop interpolating, and snap our render position to our physical position			interpolating_render_position = false;			render_xpos = xPos;			render_ypos = yPos;			message->Add_To_Chat(player->Get_ID(),RakNetGetTime(),"RENDER == POS");		}	}	else	{		render_xpos = xPos;		render_ypos = yPos;	}


next, i do collision detection with the world and movement and last, i render using my render x/y position

Do_Collision_And_Movement();Render()


hopefully someone can spot out what im doing wrong.. thanks for any help!
FTA, my 2D futuristic action MMORPG
void Player::Movement_Request_Accepted(Uint32 timestamp,float x,float y){	//DONT FORGET! OUR INTERPOLATED POSITION STARTS HERE, AT OUR CURRENT X/Y!	if(!Math::Float_Equal(x,xPos) && !Math::Float_Equal(y,yPos))	{		render_xpos = xPos;		render_ypos = yPos;		interpolating_render_position = true;	}


I didn't read all of it, but this will snap the rendered position right there, each time you get an update. You really don't want to snap the render position at all; just keep interpolating it. The only code that should change render_pos is the code that interpolates render_pos closer to the desired physical pos; it shouldn't be written to anywhere else.

Also, you PROBABLY would want the if() to use an or (||) rather than an and, because you're probably testing whether any part of the position is different.
enum Bool { True, False, FileNotFound };
hey hplus,

that sets my rendered position to what my physical position is. but i hadnt snapped my physical position yet, which i do in the other part of the function.

also, you were right about the || [grin].

thanks for any more help.
FTA, my 2D futuristic action MMORPG

This topic is closed to new replies.

Advertisement