Usually slow A* is due to poor data structure choice
I'd actually say that - on these forums, at least - slow A* is usually because the algorithm is implemented wrongly.
It doesn't help that few game developers understand state space search, and so they do things like re-opening nodes from the closed list, which makes no sense.
Thanks for your very helpful input!
I cleaned it up and removed the double PQ, and it's quick now- However in some cases it doesn't path find completely straight, it adds a little loop even when not needed. See below (first is fine, but when I path find with the target one step further away it adds the loop close to the start. What in my code can cause this?
Belwo is my full code (but the error should be in simplePather.cpp i think). I am very appreciative for any more improvement suggestions (both when it comes to cleanliness and optimization).
simplePather.ccp
#include "simplePather.h"
#include <vector>
SimplePather::SimplePather(){
setDiagonalMode( false); // by default, diagonal moves should not be allowed
}
void SimplePather::setDiagonalMode(bool allowed){
diagonalAllowed = allowed;
if(diagonalAllowed){
dx[0]=1; dy[0]=0;
dx[1]=1; dy[1]=1;
dx[2]=0; dy[2]=1;
dx[3]=-1; dy[3]=1;
dx[4]=-1; dy[4]=0;
dx[5]=-1; dy[5]=-1;
dx[6]=0; dy[6]=-1;
dx[7]=1; dy[7]=-1;
directions=8;
}
else{
dx[0]=1; dy[0]=0;
dx[1]=0; dy[1]=1;
dx[2]=-1; dy[2]=0;
dx[3]=0; dy[3]=-1;
directions=4;
}
}
int SimplePather::FindPath(const int nStartX, const int nStartY, const int nTargetX, const int nTargetY,
const unsigned char* pMap, const int nMapWidth, const int nMapHeight, int* pOutBuffer, const int nOutBufferSize)
{
std::priority_queue<simplePatherNode> pq; // list of open nodes. Open nodes are not yet tried
simplePatherNode n2(0,0,0,0); // used when checking the neighbors of n
int i, j, x, y, x2, y2;
int mapSize = nMapWidth * nMapHeight;
std::vector<int> closedMap(mapSize, 0); // closed nodes have been checked
std::vector<int> openMap(mapSize, 0); // open nodes have not been checked
std::vector<int> dirMap(mapSize);
// create the start node and push into map of open nodes
simplePatherNode n(nStartX, nStartY, 0, 0);
n.setF(nTargetX, nTargetY);
pq.push(n);
openMap[nStartX+nStartY*nMapWidth]=n.getF(); // mark it on the open nodes map
// Main path-find loop
while(!pq.empty())
{
// get the current node w/ the highest priority
// from the list of open nodes
n.setAll(pq.top().getxPos(), pq.top().getyPos(), pq.top().getG(), pq.top().getF());
x=n.getxPos();
y=n.getyPos();
// the goal state is reached = finish searching
if(x==nTargetX && y==nTargetY)
{
//hold the temporary node indexes
std::vector<int> tempNodes(nOutBufferSize);
int pathLength=0;
// generate the path from target to start
// by following the directions back to the start
while(!(x==nStartX&&y==nStartY))
{
// not enough buffer to write our path = fail path-finding
if(pathLength>=nOutBufferSize)
return -1;
j=dirMap[x+y*nMapWidth];
tempNodes[pathLength]=x+y*nMapWidth;
pathLength++;
x+=dx[j];
y+=dy[j];
}
//invert the buffer since we want to return a buffer with nodes from start to target
for(int i=0;i<pathLength;i++){
pOutBuffer[i]=tempNodes[pathLength-1-i];
}
// garbage collection
while(!pq.empty())
pq.pop();
return pathLength;
}
// If we are not at the target location, check neighbors in all possible directions
pq.pop(); // remove the node from the open list
openMap[x+y*nMapWidth]=0;
closedMap[x+y*nMapWidth]=1; // mark it on the closed nodes map
for(i=0;i<directions;i++)
{
x2=x+dx[i]; y2=y+dy[i]; // set position of next node to check
//check if already checked, is outside map-scope, impassable "terrain type"/obstacle
if(!(x2<0 || x2>nMapWidth-1 || y2<0 || y2>nMapHeight-1 || pMap[x2+y2*nMapWidth]==IMPASSABLE_NODE_TYPE || closedMap[x2+y2*nMapWidth]==1 ))
{
// set a neighbor node
n2.setAll( x2, y2, n.getG(), n.getF());
n2.increaseG(i, diagonalAllowed);
n2.setF(nTargetX, nTargetY);
// if it is not in the open map then add into that
if(openMap[x2+y2*nMapWidth]==0)
{
openMap[x2+y2*nMapWidth]=n2.getF();
pq.push(n2);
dirMap[x2+y2*nMapWidth]=(i+directions/2)%directions; // mark its parent node direction
}
else if(openMap[x2+y2*nMapWidth]<n2.getF())
{
openMap[x2+y2*nMapWidth]=n2.getF(); // update the priority info
dirMap[x2+y2*nMapWidth]=(i+directions/2)%directions; // update the parent direction info
pq.push(n2); // add the better node instead
}
}
}
}
// garbage collection
while(!pq.empty())
pq.pop();
return -1; // no route was found (couldn't reach the target node), indicate this with -1
}
// wrapper
int FindPath(const int nStartX, const int nStartY, const int nTargetX, const int nTargetY,
const unsigned char* pMap, const int nMapWidth, const int nMapHeight, int* pOutBuffer, const int nOutBufferSize)
{
SimplePather pather;
return pather.FindPath(nStartX, nStartY, nTargetX, nTargetY, pMap, nMapWidth, nMapHeight, pOutBuffer, nOutBufferSize);
};
-
simplePather.h
#pragma once
#include <queue>
#include "simplePatherNode.h"
/**
A class using a simple A-star implementation
that does not allow diagonal movement (by default)
Note that in this version all nodes (unless impassable) are considered equally easy to pass through (no variable "terrain cost")
*/
class SimplePather{
static const int IMPASSABLE_NODE_TYPE = 0; // value of map-tile if impassable
int directions; // number of possible directions to move (from a node). Will be 4 or 8 depending on diagonalMode
int dx[8];
int dy[8];
bool diagonalAllowed;
public:
SimplePather();
/**
Sets if diagonal moves should be allowed or not. Also sets the concerned variables (dx, dy)
@param allowed If diagonal moves should be allowed
@return void
*/
void setDiagonalMode(bool allowed);
/**
Finds a path from start to target or returns -1. Populates a buffer to hold indexes of the nodes from start-node to target-node excluding the start-node itself.
@param nStartX The starting x-pos
@param nStartY The starting y-pos
@param nTargetX The target x-pos
@param nTargetY The target y-pos
@param pMap The array to hold the map data (all nodes). The grid should be in row-major order.
@param nMapWidth The width (x-size) of the map to search
@param nMapHeight The height (y-size) of the map to search
@param pOutBuffer The buffer to hold the indexes to the nodes in the found path
@param nOutBufferSize The buffer size
@return The number of nodes in the found path, or -1 if no found path was found or the buffer size was to small for the found path
*/
int FindPath(const int nStartX, const int nStartY, const int nTargetX, const int nTargetY,
const unsigned char* pMap, const int nMapWidth, const int nMapHeight, int* pOutBuffer, const int nOutBufferSize);
};
//simple wrapper for the simplePather::pathFind
int FindPath(const int nStartX, const int nStartY, const int nTargetX, const int nTargetY,
const unsigned char* pMap, const int nMapWidth, const int nMapHeight, int* pOutBuffer, const int nOutBufferSize);
-
simplePatherNode.h
#pragma once
#include <stdlib.h>
// A node-class to use with simplePather
class simplePatherNode
{
int xPos;
int yPos;
int gValue; // G = total "movement cost" to reach the node from the start
int fValue; // F = G + H. Smaller F means higher priority
public:
void setAll(int xp, int yp, int gVal, int fVal)
{
xPos=xp;
yPos=yp;
gValue=gVal;
fValue=fVal;
}
simplePatherNode(int xp, int yp, int d, int p)
{
setAll(xp, yp, d, p);
}
int getxPos() const {return xPos;}
int getyPos() const {return yPos;}
int getG() const {return gValue;}
int getF() const {return fValue;}
void setF(const int & xDest, const int & yDest)
{
fValue=gValue+getH(xDest, yDest)*10;
}
// Adds to the G-value
// If diagonal movement is allowed, such moves cost 40% extra
// (1.4 is close enough to sqrt(2) which is the length of the diagonal side of a square
// Note! All ground is considered equally easy to travel.
void increaseG(const int & dir, bool diagonalAllowed)
{
if(diagonalAllowed)
gValue+=(dir%2==0?10:14);
else
gValue+=10;
}
// Get the remaining distance (not bothering with obstacles) to the goal
// (known as H-value or heuristic)
const int getH(const int & xDest, const int & yDest) const
{
// Use simple Manhattan distance for h-value
return abs(xDest-xPos)+abs(yDest-yPos);
}
};
// Used to determine priority (in the priority queue)
inline
bool operator<(const simplePatherNode & a, const simplePatherNode & b)
{
return a.getF() > b.getF();
}
It can be called like this:
Try rendering the direction of the path, to confirm how the loop is working. Also consider rendering the contents of your open/closed lists, the f/g/h values, etc. Ideally you could render step by step to see what is happening each time, but that might be tricky. Still, you have all the information that you need already.
In terms of code cleanliness you have a long way to go.
If I may I'd also recommend you replace your deeply nested indecipherable walls of commented text with appropriately named functions. This has the advantages of [a] your function name documents what the code it contains does, [2] when you profiler shows which function gobbles the most CPU time, you know which part of your algorithm needs tweaking, and [iii] you don't have to nest code so deeply that a horizontal scrollbar is required to see it all.
Most places in your code that are blocks starting with a comment could probably be refactored into meaningfully-named functions. In the process of doing that you are often presented with opportunities for improving your implementation.
I understand you can hold the code in your head and you understand it. You wouldn't have gotten where you are today if you weren't clever. It pays to assume the reader (the person marking the assignment, for example, or you yourself in a few weeks when you're studying for the exam) is a little slow and needs it explained to them like they've never seen your code before.
Stephen M. Webb
Professional Free Software Developer
I cleaned it up and removed the double PQ, and it's quick now- However in some cases it doesn't path find completely straight, it adds a little loop even when not needed. See below (first is fine, but when I path find with the target one step further away it adds the loop close to the start. What in my code can cause this?
Cool bug! I can't pick it out through code inspection, but I can offer a suggestion. Do you know how to use your debugger? Are you familiar with conditional breakpoints? In a case like this, where you have a clearly reproducible problem, you should be able to get right to the problem. Set a breakpoint when you are processing the problematic node. Probably right after:
x=n.getxPos();
y=n.getyPos(); Set the condition such that x and y are the problem node. (23,6), I think. Then if you step through the code it should become apparent what's going wrong. Particularly, I don't think node (23,5) should even get evaluated in A*, but there it is on the path.
Hope that helps,
Geoff
Not related to your current problem (since it doesn't look like you're using diagonals), but your heuristic won't work (i.e. won't be guaranteed to find the shortest path) if diagonalAllowed is true, since it would be overestimating the cost of getting to the goal.
Cascade Quest - IceFall Games - Dev blog - twitter - youtube
Actually, it might be relevant. An over-estimating heuristic will result in nodes being examined in the wrong order, which can mean the eventual path is not the optimal one.
The bug was from comparing the F values with "<" instead of ">"... Now the loops are gone!
Im still not being accepted by the server compiler, it says I get the wrong answer to one of the (unknown) tests, but all maps I try it on works fine, so I might be stuck :(
But I really appreciate the help! My code is much neater now and I learned alot.
but all maps I try it on works fine, so I might be stuck
Some suggestions for variations to test... What happens (and what should happen) in the following scenarios:
...if start and end are the same?
...if you cannot reach end from start (i.e. there is no valid path)?
...if end and/or start is inside collision (i.e. invalid map and/or invalid positions)?
...if start and/or end is not inside the map (i.e. invalid positions given for start and/or end)?
...if there is no valid map provided?
Hello to all my stalkers.
Yeah I check for all those cases and still it complains. Rather frustrating.
When start = target i fail the path, but I also tried it with including the goal node (the instructions aren't clear on how that case should be handled). None passes through all the secret tests.
