# Astar heuristics closing in on an answer before searching around to find nodes with lower movement costs

I am having some trouble with my A* path finding. everything works fine and the path is always found. However, my game is a open map space strategy game. There are no walls etc to navigate around. Now, the movement cost along the navgrid is the same unless the agent chooses to navigate thro a 'jump gate' (in which case the cost is 100 times cheaper. almost always the better option).

I have a problem where the heuristics will narrow in directly towards the answer rather than searching around for a better solution. If my heuristics function always returns 0, then I always get the correct route, however with no heuristics I need to search the entire map and this makes it far too slow.

As you can see, the top agent ignores the jump gate and flies directly towards the destination, completely ignoring the gate way. The bottom agent opts to use the gate way (only because its heuristics was causing it to search in a north-west pattern anyway.

What are some possible solutions?

-
What heuristic are you using now? – Trevor Powell Dec 23 '12 at 8:06
pythagorean distance – Prodigga Dec 23 '12 at 11:01
How big is your map? Did you introduce the grid solely for path finding? What language do you use? How often will you need to calculate a route? – aaaaaaaaaaaa Dec 23 '12 at 15:03
At the moment, the map is a 50x50 grid. I've introduced the path finding for primarily path finding as I will be using it to find the "safest" route after I get it working. (Certain nodes will be more dangerous as agents are destroyed on or around them, so the path finding will be able to find a safer way around). I use C# and I will be calculating the path finding up to once every few frames (fast as the player could click) and once every so often (for NPC's to route their own paths.). I use C# – Prodigga Dec 23 '12 at 23:13

I assume you are using simple pythagorean distance as your heuristic. In that case, the answer is simple - this is not an admissible heuristic (meaning it overestimates distance), and A* is not guaranteed to give an optimal answer. It overestimates because your heuristic is more or less equal to "flying in a straight line", while jump gates are - as you say - a 100 times cheaper solution.

There is some academic theory behind A*, which includes formal definitions of "admissible heuristics" and proofs of when A* is guaranteed to return optimal solutions. If you're interested, the wikipedia page is a good place to start.

As for solutions, I wouldn't recommend changing the heuristic. It's fine. I would rather try a compound search - issue two search queries at the same time, one using "conventional flight" and one using warp gates (to the nearest warp gate, jump to warp gate heuristically closest to target, fly from warp gate to target). This assumes all warp gates are connected; I they are an interconnected network, you'll need to issue a small search in warp-gate space.

Anyways, of the two search queries you issued, whichever finishes first is optimal.

EDIT: After your comment about there being multiple warp gates from A to B, I think your search space is different than you think - you should be thinking in terms of a graph of nodes, not a flat area. Really, since there are no obstacles, there are only a few important points for pathfinding - start point, end point and warp gates. The ship can fly between these freely (normal flight or, between certain pairs of points, warp jump), so they are edges in your graph. They have well defined distances. You probably can't use A* in such an environment, but as long as the number of warp gates isn't too high, Dijkstra's should suffice.

-
I was thinking the same thing. However, the problem is that all warp gates are not connected. Its simply a way to quickly travel from point A to B. So say I try the nearest warp gate - when I get to point B, if I was to (at that point) take the shortest path to the exit, i'd have the same issue. The A* would ignore any other jump gates unless they happened to be in its path. – Prodigga Dec 23 '12 at 11:00
@Prodigga I think you could reduce the search space by looking only at the important points. Check the edit to my answer – Liosan Dec 23 '12 at 12:48
well eventually i would like the algorithm to take into consideration information one each node. for example, each node will have a 'danger' rating and I would like to use the pathing to find the quickest/least dangerous path as well. Without a grid to navigate on, the pathing can only fly straight through a dangerous area or try somewhere else completely. With my current method, the AI has a chance to fly around the dangerous areas. – Prodigga Dec 23 '12 at 23:26
I'm starting to think that maybe I use both dijkstras and Astar. Dijkstras for the 'quickest path', and Astar for the 'least dangerous'. But then ofcourse, the problem isn't really solved and my 'least dangerous' paths are going to be pretty crummy... see image:imgur.com/VMFz6 (red = dangerzone) – Prodigga Dec 23 '12 at 23:30

The special case with the warp gates makes it impossible to make A* work with a formal heuristic as Liosan explained perfectly. So you will need to try something else. First of all we note that since there are no obstacles this isn't really a hard pathfinding problem since we have an almost perfect heuristic for finding the path without using the warp gates. The problem is knowing if going via a warp gate is faster.

Say we want to go from A to B we want to know two things:

• The cost trough normal space: Euclidean distance (ED)
• The cost via one warp gate: ED to entrance + warp-gate cost + ED from exit to target

Since your guess on these distances is so good you can create an 'Heuristic' that is almost always right, it computes the cost to the target directly (in O(1)) and the lowest cost via one warp gate (in O(N) where N is the number of warp-paths). If you take the minimum of these two for the cost of the node A* will converge on either the direct path (if that is cheapest) or on a path via one warp-path (if that is cheaper).

Now this doesn't account for when a path via 2 or more warp-paths is cheaper than the direct approach. This unfortunately is a very hard problem since there are 2^N possible combinations of warp-paths to take. You can try an un-optimal approach by starting the algorithm from above all over again when exiting a warp-path, it will then either directly go to the target or take another warp-path which should most of the times be OK. But if there is a path of multiple warp-path that starts of in the wrong direction this will never work.

Note: this is just me thinking a bit about the problem, no guarantees, proofs or test-code here :)

-

A* is an optimization of Dijkstra's algorithm, it works only when you can guarantee a minimum travel time between any two nodes. With wormholes you can't make that guarantee, so you should switch to Dijkstra.

-
(Small note: since A* is just Dijkstra + a heuristic he already did this when he just 'returned 0' for the heuristic part) – Roy T. Dec 23 '12 at 14:43
@RoyT. Ah yeah, I better learn to read. For now a better answer will require more information. – aaaaaaaaaaaa Dec 23 '12 at 15:05