from Hacker News

Introduction to the A* Algorithm (2014)

by auraham on 6/17/25, 7:25 AM with 103 comments

  • by apnorton on 6/18/25, 1:51 PM

    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.

  • by ecshafer on 6/18/25, 12:42 PM

    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.

  • by leftnode on 6/18/25, 4:47 PM

    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.

    [0] https://imgur.com/a/zRYaodL (apologies for the Imgur link)

  • by upghost on 6/18/25, 12:54 PM

    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".

  • by kazinator on 6/18/25, 8:00 PM

    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".

  • by k2xl on 6/18/25, 2:07 PM

    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.

  • by 90s_dev on 6/19/25, 2:34 AM

  • by lukeyoo on 6/18/25, 9:09 PM

  • by kriro on 6/18/25, 8:36 PM

    Best introduction to A* in my opinion is travelling in Romania :)

    AI a Modern Approach.

  • by cryptomic22 on 6/18/25, 3:28 PM

    Path finding visualization, highlighting A*: https://youtube.com/shorts/L8t0tt1Vrsw

  • by mysteria on 6/18/25, 5:33 PM

    Funny enough I got a hit of nostalgia seeing this as I learned A* for a school project many years ago using this exact same tutorial.

  • by 0manrho on 6/18/25, 3:17 PM

    I have a perhaps overly simplistic question, but how is this meant to be pronounced? A-star? Ah-sterisk?

  • by deadbabe on 6/18/25, 3:58 PM

    A* is simple enough, but how do you handle pathfinding when the environment isn’t known to the entity?

  • by Kye on 6/18/25, 7:58 PM

    Not to be confused with Sagittarius A*.

    https://en.wikipedia.org/wiki/Sagittarius_A*

  • by JohnKemeny on 6/18/25, 12:24 PM

    It's that time of year again. I like A* as much as the next one, but it seems a bit excessive a times.

    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)

  • by hoseja on 6/18/25, 12:29 PM

    I don't like A*

    It's a performance hack, not how entities trying to get somewhere behave.