Jump to content
  • Advertisement
Sign in to follow this  
Greever

Pathfinding for flying creatures

This topic is 4555 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Greever, I've forwarded a paper to you through the hotmail address listed in your profile.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!