Sign in to follow this  
Anand Baumunk

A* on large Map

Recommended Posts

Anand Baumunk    699

Well met,

 

I tried to implement simple pathfinding into my game, using A* algorithm. The map is a simple 2D map with the classic open/closed-nodes mechanic. But my implementation of A* takes about one second to get a path on a 32x32 grid, which is, of corse, already much too slow. When applied on a larger grid, there is no way of using it.

So, my question is how to approach this. Did I mess up with the implementation, or do I have to have some kind of subdivision (movementmesh etc) for my grid to use A* effectively? At the moment, my map has 1024x1024 vertices in it.

 

Thanks in advance!

-gnomgrol

Share this post


Link to post
Share on other sites
DrEvil    1148
Something is wrong with your algorithm. 1 second for a 32*32 grid suggests a broken algorithm. You should be comfortably inside 1 second in. A 100*100 or larger easily.

Are you profiling in release mode? How are you handling your open/closed lists? Memory allocation?

Share this post


Link to post
Share on other sites
markr    1692

You're going to have to put some instrumentation in to find out the answer to these questions.

 

If you implement it incorrectly, A* becomes the same as Dijkstra's algorithm. This still always finds the shortest path, but in some cases takes a lot longer.

 

You need to produce some test-cases where A* should be considering only a small number of nodes, to check that it really is only considering the nodes it needs to (not going to the opposite side of the map, looking for a shorter route, because there can't be one (assuming no teleporters, time machines etc, in the map))

Share this post


Link to post
Share on other sites
Postie    1559

How did you implement the open and closed lists? If you use basic lists and perform a search to find the appropriate node each time that'll kill your performance.

 

In my implementation (in C#) I eventually settled on a BinaryHeap for the open list and a Hashset for the closed list. My first cut used basic lists, and it was horrific. 

Share this post


Link to post
Share on other sites
ericrrichards22    2421

You definitely want to use some kind of priority queue for the open list.

It's possible that you are using a bad heuristic.

1 sec for a 32x32 map is way too slow.  I'm doing pathing on a 1024x1024 grid, and I'm getting < 100 ms performance.  I haven't finished writing up my blog post on pathfinding, but if you check back on my developer journal tomorrow or saturday, I should have my code up.

Another great resource for A* is http://theory.stanford.edu/~amitp/GameProgramming/

Share this post


Link to post
Share on other sites
Anand Baumunk    699

For the open/closed lists, I'm using 

static int closed_nodes_map[n][m];
static int open_nodes_map[n][m];
static priority_queue<node> pq[2];

and using classic pop()/push() on pq.

Im also using some new/delete stuff, maybe that's contributing to it.

Is there something better to use than arrays?

 

I'll have to run some tests on that, thanks a lot!

Edited by gnomgrol

Share this post


Link to post
Share on other sites
greenpig83    330

Hey I'm working with path Finding, and solve a very hard problem, 1 thousand units moving through map of size 512x512 at a time (speed is crucial for me). So i think I can help u a bit !

32x32 size in normal computer will take no longer than 1ms (milisecond)  (even if it's unreachable). So ofcourse u mess up something ! download an A* sourcecode with example and test it first!

A* is overall good, but implement it take a bit problem.

I myself prefer a better way, although i think basically it's quite like A* , just different in how u program it !

 

I dont use openSet, closeSet. I use 2 openSet to swap. we get all node in first openSet -> process it -> put new nodes in the second Set, then swap! so we dont have to worry about openSet size,index....This way it's very easy to program.

in worst case, every pathFinding will search all nodes, so dont worry, we just need that in easy case, or normal case, we find goal as fast as possible !

 

in each loop, we choose a best candidate. how is it best, we calculate it length to goal (real length in cordinate : (goalX-x)^2 +(goalY-y)^2 ). if we have best candidate, we just use it, we dont use the openSet. If there is no best candidate, we come back to the openSet. The nice thing about this : we will always head to the goal, if there is a clear path from source to goal, we will reach the goal in the fastest way(no openSet used)  ! in bad case, if we have to go around, around to get to goal, it's still have the speed of other algorithm. 

 

If u like my idea, and want the code, i can put it here ! It's quite simple !

Edited by greenpig83

Share this post


Link to post
Share on other sites
greenpig83    330
OK here the code.
Hope it's helpful for u!
This is just a simple version, u can modify it for  min,maxRange search, source Size, goal Size.... Check goal if goal is surrounded by obstacle (so no way reach it)...
 
int * sOpenSet[2];
int sOpenSetSize[2];
int * sMatrixLen = NULL;
int * sMatrixFrom = NULL; //direction
 
//check if we can move to pos x,y
//check with your map here!
bool canMoveHere(int x,int y){
if (x==6 && y==6) return false;
return true;
}
const int Heading2X[9] = {  0,+1,+1,+1, 0,-1,-1,-1, 0 };
const int Heading2Y[9] = { -1,-1, 0,+1,+1,+1, 0,-1, 0 };
int HeadingFull[8]; //use for fast track back found Path
int sourceIndex;
int goalIndex;
 
 
bool processPoint2(int index,int size,int gx,int gy,int &bestLen,int &bestIndex,int leftSet ){
 
 
bool foundBest=false;
int dy=index/size;
int dx=index%size;
 
int curLen=sMatrixLen[index];
int newLen=curLen+1;
 
//numDirection is 8, choose 4 if u want !
for (int k=0;k<8;k++){
int rx=dx+Heading2X[k];
int ry=dy+Heading2Y[k];
 
int len=(rx-gx)*(rx-gx)+(ry-gy)*(ry-gy);
int index2=ry*size+rx;
 
//found the path
//we can stop and get the best Path right here
if (curLen>=0 && index2==goalIndex){
sMatrixLen[index2]=newLen;
sMatrixFrom[index2]=k;
return true;
}
 
//if (mx>=0 && my>=0 && mx<Map.Info.MapWidth && my<Map.Info.MapHeight  && !iMapUnit[my][mx] )
if (canMoveHere(rx,ry )){
if (rx>=0 && ry>=0 && rx<size && ry<size && index2!=sourceIndex){
if ( newLen < sMatrixLen[index2] )
{
sMatrixLen[index2] = newLen;
sMatrixFrom[index2]=k;
}
 
if (sMatrixLen[index2]==0){
 
if (len<bestLen){
bestIndex=index2;
foundBest = true;
bestLen = len;
}
 
sMatrixLen[index2] = newLen;
sMatrixFrom[index2] = k;
 
//add new node to OpenSet
sOpenSet[leftSet][sOpenSetSize[leftSet]]=index2;
sOpenSetSize[leftSet]++;
 
}
 
}
}
}
return foundBest;
}
 
 
//search from (sx,sy) to (gx,gy)
int mySuperSimpleSearch2(int sx, int sy, int gx, int gy){
//your map size
int size=32;
 
sOpenSetSize[0] = 0;
sOpenSetSize[1] = 0;
 
//this init only run once! can move to other place
if (sMatrixLen==NULL){
sMatrixLen = new int[size*size];
sMatrixFrom = new int[size*size];
sOpenSet[0] = new int[size*size];
sOpenSet[1] = new int[size*size];
 
for (int i=0;i<8;i++){
HeadingFull[i]=Heading2Y[i]*size+Heading2X[i];
}
}
//use memset for best speed init!
memset(sMatrixLen, 0, ( size*size*sizeof(int) ));
memset(sMatrixFrom, 0, (size*size*sizeof(int) ));
 
goalIndex=gy*size+gx;
sourceIndex = sy*size+sx;
 
int bestIndex = sourceIndex;
int bestLen=10000; //keep the bestLen to goal, so we always head for node that is close to goal!
int curOpenSet = 0;
bool haveBest = true; //if we found the node that closest to goal, we process it first!
 
while(1){
int leftSet=1-curOpenSet;
 
if (sMatrixLen[goalIndex]>0 ){
//found goal get the Path;
int track=goalIndex;
int pathTotal=0;
 
int savePath[200];
for (int i=0;i<size*size;i++){
int dir=sMatrixFrom[track];
savePath[pathTotal]=dir;
pathTotal++;
track=track-HeadingFull[dir];
 
if (track==sourceIndex)
break;
}
return pathTotal;
}
if (haveBest){
haveBest = processPoint2(bestIndex,size,gx,gy,bestLen,bestIndex, curOpenSet );
}else
{
int nSize= sOpenSetSize[curOpenSet];
if (nSize ==0){
//no path left, unReachable;
return -1;
}
 
for (int i=0;i< nSize ;i++){
int index=sOpenSet[curOpenSet][i];
 
bool f1 = processPoint2(index,size,gx,gy,bestLen,bestIndex,leftSet );
if (f1) haveBest = true;
}
 
sOpenSetSize[curOpenSet]=0; 
curOpenSet=leftSet; //swap Openset
}
}
}
Edited by greenpig83

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this