# A* on large Map

This topic is 1781 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

-gnomgrol

##### Share on other sites
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 on other sites

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 on other sites

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 on other sites

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 on other sites

for testing you can draw the path on screen as it is generated.

##### Share on other sites

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 on other sites

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 on other sites

Your idea sounds very nice! If you could put your code on here, me and a lot of other people sure would appreciate it very much!

Thank you, kind sir!

##### Share on other sites
OK here the code.
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
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 len=(rx-gx)*(rx-gx)+(ry-gy)*(ry-gy);
int index2=ry*size+rx;

//found the path
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;

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){
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++){
}
}
//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++;

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];

bool f1 = processPoint2(index,size,gx,gy,bestLen,bestIndex,leftSet );
if (f1) haveBest = true;
}

sOpenSetSize[curOpenSet]=0;
curOpenSet=leftSet; //swap Openset
}
}
}
Edited by greenpig83

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633300
• Total Posts
3011266
• ### Who's Online (See full list)

There are no registered users currently online

×