I’m using a Point Graph in a project that has World Portals (like Prey, etc…), not to be confused with the Funnel Modifier portal stuff
Each portal gets a point node associated, so when the portal has a target, it calls this.pointNode.AddConnection( targetPortal.pointNode, cost ), creating a connection to traverse the world portal.
Currently I just set the cost to a value based on the original connectionCosts of the node (the Min of them)- that is stored when first baking the graph. So that it behaves as if the connection was to a nearby node- all the nodes have roughly the same spacing. This is because I wouldn’t want the real cost of the distance, ex: if the portal was linking a destination 50 meters away, walking through the portal gets you there immediately, so the true cost isn’t suitable.
This all seems to be working- things pathfind through the portals; but then digging through the code I noticed in Path.cs there is CalculateHScore which looks to be using the int3 positions of nodes. So for a world portal connection, it might be seeing that they are 50 meters away in world space.
I’m wondering, could that potentially conflict with the low connection cost I’m putting in for the World Portals? Or is it more to do with how the system chooses what nodes to search initially? I currently use the Manhattan heuristic.
I haven’t spotted anything strange with the calculated paths, just more wondering if it could cause trouble in how the best paths are chosen. The A* asset has been working wonderfully for my project so far!
The A* algorithm uses a heuristic to speed up the search. The heuristic is simply the estimated distance to the target point from a node it is currently searching. The key thing about that heuristic is that it needs to be a lower bound on the distance, i.e if it estimates the distance to be 10 meters, then any path to the target must be at least 10 meters, otherwise it may not find the optimal path. Portals break that assumption since you can potentially move from any part of the graph to any other part with no cost at all. This means that the estimated distance that the heuristic uses must be set to zero at all times since there is no guarantee that there is not a portal from the current node straight to the target. The way to do this is by setting the Heuristic setting (A* Inspector -> Settings) to None (alternatively reduce the heuristic scale to zero, but that is slightly slower). This will slow down pathfinding quite a bit, but unfortunately there is not much one can do about it if you want to ensure that the paths are optimal. If you never update your graph during runtime then you can actually use some heuristic (just not None), set the heuristic scale to zero and then enable the ‘Heuristic Optimization’ setting. It will then be able to precalculate some distances in the graph which can improve performance a lot, especially compared to not using any heuristic at all. You would need to set the heuristic scale to zero because otherwise it will try to also use the normal heuristic, but we know that it is incorrect, so we cannot use it.
