Hi I finally understand the A* algorithm and have written a console program to do the search and display the results... I wrote this because I am making an rpg tile game and needed some pathfinding. Anyway, I was wondering what is the best way to implement this pathfinding into my game. Should I store the path in a list/stack and take them off as the previous one is reached? or is there a better way? I''m not looking for code, just a tip as to where to start. Thanks - Free Your Mind -

Your idea for how to store the path sounds fine to me. In terms of the details: Storing it as a linked list style stack probably isn''t worth it because of the extra overhead of pointers. I would just allocate a block of memory, access it as an array, and store the current index. But you may have reason to do otherwise.

Also, If you have any questions on A* itself or how to speed up your implementation, then we''ll be more than glad to help out with that too.

Thanks, does using pointers (linked list) really have more overhead? I should probably know this, and I know this isn''t really topic for this forum, but since you mentioned it, could you explain this to me. Also, if I were to go with an array for the final path, the array would only have to be the size of the max number of moves on the screen (i''m limiting the search space to only a little larger than the number of tiles on the screen) which in a worst case scenario would be a maze from bottom left to top right I guess. Does that last statement I made sound valid? Any other tips in this area would be great. Thanks again.



- Free Your Mind -

General practice with linked lists lends them to an on-the-fly implementation, allocating/deallocating as you need them, compared to the general use of an array being overwriting with just one allocation at the beginning.

So while it is possible (maintaing a used and unused stack swapping entries back and forth), chances are with an LL you''ll be using a lot more allocation calls which will give it more overhead, and possibly slow it down a tetch.

that makes sense, thank you.


- Free Your Mind -

My main point regarding linked lists was that you increase the memory overhead. Let''s assume each list item consists of two long integers (an x and a y value). When you add a next pointer, you increase the size of each struct - and thus that of the entire list - by a third. An array requires no such explicit ordering since it is contiguous in memory.

I just got the A* implemented in my rpg... i worked all weekend on it. The only problem is that the character''s movement is kind of jerky. I was wondering if anyone knew of something I could do to smooth it out and make it look more natural. Thanks



- Free Your Mind -

Just a quick point, even though you limit the area the user can choose to move it, it''s possible that the character will have to move quite far off the current screen and come back. For example, say you''ve got a river and the only bridge is several screen away, you might be able to see across the river, and be able to click on the far bank, but you''ll have to find some way to make sure that your character doesn''t try and find a path there, otherwise you''ll end up with a huge search space. I''d say just limit the number of tiles you search through before giving up.

Hmm, that paragraph above is a bit un-thought-out... I guess my point is that just limiting the area the user can click in won''t limit the area your path-finding code will search in...

codeka.com - Just click it.

If you''re A* algorithm is returning a set of waypoints for the NPC to move between, then you can smooth the path out in several ways...

The first is to take any sequential triplet of waypoints and check to see if the middle one can be removed. This would involve checking for collisions along the path between the end waypoints in the triplet. You can do this iteratively for all possible triplets to find the simplest path through a subset of the waypoints.

The second is to use Bezier curves. These use the waypoints as weights to ''bend'' a smooth curve so that it passes close to each waypoint. The problem with this is that the curve may pass through an obstacle that the original sharp curve actually avoided.

Finally, you can actually add more waypoints to the path to smooth it out. This involves fitting a smooth spline (curve) through subsets of the waypoints (usually triplets, so you get a cubic spline) and then adding waypoints along this curve.

Good luck,

Timkin

Actually, the spline solution can be implemented without all the pesky chances of you running into something, as long as you don''t use the Bezier variety. I would instead suggest either using Catmull-Rom or Hermite splines, both of which pass directly through the defined anchor points.

The drawback for each of these however, is that the Catmull-Rom spline has the same tangent at each anchor (not a huge problem, but it can look a bit odd), and for Hermite splines, it is necessary to define the tangent for each anchor. Hermite splines, however, have the additional advantage of not requiring buffer anchors at either end of the path (cubic splines require four points, and thus you must have a waypoint before the start and after the end). All in all, this will probably be your best bet for smoothing out the path.