Introduction to the A* Algorithm

Here's a breakdown of the key themes from the Hacker News discussion about the A* algorithm, along with supporting quotes:

A* Algorithm: "That Time of Year Again"

The repeated posting of the A* algorithm introduction sparks a meta-discussion about reposts on Hacker News. Some users find the repetition excessive, noting that it seems to appear annually.

• "It's that time of year again. I like A* as much as the next one, but it seems a bit excessive a times." - JohnKemeny

This sentiment is countered by others who argue that reposts are valuable for newcomers and can lead to new discussions.

Defending Reposts

Several users defend the re-posting of content, arguing that not everyone sees every post the first (or second, or third) time. They also highlight the value of fresh perspectives and discussions.

• "Please consider some folks might be new to A*, and perhaps even HN, so maybe this is the first time they’ve seen it! :)" - bandoti
• "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." - add-sub-mul-div

The Psychology of Pointing Out Reposts

Some users delve into the psychology behind those who point out reposts, suggesting it's a form of validation or a "hall monitor" mentality.

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

Suggestions for an "Evergreen" Feature

One user suggests a potential solution: an "evergreen" feature that would track re-submissions, suggest them to new users, and periodically resurface them for existing users, minimizing complaints about repetitions.

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

A*'s Continued Relevance as a Teaching Tool

The article's merit as a teaching tool is brought up, suggesting that the A* algorithm concept makes regular appearances because of its usefulness for people new to pathfinding and visualization.

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

A*'s Pedagogical Significance

Some consider A* to be an important algorithm for computer science education:

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

A* Algorithm's Limitations in Realistic Scenarios

A contrasting viewpoint emerges, questioning A*'s suitability for simulating realistic behavior, particular in games. Some argue that it relies on omniscient perspective and doesn't account for limited information that entities typically have.

• "I don't like A* It's a performance hack, not how entities trying to get somewhere behave." - hoseja
• "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." - hoseja

Alternative Approaches to Pathfinding

This criticism leads to the discussion of alternatives, such as Brownian motion or reactive approaches based on local information.

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

Pragmatism in Game Design

Counterarguments emphasize the importance of engaging and challenging behavior in games over strict realism. The goal is not to perfectly simulate, but to create a fun and interesting experience for the player.

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

The Role of Heuristics and Information

Some point out that the perceived "unfairness" of A* in games stems from the heuristic function, which effectively gives the enemy knowledge they shouldn't have. The suggestion is to use more realistic heuristic functions based on limited information.

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

Incomplete Graphs for More Realistic Behavior

Some note that A can be used with* an incomplete graph to simulate a character's limited knowledge.

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