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

31–40 of 111 posts

Re: Introduction to the A* Algorithm (2014)

#31

Post by bandoti »

dspillett wrote: post #19
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 agree, though to be a pedant: > perhaps ONE of those articles It is the same article each time, though the comments coming off the different postings of it might have unique nuggets of useful information to dig for. > Thank you for providing links to the others though! I’m sure it will be helpful for someone. It isn't as prominent as on other sites, so it isn't difficult to miss sat right at the bottom of the main…

Personally, I don’t bother searching because I only consume the headlines, on other news sites too, come to think of it. There’s lots of interesting things people post but frankly I’d rather pay for a good book on any subject.

hides from the dreaded downvoters

I used to spend more time browsing when reading an actual newspaper or magazine. The discourse on opinion pieces and such is more thought out too—many people, myself included, post too quickly before thinking because we’re always on the go.

Something about the online experience consuming news is less satisfying. Perhaps a hacker out there can set up a print version of HN archives, and print it on a Gutenberg Press. :)

Re: Introduction to the A* Algorithm (2014)

#32

Post by Barrin92 »

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…

> Brownian motion until you do or get tired

The point of movement for npcs in a videogame isn't to behave realistically (or to be simulated fully), it's to produce engaging and challenging behavior to the player. In 99% of cases giving characters, like enemies in an action game, some extra information to enable them moving towards the player is the correct choice, people are fine with suspending their disbelief if the alternative is npcs giving up or running around like brownian particles, which does not make for a good experience.

Almost all the time the correct choice in game design is that it's fun and interesting, unless for the exception where you're literally building a real world simulator.

Re: Introduction to the A* Algorithm (2014)

#33

Post by apnorton »

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.

Re: Introduction to the A* Algorithm (2014)

#34

Post by marcosdumay »

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…

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

What a long and convoluted way to try to reinvent the A* algorithm...

Re: Introduction to the A* Algorithm (2014)

#35

Post by breckognize »

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!

Re: Introduction to the A* Algorithm (2014)

#36

Post by k2xl »

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.

Re: Introduction to the A* Algorithm (2014)

#37

Post by cornstalks »

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…

I encourage you to build a game with the mechanics you describe, especially something like an RTS, and see if it's any fun to play...

Re: Introduction to the A* Algorithm (2014)

#38

Post by HelloNurse »

JohnKemeny wrote: post #22
hoseja wrote: post #3

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

It's neither a hack nor trying to "behave" like anything. It is complete and optimal, with provable properties. Whenever there exists an admissible heuristic, you should use A* over Dijkstra's algorithm.

Even inadmissible heuristics can have their place, and it is easy to reason about how suboptimal they can be: you might want to trade off optimal results for performance (i.e. ignoring some part of the search space that should be searched) or to make an agent in a game a little stupid or stylized (e.g. prone to zig-zagging).

Re: Introduction to the A* Algorithm (2014)

#39

Post by Al-Khwarizmi »

diggan wrote: post #15
upghost wrote: post #14

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

The definition of "AI" has for a long time now been basically "We know it works somehow, but only few people really understand it", which is a moving target. At one point in the future, the LLMs we use today won't even be called AI anymore.

https://en.m.wikipedia.org/wiki/AI_effect

PS: the wiki article needs updating with more confirmation from the LLM era, if anyone's up for it... :)

Re: Introduction to the A* Algorithm (2014)

#40

Post by devrandoom »

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…

There are a lot of people on HN that aren't you.
Post reply on HN