Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting > Code Gallery
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 07-29-2011, 12:51 PM
xXziroXx xXziroXx is offline
Master of Puppets
xXziroXx's Avatar
Join Date: May 2004
Location: Sweden
Posts: 5,288
xXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant future
Send a message via AIM to xXziroXx Send a message via MSN to xXziroXx
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.destinationXtemp.destinationY)
{
  if (
onwall2(temp.destinationX X_OFFSETtemp.destinationY Y_OFFSETWIDTH_IN_TILESHEIGHT_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.destinationXtemp.destinationY);
}

function 
processNodes(temp.destinationXtemp.destinationY)
{  
  
temp.lowestFScore getLowestFScore();
  
temp.node.copyFrom(this.openNodes.(@temp.lowestFScore));
  
  
temp.pathFound closeNode(temp.lowestFScoretemp.destinationXtemp.destinationY);
  
checkSurroundingNodes(temp.node.nodeXtemp.node.nodeYtemp.lowestFScoretemp.destinationXtemp.destinationY);
  
  if (!
temp.pathFound)
    
processNodes(temp.destinationXtemp.destinationY);
  else
    
followPath(temp.lowestFScore);
}

function 
checkSurroundingNodes(temp.startXtemp.startYtemp.parentNodetemp.destinationXtemp.destinationY)
{
  
temp.surroundingNodes = {
    { 
temp.startX 1temp.startY }, // top left
    
temp.startXtemp.startY },     // top middle
    
temp.startX 1temp.startY }, // top right
    
temp.startX 1temp.startY },     // middle right
    
temp.startX 1temp.startY }, // bottom right
    
temp.startXtemp.startY },     // bottom middle
    
temp.startX 1temp.startY }, // bottom left
    
temp.startX 1temp.startY },     // middle left
  
};
  
  
temp.counter 0;
  for (
temp.nodetemp.surroundingNodes) {
    
temp.nodeX temp.node[0];
    
temp.nodeY temp.node[1];
    
temp.identifier temp.nodeX "_" temp.nodeY;
    
    
temp.isDiagonal = (temp.counter%== true false);
    
temp.nodeOnWall onwall2(temp.nodeX X_OFFSETtemp.nodeY Y_OFFSETWIDTH_IN_TILESHEIGHT_IN_TILES);
    
    
temp.gScore = (temp.isDiagonal DIAGONAL_GSCORE NORMAL_GSCORE);
    
temp.hScore getNodeDistance(temp.nodeXtemp.nodeYtemp.destinationXtemp.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.identifiertemp.destinationXtemp.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.nodeXtemp.nodeYtemp.destinationXtemp.destinationY)
{
  
temp.distance = ((temp.nodeX temp.destinationX)^+ (temp.nodeY temp.destinationY)^2)^0.5;
  return 
int(temp.distance);
}

function 
getLowestFScore()
{
  if (
this.lowestFScore != "")
    return 
this.lowestFScore;
  
  for (
temp.identifierthis.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.identifiertemp.nodeList) {
    
temp.node.copyFrom(this.closedNodes.(@temp.identifier));
    
    
setCharAni("walk""");
    
move(temp.node.nodeX this.xtemp.node.nodeY this.yMOVEMENT_SPEED16);
    
sleep(MOVEMENT_SPEED);
  }
  
  
this.trigger("MovementFinished""");
}

function 
getPath(temp.destinationNode)
{
  
temp.nodeList = new[0];
  
temp.nodeList.insert(0temp.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."_" this.y)
      
temp.nodeList.insert(0temp.node.parentNode);
    
    
temp.identifier temp.node.parentNode;
  }
  
  return 
temp.nodeList;


Usage example:
PHP Code:
//#CLIENTSIDE
function onCreated()
{
  
this.join("aStar");  
  
showCharacter();
  
moveTo(488);
}

function 
onMovementFinished()
{
  
setCharAni("idle""");
  
this.movementCounter ++;
  
  
this.dir 2;
  
this.chat "Movement finished!";
  
sleep(1);
  
this.chat "";
  
  if (
this.movementCounter == 1)
    
moveTo(4529);
  else if (
this.movementCounter == 2)
    
moveTo(5053);
  else if (
this.movementCounter == 3)
    
moveTo(2547);
  else if (
this.movementCounter == 4)
    
moveTo(819);


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.

__________________

"A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
Reply With Quote
  #2  
Old 07-29-2011, 05:17 PM
PowerProNL PowerProNL is offline
Retired Zone Manager
PowerProNL's Avatar
Join Date: Feb 2008
Location: Holland
Posts: 266
PowerProNL can only hope to improve
Send a message via AIM to PowerProNL
Wow Awesome!
__________________
Graal Mail: [email protected]
McPowerProNL, I'm loving it
Reply With Quote
  #3  
Old 07-29-2011, 06:22 PM
fowlplay4 fowlplay4 is offline
team canada
fowlplay4's Avatar
Join Date: Jul 2004
Location: Canada
Posts: 5,200
fowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond repute
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:
Reply With Quote
  #4  
Old 07-29-2011, 06:26 PM
xXziroXx xXziroXx is offline
Master of Puppets
xXziroXx's Avatar
Join Date: May 2004
Location: Sweden
Posts: 5,288
xXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant future
Send a message via AIM to xXziroXx Send a message via MSN to xXziroXx
Quote:
Originally Posted by fowlplay4 View Post
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.
__________________

"A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto

Last edited by xXziroXx; 07-29-2011 at 06:36 PM..
Reply With Quote
  #5  
Old 07-29-2011, 06:37 PM
salesman salesman is offline
Finger lickin' good.
salesman's Avatar
Join Date: Nov 2008
Location: Colorado
Posts: 1,865
salesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud of
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 View Post
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.
__________________
Reply With Quote
  #6  
Old 07-29-2011, 06:40 PM
TSAdmin TSAdmin is offline
Forum Moderator
TSAdmin's Avatar
Join Date: Aug 2006
Location: Australia
Posts: 1,980
TSAdmin is a splendid one to beholdTSAdmin is a splendid one to beholdTSAdmin is a splendid one to beholdTSAdmin is a splendid one to beholdTSAdmin is a splendid one to behold
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.
__________________
TSAdmin (Forum Moderator)
Welcome to the Official GraalOnline Forums! Where sharing an opinion may be seen as a declaration of war!
------------------------
· User Agreement · Code of Conduct · Forum Rules ·
· Graal Support · Administrative Contacts ·
Reply With Quote
  #7  
Old 07-29-2011, 06:45 PM
salesman salesman is offline
Finger lickin' good.
salesman's Avatar
Join Date: Nov 2008
Location: Colorado
Posts: 1,865
salesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud of
Quote:
Originally Posted by TSAdmin View Post
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.
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).
__________________
Reply With Quote
  #8  
Old 07-29-2011, 07:18 PM
xXziroXx xXziroXx is offline
Master of Puppets
xXziroXx's Avatar
Join Date: May 2004
Location: Sweden
Posts: 5,288
xXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant future
Send a message via AIM to xXziroXx Send a message via MSN to xXziroXx
Quote:
Originally Posted by salesman View Post
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 View Post
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.
Good point, I'll try it out.
__________________

"A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
Reply With Quote
  #9  
Old 07-29-2011, 07:45 PM
DustyPorViva DustyPorViva is offline
Will work for food. Maybe
DustyPorViva's Avatar
Join Date: Sep 2003
Location: Maryland, USA
Posts: 9,589
DustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond repute
Send a message via AIM to DustyPorViva Send a message via MSN to DustyPorViva
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.
Reply With Quote
  #10  
Old 07-29-2011, 07:51 PM
salesman salesman is offline
Finger lickin' good.
salesman's Avatar
Join Date: Nov 2008
Location: Colorado
Posts: 1,865
salesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud of
Quote:
Originally Posted by xXziroXx View Post
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.
__________________
Reply With Quote
  #11  
Old 07-29-2011, 09:42 PM
DustyPorViva DustyPorViva is offline
Will work for food. Maybe
DustyPorViva's Avatar
Join Date: Sep 2003
Location: Maryland, USA
Posts: 9,589
DustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond repute
Send a message via AIM to DustyPorViva Send a message via MSN to DustyPorViva
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?
Reply With Quote
  #12  
Old 07-29-2011, 09:54 PM
salesman salesman is offline
Finger lickin' good.
salesman's Avatar
Join Date: Nov 2008
Location: Colorado
Posts: 1,865
salesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud of
Quote:
Originally Posted by DustyPorViva View Post
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.
__________________

Last edited by salesman; 07-29-2011 at 09:55 PM.. Reason: removed pic from quote
Reply With Quote
  #13  
Old 07-29-2011, 10:17 PM
DustyPorViva DustyPorViva is offline
Will work for food. Maybe
DustyPorViva's Avatar
Join Date: Sep 2003
Location: Maryland, USA
Posts: 9,589
DustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond repute
Send a message via AIM to DustyPorViva Send a message via MSN to DustyPorViva
Quote:
Originally Posted by salesman View Post
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.
Reply With Quote
  #14  
Old 07-29-2011, 10:38 PM
Twinny Twinny is offline
My empire of dirt
Twinny's Avatar
Join Date: Mar 2006
Location: Australia
Posts: 2,422
Twinny is just really niceTwinny is just really nice
Send a message via AIM to Twinny
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
Reply With Quote
  #15  
Old 07-29-2011, 10:44 PM
DustyPorViva DustyPorViva is offline
Will work for food. Maybe
DustyPorViva's Avatar
Join Date: Sep 2003
Location: Maryland, USA
Posts: 9,589
DustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond repute
Send a message via AIM to DustyPorViva Send a message via MSN to DustyPorViva
Quote:
Originally Posted by Twinny View Post
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.
Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 04:16 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.