Jump to content
  • Advertisement
Sign in to follow this  

A Star (A*) Pathfinding in C

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

If you intended to correct an error in the post then please contact us.

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;
	int lowestf=10000; // start with the lowest being the highest

	// 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) 
					{
						//add it to open list 
						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 this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Cosmic R
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!

*** 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 this post


Link to post
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 node
i = 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 this post


Link to post
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 this post


Link to post
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!