21–30 of 111 posts
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 don't like A* It's a performance hack, not how entities trying to get somewhere behave.
It is complete and optimal, with provable properties.
Whenever there exists an admissible heuristic, you should use A* over Dijkstra's algorithm.
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…
Your example also fails in several really obvious ways. What if there is a pool of mud or water in the middle of the path, it IS traversable but doing so is not ideal? A* you give this a high traversal cost and you'll naturally path around it. Your solution will have the object going through high cost but traversable areas in strange ways. This is going to be worse, as players will just kite and exploit this fact.
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".
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".
What has been called AI in gaming in the past is rich and varied, and goes all the way down to a computer control opponent “seeing” a player and opening fire, moving towards, or moving away. Any code controlling NPC was referred to as “the AI of the game” even if all the code was doing was applying a few simple rote rules rather than following an exactly pre-specified sequence.
“AI” in gaming means (or has previously meant) a lot less than “AI” has meant in other fields, but with the increasing use of “AI” in all contexts this will soon no longer be the case.
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…
You can achieve exactly what you're describing by hiding information entities do not have from their pathfinding.
Graphs aren't the problem, and thinking along those lines won't get you where you're trying to go.
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 don't like A* It's a performance hack, not how entities trying to get somewhere behave.
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.
Earlier quoted context omitted.
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.
The way to think about water crossing with naval transports, is to consider those things to be conditions. You already have a set of condition when pathfinding. Just add another case for water. Make it so the requirement is that you’re either on a ship or there is a ship on the adjacent tile you checked previously, e.g N-1. If valid, set a flag and now every tile check that is water should be appropriate.