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

11–20 of 111 posts

Re: Introduction to the A* Algorithm (2014)

#11

Post by pmichaud »

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 it's just the first, most obvious thing to teach people just starting in pathfinding. It works in real life, it's easy to visualize and compute. Therefore all the tutorials are about it :)

Re: Introduction to the A* Algorithm (2014)

#12

Post by hoseja »

herman_toothrot wrote: post #4
hoseja wrote: post #3

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

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 simulation of the entity though instead of solving a graph problem from omniscient perspective. Many topdown games really break my immersion when I see things just blatantly a-staring places.

Basically, things usually have limited information and it's weird to see them behave as if they don't. Plus on grids there's the cringe "diagonal and then straight" movement pattern.

Re: Introduction to the A* Algorithm (2014)

#13

Post by smallstepforman »

ecshafer wrote: post #10
hoseja wrote: post #3

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

It works really wells for many situations. If I am making a top down strategy game (Think Civilization) then A* is exactly what I need, a fast performance hack that gives me the shortest path without anything weird going on. For different kind of environments, then yes it doesn't work. A* isn't very useful in a racing game.

It took me 3 hours to implement A* with hex tiles, got it working on first attempt (land tiles only), specifically for Civ type game. It gets complex when you want to group units so that they travel together. Adding water crossings with cargo ships and war ships is a different challenge.

Re: Introduction to the A* Algorithm (2014)

#14

Post by upghost »

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

Re: Introduction to the A* Algorithm (2014)

#15

Post by diggan »

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.

Re: Introduction to the A* Algorithm (2014)

#16

Post by diggan »

hoseja wrote: post #3

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

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

Welcome to game development, where fun and performance tends to be more important than realism :)

Re: Introduction to the A* Algorithm (2014)

#17

Post by dweekly »

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'm not sure your complaint is actually that A* is bad, it's that the heuristic function is unfair (to the player, by giving the mob data they shouldn't have). A more sophisticated game could use a more interesting function like an estimate as to what direction the player's movement sound would be heard from.

Re: Introduction to the A* Algorithm (2014)

#18

Post by tialaramex »

add-sub-mul-div wrote: post #8
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…

Yeah people live by this leaky abstraction that an article having been posted before means everyone was online that day and saw it and now it has expired . And for some reason they chase these hall monitor points for pointing it out. Let's see what a discussion would be like from today's point of view.

The cheapest available model once you have Theory of Mind (the idea that the other things in the environment might be thinking like you do) is that they're you again.

The Smarties test (What's in this Smarties tube - look it's not Smarties, ok now what does somebody else think is in the tube?) shows that humans need a further step to discover that model isn't enough.

But it's still cheaper and it's pretty good. It will correctly predict that this person you've never met before probably wants cake not death, just like you. It won't reliably predict whether they prefer lemon cake or coffee cake. But it's a good first guess.

Re: Introduction to the A* Algorithm (2014)

#19

Post by dspillett »

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…

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 page, but HN does have a working search function. I find searching for older posts this way can be quite useful for the above reason, when something comes up that has existed for a few years.

Re: Introduction to the A* Algorithm (2014)

#20

Post by dspillett »

add-sub-mul-div wrote: post #8
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…

Yeah people live by this leaky abstraction that an article having been posted before means everyone was online that day and saw it and now it has expired . And for some reason they chase these hall monitor points for pointing it out. Let's see what a discussion would be like from today's point of view.

Also: some people seem to get an amount of pleasure from pointing out repeats, as if remembering that something was posted before is knowledge enough to make them a better person than the poster, us all, or just the person they thought they were themselves. This is fine when something is posted far too often, or is reposted by a point-farming bot (presumably the users running such bots hope to use the reputation of the account somehow in future), but is often done overzealously.
Post reply on HN