from Hacker News

Introduction to the A* Algorithm (2014)

by djood on 2/10/22, 3:42 PM with 30 comments

• by sebg on 2/10/22, 4:08 PM

  Previous 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)

• by Animats on 2/10/22, 6:19 PM

  A* 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.

• by tedivm on 2/10/22, 5:13 PM

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

• by feoren on 2/10/22, 10:23 PM

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

• by self-symmetric on 2/11/22, 3:20 AM

  A 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

  It shows a spaceship finding time-optimal paths around asteroids, with nothing but A* doing the pathing.

• by sapein on 2/10/22, 10:28 PM

  I'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.

• by two_poles_here on 2/11/22, 4:59 AM

  Amit, 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.

• by DoryMinh on 2/10/22, 4:09 PM

  Really enjoy your works.

• by wingman-jr on 2/10/22, 9:39 PM

  Jump point search is also pretty nifty for a block-based subset of pathfinding.