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

## Recommended Posts

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 on other sites

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 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 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 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 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

## Create an account

Register a new account

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633388
• Total Posts
3011614
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

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!