Pathfinding structure...

BlitzMax Forums/BlitzMax Beginners Area/Pathfinding structure...

po(Posted 2007) [#1]
After reading up a bunch on A* pathfinding (read some tuts, this one was good: http://www.policyalmanac.org/games/aStarTutorial.htm )
I am now trying to implement it into my basic RTS game. I understand how it works, but I am a bit confused as to how I should structure it in my code.
In my game I have the map (TMap) set up as an array of tiles (TTile, which I will use for the pathfinding), and I have a type for holding the unit objects (TUnit). Each TTile has the boolean field 'occupied' which is True if an object is on that tile.
My first thought on implementing the pathfinding looked like this:

I know that I need an OpenList and a ClosedList, but should I be using lists rather than arrays? The link I posted above has a download for a Blitz Basic example. In the code he appears to be using arrays for the OpenList and ClosedList, but I assume that's because of BB not allowing access to lists?
I am also confused as to which fields I need for TPathfind. Would I need f,g, and h, when I could just calculate them? Do I even need startx,starty, and goalx,goaly?


Jesse(Posted 2007) [#2]
definitelly arrays are faster but banks are even faster.
from the link you posted above there is a link to this blitzbasic code:
http://www.blitzcoder.com/cgi-bin/showcase/showcase_showentry.pl?id=turtle177604062002002208&comments=no
that is a good example and they use banks to speed the search.
I converted a sample program from there to bmax.
hopefully you can understand it. take a look at this thread:
http://www.blitzmax.com/Community/posts.php?topic=62388#697498


Space_guy(Posted 2007) [#3]
Another tip:
Look up heaps on the net. BinaryHeaps are very fast for AStar as you need no extra sorting.


FlameDuck(Posted 2007) [#4]
In order to use aStar, or any other graph traversal algorithm for that matter, it's probably best to organize your data in a graph.


po(Posted 2007) [#5]
Alright, never heard of heaps or banks before, I'll take a look at them though. Thanks for the example Jesse.
Ugh, I have 18 days to figure this pathfinding thing out, as I'm doing my RTS for an info-tech project.

Thanks all.


smilertoo(Posted 2007) [#6]
the fastest A* ive seen on blitz used arrays, i did 1 using lists that was much easier to follow but a lot slower.


Dreamora(Posted 2007) [#7]
Both works.

For a 2D tilemap based application, using an array is the natural solution, would be totally pointless creating an overhead through a graph if the graph is restricted to the tile structure. Unless you use the tilemap only as a visual construct and the actual AI paths are not related to it.
In that case using graphs (nodes with connections to nodes, so nothing highly complicated) would logically be the way to solve the problem.

And yes, heaps are most likely the easiest and most efficient way (of the not complex structures like fibonacci heap and the like) to write a structure for the set of not traveled nodes with their distance as it is a 1 hit, log(n) refill structure for getMin / getMax.