Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introduction to the A* Algorithm (2014)

redblobgames.com

Post reply on HN
Print view View original

71–80 of 111 posts

Re: Introduction to the A* Algorithm (2014)

#71

Post by teo_zero »

JohnKemeny wrote: post #2

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=302877…

I think the real reason this article keeps coming back is how good it is at teaching through examples and visualization, rather than the A* algorithm itself.

Re: Introduction to the A* Algorithm (2014)

#72

Post by giancarlostoro »

bandoti wrote: post #5
JohnKemeny wrote: post #2

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=302877…

Please consider some folks might be new to A*, and perhaps even HN, so maybe this is the first time they’ve seen it! :) 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 fo…

> Also, I have ten books on perspective drawing, and my understanding isn’t complete without all ten of them

Which books might those be? ;)

Re: Introduction to the A* Algorithm (2014)

#73

Post by repiret »

JohnKemeny wrote: post #2

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=302877…

I think A* deserves the popularity. It’s a simple variation on depth-first and breadth-first graph traversal that everyone learns in CS101, massively useful in some situations, yet for some reason isn’t a standard part of CS education. It’s a marvelous thing the first time you learn about it.

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.

Re: Introduction to the A* Algorithm (2014)

#74

Post by cornstalks »

salamanderman wrote: post #63
apnorton wrote: post #33

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) Di…

Breadth-first is a queue. Depth-first is a stack. A* is a priority queue.

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.

Re: Introduction to the A* Algorithm (2014)

#75

Post by wat10000 »

hoseja wrote: post #3

I don't like A* It's a performance hack, not how entities trying to get somewhere behave.

A* isn't how you get there, it's how you decide how to get there. The output is the shortest path, and that's what you actually follow.

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.

Re: Introduction to the A* Algorithm (2014)

#79

Post by cmrdporcupine »

ecshafer wrote: post #9

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.

Red Blob Games is also "amitp", one of the earliest Google employees. #7 or something like that.
Post reply on HN