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

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.

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

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.

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.

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