HN Debrief

Improving Heuristics for A* Pathfinding

  • Algorithms
  • AI
  • Games
  • Developer Tools

The post is a tutorial on improving A* pathfinding with differential heuristics. Instead of relying on a simple distance estimate like Manhattan distance, it precomputes distances from selected landmarks to every node, then uses the difference between landmark distances to the current node and the goal as a tighter lower bound. The point is to make A* expand far fewer nodes without giving up optimality on static graphs. Red Blob Games presents it as an interactive explanation rather than a paper-style result dump, and that teaching style landed well with most readers.

If you use A* in games, robotics, or routing, this is a practical reminder that better heuristics often beat algorithm swaps for real speedups. It is also a cue to separate static-map preprocessing from dynamic-map updates, because that design choice determines whether landmark-based heuristics stay correct and useful.

Discussion mood

Strongly positive. People admired the clarity and interactivity of the write-up, trusted Red Blob Games as a teaching resource, and enjoyed seeing a genuinely useful pathfinding idea instead of the usual hype around “AI.” The few criticisms were about onboarding for readers who do not already know A* terminology and about how well the method carries over to changing maps.

Key insights

  1. 01

    Why multiple landmarks do not cancel out

    The confusing part of the method is that the heuristic is not the raw distance to each landmark. It is the absolute difference between landmark-to-current and landmark-to-goal distances. That detail is what keeps the estimate admissible and prevents a landmark behind the search from misleading the algorithm. Once you see that, taking the maximum across many landmarks makes sense as a way to keep only the strongest lower bound at each step.

    When you implement landmark heuristics, validate the formula before tuning landmark placement. If your code uses plain landmark distance instead of distance differences, you are not getting the method described here and may break correctness.

      Attribution:
    • kevincox #1 #2
  2. 02

    Dynamic maps turn this into a systems problem

    The hardest part is not the heuristic math. It is deciding how and when to refresh precomputed landmark data as the world changes. A practical model emerged here: recompute in the background, do not repath every unit on every map edit, and treat stale data differently depending on whether traversal costs rose or fell. That reframes pathfinding performance as an update policy problem, not just a search algorithm problem.

    If your world changes often, design pathfinding around invalidation, refresh cadence, and repath triggers. Benchmark those policies separately from raw A* speed, because they will dominate player-visible behavior.

      Attribution:
    • amitp #1
    • bombcar #1
    • futune #1
  3. 03

    The frontier has moved past textbook A*

    Several comments pointed out that differential heuristics sit in a broader toolbox that now includes Jump Point Search for grid pruning, NBA* for bidirectional search, D* Lite for replanning, and newer planning work. That does not reduce the value of this article. It clarifies where this technique fits: a strong heuristic for standard A* rather than a replacement for specialized methods built for grids or changing environments.

    Choose your speedup based on map structure and update frequency, not on name recognition. Landmark heuristics are a good fit for repeated searches on mostly stable graphs, while replanning or pruning methods may fit better elsewhere.

      Attribution:
    • mpmisko #1
    • taneq #1
    • leeoniya #1
    • HappyPanacea #1
  4. 04

    The article teaches by discovery, not by reference

    One criticism was that the piece takes too long to define terms like heuristic and landmark. The better read is that it is intentionally structured like an explorable lesson, where the reader builds intuition before formal labels arrive. That works well for readers who already know basic A*, but it is not a zero-background introduction to pathfinding.

    Share this with engineers who already know A* and want a better heuristic. For newcomers, pair it with a basic A* primer first so they do not get lost in the presentation style.

      Attribution:
    • stevesimmons #1
    • fn-mote #1
    • nkrisc #1

Against the grain

  1. 01

    The intro assumes too much A* knowledge

    The main complaint was not about the technique itself. It was about pacing. The post asks readers to manipulate a landmark and follow the idea before clearly stating what the heuristic function is or why the landmark matters. For anyone coming in cold, that can make a simple concept feel harder than it is.

    If you are sending this to a mixed audience, add one sentence of your own upfront about what A* heuristics do and what the landmark precompute is for. That will widen the pool of people who can use the article.

      Attribution:
    • stevesimmons #1

In plain english

A* ↩
A search algorithm that finds the shortest path by combining the known cost so far with a heuristic estimate of the remaining distance.
admissible ↩
A property of a heuristic meaning it never overestimates the true remaining cost, which helps A* still find an optimal path.
D* Lite ↩
A pathfinding algorithm designed for replanning efficiently when the map changes over time.
grid pruning ↩
A set of techniques that remove unnecessary grid nodes from consideration during pathfinding to speed up search.
heuristic ↩
A fast estimate used by a search algorithm to guess how far a state is from the goal.
Jump Point Search ↩
A pathfinding optimization for uniform-cost grids that skips over many intermediate nodes to reduce A* expansions.
landmark ↩
In this context, a chosen reference node whose precomputed distances to other nodes are used to improve A*’s heuristic.
lower bound ↩
An estimate that is guaranteed to be less than or equal to the true value.
NBA* ↩
A bidirectional variant of A* that searches from both the start and the goal.
optimality ↩
The guarantee that an algorithm finds the best possible solution, such as the shortest path.

Reference links

Related Red Blob Games resources

  • Hexagonal Grids
    Cited as another standout Red Blob Games guide, praised for clear illustrations and practical usefulness.

Research papers

  • AAAI paper mentioned in comments
    Shared as an example of further research progress in search and planning, though another commenter questioned how directly it relates to A* pathfinding.
  • arXiv:2212.03978
    Shared as a newer research reference for readers looking beyond the tutorial toward current work.

Alternative pathfinding implementations and demos

Games mentioned as context

  • Tzaar
    Mentioned as the board game one commenter was implementing when they found Red Blob Games' hex grid guide.