A* Search | Hacker News Reader

A* Search

kartikkukreja.wordpress.com

84 pointskartikkukreja19 comments

The A* algorithm is a really interesting one. It's conceptually quite simple if you approach it from the right angle, but most of the time I've seen it poorly explained, and as a consequence, people really struggling to "get it".

My little contribution is a very accessible series of articles that derives A* almost from scratch, in a way that is really easy to understand: http://gabrielgambetta.com/path1.html

That's great; much better than TFA! I really appreciated the very logical division into Parts I-IV.

Amazing set of articles. I would up vote this many times over if I could. Thank you my friend!

What I find interesting is that A star, DFS, BFS, Dijkstra's algorithm, JPS, etc are all basically the same algorithm. The only real difference is the queuing priority. (BFS is LIFO, DFS is FIFO, Dijkstra is min-distance-from-start-first, A star is min-distance-from-start-plus-(admissible,ideally)-heuristic-distance-to-end-first )

Most CS courses I've seen teach them as entirely separate algorithms, which I find... frustrating. Or rather, unnecessarily complex.

What you say is absolutely correct, and I really don't understand why this is not the way it's explained by default. I've written some articles, linked from some other comment here, that does exactly what you propose. People generally find them extremely useful.

I learned them as refinements of each other. Similarly, we were taught alpha-beta search as refinement of minimax search in games.

Then I am glad that my CS course taught them the way you describe.

If you're interested in pathfinding, you might enjoy this video. http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-th...

Taken from the description:

In 2011, Harabor and Grastien introduced Jump Point Search (JPS) that achieves up to a 10x speed improvement over A* on uniform cost grids. In the last year, an additional 10x speed improvement to JPS, called JPS+ was independently developed by Steve Rabin as well as Harabor and Grastien. This improved algorithm is over 100x faster than A* on maps with open areas and over 2x faster than A* on worst-case maps. This incredible speed-up is due to pre-computation, eliminating the recursion in JPS and focusing only on touching select relevant nodes during the search.

There is another pathfinding algorithm with smaller pre-computation step and comparable (if not higher) speed. It allows you to do benchmarks on various maps, and it compares itself to other algorithms. I also think it's simpler than JPS.

http://mikolalysenko.github.io/l1-path-finder/www/

Unfortunately, they require large precompute time and static maps. If your maps change, you can't use it.

And if your maps don't change, you can use precomputation with A* , making it even faster than JPS+.

1. Preprocess the graph to make it smaller. Visibility graphs are a first step, but if you have grid movement you can remove the redundancies (e.g. N-N-W taking you to the same place as W-N-N) to make an even smaller pathfinding graph. Here's a library implementing one of many such algorithms: http://mikolalysenko.github.io/l1-path-finder/www/

2. Preprocess the graph to get better distance estimates. The closer your A* heuristic is to the actual distance, the faster A* will run. “Differential heuristics” use the triangle inequality: if you have exact distances to one point L, then you can say dist(A, B) >= dist(L, B) - dist(L, A). There are other approaches too.

There's a recent paper http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf that covers some of the optimizations for pathfinding on grids.

Amit Patel has a great series on A* pathfinding: http://theory.stanford.edu/~amitp/GameProgramming/AStarCompa...

Came here to post exactly this. I was once trying to implement A* and his explanation was what helped me understand it properly.

I wrote a tutorial for this too which includes c++ source code that's been used in some succcesful video games and thereby tested by millions of people http://heyes-jones.com/astar.php

One of the most used in industry approaches to pathfinding in things like RTSes is what's called a flow field. It's a bit like a precalculated pathfinding map.

These are some of the most interesting for what you can accomplish (pathfinding a ton of units at once!).

A great resource for that is this blog:

https://howtorts.github.io/

It has working javascript examples and other related topics like flocking behavior.

This article was really helpful to me in understanding A*: http://www.briangrinstead.com/blog/astar-search-algorithm-in...

A nice way to visualize A* with different heuristics : https://qiao.github.io/PathFinding.js/visual. Also supports lots of other algorithms.

An example of the A* search algorithm in use: https://www.youtube.com/watch?v=DlkMs4ZHHr8

Is it really necessary to write so many blog posts explaining this 50 year old algorithm? I would have thought that there is enough material around right now.

Reply on news.ycombinator.com