# A* heuristic for a map that can have roads

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.

• Using a heuristic less than 1 per step is an unnecessary pessimization in this case. You know the cheapest cost is 1, so using 0 is just lying to yourself. You get no benefit from it. If using a heuristic of 1 across the board is not efficient enough for your needs, you might want to consider a hierarchical approach, where you precompute distances for coarse regions, and just look up this region-to-region distance when you're not yet in the same region as your destination. This improves efficiency without sacrificing correctness. – DMGregory Oct 15 '20 at 22:12
• @DMGregory Exactly, I just wanted to demonstrate that I understand that a heuristic of 0 is suboptimal in this case since the lowest cost is 1. I mentioned 0 in the paragraph below, but that's fixed already. I will check if a region-system can be added easily. – AyCe Oct 15 '20 at 22:17
• Is the map static and known ahead of time? If not, I think 1 is the best choice if you want an optimal path. But if it's known ahead of time, there are several precomputation approaches possible. The simplest I know of is a differential heuristic, which doesn't involve creating a hierarchy, but merely running A*/Dijkstra's from several points ahead of time. I have some notes but don't have a full explanation. – amitp Nov 15 '20 at 0:20
• Without running the code on a representative grid and measuring, you don't actually know if using a multiplier of 1 for your heuristic is going to be a problem performance-wise. For all you know, in practice, it may be of no concern at all. If that's the case, then you'd be making your pathfinding code needlessly complicated and harder to understand and maintain. So that's what I'd recommend - test it out first to see if there even is a problem to solve. 1/2 – Filip Milovanović Nov 15 '20 at 14:29
• This will also give you a chance to test out, and get a feel for, other values. E.g, if most of your connections have the cost of 3 with a road here and there, then you may experimentally determine that a multiplier having some value between 2 and 3 works fine 90% of the time (I'm making these numbers up, but you get the gist of it). This knowledge can then help inform your design decisions. 2/2 – Filip Milovanović Nov 15 '20 at 14:29