Vorpy is right - your method of determining connectivity between nodes really needs to be improved. There is no need to store the rect each node will occupy when rendering – this is primarily a cosmetic thing and is not very relevant to your pathfinding code. In your case, if you store your nodes in an array representing a uniform grid, just as you might store a traditional ‘tilemap’ in 2D games, it is possible to immediately determine the neighbours just by looking at adjacent cells. Vorpy suggested a 2D array and this would be a good choice – your open list would then consist of x,y references to the cells you’ve processed. However, you may also like to consider mimicking two dimensions with a 1D array by declaring it as, for example,
Node * nodes[ width * height ]
and then accessing node x,y as
nodes[ x * width + y ]
This would allow you to simply store integer values on your open list, at the cost of added complexity when accessing nodes.

You definitely should consider removing the rendering code from your path finding function as it appears to be causing dreadful performance.

Thanks for all the feedback guys :)
Using a 2D array sounds like a really good idea, I really don't need to bother with all the rect information because I use it only for rendering purposes. I don't know why, but when I started out coding it seemed like a reasonable idea, doh! I am going to re-write the program when I get home tonight.

Quote: Original post by mpathare
PS: could you point me to the name of the article Peter was talking about that talks about initially moving units with a "guess"

Sorry for getting back to you so late. The article is actually from a book, AI Programming Wisdom. I am unsure if the article is available online. The article was called "Pathfinding Design Architecture" by Dan Higgins.

If you are interested in AI design at all I would suggest picking up the book (or the entire series!). They really are very interesting to read.

Sorry I couldn't help you earlier but I'm glad these other people were.

Also consider that A* may not be the optimal pathfinding algorithm for your maps.

A method is to split your map into a handful of regions (maybe 10 or so) and for each pair of regions to compute once and store the next region to be traversed to go from the former to the latter. This way, you can send your units on their way as soon as they receive an order, using a quick A* search in a region hopefully without obstacles, and then refine the path using naive active contour techniques as the unit moves. If your choice of regions is reasonable, then this will be faster than A* and also easier to use on a large scale.

If you have 192 regions... It only takes n^2 chunks of data, or 36864 chunks, to store a complete pathing map of your area.

Until your map has 1000+ nodes, storing complete pathing maps isn't that expensive.