Introduction to A* (1997) | Hacker News Reader

Introduction to A* (1997)

theory.stanford.edu

337 pointstosh31 comments

Amit's blogs get posted quite a bit, but they're a pleasure to go through every time. My favorites are his posts about noise and map/terrain generation with noise -

https://www.redblobgames.com/articles/noise/introduction.htm...

https://www.redblobgames.com/maps/terrain-from-noise/

He updates them every so often too! I hadn't seen them in a few years and I was impressed by all the new visualizations when I checked recently!

Thank you! I'm working on a new map project using some of those techniques.

For me, figuring out how to implement A* on a world was one of those programming milestones along the way of me grokking how software is put together. In fact, I see there's a Stack Overflow question from me still online with an implementation I wrote in Python eight years ago (https://stackoverflow.com/questions/4159331/python-speed-up-...), and I have sometimes wondered how many people have then used that old snippet as a reference.

Amit's articles were online then, and definitely helped me think through these problems, and their main strength is just how visual the explanations all are. I'm pleased to see they're still online, being updated, and no doubt benefitting others, I know that personally Amit's effort was one of a number of things that has allowed me to be a full-time indie game developer all these years later.

I can relate to that feeling - I cut my teeth on A* in Standard Pascal nearly a quarter of a century ago as a freshman, and the equivalent LISP was so tiny and concise to be a thing of beauty.

Glad to hear it! :)

A 3D RTS I worked on in the mid 90's used A* in a couple of ways to do pathfinding.

1. First generation was to use a series of 'way points' that was created with the landscape/level generator itself. They were the basic 'paths of best flow' in a very broad sense. It was used when a player sent troops from one side of the map to the other. There was only 20-40 of these on a map.

2. Second generation used a much finer granularity that was a lookup of preprocessed surface normals on the terrain.

So, the tank/unit would look at the waypoints to know generally which way is the 'best ish' way, and use a finer grained one for the first and last mile.

We also used collision avoidance schemes so you could pass one group of vehicles 'thru' another and they'd miss one another in a logical way (ie small deviations left/right based upon own vs. other speed).

We ended up not using the 'one vehicle per square' technique that may RTS used at the time -- we didn't need to.

Depending on your application, if you're interested in A* you may be interested in using Theta* instead. It's not much more difficult to implement but provides much shorter paths if one does not need to remain on the edges in the graph.

Take a look at the explanation and figures here: http://aigamedev.com/open/tutorials/theta-star-any-angle-pat... for more information.

The link you provided leads to Page Not Found

Working here, perhaps try again?

I also saw page not found, but reloading several times led to a lag and then a proper pageload.

Do you blame the edge, or the node?

My Clojure take on a* was kinda of a journey. I thought I understood the algorithm several times while implementing it. It took me a few passes, now I'm quite happy about the results. Impressive how concise it is compared to the imperative version in other languages. Here if you want to see https://gist.github.com/reborg/c3372428c6ccd7d93289fb7a3a9ec...

That is a very sexy snippet.

I love well written clojure code

You should have a look at : https://github.com/TristeFigure/shuriken/blob/ffbff58b19d555....

Amit always produces such great content. I can't even count the number of times I've landed on his site... such a useful resource!

A* was probably one of the most fun projects I did back in school a few years ago. If anyone is interested, last winter I ported an old C#/Unity A* implementation of mine to Rust and compiled it to WebAssembly for a small demo. It was my first time trying out wasm and really getting into Rust.

Repo: https://github.com/jakedeichert/wasm-astar

Live demo: https://jakedeichert.github.io/wasm-astar/

I just learned about this recently during the Udacity SDC! They go over an algorithm called A* hybrid which was super neat too. Instead of the discrete decisions of up, down, left ,and right, you define a set of state space equation (e.g. x(t+1) = x(t) + vΔt). This way, your results ends up being continuous and smooth which a car can actually follow. I think this was invented by the Sebastian Thurn's team during DARPA challenge.

Check out JPS+ if you need to go "over 100 times faster than A*"

https://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-t...

https://github.com/SteveRabin/JPSPlusWithGoalBounding

Also check out A* if you want to go 1000 times faster than JPS ;------)

A* does well when it is given a graph of all the decision points that matter. An unweighted grid is full of locations where it doesn't matter — e.g. whether you go N,N,E or E,N,N or N,E,N. JPS searches for better decision points on unweighted grids. There are lots of other A* optimizations for unweighted grids (subgoal graphs, contraction hierarchies, differential heuristics, bucketed priority queues, etc.) — see Table 2 in this paper [1].

JPS is notable for using no precomputation, which is very useful when the map is changing often. If you can afford analyzing the grid ahead of time, you can build a much better graph than using the grid directly — the Tree entry listed in Table 2 takes 30 sec of precomputation to bring A* down to 0.029 ms on average, compared to JPS which takes 62.524 ms on average.

[1] https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/11...

here is a cool and interactive version: https://qiao.github.io/PathFinding.js/visual/

The second image in the post gets me thinking about another possible path finding algorithm which would take into account view distance. Most path finding I've seen either has infinite foresight (to get absolute shortest path) or no foresight, it goes super deep before having to turn around.

But what if instead of having infinite units of sight or 1 unit of sight, the subject could see for example 10 units ahead. This could give a similar path demonstrated in the second photo by the red line.

Check out the Reach algorithm, which is related to your idea.

In college, I took an AI class where one of the MPs was about path planning and one of the implementations we needed to do was A* .

I later took a mechatronics class where we tried to implement A* on the microcontroller, which was a cool opportunity to see something theoretical in a physical way.

https://www.youtube.com/watch?v=3TM-WAfE3_Y

This link should be updated to https://www.redblobgames.com/pathfinding/a-star/introduction... which is the updated version of the page which the author links to in the page posted.

I had to implement A* at university, with a little application that also showed the status of the algorithm as it found the shortest path on a little ASCII bitmap.

It was probably one of the most fun and satisfying projects I did at university, alongside coding my own implementation of the RIPv2 routing protocol and my embedded systems projects (the last of which was creating a bluetooth controlled car with a webcam on it, which required us to design and build the entire board around a provided microcontroller).

It was just so satisfying to implement something that just a couple of years prior was practically magic.

And this helped me when I was building micromouse. One of the best designed competition to actually help learn interdisciplinary technology.

Discussed in 2014: https://news.ycombinator.com/item?id=7591119

Wall of text - I liked explanation of searching techniques in book "Artificial Inteligence - Modern Approach".

Also check out the interactive diagrams for the graph search chapter of that book [1]. I especially liked the "shoes of a search agent" one, which emphasizes that the algorithm doesn't "see" the whole graph like a human does.

[1]: http://aimacode.github.io/aima-javascript/3-Solving-Problems...

Note that game engines typically use bidirectional A* for efficiency.

https://github.com/sroycode/tway

It wasn't long ago that Game AI Pro said “bidirectional pathfinding for A* is usually a poor choice”[1]. There's been some recent work presented at GDC 2018 about bidirectional search[2] but even there they said it was only useful sometimes. Have things been changing? I'm not in the industry so I only hear bits and pieces.

[1] Chapter 17 http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter17_Pathf...

[2] Slides https://www.movingai.com/GDC18/GDC18Bidir.pdf or if you have access to the GDC Vault there's a recording of the talk https://www.gdcvault.com/browse/gdc-18/play/1025071/Bidirect...

Reply on news.ycombinator.com