Game Development Community

A* Pathfinding headaches

by Kevin James · in Torque Game Builder · 08/04/2010 (1:51 pm) · 5 replies

This topic was started in this thread:
www.torquepowered.com/community/forums/viewthread/118609
But the issue is no longer about the tile custom data.

I can get the AStarDemo to work. That's no big deal. The problem starts when I try to apply these methods to my own grid. I want to click a spot on the grid and have the player move to that spot using A* pathfinding. So far the player moves toward the target but stops at least 1 node short of the destination. Sometimes it only moves to number 2 node out of 5. Here are the relevant functions with echo data:

function aStarActor::onPositionTarget(%this)
{
   // we're at our target, time to move to next node
   // first, check to make sure we're not finished with our destination
   if (%this.currentPathNodeIndex == %this.lastAStarNodeIndex)
   {
      // we've reached destination!
      %this.onAStarDestinationReached();
      return;
   }
   // increment to our next node
   if (isObject(%this.currentPath) )
   {
     %this.currentPathNodeIndex++;
     %this.moveToAStarNode(%this.currentPathNodeIndex);
echo ("aStarActor::onPositionTarget: "@%this.currentPathNodeIndex SPC %this.lastAStarNodeIndex);
   }
   else
   {
      // allow a hook if desired to track a path disappearing out from underneath us
      // %this.noPathExists();
   }
}

function aStarActor::moveToAStarNode(%this, %nodeIndex)
{
   if (!isObject(%this) )
   {
      // we shouldn't be attempting to move as an aStarActor if we aren't a valid object
      error("aStarActor (" @ %this @ ") in game but not object, how?");//never gets here
      return;
   }
   if (!isObject(%this.currentPath) )
   {
      // we shouldn't be attempting to move to an aStar node if we don't have a path
      error("aStarActor (" @ %this @ ") without a path");//never gets here
      return;
   }

     // getNodeWorldCoords(%index) is a ConsoleMethod on the pathAStar2d class
     %nodeWorldCoords = %this.currentPath.getNodeWorldCoords(%nodeIndex);
     if (%nodeWorldCoords $= "InvalidNode")
     {
        %this.noPathExists();
        echo("aStarActor::moveToAStarNode: no path");//never gets here
     }
     else
     {
       %this.moveTo(%nodeWorldCoords,
                  %this.moveSpeed,     // speed
                  false,  // stop?
                  true,   // callback?
                  false,  // snap?
                  0.8     // margin
                  );
echo("aStarActor::moveToAStarNode: "@%nodeWorldCoords);
     }

}

console output example 1:
findDestination: -20.969 -47.418
aStarActor::moveToAStarNode: -17.499992 -22.500015
aStarActor::moveToAStarNode: -17.499992 -22.500015
aStarActor::onPositionTarget: 1 3
aStarActor::moveToAStarNode: -17.499992 -42.500015
aStarActor::onPositionTarget: 2 3

example 2:
findDestination: -24.699 -48.544
aStarActor::moveToAStarNode: 2.500009 -37.500000
aStarActor::moveToAStarNode: 2.500009 -37.500000
aStarActor::onPositionTarget: 1 5
aStarActor::moveToAStarNode: -2.499991 -37.500000
aStarActor::onPositionTarget: 2 5
aStarActor::moveToAStarNode: -7.499991 -42.500015
aStarActor::onPositionTarget: 3 5
aStarActor::moveToAStarNode: -17.499992 -42.500015
aStarActor::onPositionTarget: 4 5

Here's an example where it does get to the last node, but the actor is well short of the destination:
findDestination: 25.750 -21.943
aStarActor::moveToAStarNode: 7.500010 -22.500015
aStarActor::moveToAStarNode: 7.500010 -22.500015
aStarActor::onPositionTarget: 1 2
aStarActor::moveToAStarNode: 27.500010 -22.500015
aStarActor::onPositionTarget: 2 2

Every tile in the grid has custom data set to zero.

Any ideas or troubleshooting suggestions?


About the author

Computer security, digital forensics, and platform jumper enthusiast. shells.myw3b.net/~syreal/


#1
08/04/2010 (6:17 pm)
I found a way for the player to find the destination. These lines go in the player's onUpdate:
%this.destinationCoords = %this.findDestination(); 
%this.startPath(%this.position,%this.destinationCoords);

This is very sloppy and probably creates a bunch of memory leaks. Oh well.

Now the problem is how the player frequently gets stuck on wall corners trying to reach the destination.
#2
08/04/2010 (6:49 pm)
Kevin,

You really shouldn't have to put that in there but I can't see what's going on with your project. Send me an email if you want an example that I have working to compare against.

patrickadesso --hat-- gmail
#3
08/05/2010 (3:53 pm)
Thanks Patrick! Your demo showed me why my player was getting stuck on the corners. Apparently, the tile size needs to be at least as big as the unit on the path. I have wide open rooms and tunnels, but going around the corners requires the correct size.
#4
08/05/2010 (4:17 pm)
Glad it's working for you now!
#5
08/05/2010 (4:53 pm)
I still can't get away starting the path in onUpdate. Without that, it only moves a short distance and then stops for no reason. This way, the path is constantly updated and the actor eventually gets there.