The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue:
Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue)
Dijkstra: Priority is distance so far + next edge distance
A*: Priority is distance so far + next edge distance + estimate of distance to target node.
This also helps me remember whether the estimate must over- or under-estimate: Since Dijkstra is making the estimate "0", clearly the "admissible heuristic" criteria must be an under-estimation.
Another way I like to think about it is that every graph traversal can be represented as a white set of unknown nodes, a grey set of known but unvisited nodes, and a black set of visited nodes. The data structure used to represent the grey set defines the algorithm:
DFS = queue
BFS = stack
Dijstra's = priority queue keyed by edge weight
A* = priority queue with heuristic function
Beam search = bounded priority queue with heuristic function
Topological sort = priority queue keyed by number of unvisited inbound edges
Copying garbage collector = pointer address
Mark & sweep garbage collector = dirty bit on the object pointed to
Generational garbage collector = multi-level grey set represented by the write barriers between each generation.
A* = priority queue with heuristic function _with specific properties_ ... in particular it must be an "admissible" hueristic that never overestimates the true value.
More specifically Dijkstra's is a priority queue. A* is a priority queue with an added estimate to the cost function to prioritize searching nodes closer to the destination.
> This also helps me remember whether the estimate must over- or under-estimate: Since Dijkstra is making the estimate "0", clearly the "admissible heuristic" criteria must be an under-estimation.
You're thinking too hard. :-) Just think of a map the same way a 10-year-old would.
Straight-line (Euclidean) distance is the most obvious heuristic on a map for estimating distance, and it's admissible.
Straight lines minimize distances i.e. they never overestimate. Which is enough to remind you that you want an underestimate.
> the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue
A much less obvious but much more fascinating (IMO) way to look at A* is that A* is actually Dijkstra but with a modified graph, where you adjust the heuristic delta between each edge's vertices to the edge's weight.
To remember the sign of the adjustment with this method, just imagine the next vertex getting super close to the destination, and then work out whether the weight needs to increase or decrease significantly in that case. (It needs to decrease, given you're getting closer to the destination.)
Yes, but it doesn't come right away. When preferring deeper nodes for a moment you have a loop-safe Depth-first traversal, and then when simplifying things in case the Graph is a Tree you get your regular stack-based Depth-first traversal, in which if you settle for the first goal you get back a tail-call optimised DFS.
Red Blob Games is a great blog if you are interested in game development. The explanations are solid, they have at least pseudo code or an implementation for most of their posts, and they have great animations on a lot of their bigger posts to help build intuition.
I remember one of the Advent of Code challenges had a hex grid puzzle on it, and Red Blob Games hex grid guide was so good the site got hugged to death because of it for a while. Used that later when I built a civ clone too, it's a fantastic resource.
I still remember a decade on the little pop of joy of realizing that not only do all the graphics on that blog post change when moving from flat to pointy, the code animates too.
The interactive graphics evoke all the fun of being a child in a science museum.
I have a deep love of A* because it was the first complex algorithm I fully understood. In my first data structures and algorithms in college (early 2000's), we had to pick an algorithm to study, code, and write a paper on and I picked A*.
I spent hours painstakingly drawing similar grids that the author of this article made and manually doing the calculations [0]. I still have these notes somewhere, even though they're over 20 years old at this point, because I was so proud of the work I put into it.
At any rate, thanks for this article and the trip down memory lane.
Interesting that this used to be called "AI". I'm still trying to figure out what to call the umbrella field of Artificial Intelligence now that "AI" has come to mean the genAI subset of DL which is a subset of ML which is a subset of what used to be called "AI".
What has been called AI in gaming in the past is rich and varied, and goes all the way down to a computer control opponent “seeing” a player and opening fire, moving towards, or moving away. Any code controlling NPC was referred to as “the AI of the game” even if all the code was doing was applying a few simple rote rules rather than following an exactly pre-specified sequence.
“AI” in gaming means (or has previously meant) a lot less than “AI” has meant in other fields, but with the increasing use of “AI” in all contexts this will soon no longer be the case.
Not just computer game AI. Literally university courses called "Artificial Intelligence" would teach A*, formal logic, planning, knowledge representation, etc. See for example the famous Russell-Norvig textbook. Since deep learning became dominant around 2012-2014, that conception of AI is now (somewhat deprecatingly) called GOFAI, or "good old-fashioned AI".
There is also certainly more sophisticated AI in gaming. Remember the AI used by Deep Blue in chess? Or the AI used by DeepMind in Go against Lee Sedol? Classic games like chess or Go receive more attention from the AI community than contemporary video games.
The definition of "AI" has for a long time now been basically "We know it works somehow, but only few people really understand it", which is a moving target. At one point in the future, the LLMs we use today won't even be called AI anymore.
"Artificial intelligence" has always been a marketing term, not a technical one. John McCarthy coined the phrase when he was applying for a DARPA grant, and he picked it because he thought it would sound cool to the grant reviewers.
The way I explain it to my students is through a venn diagram of "Traditional AI", "Machine Learning", and "Data Science" (though I suppose Gen AI is starting to form another circle). A* falls into the "Traditional AI" space, which is a mixed of state searching, logic representation, and statistics/probability (now called data science). What general public considers "AI" is where all the circles meet, and it means everything from Robots to if-else statements.
I took a course in grad school on "Game AI" that put different path finding approaches and methods of making decisions into a useful bucket away from ML and AI.
Someone send this to the idiots at Garmin, because their navigators will tell you to drive in a straight line across mountains or water water to an unreachable destination. It's like AI that never says "I don't know".
As a game developer for a grid based puzzle game (https://thinky.gg - one of the games Pathology is a game where you have to go from Point A to Point B in shortest amount of steps).
I have found A* fascinating not because of the optimization but also from the various heuristics that can be built on top of it make it more generalized for other types of pathfinding.
Some devs have built solvers that use techniques like bidirectional search, precomputed pattern databases, and dead locking detection.
Readit News
Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue)
Dijkstra: Priority is distance so far + next edge distance
A*: Priority is distance so far + next edge distance + estimate of distance to target node.
This also helps me remember whether the estimate must over- or under-estimate: Since Dijkstra is making the estimate "0", clearly the "admissible heuristic" criteria must be an under-estimation.
DFS = queue
BFS = stack
Dijstra's = priority queue keyed by edge weight
A* = priority queue with heuristic function
Beam search = bounded priority queue with heuristic function
Topological sort = priority queue keyed by number of unvisited inbound edges
Copying garbage collector = pointer address
Mark & sweep garbage collector = dirty bit on the object pointed to
Generational garbage collector = multi-level grey set represented by the write barriers between each generation.
· BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges
· Dijkstra's is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = sum over edges
· A* is priority queue with key h(n) + g(n), where h(n) = heuristic(n), g(n) = sum over edges
It's cute.
You're thinking too hard. :-) Just think of a map the same way a 10-year-old would.
Straight-line (Euclidean) distance is the most obvious heuristic on a map for estimating distance, and it's admissible.
Straight lines minimize distances i.e. they never overestimate. Which is enough to remind you that you want an underestimate.
> the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue
A much less obvious but much more fascinating (IMO) way to look at A* is that A* is actually Dijkstra but with a modified graph, where you adjust the heuristic delta between each edge's vertices to the edge's weight.
To remember the sign of the adjustment with this method, just imagine the next vertex getting super close to the destination, and then work out whether the weight needs to increase or decrease significantly in that case. (It needs to decrease, given you're getting closer to the destination.)
I have no information other than the fact that my agent has a decision to make (left or right).
- DFS or BFS
I have some information about the cost of the decision.
- UCS or Djikstra's algorithm
I have some idea of the cost of the decision, and a rough idea which direction the goal is in.
- A star
As well as knowing the cost, and a rough idea of the direction, I also know that I have a uniform cost grid.
- Jump point search
https://www.redblobgames.com/grids/hexagons/
The interactive graphics evoke all the fun of being a child in a science museum.
I spent hours painstakingly drawing similar grids that the author of this article made and manually doing the calculations [0]. I still have these notes somewhere, even though they're over 20 years old at this point, because I was so proud of the work I put into it.
At any rate, thanks for this article and the trip down memory lane.
[0] https://imgur.com/a/zRYaodL (apologies for the Imgur link)
What has been called AI in gaming in the past is rich and varied, and goes all the way down to a computer control opponent “seeing” a player and opening fire, moving towards, or moving away. Any code controlling NPC was referred to as “the AI of the game” even if all the code was doing was applying a few simple rote rules rather than following an exactly pre-specified sequence.
“AI” in gaming means (or has previously meant) a lot less than “AI” has meant in other fields, but with the increasing use of “AI” in all contexts this will soon no longer be the case.
PS: the wiki article needs updating with more confirmation from the LLM era, if anyone's up for it... :)
I remember learning about A* in the AI lab at the University. Now these things sound trivial and we take them for granted. The joys of becoming old.
although perceptrons go back decades and decades.
I have found A* fascinating not because of the optimization but also from the various heuristics that can be built on top of it make it more generalized for other types of pathfinding.
Some devs have built solvers that use techniques like bidirectional search, precomputed pattern databases, and dead locking detection.
One also has multiple layers of roadways of varying arterial significance, allowing higher speed (lower weight) travel, with real-world roads.
It was used at a mapping job to great boon by our backend.
https://juhrjuhr.itch.io/deep-space-exploitation/devlog/9454...
and https://www.redblobgames.com/grids/hexagons/
- https://lukeyoo.fyi/recap/2025/5/a-star
- https://github.com/micttyoid/quantized-pathfinding