Improving Heuristics for A* Pathfinding | Hacker News Reader

Improving Heuristics for A* Pathfinding

redblobgames.com

352 pointsbobbiechen41 comments

> I learned about this technique in 2007, then tried writing it up in 2015. I realized that I didn’t understand it enough to be able to explain it. I studied it off and on in 2016, 2018, 2019, 2022, 2024, and 2026. I abandoned and restarted this page many times. And by 2026 I think I understand it well enough to write this page.

Outstanding.

I have an appreciation for people who keep going. Sometimes it doesn't really matter how long it takes you to learn something. I've found it's more valuable to see what you'd do with that knowledge.

Teach Yourself A* in Ten Years

I legit love this idea as a general book concept

*Insidestudying

Red Blob Games has quite a few S-tier posts, highly recommend exploring further if this is at all interesting to you

Incredible write-up, as usual. I still fondly remember discovering Red Blob Games' Hexagonal Grids [1] guide while building an implementation of the Tzaar board game [2]. The illustrations are enormously helpful!

[1] https://www.redblobgames.com/grids/hexagons

[2] https://boardgamegeek.com/boardgame/31999/tzaar

I remember reading it in 2006 or so to better understand pathfinding algorithms for my data structures and algorithms class.

In the event this helps a random developer with some fun experimentation: I had once accidentally independently reinvented drunken pathfinding by adding random additional weights to the node costs, which has the side effect of making an object seeking a path end wander "drunkenly."

There has been a lot of progress in this field in the research community. Two good papers:

* https://ojs.aaai.org/index.php/AAAI/article/view/11027 * https://arxiv.org/abs/2212.03978

Errrrr... how is the first paper related to A* and path finding?

It's about "planning" (ie. searching an action space) which does not generally have a heuristic, so it needs to do "exploration" (which is exactly the opposite of what you want for optimal path finding) to counteract getting stuck in local optima due to greedy search...

Damn, isn't A* fun and intuitive?

I'd be interesting to dive into bounds and good properties for sets of landmarks.

I imagine that if, - Every node is at least X cost/distance away from a landmark - Landmarks are no closer than Y cost/distance from each other

You can start promising a lot about the size of your open set on any execution.

A* on h* (perfect heuristic) takes O(l) where l is the length of the solution (could expand exactly l nodes, but solving/guessing ties incorrectly might bump this to a multiple around the avg edges per vertex). I imagine that having good bounds mean you'll take no longer than a certain amount of expansions/depth before you lock-into the railway that h* provides (and you need some extra work to get off it too).

Finally an interesting article about AI!

I see redblobgames, I click

Usually I would not point out a typo, but this one makes it difficult to grasp the magnitude of potential improvements:

> the number of nodes A* has to explore decreases from 12693 to 12693

It's a little unclear, but it's a live updating number, if you follow the directions, you'll see the second number decrease.

Good catch. I was thinking people would read that after they have moved the green L but I should handle both before and after moving L.

I'm also fairly certain I read a "helsp" instead of "helps" somewhere in the post

From the title I was expecting something about jump point search but this is even more interesting. Bravo!

I don't understand how the multiple landmarks works. If you just max all of the landmark distances wouldn't some landmark near the starting point eventually dominate as you move away from it? Once you get halfway through the path the useful landmarks would be returning lower and lower values while ones behind you return larger and larger values. Or just in general one far-away landmark would complete nullify any input from useful ones.

It seems to me that you would need a step to select useful landmarks but the code doesn't seem to do this and I don't see it discussed.

Ah, I figured it out. It is because he isn't using the distance to the landmark as the heuristic but the difference between the distance to the current location and the distance to the target. This means landmarks behind you will be negative (or useful in an undirected graph). This is also important for making the heuristic admissible as otherwise your heuristic would say zero when you are standing on top of the landmark.

i've always been impressed by NBA*: https://github.com/anvaka/ngraph.path

demo: https://anvaka.github.io/ngraph.path.demo/

Long time ago I remember reading about D* lite, I wonder how do they compare.

The author, Amit Patel, wrote the BBS door game Solar Realms Elite! His brother went on to write Baron Realms Elite.

He was also employee number 4 or 5 or something at Google, if I recall. Keeps a genuinely low profile, and seems like a super decent dude.

Blast from the past. I remember reading this site's A* intro when I was in college trying to use A* for our robotic's team autonomous sailboat.

Man I opened this website after so so long, so nostalgic.

It uses df as an example, but it (unlike the others) has the problem that the set of valid paths between any two points can be constantly changing.

One of the big questions for an algorithm is - when do you recalculate the path? A real "human" doesn't recalculate until they receive information that the chosen bath is blocked/changed (they see the road closed sign, etc).

But many games recalculate distance to target (one ping only) over and over again each step, so moving a single block half a map away causes an entire army to repath immediately.

Real humans also don't have perfect knowledge of the map and have additional concerns besides the path length so A* should only be part of the whole solution if you want realistic movement.

The landmark data can be calculated in a background thread. For DF I imagine you'd have a background thread running all the time, updating one landmark every so often. But what happens if you look for a path before the landmark data is updated? I haven't tested this yet but I believe this is how it'd work:

1. If the cost of a tile decreases, the precalculated heuristic will be too high, so A* might find a non-shortest but ok path. In game, you can think of the dorf as following the path they already know about, because they don't yet know that there's a shorter way.

2. If the cost of a tile increases, the precalculated heuristic will be too low, so A* will find the optimal path but it will take a little bit longer (still not as long as if we weren't using this heuristic). In game, you can think of the dorf as following the path they already know about, but running into a wall, so then they find a path around it.

One of the famous problems with df is that it's very much single threaded. At least the last time I checked, which is some years ago by now.

Besides that blocker, your idea sounds like a nice win.

Experimental multithreading was added in 2023 https://www.bay12forums.com/smf/index.php?topic=181776 I'm not sure if it's improved since then. Performance doesn't seem to be a priority for Tarn. It's kind of unfortunate, since I think DF would be an interesting problem space for optimizations, similar to Factorio, and it really needs it.

This Red Blob Games blog post would be accessible to a wider group of readers if it spent just a few sentences up front on motivation and terminology.

If you don't already know exactly what the heuristic function is and that L is something called a landmark marker, and anyway what is a landmark marker anyway, you need to read quite a long way through the blog post to make sense of it.

And when you do finally get to that point, you realise it is all very simple, so why not just say that at the start?

Before reading about optimizing the A* algorithm, read about the algorithm itself first.

You’re asking for a different post. More like a science paper where they say the result up front.

This blog post is like a story. It doesn’t start with the ending.

I read your comment first, expecting to go to the article and see a bunch of undefined math terms, but that isn’t what happened at all.

Of course you need to know what a heuristic function is, so maybe you’re right in that sense. You absolutely do not need to know anything about landmarks to enjoy the post. I didn’t, and it was no trouble at all to follow.

Perhaps you found the “discovery” method of presentation not to your liking. Discovery means there’s a demo where you move the L around before its purpose is defined. Building an intuitive understanding before producing a rigorous definition is (now) considered a good teaching method.

I love this blog. 10/10

One might even say it's an A+ resource

You mean an A* resource?

I would if there were a grading scale that uses star suffixes :D

One of my fav LLM tests is asking it to implement A* algorithm, in X language, in a single file, output 80x40 char map with random obstacles and show the path. Ask it to build UI or change path heuristiscs, etc.

It's such a quick prompt but can quickly signal how useful the model is in that language or framework, how much you have to constraint output with specs and tests.

Reply on news.ycombinator.com