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

51–60 of 111 posts

Re: Introduction to the A* Algorithm (2014)

#51

Post by bcrosby95 »

tonyhart7 wrote: post #49
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…

well they all just loop???

Simplifications help people memorize things but if you get too reductive it becomes useless.

Re: Introduction to the A* Algorithm (2014)

#57

Post by dietr1ch »

breckognize wrote: post #35
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…

And depth first search is just a stack!

Yes, but it doesn't come right away. When preferring deeper nodes for a moment you have a loop-safe Depth-first traversal, and then when simplifying things in case the Graph is a Tree you get your regular stack-based Depth-first traversal, in which if you settle for the first goal you get back a tail-call optimised DFS.

Re: Introduction to the A* Algorithm (2014)

#58

Post by S0y »

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 came here to say the same thing. Red Blob Games is such a gold mine of resources for anyone looking to get into gamedev.

Re: Introduction to the A* Algorithm (2014)

#59

Post by dietr1ch »

schneems wrote: post #27
bandoti wrote: post #5

Earlier quoted context omitted.

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…

I wish there was a “evergreen” feature for social sites where it tracked resubmissions and would auto suggest them to people who haven’t seen them and periodically surface them to those who have and ask “is this still relevant” That way really good content keeps being recommended to those who need it and you get fewer complaints from old timers who don’t have to see it N times.

My dream is a knowledge-aware Wikipedia that can be more relevant by understanding what the reader knows, might know and might find interesting w/o being overwhelming. I guess you can make this social too and have discussion groups, but it's already too large of a project in my mind.

Re: Introduction to the A* Algorithm (2014)

#60

Post by ViscountPenguin »

deadbabe wrote: post #54

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

Iirc, the best approaches for this nowadays are machine learning based. Otherwise, you probably want to do an exploration step first, and bake in the environment.
Post reply on HN