Jump to content

  • Log In with Google      Sign In   
  • Create Account


A* on large Map


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 gnomgrol   Members   -  Reputation: 549

Like
1Likes
Like

Posted 26 December 2013 - 01:50 PM

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



Sponsor:

#2 DrEvil   Members   -  Reputation: 1079

Like
0Likes
Like

Posted 26 December 2013 - 02:09 PM

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?

#3 markr   Crossbones+   -  Reputation: 1653

Like
0Likes
Like

Posted 26 December 2013 - 02:10 PM

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))



#4 Postie   Members   -  Reputation: 856

Like
0Likes
Like

Posted 26 December 2013 - 04:02 PM

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. 


Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#5 ericrrichards22   Members   -  Reputation: 709

Like
0Likes
Like

Posted 26 December 2013 - 07:24 PM

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/


Eric Richards

SlimDX tutorials - http://www.richardssoftware.net/

Twitter - @EricRichards22


#6 SaurabhTorne   Members   -  Reputation: 238

Like
0Likes
Like

Posted 27 December 2013 - 03:05 AM

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



#7 gnomgrol   Members   -  Reputation: 549

Like
0Likes
Like

Posted 28 December 2013 - 03:10 PM

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, 28 December 2013 - 03:18 PM.


#8 greenpig83   Members   -  Reputation: 321

Like
1Likes
Like

Posted 28 December 2013 - 11:01 PM

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, 28 December 2013 - 11:02 PM.


#9 gnomgrol   Members   -  Reputation: 549

Like
0Likes
Like

Posted 29 December 2013 - 08:57 AM

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!



#10 greenpig83   Members   -  Reputation: 321

Like
1Likes
Like

Posted 29 December 2013 - 09:47 AM

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, 29 December 2013 - 09:52 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS