Graal Forums - A* Movement System

Graal Forums (https://forums.graalonline.com/forums/index.php)

- Code Gallery (https://forums.graalonline.com/forums/forumdisplay.php?f=179)

- - A* Movement System (https://forums.graalonline.com/forums/showthread.php?t=134264033)

A* Movement System

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.

Looks good, the movement just looks unnatural particularly when it's going through the diagonal sections but that's probably because of the level also being out of the ordinary.

Quote:

Originally Posted by fowlplay4 (Post 1660839)

Looks good, the movement just looks unnatural particularly when it's going through the diagonal sections but that's probably because of the level also being out of the ordinary.

Yeah, it's really not a level where you normally would use it, I just wanted to test the limitations of it. Due to the nature of the level, the loop limit is easily reached if I were to only use 1 path to get from the start to the end, but it shouldn't be a problem in normal levels.

Nice work, but it looks like your final path has some unnecessary nodes in it (such as at :25 when the npc goes in the wrong direction for a few tiles and then turns around).

Quote:

Originally Posted by xXziroXx (Post 1660840)

Yeah, it's really not a level where you normally would use it, I just wanted to test the limitations of it. Due to the nature of the level, the loop limit is easily reached if I were to only use 1 path to get from start ot end, but it shouldn't be a problem in normal levels.

You can avoid the loop limit by counting the number of loop iterations and adding sleep(.05) whenever you reach this.maxlooplimit. That way you'll still find a path, it just might take a little longer.

Sales, you made something similar once, didn't you?

Edit: http://forums.graalonline.com/forums...hp?t=134256443
The diagonals seem smoother in Sales' thread, but I'm not sure if it'd be of much use in your project for study, Ziro.

Quote:

Originally Posted by TSAdmin (Post 1660844)

I was using an npc with one direction in my movement.

I did find a few solutions to fix the the choppiness, though. The first was to just make the NPC always face the final node, so it will look like it's strafing. The second was to strip out unimportant nodes and just use the nodes where the path changes direction (in my thread, I gave the "important" nodes a different color so you can see what I'm talking about).

Quote:

Originally Posted by salesman (Post 1660843)

Nice work, but it looks like your final path has some unnecessary nodes in it (such as at :25 when the npc goes in the wrong direction for a few tiles and then turns around).

The problem with those nodes is that they're technically closer to the target, thus have a lower F score. I'm not quite sure what I can do to change that.

Quote:

Originally Posted by salesman (Post 1660843)

Good point, I'll try it out.

Hmm, I haven't done much pathfinding but... what if you ran a scan after you created a successful path and did a raycast between each node and te player. Whenever a node can no longer reach the player because of an obstruction, add the node before it to a new queue. Then, run this same check between the last position in the new queue. Use this much smaller array to create a smoother movement?

Give me a bit and I will draw out a diagram.

Quote:

Originally Posted by xXziroXx (Post 1660850)

The problem with those nodes is that they're technically closer to the target, thus have a lower F score. I'm not quite sure what I can do to change that.

There's a problem with your algorithm. With the way A* works, it will try those nodes first because of their low score, but will eventually correct itself once it realizes that they are not actually part of the "best" path.

It's been a while since I've done any pathfinding work, but I'm guessing that your problem has to do with fixing parent nodes as you find better paths. I actually used the same guide as you when creating my version of A*...this line sums up what I'm talking about pretty nicely:

Quote:

6) If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything.
On the other hand, if the G cost of the new path is lower, change the parent of the adjacent square to the selected square (in the diagram above, change the direction of the pointer to point at the selected square). Finally, recalculate both the F and G scores of that square. If this seems confusing, you will see it illustrated below.

It could be something else, but I had the same problem with not correcting parent nodes.

edit: It helps to see the path that it's creating visually. Try drawing the nodes of the final path, so you can see where it's adding nodes that it shouldn't be adding.

Now, this is just a drawing, it isn't representing a node set-up a real pathfinding has created. Just portrays the kind of path pathfinding will create: hugging the walls. Very unnatural.

http://i.imgur.com/is5kT.png

Red Circle = start
Blue Circle = end
Cyan circles = nodes
Red lines = ray cast that encounters a wall between last successful path and node check.
Yellow line = when above check encounters wall, designate previous node as optimal path and the last path chosen.

Like I said, I've dabbled very little in pathfinding, but couldn't this work?

Quote:

Originally Posted by DustyPorViva (Post 1660863)

Now, this is just a drawing, it isn't representing a node set-up a real pathfinding has created. Just portrays the kind of path pathfinding will create: hugging the walls. Very unnatural.

Red Circle = start
Blue Circle = end
Cyan circles = nodes
Red lines = ray cast that encounters a wall between last successful path and node check.
Yellow line = when above check encounters wall, designate previous node as optimal path and the last path chosen.

Like I said, I've dabbled very little in pathfinding, but couldn't this work?

A good A* implementation should give you something closer to the yellow lines not the dots anyways.

Quote:

Originally Posted by salesman (Post 1660864)

A good A* implementation should give you something closer to the yellow lines not the dots anyways.

My idea would cut back on the unnatural movements though, wouldn't it? I'm talking about the 45 degree movement, specifically, which even your A* ends up having.

Unfortunately without preset nodes, natural movement becomes incredibly taxing. For paths, I put preset nodes into the paths. These nodes contain information about which direction goes where.

So, a NPC was off path (chasing a rabbit) and needs to get back on. You work possible route(s) to the node, go back through path, always choosing lowest cost and then travel that cost effective path (this should eliminate that weird part where his NPC walked backwards randomly).

As soon as you start requiring things like 'must be 2 tiles from nearest walls' and such it just becomes far too taxing on the server.

Once I was going to set up communication so i could offload these calculations to a dev server :D

Quote:

Originally Posted by Twinny (Post 1660867)

Unfortunately without preset nodes, natural movement becomes incredibly taxing. For paths, I put preset nodes into the paths. These nodes contain information about which direction goes where.

I was thinking Bezier Curves combined with my above method O.o though I imagine that would be just as taxing.