A* Search

https://kartikkukreja.wordpress.com/2013/12/28/a-star-search/

by kartikkukreja • 11 years ago

84 19 11 years ago

kartikkukreja.wordpress.com

ggambetta2• 11 years ago

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

jessaustin• 11 years ago

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

trcollinson• 11 years ago

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

bpp• 11 years ago

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

logane• 11 years ago

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

hippo8• 11 years ago

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

suby• 11 years ago

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.

kefka• 11 years ago

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

amitp• 11 years ago

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.

ingenter• 11 years ago

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/

akeruu• 11 years ago

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

justinhj• 11 years ago

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

TheLoneWolfling• 11 years ago

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.

ggambetta2• 11 years ago

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.

Scea912• 11 years ago

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

mcv• 11 years ago

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

octaveguin• 11 years ago

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.

c3534l• 11 years ago

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

Scea912• 11 years ago

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.

A* Search

Related Stories