Introduction to A*

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

by ghosh • 12 years ago

298 56 12 years ago

theory.stanford.edu

royjacobs• 12 years ago

This is a really clear explanation of the algorithm. It's very powerful but at the same time reasonably simple to implement. However, a lot of the explanations of the algorithm either are extremely convoluted (Wikipedia) or they are handwavey or broken (game development 'community' sites). This is a good middle ground.

OT: As an exercise I did a 6510 Assembly implementation on the c64 a while ago on a pretty tiny grid (20x10 IIRC) and that worked wonderfully. Not sure if there would be any practical use for it, but there you go.

danso• 12 years ago

A great walkthrough...I've read this before and still remember how the article was laid out...it's unfortunately rare for "theory" websites to have decent typography and whitespace that doesn't hinder reading.

In my comsci classes, I'm pretty sure we talked about Dijkstra's algorithm...and I'm pretty sure we talked about priority queues. But not until I recently tried implementing the algorithm on my own (just for a fun six-degrees-of-separation network graph) did I realize how important having a priority queue was...I wish the two concepts had been taught in tandem and shown how they relate to algorithm performance (though yes, I do realize, according to Wikipedia, that Dijkstra's original algorithm did not have a min-priority queue).

It'd be fun to go to a college com sci class now and see if these concepts are much better explained now that we have the ability to show them easily via interactive means (I'm sure many here have seen this wonderful site: http://qiao.github.io/PathFinding.js/visual/)...It's not only that they can be seen and interacted with, but it's conceivably much easier for the average com sci student to attempt to build an interactive visualization to demonstrate these concepts....A bit harder when you're working with only C/C++

gemignani• 12 years ago

Thanks for sharing, this is perfect! I did the coursera IA, but this simulation is something really cool, I will share with them.

gambiting• 12 years ago

One of my favourite algorithms....I am writing my dissertation on A* implementation in CUDA at the moment, so I've got to work with different approaches to it, it's fascinating really.

fddlr• 12 years ago

Hey! I also wrote my thesis in CUDA, but I implemented the interval newton algorithm. Could you send me an email when it's done? I'm very interested in it.

Qworg• 12 years ago

I think you'll find there are quite a few people interested in something like this - I know I certainly am.

Do you have plans to share some of your data/sections early? If you'd like, I'm even willing to help proof your dissertation. My email is in my profile.

icegreentea2• 12 years ago

I don't know how much help I could be with proofing, but I am also super interested in this! Just spent the last 6 months puttering around trying to squeeze out every bit of performance out of A* and related algorithms, and would sure love to see some paralleled lovelyness.

psycovic234• 12 years ago

Have any publications you could point me to?

j_s• 12 years ago

Seems there is a great deal of interest in this; I hope you'll add some contact info to the publicly-visible 'about' section of your HN profile so that people can get in touch!

gabipurcaru2• 12 years ago

Wasn't it called the Breadth-First Search algorithm (as opposed to the Depth First Search)? I never noticed this name before.

ekr• 12 years ago

Those are two different algorithms for searching in a graph (they are in fact very similar, one uses a queue, and the other uses a stack). Check your Cormen.

sltkr• 12 years ago

It's more like: breadth-first search is a specialization of Dijkstra's algorithm, which is a specialization of A*.

navait• 12 years ago

No. A* uses a heuristic and cost function to decide which nodes to expand next, rather than BFS which uses a straight up queue. They do have a lot in common though.

ralfn• 12 years ago

No! You are likely confusing it with best-first-search. A* is an implementation of best-first-search, not breadth-first-search.

Breadth-first-search does not prune a search space; it just sorts the search space based on depth. It also assumes the cost of every path is equal.

Example: Finding the shortest road between two cities.

With breadth-first-search, we would consider all connected cities, and then the cities they are connected to, until we reach our destination. We would end up with a route, that travels through the least amount of cities, irregardless of the lengths of the actual roads. We would get the most simple route not the shortest route nor the fastest route.

Feature: calculating using actual costs

To get the shortest route we need to be able to annotate road-length (as cost) in our graph. Using that information we can choose to expand shorter routes before we dive into the longer routes. We might expand A -> B -> C before A -> D because the cummulative road-length of A -> B -> C might be less than the direct road between A -> D. For this to happen we would constantly sort our working set, based on the calculated cost.

As soon as a completed route (to the destination) is at the top of our working set, we can stop and deliver the answer.

Optimization: Pruning

Now, this working set, gets larger with every iteration. If we were to search for the shortest route from A -> D and the answer would be 100 miles, than the working set will contain all routes from A to anywhere, that are less than a 100 miles.

This is very expensive in terms of memory and time: we need to prune the search space. Now, our working set is already sorted based on cost. So we can safely remove every route that ends in the same place as a route above it in the working set. In other words, if A -> B -> C is higher in the working set than A -> D -> C, than we remove A -> D -> C. We simply don't have to expand routes from the same origin twice.

Optimization: using a lower bound

If the costs are truly unpredictable, and we want a perfect answer, this is the best we can do. But costs are rarely unpredictable! Can we provide a lower bound? Sure! Let's use the geospatial distance between two cities. No road is shorter, than the actual distance between the cities.

In this scenario, the costs of our working-set would be calculated as the actual costs of the partial route plus the lower bound. So, the cost of A -> B -> C would be calculated as the actual road length from A upto C plus the distance from C to the destination.

Now this impacts the sorting of the working set. Which is why it is so important it is a lower bound and not an estimate. Because as soon a completed route is at the top of our working-set we call it quits, and deliver the answer.

In a nutshell: A* is a best-first-search that is capable of utilizing a lower bound to sort the search space. It's behavior is far removed from breadth-first-search.

gabipurcaru2• 12 years ago

The more you know I guess. Thanks for the explanation!

glenra• 12 years ago

The key thing that distinguishes A* from BFS or DFS is that you use it when you want to make use of a distance metric to traverse a graph. What I mean by that is you have some way of objectively measuring whether you are getting closer or getting further away from your goal as you progress along different possible paths.

For example, if the task is to find the shortest path between two cities on a highway map, you can calculate a straight-line "as the crow flies" distance to the goal from any point on the map - that is a usable distance metric. A* makes use of that additional information to find the shortest possible path while evaluating the fewest necessary number of alternative routes.

[Caveat: My dad invented A*, so I've probably got this laughably wrong. :-) ]

jrabone• 12 years ago

https://www.codeofhonor.com/blog/the-starcraft-path-finding-... is a great article on the woes of path finding even when given a good basic algorithm. Nice contrast of theory and practice.

vanderZwan• 12 years ago

If you're trying to simulate crowds, I get the impression this is the new hotness:

http://grail.cs.washington.edu/projects/crowd-flows/

It's currently being used in Supreme Commander 2, and in the up and coming Planetary Annihilation. Here's a livestream where the developers demonstrate an implementation in an early build of their game:

https://www.youtube.com/watch?v=5Qyl7h7D1Q8&feature=youtu.be...

justinhj• 12 years ago

Here's another http://heyes-jones.com/astar.php I'm the author. Expands a bit more on what a heuristic is, admissibility and includes source on GitHub of a cpp implementation of the algorithm.

FLUX-YOU• 12 years ago

http://ocw.mit.edu/courses/electrical-engineering-and-comput...

AI course which goes into the details leading up to the A* algorithm (45 minutes)

Rizz• 12 years ago

There are many variants of A* that can handle changing environments/imperfect information, multiple goals, limited time, etc. A number of them are listed at:

http://idm-lab.org/project-a.html

amitp7• 12 years ago

(author here)

I wrote most of these notes in 1997 while working on a game. Little did I realize that it'd be one of my most popular web pages.

The diagrams are colorful but I don't like them (http://simblob.blogspot.com/2013/12/diagrams-on-my-pathfindi...) so I'm now making new interactive diagrams, starting with breadth first search (http://www.redblobgames.com/pathfinding/tower-defense/). While writing that page, I realized that I need to explain graphs (http://www.redblobgames.com/pathfinding/grids/graphs.html) (many game developers don't know graph theory) and suggest optimizations for grids (http://www.redblobgames.com/pathfinding/grids/algorithms.htm...) (a common use case, with interesting variants of A* like Jump Point Search).

I'm also unhappy with the overall structure and navigation so I have a rough plan for how to organize the new pages (https://twitter.com/redblobgames/status/410182845777195008/p...). I'm taking it one page at a time instead of trying to do it all at once. Feedback appreciated!

vowelless2• 12 years ago

I just want to say thank you! I have that page burned in my memory. I relied on it heavily when I first encountered A* many years ago in undergrad. I think you have changed the design of the page because I don't remember so much red!

amitp7• 12 years ago

You're welcome! I do change the design every few years. The earliest one on Wayback Machine is https://web.archive.org/web/19981202094104/http://theory.sta...

agersant• 12 years ago

Your page was a great source of knowledge and motivation for me when I was learning the ropes of game development (some ~12 years ago). Thanks for all the great work!

eliben2• 12 years ago

Loved your articles back in the day :-) The new animated diagrams are really cool. Can you describe in a few words how you create them?

amitp7• 12 years ago

Thanks! I use d3.js + SVG for most of the interactive ones. SVG makes it easy for me to attach mouse events to the elements in the diagram, and d3.js makes it easy for me to create, remove, and animate the elements individually. For the tower defense (breadth first search) page, I have three elements:

1. The graph (square grid for now but I'll make other types) — nodes and edges and edge weights 2. The search algorithm (breadth first search for now) — visited, open, costs, parent pointers. 3. The SVG visualization — a polygon for each node colored by its search state, and overlays for text or arrows

When the slider moves, I rewind or advance the search algorithm, which tells me which nodes have changed. I then update those nodes in the diagram. I considered running search once and recording a trace, but it turned out the performance bottleneck was the SVG, not the algorithm, so I didn't bother. It's fast enough to re-run at each step.

samstave• 12 years ago

How would you deal with an obstruction in the center of the U obstacle that occludes an alternate path through the U to the goal?

sesqu• 12 years ago

FWIW, I liked the colors, but totally misinterpreted them (I assumed the color represented a single value on a gradient, rather than two channels), and I almost missed the "next page" link at the bottom

I also thought it would be better to have the starting point inside the convex hull or the ending point higher behind it, so that the algorithm would look further than 1 square in the counter-heuristic directions. As it is, the heuristic was exactly correct about the length of the final path, it just happened to start searching to the right instead of starting straight down.

sgeisenh5• 12 years ago

The discussion of heuristics includes only information about admissibility and not consistency. An admissible but inconsistent heuristic can also cause A* to miss the correct solution.

amitp7• 12 years ago

There's not even much about admissibility (which is not always used in game settings). I don't have a good sense for consistency/monotonicity. Do you have an example of an inconsistent admissible heuristic?

psycovic234• 12 years ago

Take a look at this paper:

http://web.cs.du.edu/~sturtevant/papers/incnew.pdf

Specifically, look at the Martelli G family example.

sgeisenh5• 12 years ago

I'll do my best to provide an example. It is hard to come up with a general idea, but I can demonstrate using a graph: http://i.imgur.com/AwpTeRt.png

The numbers in the nodes represent heuristic values at each node and the numbers on edges represent edge weights; we're looking to get from S to T.

Our heuristic is admissible because it never overestimates the distance to the target.

Consistency dictates that the heuristic value at any node may at most be the weight of any out-edge added to the heuristic value of the node that the edge connects to. So in our example, the heuristic at A is 3, but at B it is 0, but 3 > 1 + 0, so our heuristic is inconsistent.

The reason this causes issues is because our algorithm assumes that any visited path is the shortest path to the end vertex of that path. So when we traverse this graph, we will visit B first, because the sum of its heuristic value and the respective edge weight is less than that of A.

psycovic234• 12 years ago

This isn't true. An admissible heuristic guarantees the optimal solution. With an inconsistent heuristic, A* can re-expand states multiple times, but will still end with an optimal path.

In other words, if the heuristic is consistent, then it implies that A* will expand the optimal number of states.

sgeisenh5• 12 years ago

If we operate under the assumption that each intermediate path found is shortest for its respective endpoint (which is the fundamental insight for Dijkstra's), we could potentially throw away the solution because it travels through the "visited set."

Edit: The paper you cited uses a traversal slightly different from traditional A*.

vowelless2• 12 years ago

If anyone is interested in robotics, definitely checkout D-star, which is pretty much a dynamic A-star with changing edge weights.

Dijkstra, A-star and D-star all share a similar structure.

film422• 12 years ago

Can D-star be used to model problems that have some form of random change, ex: While playing 2048, can you model the new random locations as an opponent making decisions (AI driven)?

icegreentea2• 12 years ago

You can apply probabilties to your edge weights.

Also, if you were considering D, consider looking at D-Lite. It's an alternate approach to the same problem, and more easily understood/implemented.

Schwolop• 12 years ago

In pathological scenarios where the edge weights change near the goal, rather than near the start of the search, D-star and all its backwards-incremental-graph-search variants can be slower than regular A-star. I would only recommend the use of D-star where a) that effect is unlikely or doesn't matter, or b) you can guarantee edge cost changes to occur only near the start of the search - such as a robot with a proprioceptive sensor, which is precisely what the algorithm was designed for.

psycovic234• 12 years ago

If you're interested in A* with humanoid robots, check out my post here:

http://victor.hwanger.com/a-technical-peek-into-motion-plann...

film422• 12 years ago

If you want some great notes on A* , my professor puts his slides online. He also included a video lecture on A* .

Lecture Slides: http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures...

Lecture Video: http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures...

There is a part 2 to this lecture called "The Optimality of A* ."

Lecture 2 Slides: http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures...

SilasX• 12 years ago

If the game world is changing often, planning ahead is less valuable.

This is actually a very general insight, and you can drop the "game" from it.

chavesn• 12 years ago

I always thought the Wikipedia progress animations illustrated the difference between A*[1] and Dijkstra's[2] nicely (and see some variations compared[3]).

[1] https://en.wikipedia.org/wiki/File:Astar_progress_animation....

[2] https://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstra...

[3] https://en.wikipedia.org/wiki/User:Subh83/CommonsContrib#Ani...

Lambdanaut• 12 years ago

People so often jump straight into A* pathfinding on a grid, but in my experience that makes the algorithm really opaque. It's been far easier for me to grasp when I was pathfinding over a simple, explicit graph instead.

That being said, great tutorial!

dragonwriter• 12 years ago

When I was learning A*, I found the fact that it was introduced on a grid helpful because the idea of the metric on the grid is very intuitive. But, different strokes, I guess.

tieTYT• 12 years ago

This article is "OK". I wish it was ordered differently. My complaint is it spends wayyy too much time on heuristics (2nd page) before it discusses the implementation (3rd page). I think it's important to get an overall idea of what the algorithm is before you focus on the minute details of a part of it. Plus, when it discusses the implementation, it doesn't spend enough time explaining it.

I found this video more helpful initially: https://www.youtube.com/watch?v=eTx6HQ9Veas

amitp7• 12 years ago

(author here) I agree! I'm planning to reorder everything; see https://twitter.com/redblobgames/status/410182845777195008/p... for my current plan. The choice of heuristic is near the end of the new flow.

Introduction to A*

Related Stories