A* Pathfinding in 3D Environment

You can get a more accurate estimate of the cost by using the cost to travel from one edge to another, instead of using the center of the polygon (which is nearly meaningless in this case). As long as the costs are close to those of the final path, A* will find a decent path. If the costs seen by A* are within a factor of 1 to 2 of the costs of the real path, A* will never suggest a path that is more than twice as long as the real optimal path.

Already using that method, and it can return rediculously off results in some cases :
Thinking about finding the closest point on the edge to the start point, then the closest point on the next edge from that point, ect, ect. That would return equally bad results for all paths.

Take a look at the 'Framed Quad Tree' approach... it should give you the inspiration you need. ;)

Cheers,

Timkin

Mmmm, I dont think that'll work for me, Im using N-sided polygons, thanks for replying tho.

[Edited by - Zukarakox on February 17, 2008 3:08:22 PM]

I wasn't implying that you directly apply the framed-quadtree... but that you use it for inspiration. N-sided polygons can still have their edges discretised and a cost matrix can be devised for crossing the polygon. It's the use of this information during your search algorithm that is most relevant and that's what you'll get out of looking at the framed-quadtree approach.

Oh sorry, I guess I didn't look deep enough to find anything about cost matricies, I was having trouble finding a good article on it, and ended up just reading over a few that had applied it and vaguely described how it worked.

I'll take another look tommorow.

Holler if you have any difficulties findin good information on the technique. Some articles are not accessible to the general public.

Cheers,

Timkin

Cant find crap. :( Google searchs either end up with abstracts from books that look promising, but I can't actually access, or references to your post. Wiki/GameDev Article searches end up with great tutorials on quadtrees, but nothing about cost matricies. :P

I did find a neat article on how they made the pathfinding for the Mars drone. :)

I've emailed some papers to the address listed in your profile.

Regards,

Timkin

Hiya Zukarabox, judging from your A* algorithm, it is evident that you are trying to modify it to suit your own needs. In order for me to answer the question in more detail, I need to be exactly clear on what you are trying to achieve. When I studied A* algorithms in Maths at University, I found the centre point for each node, then moved between each node until I found the final destination node. However, am I right that you want to enhance this by working out the best angle to travel between these nodes, which are also determined by the pathway the character is travelling from? From what I have read, you have created an Algorithm to work out the best angles, but unfortunately for the whole Path rather than for the next node the character needs to do. If I am right, then you are trying to be more efficient with your code, so the angle does not have to be worked out between each path, when the next frame occurs, and the path is reworked.

To summarise what I have just said, could you please tell me in a bit more detail what exactly you are looking to achieve, Thank you.

Dalyk

Sorry, in retrospect my first post was alittle vague. I do not know any proper terminology, I'm 100% self-taught, so try to bear with me. :P

Structure of NavMesh:
Polygons (A flat, convex figure, containing Edges)
Edges (Connections of Polygons)

So for a very basic pathfinding, I just used A*, using Edges' center's as mediums for nodes (using a Manhattan heuristic).
After the edge-to-edge path was calculated, I applied an algorithm to find the proper points to cross the edges at, keeping in mind where the unit was coming from and where it was going to. (IE: If his destination is far right of an edge, he would hug the right point, given that the destination was not around a strange curve or some such.)

The problem with this is, in short, that the first edge-to-edge A* technique would sometimes return wrong edges for the optimal path because the center of an edge is almost never used, and can cause the acutal distance travled to vary greatly.

So, I'm looking for a suitible technique to avoid this issue, while still maintaining a good deal of flexibility and a half-decent speed (I tried spamming every POSSIBLE path from poly A to poly B and after I ended up with more than 50 or so polygons, the program would freeze up for a few seconds when calculating the path.)


Edit: Still reading through the Framed Quadtree papers, I havn't had much time to work on AI lately :P