A* Movement System

[xXziroXx]

With this code, you can tell an NPC to move from point A to point B, and it'll calculate the best path using the Manhattan method. If you want to learn how this system works, I recommend reading this.

The only parts you might need to customize can be found in the onCreated() function. The system can be used both serverside and clientside.


Class: aStar

PHP Code:

//#CLIENTSIDE
function onCreated()
{
  // The following settings are adjusted for useage with a "normal" showCharacter() and can be changed to your likings.
  enum {
    WIDTH_IN_TILES = 2.5,
    HEIGHT_IN_TILES = 2,
    MOVEMENT_SPEED = 0.1,
    X_OFFSET = 0,
    Y_OFFSET = 1,
    NORMAL_GSCORE = 10,
    DIAGONAL_GSCORE = 14
  };
  
  showCharacter();
}

function moveTo(temp.destinationX, temp.destinationY)
{
  if (onwall2(temp.destinationX + X_OFFSET, temp.destinationY + Y_OFFSET, WIDTH_IN_TILES, HEIGHT_IN_TILES))
    return this.chat = "Error: blocking!";
  
  this.chat = "";
  
  temp.startX = this.x;
  temp.startY = this.y;
  temp.identifier = temp.startX @ "_" @ temp.startY;
  
  this.closedNodes = new TStaticVar();
  this.openNodes   = new TStaticVar();
  this.openNodes.(@temp.identifier).nodeX = temp.startX;
  this.openNodes.(@temp.identifier).nodeY = temp.startY;
  this.openNodes.(@temp.identifier).parent = "";
  
  processNodes(temp.destinationX, temp.destinationY);
}

function processNodes(temp.destinationX, temp.destinationY)
{  
  temp.lowestFScore = getLowestFScore();
  temp.node.copyFrom(this.openNodes.(@temp.lowestFScore));
  
  temp.pathFound = closeNode(temp.lowestFScore, temp.destinationX, temp.destinationY);
  checkSurroundingNodes(temp.node.nodeX, temp.node.nodeY, temp.lowestFScore, temp.destinationX, temp.destinationY);
  
  if (!temp.pathFound)
    processNodes(temp.destinationX, temp.destinationY);
  else
    followPath(temp.lowestFScore);
}

function checkSurroundingNodes(temp.startX, temp.startY, temp.parentNode, temp.destinationX, temp.destinationY)
{
  temp.surroundingNodes = {
    { temp.startX - 1, temp.startY - 1 }, // top left
    { temp.startX, temp.startY - 1 },     // top middle
    { temp.startX + 1, temp.startY - 1 }, // top right
    { temp.startX + 1, temp.startY },     // middle right
    { temp.startX + 1, temp.startY + 1 }, // bottom right
    { temp.startX, temp.startY + 1 },     // bottom middle
    { temp.startX - 1, temp.startY + 1 }, // bottom left
    { temp.startX - 1, temp.startY },     // middle left
  };
  
  temp.counter = 0;
  for (temp.node: temp.surroundingNodes) {
    temp.nodeX = temp.node[0];
    temp.nodeY = temp.node[1];
    temp.identifier = temp.nodeX @ "_" @ temp.nodeY;
    
    temp.isDiagonal = (temp.counter%2 == 0 ? true : false);
    temp.nodeOnWall = onwall2(temp.nodeX + X_OFFSET, temp.nodeY + Y_OFFSET, WIDTH_IN_TILES, HEIGHT_IN_TILES);
    
    temp.gScore = (temp.isDiagonal ? DIAGONAL_GSCORE : NORMAL_GSCORE);
    temp.hScore = getNodeDistance(temp.nodeX, temp.nodeY, temp.destinationX, temp.destinationY) * 10;
    temp.fScore = temp.gScore + temp.hScore;
    
    temp.counter ++;
    
    // On a wall? Ignore.
    if (temp.nodeOnWall)
      continue;
    // Closed already? Ignore.
    if (temp.identifier in this.closedNodes.getDynamicVarNames())
      continue;
    // On the open list already?
    if (temp.identifier in this.openNodes.getDynamicVarNames()) {
      // Is this path better?
      if (temp.gScore >= this.openNodes.(@temp.identifier).gScore)
        continue;
    }
    
    this.openNodes.(@temp.identifier).nodeX = temp.nodeX;
    this.openNodes.(@temp.identifier).nodeY = temp.nodeY;
    this.openNodes.(@temp.identifier).parentNode = temp.parentNode;
    this.openNodes.(@temp.identifier).gScore = temp.gScore;
    this.openNodes.(@temp.identifier).hScore = temp.hScore;
    this.openNodes.(@temp.identifier).fScore = temp.fScore;
    
    if (this.lowestFScore == "" || temp.fScore < this.openNodes.(@this.lowestFScore).fScore || this.lowestFScore in this.closedNodes.getDynamicVarNames())
      this.lowestFScore = temp.identifier;
  }
}

function closeNode(temp.identifier, temp.destinationX, temp.destinationY)
{  
  if (temp.identifier == this.lowestFScore)
    this.lowestFScore = "";
  
  temp.node.copyFrom(this.openNodes.(@temp.identifier));
  this.openNodes.(@temp.identifier).clearVars();
  this.openNodes.clearEmptyVars();
  
  if (temp.identifier in this.closedNodes.getDynamicVarNames())
    return;
  
  this.closedNodes.(@temp.identifier).copyFrom(temp.node);
  this.closedNodes.(@temp.identifier).pathIndex = this.closedNodes.getDynamicVarNames().size() - 1;
  
  if (this.closedNodes.(@temp.identifier).nodeX == temp.destinationX
   && this.closedNodes.(@temp.identifier).nodeY == temp.destinationY)
    return true;
}

function getNodeDistance(temp.nodeX, temp.nodeY, temp.destinationX, temp.destinationY)
{
  temp.distance = ((temp.nodeX - temp.destinationX)^2 + (temp.nodeY - temp.destinationY)^2)^0.5;
  return int(temp.distance);
}

function getLowestFScore()
{
  if (this.lowestFScore != "")
    return this.lowestFScore;
  
  for (temp.identifier: this.openNodes.getDynamicVarNames()) {
    temp.node.copyFrom(this.openNodes.(@temp.identifier));
    
    if (temp.lowestFScore == "" || temp.node.fScore < this.openNodes.(@temp.lowestFScore).fScore)
      temp.lowestFScore = temp.identifier;
  }
  
  return temp.lowestFScore;
}

function followPath(temp.destinationNode)
{
  temp.nodeList = getPath(temp.destinationNode);
  
  for (temp.identifier: temp.nodeList) {
    temp.node.copyFrom(this.closedNodes.(@temp.identifier));
    
    setCharAni("walk", "");
    move(temp.node.nodeX - this.x, temp.node.nodeY - this.y, MOVEMENT_SPEED, 16);
    sleep(MOVEMENT_SPEED);
  }
  
  this.trigger("MovementFinished", "");
}

function getPath(temp.destinationNode)
{
  temp.nodeList = new[0];
  temp.nodeList.insert(0, temp.destinationNode);
  temp.identifier = temp.destinationNode;
  
  while (temp.identifier != "") {
    temp.node.copyFrom(this.closedNodes.(@temp.identifier));
    if (temp.node.parentNode == "")
      break;
    
    if (temp.node.parentNode != this.x @ "_" @ this.y)
      temp.nodeList.insert(0, temp.node.parentNode);
    
    temp.identifier = temp.node.parentNode;
  }
  
  return temp.nodeList;
} 


Usage example:

PHP Code:

//#CLIENTSIDE
function onCreated()
{
  this.join("aStar");  
  showCharacter();
  moveTo(48, 8);
}

function onMovementFinished()
{
  setCharAni("idle", "");
  this.movementCounter ++;
  
  this.dir = 2;
  this.chat = "Movement finished!";
  sleep(1);
  this.chat = "";
  
  if (this.movementCounter == 1)
    moveTo(45, 29);
  else if (this.movementCounter == 2)
    moveTo(50, 53);
  else if (this.movementCounter == 3)
    moveTo(25, 47);
  else if (this.movementCounter == 4)
    moveTo(8, 19);
} 


Here's a video showing an example of usage. Note that in a lot of cases, it's better to split up the movement sequence in several shorter routes than one big, especially when your target position is close to the start from a birds eye point of view but still so far away.

The movement looks a bit choppy in the video, but it's not in-game.