Introduction to A*

http://www.redblobgames.com/pathfinding/a-star/introduction.html

by phenylene • 12 years ago

509 28 12 years ago

dj-wonk2• 12 years ago

Excellent! One suggestion. The article mentions "inadmissible heuristic" but does not talk about what that means.

Per https://en.wikipedia.org/wiki/Admissible_heuristic, "In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.[1] An admissible heuristic is also known as an optimistic heuristic."

dj-wonk2• 12 years ago

Again, a great article, but I feel like some of the general thinking behind heuristics is getting lost. Heuristics can be significantly more interesting than distance between two points. This isn't a huge criticism. In this context -- pathfinding on a grid -- complicated heuristics may not be needed.

When I first read about A* a long time ago I remember, for example, reading about how static summaries of chess board positions may be useful heuristics. Developing pieces towards the center of the board is often better, for example. To me, seeing this was an "ah ha" moment for heuristics: use them if they are cheap and (sometimes) informative, relative to the search cost.

gamegoblin• 12 years ago

I once wrote an A* algorithm to solve a 15-puzzle (the thing with 15 sliding tiles and 1 empty space, often depicting a picture, or just the numbers).

An easy heuristic that vastly improves the search: the sum of the manhattan distances of the pieces' current locations to their final positions.

So, as you said, rather than thinking about distance only in a Euclidean space, A* heuristics are much more general -- any metric that measures "done-ness".

wlievens• 12 years ago

For an AI course we had to write a solver for a puzzle using a heuristic. We had a reference solution step count to aim towards. After many hours of tweaking I still could not solve it. I had writ and rewritten quite complicated heuristics but to no avail, until at one point I stumbled on a nearly optimal solution. Upon reading my code again I noticed that a stray parenthes and a forgivinv lisp parser had caused most of my heuristic's code to be ignored. The simplest thing Just Worked :-)

psycovic23• 12 years ago

This is a very interesting area of research. The state of the art in motion planning for robotics actually uses multiple heuristics at once with A*.

http://www.roboticsproceedings.org/rss10/p56.pdf

jonalmeida• 12 years ago

The visualizations are incredibly key to helping understand. It would have been much harder for me to understand what was going on without it.

Well done!

gavanwoolery2• 12 years ago

Excellent article - I recently worked on some pathfinding stuff and the material I found on A* was not that great but this is very well laid out.

Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal paths in exchange for greater speed and less memory usage - even ones that are faster than greedy-best-first search with A* shown here.

If you use recursive backtracking with a decent set of heuristics (i.e. choose the node with the closest distance to the goal, "as the crow flies"), it can be be fast and ideal in many situations (it will always give an ideal path when there are few hook or concave shapes to deal with, which in many games or applications is often the case). It can be done in linear time and memory - it is important to note the cost of adding and searching nodes in the algorithm as well. It will never "fail" but it will produce very bad paths sometimes in complex situations, although even then it occasionally produces ideal paths. In many situations where having an ideal path is not critical (say, townspeople just walking about doing their business) this can work well. Of course, you can use multiple algorithms or even mix them depending on what you are trying to achieve. RBT can be a good starting point just because it is so easy (maybe the easiest fail-safe algorithm outside of brute force?).

Secondary note: it is also good to subdivide your space - it does not need to be something complex like a sparse octree (in fact, that will make it harder to write and get good performance with in many situations). Rather consider something like two levels of nodes. On a 2D map, say you were to divide it into subsets of NxN grids of nodes. Each one of these node grids attaches to its neighbor based on whether or not it is traversable in that direction (i.e. no matter where you enter the node grid, there is a path out in that direction). This allows you to easily find a "high level" path which can be rapidly changed or discarded based on changing circumstances.

cclogg• 12 years ago

Last spring I went through a lot of different techniques including the one you mention about subdivision. Was working on tower defense path-finding so basically the challenge was to compute every waypoint-set's path at game-start and whenever a tower is built/sold.

I think I basically tried almost every A* trick available (rectangular symmetry reduction, HPA*, points of visibility, jump point search, etc) but ultimately I couldn't make it run fast enough on iOS for our max level size which was about 100x100. It also couldn't be multi-threaded because it needed to work with online code (synchronous tick engine)...

What ended up happening was I found a full C implementation of Jump Point Search, and it was incredibly fast! I had already moved several parts of my code to C in order to speed it up, but I guess using a higher level language like Objective-C is just way too slow to have instantaneous path-finding on a 100x100 grid. I think this was the code I found https://github.com/Bio2hazard/cJumpPointSearch

coldtea• 12 years ago

but ultimately I couldn't make it run fast enough on iOS for our max level size which was about 100x100.

100x100? That sounds trivial to make fast enough. What was the programming language used?

aeberbach• 12 years ago

You definitely had a bug. I shipped a single-threaded A* for 3GS and up with maps created from maps of approximately 500x500 locations.

It started out completely broken, storing waypoints in Core Data and was taking upwards of four minutes to calculate a path. Switching to prefetching Core Data paths brought it down to about 90 seconds, but that's as far as it could go with so many Core Data faults firing.

What made it really fly was the change the underlying data to direct bitmap access on maps prepared from the source maps (shopping centre levels actually) and applying simple filters to generate monochrome maps where one color was walkable and another not. Then source and destination locations were obtained through the original Core Data coordinates and a quick search algorithm found the closest walkable point to both. The A* calculation took perhaps a second or two.

Not content with that we went further and drew more complicated maps with what amounted to train tracks, a network of walkable paths one pixel wide connecting every store to every store to narrow down the solution space. The result was instant A* pathfinding and it was a very neat feature in the app.

You can definitely do A* in Objective C - just get to know Instruments inside out and keep tuning. On a 5S I expect you could get away with a lot of inefficiency.

vanderZwan• 12 years ago

Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal paths in exchange for greater speed and less memory usage - even ones that are faster than greedy-best-first search with A shown here.*

Another example is when you are dealing with large crowds. Vector fields tend to shine there. A simple example is using a vector field when dealing with a large swarm with one goal:

http://gamedevelopment.tutsplus.com/tutorials/understanding-...

Something more slightly more advanced yet incredibly powerful would be "continuum crowds", where the agents in the swarm are also obstacles for each other, affecting the vector field:

https://www.youtube.com/watch?v=lGOvYyJ6r1c

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

The intriguing part here is that these potential field can have any source - so it's relatively easy to get complex behaviour, such as pedestrians avoiding cars, or prey/predator behaviour.

Again, these are more relavant with large crowds, so as stated before: the best approach all depends on the particular use-case.

amitp2• 12 years ago

A* is typically for single source, single destination. For crowds, if you have lots of agents that want to go to a single destination, you can often use Breadth First Search or Dijkstra's Algorithm. That tutsplus article uses Breadth First Search.

The crowd flow research is neat. The videos are especially fun to watch. http://gamma.cs.unc.edu/research/crowds/ is another nice set of papers.

gavanwoolery2• 12 years ago

That is an interesting example with the fluid pathfinder - had not considered a fluid solver for that application but it seems to work really well - even perhaps mimicking nature. If you look at a large flock of Starlings their movement is almost fluid-like: http://www.youtube.com/watch?v=XH-groCeKbE

lenocinor3• 12 years ago

Yeah, vector fields are great for big crowds. Hitman: Absolution, which has one of the best implementations I've seen for crowds, uses them: http://twvideo01.ubm-us.net/o1/vault/gdc2012/slides/Programm...

lenocinor3• 12 years ago

From the article:

"A* is a good choice for most pathfinding needs."

I teach A* in my game AI class, and after having examined dozens of real-world game implementations of pathfinding, this is exactly right. While it's true that you shouldn't ALWAYS use A* , most games use A* in most situations, because actually greedy approaches like you are discussing do poorly surprisingly often. My recommendation is to start with A* and only use simpler methods if it isn't giving you the performance you need.

For your subdivision comment, the general approach is generally called hierarchical pathfinding. There are lots of ways you can do this, but I like HPA* : http://aigamedev.com/open/review/near-optimal-hierarchical-p... Your comment about two levels is good, because while hierarchical pathfinding can use any number of levels, I've never seen more than two in practice in games.

xer0x• 12 years ago

The author, Amit Patel, makes awesome stuff! His writeup on hexagon grids is excellent also. Plus for some retro gaming Solar Realms Elite is one of the finest BBS door games of it's time.

sgustard• 12 years ago

An earlier version of this article by Amit was posted to HN a few months ago:

http://theory.stanford.edu/~amitp/GameProgramming/AStarCompa...

scott_karana• 12 years ago

Thanks; I thought it looked familiar, and didn't want to bookmark the same page twice. :)

raymondh3• 12 years ago

Programming nit: The posted code should use collections.deque() rather than Queue.Queue(). The former is a high-speed C-coded datatype that is ideal for a search queue. The latter is a pure Python wrapper that adds thread synchronization around an underlying collections.deque() object. The wrapper overhead is only worth it if you're actually using multiple threads that share the same queue.

raymondh3• 12 years ago

In the author's separate page of implementation notes, a Queue class is created that doesn't have threading overhead. That would be great, but it uses list.pop(0) which is an O(n) operation. For O(1) performance, it should use collections.deque.popleft() instead.

Otherwise, the article is first-rate :-)

amitp2• 12 years ago

Ah, thanks! I've been focusing on simplicity rather than performance, but deque is just as simple here, so I should use it. :-)

sjwright• 12 years ago

It's not immediately obvious, but all the diagrams on that page are actually live and interactive demonstrations. You can move the entities, and you can reshape the walls as much as you like.

beefsack• 12 years ago

For those who haven't implemented A* before it can be quite an enlightening experience, and actually isn't too difficult once you dive in. It's a good introduction to priority queues too if you haven't played with them before.

I threw together an implentation of A* as a library in Go [1] for a game I've been doing, it has automated tests which mock up a game world and check the length of paths with visual output.

[1] https://github.com/beefsack/go-astar

lenocinor3• 12 years ago

Great article. This is the first A* article I've seen online that has good visualization. I teach this in my game AI class and the visualization is key to understanding.

MagerValp• 12 years ago

Since Amit's apparently here reading, great job on updating your A* introduction (which was already excellent!), I really like how you break it down piece by piece. While it's a very simple algorithm at its core, there are some really subtle nuances that are easy to miss when you first approach it, e.g. the difference between a search node and a map coordinate (assuming classic 2D game maps).

I had some fun earlier this year implementing A* in 6502 assembler, starting with Python and working my way down through Objective-C and C before finally hand-optimizing the critical paths in asm. Articles are here for those who enjoy that kind of thing:

http://magervalp.github.io/2014/05/02/priority-queue-in-asm.... http://magervalp.github.io/2014/05/07/astar-in-asm.html

The code is available on github too: https://github.com/MagerValp/AsmAstar

eric_bullington• 12 years ago

I had some fun earlier this year implementing A* in 6502 assembler, starting with Python and working my way down through Objective-C and C before finally hand-optimizing the critical paths in asm.

Oh, that's a really great idea. I'm going to do that with a few interesting algorithms now, starting with Python and working down via Rust and maybe C to assembly.

I'm actually doing a take on that with several network clients (Stomp and mqtt) at the present, starting with Python and then moving to Rust.

But I'm really interested now in embedded programming so I should pick a challenging algo and work all the way down to assembly to run on bare metal. Algorithms are nice for this type of exercise since they typically have limited IO.

Great idea, thanks!

kenshiro_o• 12 years ago

Awesome article! The diagrams made it extremely easy for me to recall how A* worked. I now vividly remember graph traversal theory classes an exercises from University time!

I guess the implementation effort greatly varies depending on the programming language and the libraries at one's disposal. However, I believe that even for someone not too versed into data structures, the priority queue should be relatively easy to implement.

Introduction to A*

Related Stories