Introduction to the A* Algorithm (2014)
redblobgames.com
redblobgames.com
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.
· 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.
This is the insight behind the decorate-sort-undecorate pattern; it's just heapsort, with a different key function allowing you to represent several different algorithms.
> BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges
He doesn't say that, and it isn't true.
My sentence was supposed to be read as "g(n) = number of edges", and implicitly, of course (since we're talking about BFS), that means number of edges seen up until now, from ns perspective. And yes, n usually denotes the size of the graph, however, in the context of A*, we usually write n to denote the current node (as per AI:MA).
I take full responsibility. (Disclaimer: I'm a CS professor teaching BFS and Dijkstra's algorithm every semester and A* every 2nd year.)
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
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.
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.)
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)
PS: the wiki article needs updating with more confirmation from the LLM era, if anyone's up for it... :)
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.
I absolutely love that book. Maybe that's why I get a little cringey at the "AI" monicker for LLMs.
although perceptrons go back decades and decades.
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.
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...
AI a Modern Approach.
(Or words to that effect, it's been 20+ years since I read it.)
https://www.researchgate.net/publication/355761412_Path_plan...
GOFAI techniques are: A) Usually unable to incorporate posteri knowledge of the environments they're working on. And B) Often entirely infeasible to adapt to take exploration costs into account.
I've heard of some GOFAI techniques for optimal unbiased pathfinding in unknown environments using optimal transport theory and the like. But unbiased methods are obviously going to lose out in real environments.
I never got in the habit of using share links, so it's interesting to learn Wikipedia has a URL shortener.
Title should have a (2014) in it: Introduction to the A* Algorithm (2014).
1 points, 8 months ago, 1 comments: Introduction to the a* Algorithm (https://news.ycombinator.com/item?id=41897736)
202 points, 3 years ago, 30 comments: Introduction to the A* Algorithm (2014) (https://news.ycombinator.com/item?id=30287733)
4 points, 5 years ago, 1 comments: Introduction to the a* Algorithm (https://news.ycombinator.com/item?id=24146045)
201 points, 7 years ago, 14 comments: Introduction to A* (2014) (https://news.ycombinator.com/item?id=18642462)
5 points, 7 years ago, 0 comments: Introduction to A* (https://news.ycombinator.com/item?id=16190604)
Also, I have ten books on perspective drawing, and my understanding isn’t complete without all ten of them
Or, if I’m teaching a subject on A*, perhaps ONE of those articles conveys the materials best for my students.
Thank you for providing links to the others though! I’m sure it will be helpful for someone.
The Smarties test (What's in this Smarties tube - look it's not Smarties, ok now what does somebody else think is in the tube?) shows that humans need a further step to discover that model isn't enough.
But it's still cheaper and it's pretty good. It will correctly predict that this person you've never met before probably wants cake not death, just like you. It won't reliably predict whether they prefer lemon cake or coffee cake. But it's a good first guess.
> perhaps ONE of those articles
It is the same article each time, though the comments coming off the different postings of it might have unique nuggets of useful information to dig for.
> Thank you for providing links to the others though! I’m sure it will be helpful for someone.
It isn't as prominent as on other sites, so it isn't difficult to miss sat right at the bottom of the main page, but HN does have a working search function. I find searching for older posts this way can be quite useful for the above reason, when something comes up that has existed for a few years.
hides from the dreaded downvoters
I used to spend more time browsing when reading an actual newspaper or magazine. The discourse on opinion pieces and such is more thought out too—many people, myself included, post too quickly before thinking because we’re always on the go.
Something about the online experience consuming news is less satisfying. Perhaps a hacker out there can set up a print version of HN archives, and print it on a Gutenberg Press. :)
Which books might those be? ;)
When I submit a link that has been posted on HN before, it just redirects me to the old post.
It’s even more marvelous if it helps you recognize that the difference between BFS and DFS is how you pick the next node to explore out of your bag of unexplored nodes. That symmetry is easily lost if DFS is only taught as a recursive algorithm.
Let it keep coming up every couple years to marvel a new generation of programmers.
It's a performance hack, not how entities trying to get somewhere behave.
Al these require deep and complicated simulation of the entity though instead of solving a graph problem from omniscient perspective. Many topdown games really break my immersion when I see things just blatantly a-staring places.
Basically, things usually have limited information and it's weird to see them behave as if they don't. Plus on grids there's the cringe "diagonal and then straight" movement pattern.
For example, in a RTS making units follow a leader in formation can be more natural and less expensive than performing independent optimal pathfinding for all of them, while in environments with many obstacles staying away from walls (on a simplified graph of good positions) is usually more elegant than hugging corners (on a much more complex graph).
Your example also fails in several really obvious ways. What if there is a pool of mud or water in the middle of the path, it IS traversable but doing so is not ideal? A* you give this a high traversal cost and you'll naturally path around it. Your solution will have the object going through high cost but traversable areas in strange ways. This is going to be worse, as players will just kite and exploit this fact.
You can achieve exactly what you're describing by hiding information entities do not have from their pathfinding.
Graphs aren't the problem, and thinking along those lines won't get you where you're trying to go.
The point of movement for npcs in a videogame isn't to behave realistically (or to be simulated fully), it's to produce engaging and challenging behavior to the player. In 99% of cases giving characters, like enemies in an action game, some extra information to enable them moving towards the player is the correct choice, people are fine with suspending their disbelief if the alternative is npcs giving up or running around like brownian particles, which does not make for a good experience.
Almost all the time the correct choice in game design is that it's fun and interesting, unless for the exception where you're literally building a real world simulator.
What a long and convoluted way to try to reinvent the A* algorithm...
I've seen it work that way in an RTS before. Fog of war will make a unit unaware of what the terrain actually looks like and the unit will head straight in the direction of where I told it to go until it finds a cliff, then it starts trying to go around it.
The way to think about water crossing with naval transports, is to consider those things to be conditions. You already have a set of condition when pathfinding. Just add another case for water. Make it so the requirement is that you’re either on a ship or there is a ship on the adjacent tile you checked previously, e.g N-1. If valid, set a flag and now every tile check that is water should be appropriate.
Welcome to game development, where fun and performance tends to be more important than realism :)
It is complete and optimal, with provable properties.
Whenever there exists an admissible heuristic, you should use A* over Dijkstra's algorithm.
It's pretty similar to how people find the shortest path in an unfamiliar environment. If you're looking at a map for the shortest route to a city to the north of your current position, you probably won't spend a lot of time looking at roads going south, and you'll concentrate on road segments that get you crow-flies closer to your destination.