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?