HN Reader

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

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.

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

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.

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)

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

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 don't like A*

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

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