5 ms·
Introduction to the A* Algorithm (2014)
- sebg 5y agoPrevious threads: Introduction to the a* Algorithm - https://news.ycombinator.com/item?id=24146045 https://news.ycombinator.com/item?id=24146045 - August 2020 (1 comment) Introduction to A* (2014) - https://news.ycombinator.com/item?id=18642462 https://news.ycombinator.com/item?id=18642462 - December 2018 (14 comments) Introduction to A* - https://news.ycombinator.com/item?id=16190604 https://news.ycombinator.com/item?id=16190604 - January 2018 (0 comments) Introduction to A* algorithm - https://news.ycombinator.com/item?id=10724098 https://news.ycombinator.com/item?id=10724098 - December 2015 (1 comment) Introduction to A* - https://news.ycombinator.com/item?id=8059237 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 https://news.ycombinator.com/item?id=8445732 - October 2014 (12 comments)
- slingnow 5y agoThank you, this gets posted here so frequently. And other articles from his site.
- DoryMinh 5y agoReally enjoy your works.
- amitp 5y agoThank you!
- mysterydip 5y agoAgreed, the effort you went into for explanations and interactive examples truly make it a high quality resource
- redisman 5y agoI remember reading these a long time ago! Thanks Amit, really helped me break into the games industry. (I’ve since left but still enjoy game programming)
- tedivm 5y agoI 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.
- amitp 5y agoScreeps is fascinating but I never got motivated to play it. :( I use the Stanford pages [1] to link to interesting papers and I use Red Blob Games to explore interactive ways of presenting topics. The most recent update to the Stanford pages is from 3 weeks ago, about any-angle pathfinding [2]. But most of what I do these days is on the Red Blob Games site. I probably would've kept using the Stanford pages but they have a 100MB quota limit and I was running out of space… [1] http://www-cs-students.stanford.edu/~amitp/gameprog.html http://www-cs-students.stanford.edu/~amitp/gameprog.html may be the oldest surviving game development website, as I started it in either 1994 or 1995. Older than Google or Wikipedia or even Slashdot. [2] http://theory.stanford.edu/~amitp/GameProgramming/Variations.html#any-angle-movement http://theory.stanford.edu/~amitp/GameProgramming/Variations...
- Animats 5y agoA* 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.
- adamc 5y agoGreat comment!
- 10000truths 5y agoYou can modify the A* cost function to take the sensing cost into account: f(x) = g(x) + h(x) Just becomes: f(x) = (g(x) + [past sensing costs]) + (h(x) + [estimate of future sensing costs])
- thaumasiotes 5y agoWhy are you including [past sensing costs] in g(x)? The sensing costs aren't part of the cost of following the path; they're a cost of calculating it.
- 10000truths 5y agog(x) represents the costs that have been incurred thus far, since the starting point. How you wish to quantify and evaluate that cost is up to you as the implementer. For spatial navigation purposes, most people opt for “cost = Euclidean distance traversed”, but if Euclidean distance is not the only thing you’re trying to minimize, then your cost function must take other factors into account.
- wingman-jr 5y agoJump point search is also pretty nifty for a block-based subset of pathfinding.
- feoren 5y agoI have bookmarked many Red Blob Games posts like this one, both because of their excellent content, but also as examples of how to write truly great tutorials. Well organized content, good CSS without over-styling, advanced JavaScript but only used in the exact right places: interactive demos, toggles to customize the content more to your use case (e.g. hex vs. square), and not to hijack my scroll bar or for unnecessary flashiness. This site is my go-to for inspiration on how to write a fantastic tutorial.
- sapein 5y agoI've come across this link before, and it's actually really useful. I used it to help me implement A* myself for a project I was working on, which worked decently for my rather simple use-case.
- self-symmetric 5y agoA few years ago, I wondered whether it was possible to extend A* to pathfinding with momentum. It would require a consistent and admissible heuristic for Newtonian kinematics. It was a little tricky to find but it turns out that it does exist! The code (and animations) are here: https://github.com/matthew-piziak/spacepath https://github.com/matthew-piziak/spacepath It shows a spaceship finding time-optimal paths around asteroids, with nothing but A* doing the pathing.
- two_poles_here 5y agoAmit, your amazing man. I've come across this doing Advent of Code this year. You're the only reason I no longer fear DSA as a self taught programmer. If you're ever in Bangalore I owe you a drink.