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

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.

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.