8 ms·

Introduction to A*

298 points by ghosh 13y ago

gambiting 13y 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 13y 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 13y 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.
  - icegreentea 13y 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.
- psycovic23 13y ago
  Have any publications you could point me to?
- j_s 13y 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!
royjacobs 13y 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 13y 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/ 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 13y ago
  Thanks for sharing, this is perfect! I did the coursera IA, but this simulation is something really cool, I will share with them.
gabipurcaru 13y ago
Wasn't it called the Breadth-First Search algorithm (as opposed to the Depth First Search)? I never noticed this name before.
- ekr 13y 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 13y ago
    It's more like: breadth-first search is a specialization of Dijkstra's algorithm, which is a specialization of A*.
    - jmt7les 13y ago
      A* uses BFS but was a specialization of Dijkstra's, not the other way around.
      - Sharlin 13y ago
        No, Dijkstra is simply A* whose heuristic function is h(x)=0. A* is the more general one.
        amitp 13y ago
        Another way of looking at it: A* is Dijkstra where the edge weights have been modified. http://11011110.livejournal.com/135302.html http://11011110.livejournal.com/135302.html
    - sgeisenh 13y ago
      While breadth-first search and Dijkstra's have a lot in common, Dijkstra's is a priority first search which is inherently sequential, whereas there is some parallelism to be had in BFS since you can check the neighbors of your frontier concurrently given a data structure with which it is efficient to do so.
jrabone 13y ago
https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack 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 13y 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/ 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&t=24m24s https://www.youtube.com/watch?v=5Qyl7h7D1Q8&feature=youtu.be...
justinhj 13y ago
Here's another http://heyes-jones.com/astar.php 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 13y ago
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-5-search-optimal-branch-and-bound-a/ 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 13y 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 http://idm-lab.org/project-a.html
amitp 13y 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-pathfinding-pages.html 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/ 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 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.html 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/photo/1 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!
- agersant 13y 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!
- vowelless 13y 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!
  - amitp 13y 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.stanford.edu/~amitp/GameProgramming/ https://web.archive.org/web/19981202094104/http://theory.sta...
sgeisenh 13y 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.
- amitp 13y 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?
  - psycovic23 13y ago
    Take a look at this paper: http://web.cs.du.edu/~sturtevant/papers/incnew.pdf http://web.cs.du.edu/~sturtevant/papers/incnew.pdf Specifically, look at the Martelli G family example.
  - sgeisenh 13y 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 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.
    - amitp 13y ago
      Thanks!
- 13y ago
vowelless 13y 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.
- film42 13y 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)?
  - icegreentea 13y 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 13y 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.
- psycovic23 13y ago
  If you're interested in A* with humanoid robots, check out my post here: http://victor.hwanger.com/a-technical-peek-into-motion-planning-for-humanoid-robots/ http://victor.hwanger.com/a-technical-peek-into-motion-plann...
film42 13y 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/Lecture36-astar-heuristics.pdf http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures... Lecture Video: http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures/Lecture36-astar-heuristics/Lecture36-astar-heuristics.html 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/Lecture37-astar2.pdf http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures...
SilasX 13y 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.
primaryobjects 13y ago
I wrote a little javascript demo that shows A* Search in action, solving a maze. http://goo.gl/PsO3PN http://goo.gl/PsO3PN If you really want to hack, you can make your own using the REST API (click 'Build a Maze').
chavesn 13y 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.gif https://en.wikipedia.org/wiki/File:Astar_progress_animation.... [2]: https://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstras_progress_animation.gif https://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstra... [3]: https://en.wikipedia.org/wiki/User:Subh83/CommonsContrib#Animated_GIFs_illustrating_Dijkstra.27s.2C_A.2A_and_weighted_A.2A_search_algorithms https://en.wikipedia.org/wiki/User:Subh83/CommonsContrib#Ani...
Lambdanaut 13y 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 13y 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 13y 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 https://www.youtube.com/watch?v=eTx6HQ9Veas
- amitp 13y ago
  (author here) I agree! I'm planning to reorder everything; see https://twitter.com/redblobgames/status/410182845777195008/photo/1 https://twitter.com/redblobgames/status/410182845777195008/p... for my current plan. The choice of heuristic is near the end of the new flow.

298 points by ghosh 13y 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 13y 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 13y 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.
- icegreentea 13y 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.
psycovic23 13y ago
Have any publications you could point me to?
j_s 13y 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!

royjacobs 13y 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 13y 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/ 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 13y ago
Thanks for sharing, this is perfect! I did the coursera IA, but this simulation is something really cool, I will share with them.

gabipurcaru 13y ago

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

ekr 13y 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 13y ago
  It's more like: breadth-first search is a specialization of Dijkstra's algorithm, which is a specialization of A*.
  - jmt7les 13y ago
    A* uses BFS but was a specialization of Dijkstra's, not the other way around.
    - Sharlin 13y ago
      No, Dijkstra is simply A* whose heuristic function is h(x)=0. A* is the more general one.
      - amitp 13y ago
        Another way of looking at it: A* is Dijkstra where the edge weights have been modified. http://11011110.livejournal.com/135302.html http://11011110.livejournal.com/135302.html
  - sgeisenh 13y ago
    While breadth-first search and Dijkstra's have a lot in common, Dijkstra's is a priority first search which is inherently sequential, whereas there is some parallelism to be had in BFS since you can check the neighbors of your frontier concurrently given a data structure with which it is efficient to do so.

jrabone 13y ago

https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack 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 13y 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/ 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&t=24m24s https://www.youtube.com/watch?v=5Qyl7h7D1Q8&feature=youtu.be...

justinhj 13y ago

Here's another http://heyes-jones.com/astar.php 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 13y ago

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-5-search-optimal-branch-and-bound-a/ 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 13y 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 http://idm-lab.org/project-a.html

amitp 13y 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-pathfinding-pages.html 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/ 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 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.html 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/photo/1 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!

agersant 13y 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!
vowelless 13y 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!
- amitp 13y 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.stanford.edu/~amitp/GameProgramming/ https://web.archive.org/web/19981202094104/http://theory.sta...

sgeisenh 13y 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.

amitp 13y 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?
- psycovic23 13y ago
  Take a look at this paper: http://web.cs.du.edu/~sturtevant/papers/incnew.pdf http://web.cs.du.edu/~sturtevant/papers/incnew.pdf Specifically, look at the Martelli G family example.
- sgeisenh 13y 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 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.
  - amitp 13y ago
    Thanks!
13y ago

vowelless 13y 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.

film42 13y 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)?
- icegreentea 13y 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 13y 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.
psycovic23 13y ago
If you're interested in A* with humanoid robots, check out my post here: http://victor.hwanger.com/a-technical-peek-into-motion-planning-for-humanoid-robots/ http://victor.hwanger.com/a-technical-peek-into-motion-plann...

film42 13y 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/Lecture36-astar-heuristics.pdf http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures... Lecture Video: http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures/Lecture36-astar-heuristics/Lecture36-astar-heuristics.html 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/Lecture37-astar2.pdf http://faculty.cs.byu.edu/~ringger/Winter2014-CS312/lectures...

SilasX 13y 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.

primaryobjects 13y ago

I wrote a little javascript demo that shows A* Search in action, solving a maze. http://goo.gl/PsO3PN http://goo.gl/PsO3PN If you really want to hack, you can make your own using the REST API (click 'Build a Maze').

chavesn 13y 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.gif https://en.wikipedia.org/wiki/File:Astar_progress_animation.... [2]: https://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstras_progress_animation.gif https://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstra... [3]: https://en.wikipedia.org/wiki/User:Subh83/CommonsContrib#Animated_GIFs_illustrating_Dijkstra.27s.2C_A.2A_and_weighted_A.2A_search_algorithms https://en.wikipedia.org/wiki/User:Subh83/CommonsContrib#Ani...

Lambdanaut 13y 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 13y 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 13y 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 https://www.youtube.com/watch?v=eTx6HQ9Veas

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