# A Star (A*) Pathfinding in C

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

## Recommended Posts

hi. I've written an A star implementation in C, which will eventually go in my game using Allegro. I havent yet tested it, but I was wondering if anyone could tell me, using my implementation if there is a better way to store the path when finished? ie, I want my player to walk along the path returned by the finder. here is my version - please comment!
//a star path finding take 2

//create a list struct for the path
struct list_s
{
int x;
int y;
int f;
} path[10000];

struct NODE
{
int walkable;

int onopen;
int onclosed;

int g;
int h;
int f;

int parentx;
int parenty;
} node[MAPW][MAPH];

void initnodes()
{
int x,y;

for(x=0;x<MAPW;x++)
{
for(y=0;y<MAPH;y++)
{
node[x][y].walkable = getpixel(map,x,y);
node[x][y].onopen = FALSE;
node[x][y].onclosed = FALSE;
node[x][y].g = 0;
node[x][y].h = 0;
node[x][y].f = 0;
node[x][y].parentx = NULL;
node[x][y].parenty = NULL;
}
}
}

int *findpath(int startx, int starty, int endx, int endy)
{
int x=0,y=0; // for running through the nodes
int dx,dy; // for the 8 squares adjacent to each node
int currentx=startx, currenty=starty;

// add starting node to open list
node[startx][starty].onopen = TRUE;

while (!node[currentx][currenty].onclosed) //stop when the current node is on the closed list
{
//look for lowest F cost node on open list - this becomes the current node
for(x=0;x<MAPW;x++)
{
for(y=0;y<MAPY;y++)
{
node[x][y].f = node[x][y].g + node[x][y].h;
if(node[x][y].onopen)
if(node[x][y].f<lowestf) { currentx = x; currenty = y; lowestf = node[x][y].f;}
}
}
// we found it, so now put that node on the closed list
node[currentx][currenty].onopen = FALSE;
node[currentx][currenty].onclosed = TRUE;

// for each of the 8 adjacent node
for(dx=-1;dx<=1;dx++)
{
for(dy=-1;dy<=1;dy++)
{
// if its walkable and not on the closed list
if(node[currentx+dx][currenty+dy].walkable || !node[currentx+dx][currenty+dy].onclosed)
{
//if its not on open list
if(!node[currentx+dx][currenty+dy].onopen)
{
node[currentx+dx][currenty+dy].onopen = TRUE; node[currentx+dx][currenty+dy].onclosed = FALSE;
//make the current node its parent
node[currentx+dx][currenty+dy].parentx = currentx;
node[currentx+dx][currenty+dy].parenty = currenty;
//work out G
if(dx!=0 && dy!=0) node[currentx+dx][currenty+dy].g = 14; // diagonals cost 14
else node[currentx+dx][currenty+dy].g = 10; // straights cost 10
//work out H
//MANHATTAN METHOD
node[currentx+dx][currenty+dy].h = abs(endx-currentx+dy + endy-currenty+dy) * 10;
}
//otherwise it is on the open list
else
{
if(dx==0 || dy==0) // if its not a diagonal
if(node[currentx+dx][currenty+dy].g!=10) //and it was previously
{
node[currentx+dx][currenty+dy].g = 10; // straight score 10
//change its parent because its a shorter distance
node[currentx+dx][currenty+dy].parentx = currentx;
node[currentx+dx][currenty+dy].parenty = currenty;
//recalc H
node[currentx+dx][currenty+dy].h = abs(endx-currentx+dy + endy-currenty+dy) * 10;
//recalc F
node[currentx+dx][currenty+dy].f = node[currentx+dx][currenty+dy].g + node[currentx+dx][currenty+dy].h;
}

}//end else
}// end if walkable and not on closed list
}
}//end for each 8 adjacent node
}//end while

//put the parent nodes into a list ordered from highest to lowest f value
//first count how many there are
int count=0;
for(x=0;x<MAPW;x++)
{
for(y=0;y<MAPY;y++)
{
if(node[x][y].onclosed) { path[count].x = x; path[count].y = y; path[count].f = node[x][y].f; count++; }
}
}
//sort them
qsort (path, count, sizeof(struct list_s), compare);

return &path; //we're done, return a pointer to the final path;
}//end function

//sorting stuff
int compare (const struct list_s * a, const struct list_s * b)
{
return ( a->f - b->f );
}



##### Share on other sites
heh, I guess no-one in the beginners forum has tackled pathfinding yet. I suppose I should have posted in the AI forum.

But nevermind, I solved it! The above code had a few typos and errors, and also I was going about returning the path wrongly. I removed the sorting nonsense, and replaced it with a loop that starts at the end node and works its way back through all the parent nodes placing each of them in the path list.

If anyone wants to see my final result, let me know and I'll post it up.

Beginner

##### Share on other sites
Hi. I saw your code. I am also trying to implement in C. Can I have your new code with errors corrected. I have trouble traversing back to path and storing them in array. While traversing I am surprised to see that my parent information is lost. Can I have your complete code to have a check?
Thanks.

##### Share on other sites
Quote:
 Original post by Cosmic Rhi. I've written an A star implementation in C, which will eventually go in my game using Allegro.I havent yet tested it, but I was wondering if anyone could tell me, using my implementation if there is a better way to store the path when finished?ie, I want my player to walk along the path returned by the finder.here is my version - please comment!*** Source Snippet Removed ***

First of all, is there a particular reason you're doing this in C, rather than a higher-level language?

Anyway, I gave your code a brief look and I've got a few things I want to point out:
• You're creating a node for every terrain tile. This means (a lot of) memory overhead - it's unlikely that you'll need that many nodes. In the end, you already have the map. Nodes are only necessary to indicate what tiles you've checked or still need to check, and how costly they are, as well as what their parent is (hint: the final node already contains your path: just follow it's chain of parents).

• Your comments are misleading: you don't have an open and a closed list. You're storing that information in your nodes. This is inefficient, because you need to search the whole node-grid to see if there are open or closed nodes. Use actual lists for that instead.

• Your implementation is somewhat cumbersome: instead of keeping x and y coordinates, you can use pointers to nodes instead. The same can be done for storing parents.

• You're storing paths in a global array. This means that, every time you perform a search, any old path is overwritten. Such behavior, especially when undocumented, can lead to subtle bugs.

All in all, it doesn't look very efficient, both in terms of memory and performance. It's not a very elegant solution either. I would suggest using a higher-level language, using lists (containers) for the open and closed nodes rather than a grid of nodes, and returning paths as self-contained objects (you can write a class or struct for that).

##### Share on other sites
Hi I've since documented how I did it in my blog. I do realise its not the most elegant solution, but I wanted to keep it simple. For my purpose it wasnt important to be fast. If anyone wants to see my final code, it can be found on my blog. Its kind of a coincidence that I came back to this thread today, and had already documented on how I could improve the code.

Getting the final path is actually the easiest part. In the code above, I was going about it wrongly. That qsort is nonsense and not needed! All you need to do is make a while loop:
current node = end nodei = 0;while(current node is not the start node){ thepath = current node's parent; i++;}
anyway, like I said have a look at my page and you'll see how I did it. let me know if there's any more questions.

On another note, I found that implementing A Star in a way that was familiar made the whole process a lot easier to understand. If you've already got a really good grip on pointers and stacks etc, then you'll probably find it easier to do it another way. As for why I did it in C, well because I'm using Allegro, which is in C, and I grew up with C and well I just feel more comfortable with C.

##### Share on other sites
The reason I'm giving you these harsh comments is because I want to help people out by teaching them and helping them improve their skills (just as reading certain posts here helps me improve mine). I checked your blog and I understand why you're not in a hurry to optimize this - it's a turn-based game after all. I also understand you're familiar with C and you're only programming in your spare time (which could explain your lack of familiarity with pointers and memory management - an alarming situation for someone who has programmed for 10 years!).

However, with that background and mindset, I do not think calling your blog a tutorial blog is a correct thing to do. You're not presenting an efficient or elegant solution and you're not showing 'proper' (idiomatic) C code either. In other words, you're teaching bad habits.

The reason I suggested using (or in this case, learning) a higher-level language is because it makes you more productive. It takes away several low-level burdens and allows you to focus on what you actually want to do. I can write a more efficient A* implementation in Python much faster and with less hassle than I could write it in C (or C++). Maybe the best thing is that some of these languages are actually quite easy to learn - easier than C!

With C, you'll have to take care of the memory management yourself. This can be done dynamically: then you'll have to free what you allocate once you're done with it, and determine where and when the allocations and deallocations need to happen. It can also be done statically, as you did, which is less of a hassle but often causes either a lot of overhead or overflow - and it can introduce nasty side-effects like I mentioned (old results being overwritten).
For example, because maintaining dynamic lists is tricky, you chose to use the grid instead, making your implementation much less efficient.

With Python, you don't need to worry about all of that (but you still need to be sensible, of course). You create a list and return it. The next path-finding call, you create a new list and return that one. Each caller gets it's own path - which is cleaned up by the garbage collector when you're not using it anymore.
Because making lists is easy, you can make an open and closed list in mere seconds, and you know they're going to work properly.

##### Share on other sites
Thanks for the advice captain p. To be honest, like you said its just a hobby, and I'm really happy to just be using C, whether I'm doing it right or not. I have experimented with other languages, but I just keep coming back to C. Guess I'm just reluctant to change!