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

61–70 of 111 posts

Re: Introduction to the A* Algorithm (2014)

#61

Post by leftnode »

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)

Re: Introduction to the A* Algorithm (2014)

#63

Post by salamanderman »

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.

Re: Introduction to the A* Algorithm (2014)

#64

Post by raincole »

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…

How could the OP submit this link anyway?

When I submit a link that has been posted on HN before, it just redirects me to the old post.

Re: Introduction to the A* Algorithm (2014)

#65

Post by lelandfe »

Barrin92 wrote: post #29
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.

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. https://www.redblobgames.com/grids/hexagons/

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.

Re: Introduction to the A* Algorithm (2014)

#66

Post by random3 »

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…

Maybe there's a secret guide on how to build up karma :))

Re: Introduction to the A* Algorithm (2014)

#69

Post by ncr100 »

k2xl wrote: post #36

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 lik…

Just a note about bidirectional, or "double-ended" as I learned it - this can be very useful (i read 30% speed-up) for City / National Road searches.

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.

Re: Introduction to the A* Algorithm (2014)

#70

Post by Sohcahtoa82 »

hoseja wrote: post #12
herman_toothrot wrote: post #4

Earlier quoted context omitted.

What is your preference?

See the target/know which direction it is? Go that direction unless you see an obstacle, in that case go around the obstacle, eventually even backtracking if it turns out the obstacle was worse than you could see. Don't see/know the target? Brownian motion until you do or get tired. Have pathfinded to the target previously? The shortest path you saw while walking there. Al these require deep and complicated simulatio…

Everything you mentioned (Aside from Brownian motion, which is certainly the wrong solution) could be implemented with A* but with an incomplete graph.

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.

Post reply on HN