Interpolation

[12171217]

Hi. Interpolation is basically the concept of taking known values in a linear path and figuring out the points in between. In games, it generally makes things look a lot smoother. Most all FPS games interpolate other players and stuff, so I figured I'd implement it in Graal for fun. I don't have my desktop PC, as the machine took a kick to the case (literally) and the graphics card got smashed up, so I can't test if this works or what anymore. It worked last time I checked, a few weeks ago on Delteria, but I can't tell for sure if it's been touched since.

Anyway, observe another player walking around, add this script to yourself, and press Z to toggle it on and off and observe the difference. They'll be walking a lot smoother after you activate it, especially if they disable UDP. If the boxes around the player make it difficult to tell the difference, comment out the showpoly calls from the script.

IF YOU WANT TO INTERPOLATE NPCS READ THIS

It can also be used on NPCs so you can move them normally (setting their X/Y coordinates) and not have to worry about the move() command (the client will automatically smooth out the NPC's movement) and how annoying move() is to use. Just increment attr[9] every frame like so: attr[9] = (attr[9]+1)%200; on the level NPC and the system NPC in the player will do the rest. It's useful for baddies that move on a .1 or even a variable timeout (To reduce server stress, on Delteria, I had baddies on a .4 timeout, which got smaller as the player got closer to the baddy, to ensure that it would remain responsive).

If anybody wants to implement this on their server, be warned that the other players appear anywhere from 1 - (their ping/20) frames in the past, since interpolation uses values that are already known and thus "old" by a 20th of a second or so. It won't matter with NPCs, but I'm sure some players would blame losing a spar or event on it.

Any questions can be asked below :3

PHP Code:

//#CLIENTSIDE
function onPlayerEnters() {
  onTimeOut();
}

function onTimeOut() {
  setTimer(.05);
  
  hideimgs(300, this.img);
  this.img = 400;
  
  if (this.on) {
    if (this.oTimerVar == 0) this.oTimeVar = timevar2-.05;
    this.frameTime = timevar2-this.oTimeVar;
    this.oTimeVar = timevar2;
  
    checkLevelChange();
  
    saveOldPos();
    saveOldPosNPCs();
  
    lerpPlayers();
    lerpNPCs();
    
    this.frames++;
    this.hAvgReal += this.realUpdates;
    this.hAvgProjected += this.projectedUpdates;
    if (this.frames >= 20) {
      this.avgReal = this.hAvgReal/20;
      this.avgProjected = this.hAvgProjected/20;
      this.hAvgReal = 0;
      this.hAvgProjected = 0;
      this.frames = 0;
    }
    showtext(301, 0, screenheight-48, "Arial", null, "Real updates: " @ this.realUpdates);
    changeimgcolors(301, 1, 1, 0, 1);
    findimg(301).layer = 5;
    findimg(301).zoom = .7;
    showtext(302, 0, screenheight-32, "Arial", null, "Projected updates: " @ this.projectedUpdates);
    changeimgcolors(302, 0, 1, 0, 1);
    findimg(302).layer = 5;
    findimg(302).zoom = .7;
    showtext(303, 0, screenheight-80, "Arial", null, "Average real updates: " @ this.avgReal);
    changeimgcolors(303, 1, 1, 0, 1);
    findimg(303).layer = 5;
    findimg(303).zoom = .7;
    showtext(304, 0, screenheight-64, "Arial", null, "Average projected updates: " @ this.avgProjected);
    changeimgcolors(304, 0, 1, 0, 1);
    findimg(304).layer = 5;
    findimg(304).zoom = .7;
  }
  
  if (this.on == 2) {
    showtext(300, 0, screenheight-16, "Arial", null, "Cosine Interpolation on");
    changeimgcolors(300, 0, 1, 0, 1);
  } else if (this.on == 1) {
    showtext(300, 0, screenheight-16, "Arial", null, "Linear Interpolation on (Best)");
    changeimgcolors(300, 0, 1, 0, 1);
  } else if (this.on == 0) {
    showtext(300, 0, screenheight-16, "Arial", null, "All Interpolation off (Graal Default)");
    changeimgcolors(300, 1, 0, 0, 1);
  }
  findimg(300).layer = 5;
  findimg(300).zoom = .7;
}

function onKeyPressed(keycode, key) {
  if (key == "z") {
    this.on++;
    if (this.on > 1) {
      this.on = 0;
    }
  }
}

function checkLevelChange() {
  if (player.level.name != this.oldLevel) {
    for (pl : players) {
      pl.lerp = 0;
      pl.oldX = pl.newX = pl.x;
      pl.oldY = pl.newY = pl.y;
    }
    for (n : npcs) {
      n.lerp = 0;
      n.oldX = n.newX = n.x;
      n.oldY = n.newY = n.y;
    }
    this.oldLevel = player.level.name;
  }
}

function saveOldPos() {
  this.realUpdates = 0;
  for (pl : players) {
    if (pl == player) continue;
    if (pl.lerp > 0) continue;
    temp.update = false;
    if (pl.x != pl.oldX) {
      pl.oldX = pl.newX;
      pl.newX = pl.x;
      temp.update = true;
    }
    if (pl.y != pl.oldY) {
      pl.oldY = pl.newY;
      pl.newY = pl.y;
      temp.update = true;
    }
    if (temp.update) {
      //Get distance on each axis; Lerping very small values
      //looks awful.
      temp.distX = abs(pl.newX-pl.oldX);
      temp.distY = abs(pl.newY-pl.oldY);
      this.realUpdates++;
      if ((temp.distX > .25 || temp.distY > .25) && (temp.distX < 2 && temp.distY < 2)) {
        pl.doLerp = true;
        pl.oldPacketTime = pl.newPacketTime;
        pl.newPacketTime = timevar2;
        pl.lerpDiv = pl.newPacketTime-pl.oldPacketTime;
        pl.lerp = 1;
      } else {
        pl.doLerp = false;
      }
    }
  }
}

function saveOldPosNPCs() {
  this.realUpdates = 0;
  for (n : npcs) {
    if (n.attr[9] == 0) continue;
    temp.update = false;
    if (n.attr[9] != n.oldAttr) {
      n.oldX = n.newX;
      n.newX = n.x;
      n.oldY = n.newY;
      n.newY = n.y;
      n.oldZ = n.newZ;
      n.newZ = n.z;
      n.oldAttr = n.attr[9];
      temp.update = true;
    } else {
      continue;
    }
    if (temp.update) {
      //Get distance on each axis; Lerping very small values
      //looks awful.
      temp.distX = abs(n.newX-n.oldX);
      temp.distY = abs(n.newY-n.oldY);
      this.realUpdates++;
      n.oldPacketTime = n.newPacketTime;
      n.newPacketTime = timevar2;
      temp.div = n.newPacketTime-n.oldPacketTime;
      if (temp.div > 1) continue;
      n.doLerp = true;
      n.lerpDiv = 0.05/(temp.div);
      n.lerp = 1;
      continue;
    } else {
      n.doLerp = false;
      continue;
    }
  }
}

function lerpPlayers() {
  this.projectedUpdates = 0;
  for (pl : players) {
    if (pl == player) continue;
    showpoly(this.img, {pl.x+.5, pl.y, pl.x+2.5, pl.y});
    changeimgcolors(this.img, 1, 0, 0, 1);
    this.img++;
    showpoly(this.img, {pl.x+2.5, pl.y, pl.x+2.5, pl.y+3});
    changeimgcolors(this.img, 1, 0, 0, 1);
    this.img++;
    showpoly(this.img, {pl.x+2.5, pl.y+3, pl.x+.5, pl.y+3});
    changeimgcolors(this.img, 1, 0, 0, 1);
    this.img++;
    showpoly(this.img, {pl.x+.5, pl.y+3, pl.x+.5, pl.y});
    changeimgcolors(this.img, 1, 0, 0, 1);
    this.img++;
    if (!pl.doLerp) continue;
    if (pl.lerp >= -.5) {
      this.projectedUpdates++;
      pl.lerp -= .5;
      if (this.on == 1) {
        pl.x = linearInterpolateValue(pl.oldX, pl.newX, abs(1-pl.lerp));
        pl.y = linearInterpolateValue(pl.oldY, pl.newY, abs(1-pl.lerp));
      } else if (this.on == 2) {
        pl.x = cosineInterpolateValue(pl.oldX, pl.newX, abs(1-pl.lerp));
        pl.y = cosineInterpolateValue(pl.oldY, pl.newY, abs(1-pl.lerp));
      }
    }
    showpoly(this.img, {pl.x+.5, pl.y, pl.x+2.5, pl.y});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
    showpoly(this.img, {pl.x+2.5, pl.y, pl.x+2.5, pl.y+3});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
    showpoly(this.img, {pl.x+2.5, pl.y+3, pl.x+.5, pl.y+3});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
    showpoly(this.img, {pl.x+.5, pl.y+3, pl.x+.5, pl.y});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
  }
}

function lerpNPCs() {
  this.projectedUpdates = 0;
  for (n : npcs) {
    if (n.attr[9] == 0) continue;
    if (!n.doLerp) continue;
    if (n.lerpDiv == 0) n.lerpDiv = .5;
    if (n.lerp >= 0) {
      this.projectedUpdates++;
      n.lerp -= n.lerpDiv*(this.frameTime*20);
      if (this.on == 1) {
        n.x = linearInterpolateValue(n.oldX, n.newX, abs(1-n.lerp));
        n.y = linearInterpolateValue(n.oldY, n.newY, abs(1-n.lerp));
        n.z = linearInterpolateValue(n.oldZ, n.newZ, abs(1-n.lerp));
      } else if (this.on == 2) {
        n.x = cosineInterpolateValue(n.oldX, n.newX, abs(1-n.lerp));
        n.y = cosineInterpolateValue(n.oldY, n.newY, abs(1-n.lerp));
        n.z = cosineInterpolateValue(n.oldZ, n.newZ, abs(1-n.lerp));
      }
    }
    /*
    showpoly(this.img, {n.x+.5, n.y, n.x+2.5, n.y});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
    showpoly(this.img, {n.x+2.5, n.y, n.x+2.5, n.y+3});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
    showpoly(this.img, {n.x+2.5, n.y+3, n.x+.5, n.y+3});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
    showpoly(this.img, {n.x+.5, n.y+3, n.x+.5, n.y});
    changeimgcolors(this.img, 0, 1, 0, 1);
    this.img++;
    */
  }
}

function linearInterpolateValue(temp.ov, temp.nv, temp.l) {
  return (temp.ov*(1-temp.l)+temp.nv*temp.l);
}

function cosineInterpolateValue(temp.ov, temp.ny, temp.l) {
  temp.newLerp = (1-cos(temp.l*pi))/2;
  return (temp.ov*(1-temp.newLerp)+temp.ny*temp.newLerp);
} 


Please note this was a test script that was written rather hastily to see what interpolation would be like in Graal. If you want to have interpolation for NPCs/baddies or players on your server, use this as reference, but don't use this without modification.

EDIT: I didn't mean to put this in code gallery. It's not organized or structured well enough to be a finished product, I just wanted to share the concept of interpolation and how it works, while giving an example.

[fowlplay4]

Any recommended documents (aimed towards game development) to read on this particular subject?

[12171217]

Originally Posted by fowlplay4

Any recommended documents (aimed towards game development) to read on this particular subject?

How to Network like a Boss, by Valve Software:
http://developer.valvesoftware.com/w...yer_Networking

FPS-independent movement, interpolation, extrapolation, storing old player frames and stepping into the past to check for paradoxes between players, movement prediction all covered there. One of my favorite articles for networking in games

[Crono]

do you know downsider?

[12171217]

Originally Posted by Crono

do you know downsider?

but.. i am downsider..

[MrOmega]

Just wondering the actual performance benefits of this, but if the server guesses where the player will be and he isn't there, does the server take steps to correct this to make it smooth or do it make them 'choppy' even for this correction wouldn't it cause higher lag and Client1->Server->Client2 lag?

[12171217]

Originally Posted by MrOmega

Just wondering the actual performance benefits of this, but if the server guesses where the player will be and he isn't there, does the server take steps to correct this to make it smooth or do it make them 'choppy' even for this correction wouldn't it cause higher lag and Client1->Server->Client2 lag?

I haven't gone as in depth for that much yet. I only do the visual aspect right now. The server doesn't guess where the player will be, and neither does the client. The client knows the old position and the new position, and uses this to find out what could be in between. You really can't have any large error because of that. With extrapolation, the errors are large and obvious (Unless the player accelerates and decelerates slowly, Halo uses extrapolation), which is why I chose to implement interpolation in Graal, where you can change direction instantly.

The "actual performance benefits" should be large, since you can run an NPC on a .5 timeout and have it look just as good as a clientside .05 timeout. The server never "guesses where the player is" in this implementation as doing what the Valve article suggests would require an entire systems rewrite. Classic could implement prediction and interpolation, along with the history-stepping and stuff, with relative ease.

[fowlplay4]

Well I just implemented the player interpolation (on by default) on Zodiac. I am quite impressed with the differences, nice work.

For those interested in the differences, toggle it: /toggle interpolation

[12171217]

Originally Posted by fowlplay4

Well I just implemented the player interpolation (on by default) on Zodiac. I am quite impressed with the differences, nice work.

For those interested in the differences, toggle it: /toggle interpolation

Fantastic. Glad to have been of service

There also might be issues with transferring levels/off and on gmaps, I hadn't tested extensively enough to know. Look out for stuff like that.

[MrOmega]

Using this on my server, do you want 12171217 or Donwsider in my Contributors sections? :P

[cbk1994]

Added this to Era, enabled by default. You can disable it in the options menu.

[Crono]

on zodiac if you go into a dungeon and the person hasn't moved yet you don't see them in their real positions

[DustyPorViva]

Originally Posted by Crono

on zodiac if you go into a dungeon and the person hasn't moved yet you don't see them in their real positions

Should be an easy fix. Just make it interpolate when a previous position is known.

[fowlplay4]

Originally Posted by Crono

on zodiac if you go into a dungeon and the person hasn't moved yet you don't see them in their real positions

Going need instructions to replicate it, because I've been unsuccessful.

Also... Plug-n-play Player Movement Interpolation system. Obviously customize isOn() to suit your server's needs.

PHP Code:

//#CLIENTSIDE

function onPlayerEnters() {
  if (isOn()) {
    checkLevelChange();
    onTimeout();
  }
}

function isOn() {
  return !client.option_disableinterpolation;
}

function onTimeout() {
  if (isOn()) {
    if (this.oTimerVar == 0) this.oTimeVar = timevar2-.05;
    this.frameTime = timevar2-this.oTimeVar;
    this.oTimeVar = timevar2;
    saveOldPos();
    lerpPlayers();
    setTimer(0.05);
  }
}

function checkLevelChange() {
  if (player.level.name != this.oldLevel) {
    for (pl : players) {
      pl.lerp = 0;
      pl.oldX = pl.newX = pl.x;
      pl.oldY = pl.newY = pl.y;
    }
    this.oldLevel = player.level.name;
    this.forceupdate = true;
  }
}

function saveOldPos() {
  for (pl : players) {
    if (pl == player) continue;
    if (pl.lerp > 0) continue;
    temp.update = this.forceupdate;
    if (pl.x != pl.oldX) {
      pl.oldX = pl.newX;
      pl.newX = pl.x;
      temp.update = true;
    }
    if (pl.y != pl.oldY) {
      pl.oldY = pl.newY;
      pl.newY = pl.y;
      temp.update = true;
    }
    if (temp.update) {
      temp.distX = abs(pl.newX-pl.oldX);
      temp.distY = abs(pl.newY-pl.oldY);
      if ((temp.distX > .25 || temp.distY > .25) && (temp.distX < 2 && temp.distY < 2)) {
        pl.doLerp = true;
        pl.oldPacketTime = pl.newPacketTime;
        pl.newPacketTime = timevar2;
        pl.lerpDiv = pl.newPacketTime-pl.oldPacketTime;
        pl.lerp = 1;
      } else {
        pl.doLerp = false;
      }
    }
  }
  if (this.forceupdate) this.forceupdate = false;
}

function lerpPlayers() {
  for (pl : players) {
    if (pl == player) continue;
    if (!pl.doLerp) continue;
    if (pl.lerp >= -.5) {
      pl.lerp -= .5;
      pl.x = linearInterpolateValue(pl.oldX, pl.newX, abs(1-pl.lerp));
      pl.y = linearInterpolateValue(pl.oldY, pl.newY, abs(1-pl.lerp));
    }
  }
}

function linearInterpolateValue(temp.ov, temp.nv, temp.l) {
  return (temp.ov*(1-temp.l)+temp.nv*temp.l);
}