Interpolation over a network - receiving and drawing an opponent in 1v1 game

Hello. I’m creating a 1v1 game with an authoritative server and two clients.

My whole network is based on UDP packets:

  • sending positions from clients
  • sending confirmations them from the server (and deleting old ones on client)
  • sending ‘non cheated’ positions to the opponent from the server

Everything was okay, until the last issue appeared.

When I send positions from the server to the opponent, they are being received in different timings. An example:

    • Position 1 comes in 43 ms
    • Position 2 comes in 15 ms (from the previous one)
    • Position 3 comes in 34 ms
    • Position 4 comes in 10 ms
    • Position 5 comes in 35 ms

As we all know - THIS IS NETWORKING, it is impossible to make it ‘stable’ that every packet comes within a constant: 30 ms time (omg that would be perfect).

And here comes my problem, I don’t know how to adjust the interpolation that the ‘opponent’ is drawn as smooth as a normal player (me on my phone).

When the process is static (I click arrows and move my player ‘step by step’) it is really, really smooth. My gameloop has some timings and it works really well.
But when I receive my opponent’s position and set his ‘desiredPosition(x,y)’ his movement is not smooth, his ‘positions’ are not ‘updating’ in a constant time but with random delays (cause we get these positions in different timings).

And example of my issue:

The gameloop:

@Override
		public void run(){
			
			long beginTime;		// the time when the cycle begun
			long timeDiff;		// the time it took for the cycle to execute
			int sleepTime;		// ms to sleep (<0 if we're behind)
			int framesSkipped;	// number of frames being skipped 
	        
	
			while(match_running){
				beginTime = System.currentTimeMillis();
				framesSkipped = 0;	// resetting the frames skipped
				// update game state 
                
                // MOST IMPORTANT METHODS - look below
                player_me.updatePosition(); // move me (smoothly) to desired position
                player_op.updatePosition(); // move the opponent (smoothly)

				// render state to the screen
				// draws the canvas on the panel
				repaint();	
				
				// calculate how long did the cycle take
				timeDiff = System.currentTimeMillis() - beginTime;
				// calculate sleep time
				sleepTime = (int)(FRAME_PERIOD - timeDiff);
				
				if (sleepTime > 0) {
					// if sleepTime > 0 we're OK
					try {
						// send the thread to sleep for a short period
						// very useful for battery saving
						Thread.sleep(sleepTime);	
					} catch (InterruptedException e) {}
				}
				
				
				while (sleepTime < 0 && framesSkipped < MAX_FRAME_SKIPS) {
					// we need to catch up
					// update without rendering
					player_me.updatePosition(); // move me to desired position
                    player_op.updatePosition(); // move the opponent
					
					// add frame period to check if in next frame
					sleepTime += FRAME_PERIOD;	
					framesSkipped++;
				}

				
				// sending positions every 30 seconds
				time_now = System.currentTimeMillis();
				if(time_now >= (packet_past_time + 30)) {
					sendPositions();
					packet_past_time = System.currentTimeMillis();
				}
			}
		}

Listening for ‘opponent’s positions’:

  public void received(Object o){
        if(object instanceof OpponentPositionList)
            player_op.setDesiredPosition(object.x, object.y);  
    }

So we set his new ‘desired position’. The Gameloop is always calling his ‘updatePosition()’ which should move him to the ‘desired position’. And it works totally smoothly with ‘Player Me’ cause it updates positions constantly, but it freezes when receiving positions ‘not constantly’ from the opponent:

  public void updatePosition(){
		 double xDistance = desiredX - this.x;
		 double yDistance = desiredY - this.y;

		 double distance = Math.sqrt(xDistance * xDistance + yDistance * yDistance);
		 
		   if (distance > 1) {
		       this.x += xDistance * 0.5;
		       this.y += yDistance * 0.5;
		   }else{
			  this.x = Math.round(this.desiredX);
			  this.y = Math.round(this.desiredY);
		   }
	}

The main question is:

If positions come not ‘constantly’, with random 10-50 ms delays how to draw the opponent as smooth as a normal player on this device? With some sort of ‘timed interpolation’ or something?
Any suggestions would be awesome. Thanks!

You need “extrapolation.” When applied to the movement of some object it is also referred to as “dead reckoning.”

In its very simplest form it is:

  • artificially computing new positions based on the last known position and the speed/velocity of the opponent at that point
  • the speed/velocity can be explicit data or obtained from the last few (two or more) position packets and the (server-)time delta between them
  • when an actual update packet is received overwrite your last computed assumed position with the real data from the received packet and use the real data from that point on for further extrapolation

Things can become arbitrarily complicated from this point on, such as compensating for when your computed position and the real position in the received packet differ (smoothing over the last or many packets) or when you know how long it took the packet to get from the opponent’s computer to the server and then to your computer to compensate for that time lag (by assuming the actual position of the opponent to be some small way futher along its direction/velocity). All that then also depends on the characteristics of the network, which also determines what the best data rate for sending updates is (so as to not flood and stall the network).

I use this code for my interpolation, this is updated every frame.
The position that is finally used is “posLerp”.
“boolean newUpdate” has to be true if a new packet has arrived, not exclusively when a position change occurred!
The position-updates are stored separately in this case.

This code does interpolation and extrapolation, but the player will always be at least a frame behind the server.


	private Vector3 posOld = null, posLerp = null, posTarget = null;
	private float deltaAccumulated = 0f, interpolationTime = 0f;

	public void updateInterpolation(float delta, Vector3 target, boolean newUpdate) {
		if(newUpdate) { //new update came in => reset counters
			//start from where we are currently
			posOld.set(posLerp);
			//set new target
			posTarget.set(target);
			//reset the accumulated time since the last position update
			deltaAccumulated = 0;
			//set the time that will probably pass till we receive another update-packet
			//GameConstants.INTERPOLATION_PERIOD_MEASURED is an average value, but you can also just use deltaAccumulated before you set it to zero
			interpolationTime = GameConstants.INTERPOLATION_PERIOD_MEASURED;
		} else if(deltaAccumulated/interpolationTime > GameConstants.EXTRAPOLATION_FACTOR) {//Extrapolation-period expired, just jump to the target position
			//The GameConstants.EXTRAPOLATION_FACTOR constant is somewhere between 1.5f and 5f, depending on how your game shall react to packet loss
			posLerp.set(target);
			posOld.set(target);
			posTarget.set(target);
		}
		//advance the interpolation time
		deltaAccumulated += delta;
		//interpolate
		posLerp.set(posOld);
		posLerp.lerp(target, deltaAccumulated/interpolationTime);
	}

You could look into other kinds of interpolation than linear to smooth out velocity jumps.

VaTTeRGeR is this possible that you will provide your lerp() method? :v

This one from here:

posLerp.lerp(target, deltaAccumulated/interpolationTime);

I’ll give it a try.

Had to change accounts, cause facebook is kinda banned and I can’t log in here cause my old acc is connected with it :smiley:

https://github.com/libgdx/libgdx/blob/master/gdx/src/com/badlogic/gdx/math/Vector3.java#L554 :wink:
I’m using LibGDX’s Vector3 class.

Thank you very much, this will help me alot.

Just one more question. How do you check your ‘newUpdate’? Do you have a list with these packets and check it’s size, or something?

I use a system where objects(“entities”) are made of components, these components can be synchronized selectively.
Every entity on the client side has a RemoteSlave component that saves the time that has passed since the last update, etc.
This time is reset to 0f when an update-package for this entity has been received, the contents of the packet are applied immediately and the packet gets discarded.
The “newUpdate”-parameter is filled with lastUpdateDelay == 0f.
So this boolean is only true in the same frame that a packet for that entity has arrived.
(With packet i do not mean UDP packet, but bag of components that is part of an large UDP packet)


		//This has been sent by the server
		ServerPosition spc = spm.get(e);
		//This is added by the client
		InterpolatedPosition ipc = ipm.get(e);
		//This too
		RemoteSlave rsc = rsm.get(e);
		
		//Update your interpolated position
		ipc.updateInterpolation(world.getDelta(), spc.pos, rsc.lastUpdateDelay == 0f);