Problem: Our shortest paths table includes the minimum possible distance over any edge in the graph, including edges we don't have access to.
For example, AV2 uses a Map area with spots for each room with a fast-travel destination, and a singular exit to that room. If the fastest route from a starting spot S to a goal spot G goes through a fast-travel destination D that we don't have direct access, the A search will prioritize going to the Map spot that links to D, but be unable to use the edge. As a result, A will attempt to route around the "obstacle", which would include generating one state for each Map spot to put into the queue. One of those that we can fast-travel to will be the closest without the fast-travel. (In a few cases, the fastest route will involve fast-travel to move somewhere to invoke a different warp.) But from that fast-travel point that we can use, the fastest possible route may be to fast-travel to D--this might be true for all fast-travel spots, in which case they all have the same priority in the queue.
When we make a change to state (such as entering a new area and updating a context variable), then the fast-travel warp creates a distinct state from the other ones we'd already seen. If we have multiple cheap steps we can make, with the shortest paths pointing to use fast-travel like this, we may end up with many times the number of Map spots in the queue, none of which can actually make it faster than picking a different fast-travel point and moving from there. With a limited queue size (and/or limited number of states to process), this can prevent a route from being found.
Despite those differences in uniqueness, the failure to take certain edges is observable. If we observe why we can't take this edge in our first pass, i.e. we haven't visited the fast-travel point before, can we keep that observation to say, "we can't use fast-travel here unless we pass one of these observations now"? Then, when we make a subtle context change before starting fast-travel, we can say, that change doesn't affect anything, and discard the option to perform fast-travel, since it's unlikely to produce a better option.
It may perhaps be even better to have observations on entire routes between S and G, and cache or precalculate them. Our shortest path only includes edges (and thus not actions), but an A search is guaranteed to find the shortest route with actions if one exists (notwithstanding any shortest routes that take more actions than our max actions)--observing this route means that any other A search between S and G that matches this observation can take at least this route. If we include observations about shorter routes, such as the fast-travel way, then we can check observations in order. If we include negative observations, we may be able to prove that any state matching the observation has the given route as its shortest, but the hit rate may decrease, which over time would result in more entries in the cache.
Problem: Our shortest paths table includes the minimum possible distance over any edge in the graph, including edges we don't have access to.
For example, AV2 uses a Map area with spots for each room with a fast-travel destination, and a singular exit to that room. If the fastest route from a starting spot S to a goal spot G goes through a fast-travel destination D that we don't have direct access, the A search will prioritize going to the Map spot that links to D, but be unable to use the edge. As a result, A will attempt to route around the "obstacle", which would include generating one state for each Map spot to put into the queue. One of those that we can fast-travel to will be the closest without the fast-travel. (In a few cases, the fastest route will involve fast-travel to move somewhere to invoke a different warp.) But from that fast-travel point that we can use, the fastest possible route may be to fast-travel to D--this might be true for all fast-travel spots, in which case they all have the same priority in the queue.
When we make a change to state (such as entering a new area and updating a context variable), then the fast-travel warp creates a distinct state from the other ones we'd already seen. If we have multiple cheap steps we can make, with the shortest paths pointing to use fast-travel like this, we may end up with many times the number of Map spots in the queue, none of which can actually make it faster than picking a different fast-travel point and moving from there. With a limited queue size (and/or limited number of states to process), this can prevent a route from being found.
Despite those differences in uniqueness, the failure to take certain edges is observable. If we observe why we can't take this edge in our first pass, i.e. we haven't visited the fast-travel point before, can we keep that observation to say, "we can't use fast-travel here unless we pass one of these observations now"? Then, when we make a subtle context change before starting fast-travel, we can say, that change doesn't affect anything, and discard the option to perform fast-travel, since it's unlikely to produce a better option.
It may perhaps be even better to have observations on entire routes between S and G, and cache or precalculate them. Our shortest path only includes edges (and thus not actions), but an A search is guaranteed to find the shortest route with actions if one exists (notwithstanding any shortest routes that take more actions than our max actions)--observing this route means that any other A search between S and G that matches this observation can take at least this route. If we include observations about shorter routes, such as the fast-travel way, then we can check observations in order. If we include negative observations, we may be able to prove that any state matching the observation has the given route as its shortest, but the hit rate may decrease, which over time would result in more entries in the cache.