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!
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!
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!
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.
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:
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++
I always thought the Wikipedia progress animations illustrated the difference between A*[1] and Dijkstra's[2] nicely (and see some variations compared[3]).
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.
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.
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.
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!
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.
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:
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.
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.
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.
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.
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?
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)?
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.
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. :-) ]
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.
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.
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.
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.
[+] [-] amitp|12 years ago|reply
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!
[+] [-] vowelless|12 years ago|reply
[+] [-] agersant|12 years ago|reply
[+] [-] eliben|12 years ago|reply
[+] [-] sesqu|12 years ago|reply
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.
[+] [-] samstave|12 years ago|reply
[+] [-] vanderZwan|12 years ago|reply
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...
[+] [-] danso|12 years ago|reply
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|reply
[+] [-] jrabone|12 years ago|reply
[+] [-] chavesn|12 years ago|reply
[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...
[+] [-] gambiting|12 years ago|reply
[+] [-] fddlr|12 years ago|reply
[+] [-] Qworg|12 years ago|reply
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.
[+] [-] j_s|12 years ago|reply
[+] [-] psycovic23|12 years ago|reply
[+] [-] justinhj|12 years ago|reply
[+] [-] Rizz|12 years ago|reply
http://idm-lab.org/project-a.html
[+] [-] SilasX|12 years ago|reply
This is actually a very general insight, and you can drop the "game" from it.
[+] [-] tieTYT|12 years ago|reply
I found this video more helpful initially: https://www.youtube.com/watch?v=eTx6HQ9Veas
[+] [-] amitp|12 years ago|reply
[+] [-] royjacobs|12 years ago|reply
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.
[+] [-] FLUX-YOU|12 years ago|reply
AI course which goes into the details leading up to the A* algorithm (45 minutes)
[+] [-] film42|12 years ago|reply
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...
[+] [-] sgeisenh|12 years ago|reply
[+] [-] psycovic23|12 years ago|reply
In other words, if the heuristic is consistent, then it implies that A* will expand the optimal number of states.
[+] [-] amitp|12 years ago|reply
[+] [-] vowelless|12 years ago|reply
Dijkstra, A-star and D-star all share a similar structure.
[+] [-] psycovic23|12 years ago|reply
http://victor.hwanger.com/a-technical-peek-into-motion-plann...
[+] [-] film42|12 years ago|reply
[+] [-] gabipurcaru|12 years ago|reply
[+] [-] ralfn|12 years ago|reply
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.
[+] [-] glenra|12 years ago|reply
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. :-) ]
[+] [-] navait|12 years ago|reply
[+] [-] ekr|12 years ago|reply
[+] [-] Lambdanaut|12 years ago|reply
That being said, great tutorial!
[+] [-] dragonwriter|12 years ago|reply
[+] [-] primaryobjects|12 years ago|reply
[deleted]