I have a 2D grid which I am performing A* pathfinding on. Nodes are connected via a value of 3 in most cases (some connections are more expensive). In some (depends on the gameplay) circumstances the node may have a road to another node though, bringing the connection cost down to 1.
The heuristic cost is determined by multiplying the heuristic value (as stated below) with the minimum connections to take (this is known).
If I use a heuristic of 0 per connection then A* will always find the shortest path, due to just performing a Dijkstra search. Not ideal.
If I use a heuristic of 1 per connection then A* will still always find the shortest path, but will not be very efficient even when the path is straightforward. This is my fallback.
If I use a heuristic of >1 per connection then A* may not always find the shortest path, but will be more efficient. I am kind of scared of this “not always the shortest path”.
I’m considering using a heuristic of 1 (or just always lower the heuristic score by a set amount without letting it get below 1) for connections heuristically close to the target (and maybe close to the start too?) to have “perfect” pathfinding in the regions where it may matter most. Useful or wrong thinking?
What would be a good way to handle this setup? Any tips?
Edit: I just found http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html and wanted to mention it, quite helpful.