1
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory ♦
    Oct 15, 2020 at 22:12
  • \$\begingroup\$ @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. \$\endgroup\$
    – AyCe
    Oct 15, 2020 at 22:17
  • \$\begingroup\$ 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. \$\endgroup\$
    – amitp
    Nov 15, 2020 at 0:20
  • \$\begingroup\$ 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 \$\endgroup\$
    – Filip Milovanović
    Nov 15, 2020 at 14:29
  • \$\begingroup\$ 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 \$\endgroup\$
    – Filip Milovanović
    Nov 15, 2020 at 14:29

1 Answer 1

Reset to default
1
\$\begingroup\$

The point of the A* is to exploit the structural constraints present in most real-world path-finding applications. The heuristic just needs to give a meaningful lower-bound to the total cost of reaching the end-node.

For example, for a graph modeling real-life roads, we know the shortest possible distance between two cities is the bird's-eye straight-line, and teleporters don't exist, so we can safely say that no path between those cities (no matter what roads are taken) will have a shorter distance than that. This extra information doesn't come from the graph, it comes from the thing we're using a graph to represent.

You haven't told us anything about the physical constraints of the problem you're using a graph to model, so we have no way of knowing whether your idea will work or not. If you somehow know that the path from start to finish will take at least n hops, and each hop has weight of at least 1, then n*1 = n is a reasonable heuristic. However, if you don't have a lower-bound on the number of hops, then "minimum weight per connection" isn't really helpful.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I assumed this was obvious from the premise, but you are right, it should be stated, so I did. I know how many connections need to be taken minimum, so the heuristic cost for a hop is indeed n * heuristic value (see above, will be at least 1). \$\endgroup\$
    – AyCe
    Oct 15, 2020 at 22:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .