Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

Some Hierarchical Pathfinding Problem I am not sure how to solve..

Recommended Posts

5a5ef97683ecf_hmapprob.thumb.png.0b9401820eafaea2180afdc853378682.png

Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?

thanks

Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement

I'm almost certainly not understanding this correctly (it's worded a little vaguely), but it sounds like B/C/D should each be separated into two nodes for the paths that result from the two separate portals. Not sure what you mean by "the computation is wasted" though, since A* or other pathfinding algorithms will probably process the "portal #2" path first as its nodes are closer to the destination, unless you come up with some sort of heuristic that's not based on euclidean or manhattan distance.

Edited by cmac

Share this post


Link to post
Share on other sites

Oh, maybe I've forgotten some properties of astar already (because it is a little bit differnet than normal a*), do you mean, if the astar finds that D is a dead end, the next iteration will choose portal #1 as an alternative path (where it starts searching again), oh my silliness...

thanks

Jack

Share this post


Link to post
Share on other sites

If there are 2 distinct ways of traversing from A to B and they have an effect on future route availability, such as the connection between D and E, then you can't simply path through these nodes naively like this. The state space you need to search in will need to include the previous nodes, not just the current node. In abstract planning terms this means searching from the state of the whole path rather than just the current node. The simplest hack to implement that change is to make your 'find neighbours' function inspect the whole past path rather than just the latest path node. But this also requires you storing the distinct ways that you traverse from node to node, so that becomes part of that state.

Share this post


Link to post
Share on other sites

That's what it means by storing "every" portal ever visited in the opened list, so that we can come back to it when we need it.

Share this post


Link to post
Share on other sites

Now the question turns out to be how to accurately plot out the portals. Whenever I define a cluster as one "tile" one cluster as described as Mikko, or one "extent" per cluster, either way, I have to define the portals, Some guys suggested that you can make use of the contours generated from recast, or the tiles themselves. While I am interested in generating portals in just an AABB kind of thing.
I thought you have to, at the clusters' border, somehow scan along it, and check both side of the clusters, and seeing that if there are any obstacles there, and finding the longest line along the border, and push that into an array... don't know if that works..
thanks
Jack

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
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!