Hi, I use a navmesh to do the pathfinding in my 3D game. For the 2D creatures this works wonderful. However the paths for the flying creatures are far from optimal. The reason for this is that the A* does not hold into account the height of the flying creature or the height of the destination, everything gets projected on the ground (navmesh). Is there a way to make the paths closer to optimal. For instance flying over a house instead of around it. I have tried forcing the pathfinder to take 2D-distance measurements (and ignoring height) instead of 3D-distance. This way it favors straight paths over houses etc. The downside is that it now always flies over objects instead of around. When we have a thin but high object like a tree or a tower going around is shorter, but that path is ignored. I know it shouble be possible by tweaking the cost and heuristic functions of the A* but I can't figure out how. Any help would be greatly appreciated, Greever

Assuming that your creatures are above everything 90% of the time, just make them do straight line movement with bump and steer. There's no need to do an A* if there are almost no obstacles. If there are a lot of tall buildings or mountains you could always just have buildings and things make different kinds of footprints on the map. Say a house marks the grid as: BLOCKS_FOOT_TRAFFIC, while a sky scraper would be: BLOCKS_FOOT_TRAFFIC & BLOCKS_AIR_TRAFFIC.

-me

In addition to Palidine's comment, you might be crazy enough to want odd shapes in the air. Perhaps you have arches or rings inside buildings that could be flown through.

You could consider multiple height levels. As long as they are sparse it shouldn't get too expensive. For example, height level 0 (ground) has all kinds of stuff on it. Height level 1 (2m) won't have problems traversing over water and rock, but will have problems with trees, players, and buildings. Height level 2 (4m) would only have problems with trees and buildings. Perhaps your pillared building would show up as a bunch of nodes on the level. Height level 3 (6m) would clear most buildings but not trees. Maybe it will have an impassable barrier at the top of your pillared building, in addition to the temple spire and some trees. And don't forget your flag pole, er, pillar of light, that shows up as a tiny impassable spot on each of the heights.

Navigating up/down a level would have an A* cost associated with it.

Greever, I've forwarded a paper to you through the hotmail address listed in your profile.

Hi!
What about calculating the cost of every node from the height of the object occupying the place and the current hight of your flying creature?
If you store the height of every object on the map somewhere, you could just use some function to calculate the cost of that tile from the difference of your cratures actual (or estimated height as you then need to preplan height for your creature too(always go as high as needed and never go down before the goal perhaps.. and for evaluating several paths to the same node, the cost schold be first criteria and then perhaps the path with the hichest height at that point.. or the one with the lowest height if you dont like your cratures ending up high in the air) height and that objects hight. If the height of the object is much higher than your creatures actual height, it does cost more to cross over that object as the crature has to rise, so add some amount calculated from the height difference to the nodes cost. If the height of the object is lower than your cratures actual height, do not modyfy that nodes cost. I guess you then can leave the heuristics as it is, as it still can be sure to underestimate any path's cost.
For the function required, you could start with a linear one, but a more complex approach with the help of pythagoras could be more appropriate..

These are just some thoughts that came to my mind, i didn't test or implement them.

Hope they can help someone.. Niko

interesting problem. I'll think about it tonight

Quote: Original post by Timkin
Greever, I've forwarded a paper to you through the hotmail address listed in your profile.

Is this something you can post, Timkin? I'd be interested in taking a gander.

-me

Quote: Original post by Palidine
Is this something you can post, Timkin? I'd be interested in taking a gander.

I'd rather not tread the murky waters of copyright infringement by posting a journal article on a public forum. I'll email it to you (although I have referenced it here on GD.net before and you may have already read it). The title is "A Rapid Method For Planning Paths In Three Dimensions For A Small Aerial Robot", in case anyone else feels a particular need to read it.

Cheers,

Timkin