This link has been bookmarked by 205 people . It was first bookmarked on 02 Mar 2006, by someone privately.
-
21 Sep 16
-
08 Jul 16
-
23 May 16
-
03 Jan 16
-
09 Mar 15
-
10 Aug 14
-
A* Pathfinding for Beginners
-
-
07 Jul 14
-
26 Jun 14
-
02 Jun 14
-
26 Apr 14
-
11 Apr 14
-
Let’s assume that we have someone who wants to get from point A to point B. Let’s assume that a wall separates the two points. This is illustrated below, with green being the starting point A, and red being the ending point B, and the blue filled squares being the wall in between.
-
The path is found by figuring out which squares we should take to get from A to B
-
Once the path is found, our person moves from the center of one square to the center of the next until the target is reached.
-
-
26 Mar 14
-
save point A as its “parent square”.
-
adjacent squares on the open list
-
The one with the lowest F cost.
-
G is the movement cost to move from the starting point to the given square using the path generated to get there. In this example, we will assign a cost of 10 to each horizontal or vertical square moved, and a cost of 14 for a diagonal move.
-
The method we use here is called the Manhattan method
-
Since we are calculating the G cost along a specific path to a given square, the way to figure out the G cost of that square is to take the G cost of its parent, and then add 10 or 14 depending on whether it is diagonal or orthogonal (non-diagonal) from that parent square.
-
squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement, and ignoring any obstacles that may be in the way.
-
The closer our estimate is to the actual remaining distance, the faster the algorithm will be.
-
check to see if this path to that square is a better one.
-
add squares to the open list if they are not on the open list already. Make the selected square the “parent” of the new squares.
-
G score for that square is lower if we use the current square to get there.
-
change the parent of the adjacent square to the selected square (in the diagram above, change the direction of the pointer to point at the selected square).
-
So we go through the list of squares on our open list,
-
For the purposes of speed, it can be faster to choose the last one you added to the open list.
-
So let’s choose the one just below, and to the right of the starting square, as is shown in the following illustration.
-
If we instead went through the current square to get there, the G score would be equal to 20 (10, which is the G score to get to the current square, plus 10 more to go vertically to the one just above it).
-
This biases the search in favor of squares that get found later on in the search
-
You really need to go down first and then move over to that square, moving around the corner in the process.
-
We also ignore the square just below the wall.
-
We repeat this process until we add the target square to the closed list, at which point it looks something like the illustration below.
-
two are already on the closed list
-
And the last square, to the immediate left of the current square, is checked to see if the G score is any lower if you go through the current square to get there.
-
and work backwards moving from one square to its parent, following the arrows.
-
Note that the parent square for the square two squares below the starting square has changed from the previous illustration.
-
where the G score was checked and it turned out to be lower using a new path
-
just start at the red target square
-
it was suggested that you can stop when the target square (or node) has been added to the open list, rather than the closed list.
-
While A* is generally considered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0).
-
-
10 Jan 14
-
25 Nov 13
-
24 Nov 13
-
15 Oct 13
-
14 Aug 13
-
The Search Area
-
center points are called “nodes”.
-
search to find the shortest path.
-
Begin at the starting point A and add it to an “open list” of squares to be considered.
-
Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain.
-
save point A as its “parent square”.
-
add it to a “closed list”
-
Drop the starting square A from your open list,
-
e lowest F cost
-
F = G + H
-
G = the movement cost to move
-
H = the estimated movement cost to move
-
repeatedly going through our open list and choosing the square with the lowest F score.
-
assign a cost of 10 to each horizontal or vertical square moved, and a cost of 14 for a diagonal move.
-
G is the movement cost to move from the starting point to the given square using the path generated to get there
-
H can be estimated in a variety of ways. The method we use here is called the Manhattan method
-
The closer our estimate is to the actual remaining distance, the faster the algorithm will be.
-
F is calculated by adding G and H.
-
we simply choose the lowest F score square
-
the one with the lowest F cost is the one to the immediate right of the starting square
-
First, we drop it from our open list
-
-
10 Jun 13
-
05 Jun 13
-
onsidered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstra's usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.
So why use it? Sometimes we don't know where our target destination is. Say you have a resource-gathering unit that needs to go get some resources of some kind. It may know where several resource areas are, but it wants to go to the closest one. Here, Dijkstra's is better than A* because we don't know which one is closest. Our only alternative is to repeatedly use A* to find the distance to each one, and then choose that path. There are probably countless similar situations where we know the kind of location we might be searching for, want to find the closest one, but not know where it is or which one might be closest.
-
-
14 May 13
-
27 Mar 13
-
14 Mar 13
-
05 Feb 13
-
30 Jan 13
-
03 Dec 12
-
the Manhattan method is inadmissible because it slightly overestimates the remaining distance
-
-
13 Sep 12
-
If it is not walkable or if it is on the closed list, ignore i
-
-
03 Aug 12
-
01 May 12
-
The first thing you should notice is that we have divided our search area into a square grid. Simplifying the search area, as we have done here, is the first step in pathfinding. This particular method reduces our search area to a simple two dimensional array. Each item in the array represents one of the squares on the grid, and its status is recorded as walkable or unwalkable. The path is found by figuring out which squares we should take to get from A to B. Once the path is found, our person moves from the center of one square to the center of the next until the target is reached.
These center points are called “nodes”. When you read about pathfinding elsewhere, you will often see people discussing nodes. Why not just call them squares? Because it is possible to divide up your pathfinding area into something other than squares. They could be rectangles, hexagons, triangles, or any shape, really. And the nodes could be placed anywhere within the shapes – in the center or along the edges, or anywhere else. We are using this system, however, because it is the simplest.
-
-
15 Apr 12
-
19 Mar 12
Nathan Craig"are calculating the G cost "
-
13 Mar 12
-
20 Dec 11
-
23 Oct 11
-
30 Sep 11
-
27 Sep 11
-
22 Sep 11
-
09 Sep 11
-
25 Jul 11
-
18 Jul 11
-
16 Jul 11
-
02 May 11
Harlan HoweA detailed description of an algorithm for finding paths in a map.
-
27 Apr 11
-
11 Apr 11
-
H = the estimated movement cost to move from that given square on the grid to the final destination, point B.
-
G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there
-
H = the estimated movement cost to move from that given square on the grid to the final destination, point B.
-
Manhattan method, where you calculate the total number of squares moved horizontally and vertically to reach the target square from the current square,
-
ignoring diagonal movement, and ignoring any obstacles that may be in the way.
-
inadmissible heuristic
-
F is calculated by adding G and H.
-
F, G, and H scores are written in each square
-
F is printed in the top lef
-
G is printed in the bottom left
-
H is printed in the bottom right
-
f an adjacent square is already on the open list, check to see if this path to that square is a better one.
-
check to see if the G score for that square is lower if we use the current square to get there.
-
-
10 Apr 11
-
22 Mar 11
-
09 Mar 11
-
02 Mar 11
-
09 Feb 11
-
08 Feb 11
-
01 Feb 11
-
The first thing you should notice is that we have divided our search area into a square grid
-
walkable or unwalkable
-
Once the path is found, our person moves from the center of one square to the center of the next until the target is reached
-
“nodes”
-
center points
-
conduct a search to find the shortest path
-
Begin at the starting point A and add it to an “open list” of squares to be considered.
-
Look at all the reachable or walkable squares
-
ignoring squares with walls, water, or other illegal terrain
-
ave point A as its “parent square
-
Add them to the open list
-
djacent to the starting poin
-
his parent square stuff is important when we want to trace our path
-
Drop the starting square A from your open list, and add it to a “closed list” of square
-
we choose one of the adjacent square
-
hich square do we choose
-
one with the lowest F cost
-
Our path is generated by repeatedly going through our open list and choosing the square with the lowest F score
-
we will assign a cost of 10 to each horizontal or vertical square moved, and a cost of 14 for a diagonal move
-
way to figure out the G cost of that square is to take the G cost of its parent, and then add 10 or 14 depend
-
H can be estimated in a variety of ways. The method we use here is called the Manhattan method
-
F is calculated by adding G and H
-
simply choose the lowest F score
-
Drop it from the open list and add it to the closed list.
-
If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything.
-
if the G cost of the new path is lower, change the parent of the adjacent square to the selected square
-
drop it from our open list and add it to our closed list (that’s why it’s now highlighted in blue)
-
ote that the parent square for the square two squares below the starting square has changed from the previous illustration
-
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure
-
Non-square Search Areas
-
Some Speed Tips
-
Consider using larger squares (or whatever shape you are using) for your map. This reduces the total number of nodes searched to find the path. If you are ambitious, you can devise two or more pathfinding systems that are used in different situations, depending upon the length of the path. This is what the professionals do, using large areas for long paths, and then switching to finer searches using smaller squares/areas when you get close to the target.
-
This can be improved by maintaining a sorted list and simply grabbing the first item off the list every time you need the lowest F-cost square.
-
Serious A* programmers who want real speed use something called a binary heap
-
I also store values like F, G and H costs in arrays.
-
-
21 Jan 11
-
02 Jan 11
-
01 Jan 11
-
29 Oct 10
-
21 Oct 10
-
21 Aug 10
-
12 Jul 10
-
20 Mar 10
-
13 Mar 10
-
06 Mar 10
-
11 Feb 10
-
05 Feb 10
-
27 Dec 09
-
17 Nov 09
-
14 Nov 09
-
07 Sep 09
-
03 Sep 09
-
24 Jul 09
-
14 Jun 09
-
27 May 09
-
09 May 09
-
05 May 09
-
27 Apr 09
-
25 Apr 09
-
06 Apr 09
-
20 Mar 09
-
08 Mar 09
-
18 Jan 09
-
27 Dec 08
-
21 Dec 08
-
01 Dec 08
-
30 Aug 08
-
27 Aug 08
-
20 Jun 08
-
This article has been translated from English into Albanian, Chinese, French, German, Greek, Polish, Portuguese, Russian, and Spanish. Other translations are welcome. See email address at the bottom of this article.
The A* (pronounced A-star) algorithm can be complicated for beginners. While there are many articles on the web that explain A*, most are written for people who understand the basics already. This article is for the true beginner.
This article does not try to be the definitive work on the subject. Instead it describes the fundamentals and prepares you to go out and read all of those other materials and understand what they are talking about. Links to some of the best are provided at the end of this article, under Further Reading.
Finally, this article is not program-specific. You should be able to adapt what's here to any computer language. As you might expect, however, I have included a link to a sample program at the end of this article. The sample package contains two versions: one in C++ and one in Blitz Basic. It also contains executables if you just want to see A* in action.
But we are getting ahead of ourselves. Let's start at the beginning ...
-
-
17 Jun 08
-
12 May 08
-
02 Apr 08
-
18 Mar 08
-
04 Mar 08
-
31 Jan 08
-
21 May 07
-
14 May 07
Lynn MarentetteGreat resource for learning how to do beginning pathfinding for games.
AI A Star A* pathfinding policyalmanac games astar tutorial Delicious
-
27 Mar 07
-
08 Feb 07
-
26 Jan 07
-
18 Jan 07
-
14 Jan 07
Page Comments
Would you like to comment?
Join Diigo for a free account, or sign in if you are already a member.