Introduction to the A* Algorithm (2014)
redblobgames.com
Introduction to the A* Algorithm (2014)
1–10 of 31 posts
Re: Introduction to the A* Algorithm (2014)
#2Previous threads:
Introduction to the a* Algorithm - https://news.ycombinator.com/item?id=24146045 - August 2020 (1 comment)
Introduction to A* (2014) - https://news.ycombinator.com/item?id=18642462 - December 2018 (14 comments)
Introduction to A* - https://news.ycombinator.com/item?id=16190604 - January 2018 (0 comments)
Introduction to A* algorithm - https://news.ycombinator.com/item?id=10724098 - December 2015 (1 comment)
Introduction to A* - https://news.ycombinator.com/item?id=8059237 - July 2014 (28 comments)
Related threads:
Making of “Introduction to A*” - https://news.ycombinator.com/item?id=8445732 - October 2014 (12 comments)
Re: Introduction to the A* Algorithm (2014)
#3Really enjoy your works.
Re: Introduction to the A* Algorithm (2014)
#4Previous threads: Introduction to the a* Algorithm - https://news.ycombinator.com/item?id=24146045 - August 2020 (1 comment) Introduction to A* (2014) - https://news.ycombinator.com/item?id=18642462 - December 2018 (14 comments) Introduction to A* - https://news.ycombinator.com/item?id=16190604 - January 2018 (0 comments) Introduction to A* algorithm - https://news.ycombinator.com/item?id=10724098 - December 2015 (1…
Thank you, this gets posted here so frequently. And other articles from his site.
Re: Introduction to the A* Algorithm (2014)
#5I used to be obsessed with the programming game Screeps and read most of these blog posts when they were still published on the authors stanford pages- there's a lot of great stuff in there.
Re: Introduction to the A* Algorithm (2014)
#6A* is less useful when you're not omniscient, that is, testing if a cell is blocked has a sensing cost. I ran into this in a game application. To find out if a cell is obstructed, I have to do a ray cast at a few points in the cell, which uses resources. A* requires sensing a large number of cells to collect non-useful data, and if you have a big, mostly open space with some obstacles, like the real world, it does far too much sensing.
So I ended up with a variant on Pledge's approach to wall-following. Head toward the goal until an obstacle is detected. Then, start wall-following, but simultaneously in both left and right directions. When one of the wall-follower tests can head towards the goal, do that, and kill off the other wall-follower. So you alternate between heading towards the goal in open space, cheaply, and wall following.
Searching both left and right simultaneously avoids taking the long way round some obstacles.
Re: Introduction to the A* Algorithm (2014)
#7A* is less useful when you're not omniscient, that is, testing if a cell is blocked has a sensing cost. I ran into this in a game application. To find out if a cell is obstructed, I have to do a ray cast at a few points in the cell, which uses resources. A* requires sensing a large number of cells to collect non-useful data, and if you have a big, mostly open space with some obstacles, like the real world, it does fa…
Great comment!
Re: Introduction to the A* Algorithm (2014)
#8A* is less useful when you're not omniscient, that is, testing if a cell is blocked has a sensing cost. I ran into this in a game application. To find out if a cell is obstructed, I have to do a ray cast at a few points in the cell, which uses resources. A* requires sensing a large number of cells to collect non-useful data, and if you have a big, mostly open space with some obstacles, like the real world, it does fa…
You can modify the A* cost function to take the sensing cost into account:
f(x) = g(x) + h(x)
f(x) = (g(x) + [past sensing costs]) + (h(x) + [estimate of future sensing costs])Re: Introduction to the A* Algorithm (2014)
#9A* is less useful when you're not omniscient, that is, testing if a cell is blocked has a sensing cost. I ran into this in a game application. To find out if a cell is obstructed, I have to do a ray cast at a few points in the cell, which uses resources. A* requires sensing a large number of cells to collect non-useful data, and if you have a big, mostly open space with some obstacles, like the real world, it does fa…
Factorio solved this with hierarchical pathfinding: https://factorio.com/blog/post/fff-317
Re: Introduction to the A* Algorithm (2014)
#10A* is less useful when you're not omniscient, that is, testing if a cell is blocked has a sensing cost. I ran into this in a game application. To find out if a cell is obstructed, I have to do a ray cast at a few points in the cell, which uses resources. A* requires sensing a large number of cells to collect non-useful data, and if you have a big, mostly open space with some obstacles, like the real world, it does fa…
Factorio solved this with hierarchical pathfinding: https://factorio.com/blog/post/fff-317
Right, that's a low-end navmesh.