分享--- A*演算法
by smf12312, 2011-08-22 21:27:21, Views(1369)


A* Pathfinding for Beginners

By Patrick Lester (Updated July 18, 2005)

This article has been translated into Albanian, Chinese, French, German, Portuguese, Russian, Serbian, 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 ...

Introduction: The Search Area

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.

[Figure 1]

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.

Starting the Search

Once we have simplified our search area into a manageable number of nodes, as we have done with the grid layout above, the next step is to conduct a search to find the shortest path. We do this by starting at point A, checking the adjacent squares, and generally searching outward until we find our target. 

We begin the search by doing the following:

  1. Begin at the starting point A and add it to an “open list” of squares to be considered. The open list is kind of like a shopping list. Right now there is just one item on the list, but we will have more later. It contains squares that might fall along the path you want to take, but maybe not. Basically, this is a list of squares that need to be checked out.  
  2. Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too. For each of these squares, save point A as its “parent square”. This parent square stuff is important when we want to trace our path. It will be explained more later.  
  3. Drop the starting square A from your open list, and add it to a “closed list” of squares that you don’t need to look at again for now.
At this point, you should have something like the following illustration. In this illustration, the dark green square in the center is your starting square. It is outlined in light blue to indicate that the square has been added to the closed list. All of the adjacent squares are now on the open list of squares to be checked, and they are outlined in light green. Each has a gray pointer that points back to its parent, which is the starting square. 

  [Figure 2]

Next, we choose one of the adjacent squares on the open list and more or less repeat the earlier process, as described below. But which square do we choose? The one with the lowest F cost.

Path Scoring

The key to determining which squares to use when figuring out the path is the following equation:

F = G + H 


  • 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. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don’t know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.). You are given one way to calculate H in this tutorial, but there are many others that you can find in other articles on the web.

Our path is generated by repeatedly going through our open list and choosing the square with the lowest F score. This process will be described in more detail a bit further in the article. First let’s look more closely at how we calculate the equation.

As described above, 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. We use these numbers because the actual distance to move diagonally is the square root of 2 (don’t be scared), or roughly 1.414 times the cost of moving horizontally or vertically. We use 10 and 14 for simplicity’s sake. The ratio is about right, and we avoid having to calculate square roots and we avoid decimals. This isn’t just because we are dumb and don’t like math. Using whole numbers like these is a lot faster for the computer, too. As you will soon find out, pathfinding can be very slow if you don’t use short cuts like these. 

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. The need for this method will become apparent a little further on in this example, as we get more than one square away from the starting square.

H can be estimated in a variety of ways. The method we use here is called the 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. We then multiply the total by 10, our cost for moving one square horizontally or vertically. This is (probably) called the Manhattan method because it is like calculating the number of city blocks from one place to another, where you can’t cut across the block diagonally.

Reading this description, you might guess that the heuristic is merely a rough estimate of the remaining distance between the current square and the target "as the crow flies." This isn't the case. We are actually trying to estimate the remaining distance along the path (which is usually farther). The closer our estimate is to the actual remaining distance, the faster the algorithm will be. If we overestimate this distance, however, it is not guaranteed to give us the shortest path. In such cases, we have what is called an "inadmissible heuristic."

Technically, in this example, the Manhattan method is inadmissible because it slightly overestimates the remaining distance. But we will use it anyway because it is a lot easier to understand for our purposes, and because it is only a slight overestimation. On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short. Want to know more? You can find equations and additional notes on heuristics here.

F is calculated by adding G and H. The results of the first step in our search can be seen in the illustration below. The F, G, and H scores are written in each square. As is indicated in the square to the immediate right of the starting square, F is printed in the top left, G is printed in the bottom left, and H is printed in the bottom right.

  [Figure 3] 

So let’s look at some of these squares. In the square with the letters in it, G = 10. This is because it is just one square from the starting square in a horizontal direction. The squares immediately above, below, and to the left of the starting square all have the same G score of 10. The diagonal squares have G scores of 14. 

The H scores are calculated by estimating the Manhattan distance to the red target square, moving only horizontally and vertically and ignoring the wall that is in the way. Using this method, the square to the immediate right of the start is 3 squares from the red square, for a H score of 30. The square just above this square is 4 squares away (remember, only move horizontally and vertically) for an H score of 40. You can probably see how the H scores are calculated for the other squares. 

The F score for each square, again, is simply calculated by adding G and H together.

Continuing the Search

To continue the search, we simply choose the lowest F score square from all those that are on the open list. We then do the following with the selected square:

4) Drop it from the open list and add it to the closed list.

5) Check all of the adjacent squares. Ignoring those that are on the closed list or unwalkable (terrain with walls, water, or other illegal terrain), 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.

6) 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. 
    On the other hand, if the G cost of the new path is lower, 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). Finally, recalculate both the F and G scores of that square. If this seems confusing, you will see it illustrated below.

Okay, so let’s see how this works. Of our initial 9 squares, we have 8 left on the open list after the starting square was switched to the closed list.  Of these, the one with the lowest F cost is the one to the immediate right of the starting square, with an F score of 40. So we select this square as our next square. It is highlight in blue in the following illustration.

[Figure 4] 

First, we drop it from our open list and add it to our closed list (that’s why it’s now highlighted in blue).  Then we check the adjacent squares. Well, the ones to the immediate right of this square are wall squares, so we ignore those. The one to the immediate left is the starting square. That’s on the closed list, so we ignore that, too. 

The other four squares are already on the open list, so we need to check if the paths to those squares are any better using this square to get there, using G scores as our point of reference. Let’s look at the square right above our selected square. Its current G score is 14. 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). A G score of 20 is higher than 14, so this is not a better path. That should make sense if you look at the diagram. It’s more direct to get to that square from the starting square by simply moving one square diagonally to get there, rather than moving horizontally one square, and then vertically one square. 

When we repeat this process for all 4 of the adjacent squares already on the open list, we find that none of the paths are improved by going through the current square, so we don’t change anything. So now that we looked at all of the adjacent squares, we are done with this square, and ready to move to the next square. 

So we go through the list of squares on our open list, which is now down to 7 squares, and we pick the one with the lowest F cost. Interestingly, in this case, there are two squares with a score of 54. So which do we choose? It doesn’t really matter. For the purposes of speed, it can be faster to choose the last one you added to the open list. This biases the search in favor of squares that get found later on in the search, when you have gotten closer to the target. But it doesn’t really matter. (Differing treatment of ties is why two versions of A* may find different paths of equal length.)

So let’s choose the one just below, and to the right of the starting square, as is shown in the following illustration.

[Figure 5] 

This time, when we check the adjacent squares we find that the one to the immediate right is a wall square, so we ignore that. The same goes for the one just above that. We also ignore the square just below the wall. Why? Because you can’t get to that square directly from the current square without cutting across the corner of the nearby wall. You really need to go down first and then move over to that square, moving around the corner in the process. (Note: This rule on cutting corners is optional. Its use depends on how your nodes are placed.)

That leaves five other squares.  The other two squares below the current square aren’t already on the open list, so we add them and the current square becomes their parent. Of the other three squares, two are already on the closed list (the starting square, and the one just above the current square, both highlighted in blue in the diagram), so we ignore them. 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. No dice. So we’re done and ready to check the next square on our open list. 

We repeat this process until we add the target square to the closed list, at which point it looks something like the illustration below.

[Figure 6] 

Note that the parent square for the square two squares below the starting square has changed from the previous illustration. Before it had a G score of 28 and pointed back to the square above it and to the right. Now it has a score of 20 and points to the square just above it. This happened somewhere along the way on our search, where the G score was checked and it turned out to be lower using a new path – so the parent was switched and the G and F scores were recalculated. While this change doesn’t seem too important in this example, there are plenty of possible situations where this constant checking will make all the difference in determining the best path to your target. 

So how do we determine the path? Simple, just start at the red target square, and work backwards moving from one square to its parent, following the arrows. This will eventually take you back to the starting square, and that’s your path. It should look like the following illustration. Moving from the starting square A to the destination square B is simply a matter of moving from the center of each square (the node) to the center of the next square on the path, until you reach the target.

[Figure 7]

Summary of the A* Method

Okay, now that you have gone through the explanation, let’s lay out the step-by-step method all in one place:

1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

c) For each of the 8 squares adjacent to this current square …

  • If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.           

  • If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 

  • 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. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you:

  • Add the target square to the closed list, in which case the path has been found (see note below), or
  • Fail to find the target square, and the open list is empty. In this case, there is no path.   

3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path. 

Note: In earlier versions of this article, 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.  Doing this will be faster and it will almost always give you the shortest path, but not always.  Situations where doing this could make a difference are when the movement cost to move from the second to the last node to the last (target) node can vary significantly -- as in the case of a river crossing between two nodes, for example.

Notes on Implementation 

Now that you understand the basic method, here are some additional things to think about when you are writing your own program. Some of the following materials reference the program I wrote in C++ and Blitz Basic, but the points are equally valid in other languages.

1.  Other Units (collision avoidance): If you happen to look closely at my example code, you will notice that it completely ignores other units on the screen. The units pass right through each other. Depending on the game, this may be acceptable or it may not. If you want to consider other units in the pathfinding algorithm and have them move around one another, I suggest that you only consider units that are either stopped or adjacent to the pathfinding unit at the time the path is calculated, treating their current locations as unwalkable. For adjacent units that are moving, you can discourage collisions by penalizing nodes that lie along their respective paths, thereby encouraging the pathfinding unit to find an alternate route (described more under #2).

If you choose to consider other units that are moving and not adjacent to the pathfinding unit, you will need to develop a method for predicting where they will be at any given point in time so that they can be dodged properly. Otherwise you will probably end up with strange paths where units zig-zag to avoid other units that aren't there anymore.

You will also, of course, need to develop some collision detection code because no matter how good the path is at the time it is calculated, things can change over time. When a collision occurs a unit must either calculate a new path or, if the other unit is moving and it is not a head-on collision, wait for the other unit to step out of the way before proceeding with the current path.

These tips are probably enough to get you started. If you want to learn more, here are some links that you might find helpful:

2. Variable Terrain Cost: In this tutorial and my accompanying program, terrain is just one of two things – walkable or unwalkable. But what if you have terrain that is walkable, but at a higher movement cost? Swamps, hills, stairs in a dungeon, etc. – these are all examples of terrain that is walkable, but at a higher cost than flat, open ground. Similarly, a road might have a lower movement cost than the surrounding terrain.

This problem is easily handled by adding the terrain cost in when you are calculating the G cost of any given node. Simply add a bonus cost to such nodes. The A* pathfinding algorithm is already written to find the lowest cost path and should handle this easily. In the simple example I described, when terrain is only walkable or unwalkable, A* will look for the shortest, most direct path. But in a variable-cost terrain environment, the least cost path might involve traveling a longer distance – like taking a road around a swamp rather than plowing straight through it.

An interesting additional consideration is something the professionals call “influence mapping.” Just as with the variable terrain costs described above, you could create an additional point system and apply it to paths for AI purposes. Imagine that you have a map with a bunch of units defending a pass through a mountain region. Every time the computer sends somebody on a path through that pass, it gets whacked. If you wanted, you could create an influence map that penalized nodes where lots of carnage is taking place. This would teach the computer to favor safer paths, and help it avoid dumb situations where it keeps sending troops through a particular path, just because it is shorter (but also more dangerous).

Yet another possible use is penalizing nodes that lie along the paths of nearby moving units. One of the downsides of A* is that when a group of units all try to find paths to a similar location, there is usually a significant amount of overlap, as one or more units try to take the same or similar routes to their destinations. Adding a penalty to nodes already 'claimed' by other units will help ensure a degree of separation, and reduce collisions. Don't treat such nodes as unwalkable, however, because you still want multiple units to be able to squeeze through tight passageways in single file, if necessary. Also, you should only penalize the paths of units that are near the pathfinding unit, not all paths, or you will get strange dodging behavior as units avoid paths of units that are nowhere near them at the time. Also, you should only penalize path nodes that lie along the current and future portion of a path, not previous path nodes that have already been visited and left behind.

3. Handling Unexplored Areas: Have you ever played a PC game where the computer always knows exactly what path to take, even though the map hasn't been explored yet? Depending upon the game, pathfinding that is too good can be unrealistic. Fortunately, this is a problem that is can be handled fairly easily.

The answer is to create a separate "knownWalkability" array for each of the various players and computer opponents (each player, not each unit -- that would require a lot more computer memory). Each array would contain information about the areas that the player has explored, with the rest of the map assumed to be walkable until proven otherwise. Using this approach, units will wander down dead ends and make similar wrong choices until they have learned their way around. Once the map is explored, however, pathfinding would work normally.

4. Smoother Paths: While A* will automatically give you the shortest, lowest cost path, it won't automatically give you the smoothest looking path. Take a look at the final path calculated in our example (in Figure 7). On that path, the very first step is below, and to the right of the starting square. Wouldn't our path be smoother if the first step was instead the square directly below the starting square?

There are several ways to address this problem. While you are calculating the path you could penalize nodes where there is a change of direction, adding a penalty to their G scores. Alternatively, you could run through your path after it is calculated, looking for places where choosing an adjacent node would give you a path that looks better. For more on the whole issue, check out Toward More Realistic Pathfinding, a (free, but registration required) article at Gamasutra.com by Marco Pinter.

5. Non-square Search Areas: In our example, we used a simple 2D square layout. You don't need to use this approach. You could use irregularly shaped areas. Think of the board game Risk, and the countries in that game. You could devise a pathfinding scenario for a game like that. To do this, you would need to create a table for storing which countries are adjacent to which, and a G cost associated with moving from one country to the next. You would also need to come up with a method for estimating H. Everything else would be handled the same as in the above example. Instead of using adjacent squares, you would simply look up the adjacent countries in the table when adding new items to your open list.

Similarly, you could create a waypoint system for paths on a fixed terrain map. Waypoints are commonly traversed points on a path, perhaps on a road or key tunnel in a dungeon. As the game designer, you could pre-assign these waypoints. Two waypoints would be considered "adjacent" to one another if there were no obstacles on the direct line path between them. As in the Risk example, you would save this adjacency information in a lookup table of some kind and use it when generating your new open list items. You would then record the associated G costs (perhaps by using the direct line distance between the nodes) and H costs (perhaps using a direct line distance from the node to the goal). Everything else would proceed as usual.

Amit Patel has written a brief article delving into some alternatives. For another example of searching on an isometric RPG map using a non-square search area, check out my article Two-Tiered A* Pathfinding.

6. Some Speed Tips: As you develop your own A* program, or adapt the one I wrote, you will eventually find that pathfinding is using a hefty chunk of your CPU time, particularly if you have a decent number of pathfinding units on the board and a reasonably large map. If you read the stuff on the net, you will find that this is true even for the professionals who design games like Starcraft or Age of Empires. If you see things start to slow down due to pathfinding, here are some ideas that may speed things up: 

  • Consider a smaller map or fewer units.
  • Never do path finding for more than a few units at a time. Instead put them in a queue and spread them out over several game cycles. If your game is running at, say, 40 cycles per second, no one will ever notice. But they will notice if the game seems to slow down every once in a while when a bunch of units are all calculating paths at the same time.
  • 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. If you are interested in this concept, check out my article Two-Tiered A* Pathfinding.
  • For longer paths, consider devising precalculated paths that are hardwired into the game.
  • Consider pre-processing your map to figure out what areas are inaccessible from the rest of the map. I call these areas "islands." In reality, they can be islands or any other area that is otherwise walled off and inaccessible. One of the downsides of A* is that if you tell it to look for paths to such areas, it will search the whole map, stopping only when every accessible square/node has been processed through the open and closed lists. That can waste a lot of CPU time. It can be prevented by predetermining which areas are inaccessible (via a flood-fill or similar routine), recording that information in an array of some kind, and then checking it before beginning a path search.
  • In a crowded, maze-like environment, consider tagging nodes that don't lead anywhere as dead ends. Such areas can be manually pre-designated in your map editor or, if you are ambitious, you could develop an algorithm to identify such areas automatically. Any collection of nodes in a given dead end area could be given a unique identifying number. Then you could safely ignore all dead ends when pathfinding, pausing only to consider nodes in a dead end area if the starting location or destination happen to be in the particular dead end area in question.

7. Maintaining the Open List: This is actually one of the most time consuming elements of the A* pathfinding algorithm. Every time you access the open list, you need to find the square that has the lowest F cost. There are several ways you could do this. You could save the path items as needed, and simply go through the whole list each time you need to find the lowest F cost square. This is simple, but really slow for long paths. 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. When I wrote my program, this was the first method I used.

This will work reasonably well for small maps, but it isn’t the fastest solution. Serious A* programmers who want real speed use something called a binary heap, and this is what I use in my code. In my experience, this approach will be at least 2-3 times as fast in most situations, and geometrically faster (10+ times as fast) on longer paths. If you are motivated to find out more about binary heaps, check out my article, Using Binary Heaps in A* Pathfinding.

Another possible bottleneck is the way you clear and maintain your data structures between pathfinding calls. I personally prefer to store everything in arrays. While nodes can be generated, recorded and maintained in a dynamic, object-oriented manner, I find that the amount of time needed to create and delete such objects adds an extra, unnecessary level of overhead that slows things down. If you use arrays, however, you will need to clean things up between calls. The last thing you will want to do in such cases is spend time zero-ing everything out after a pathfinding call, especially if you have a large map.

I avoid this overhead by creating a 2d array called whichList(x,y) that designates each node on my map as either on the open list or closed list. After pathfinding attempts, I do not zero out this array. Instead I reset the values of onClosedList and onOpenList in every pathfinding call, incrementing both by +5 or something similar on each path finding attempt. This way, the algorithm can safely ignore as garbage any data left over from previous pathfinding attempts. I also store values like F, G and H costs in arrays. In this case, I simply write over any pre-existing values and don't bother clearing the arrays when I'm done.

Storing data in multiple arrays consumes more memory, though, so there is a trade off. Ultimately, you should use whatever method you are most comfortable with.

8. Dijkstra's Algorithm: 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). 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.

Further Reading

Okay, now you have the basics and a sense of some of the advanced concepts. At this point, I’d suggest wading into my source code. The package contains two versions, one in C++ and one in Blitz Basic. Both versions are heavily commented and should be fairly easy to follow, relatively speaking.  Here is the link.

If you do not have access to C++ or Blitz Basic, two small exe files can be found in the C++ version. The Blitz Basic version can be run by downloading the free demo version of Blitz Basic 3D (not Blitz Plus) at the Blitz Basic web site.

You should also consider reading through the following web pages. They should be much easier to understand now that you have read this tutorial.

  • Amit’s A* Pages: This is a very widely referenced page by Amit Patel, but it can be a bit confusing if you haven’t read this article first. Well worth checking out. See especially Amit's own thoughts on the topic.
  • Smart Moves: Intelligent Path Finding: This article by Bryan Stout at Gamasutra.com requires registration to read. The registration is free and well worth it just to reach this article, much less the other resources that are available there. The program written in Delphi by Bryan helped me learn A*, and it is the inspiration behind my A* program. It also describes some alternatives to A*.
  • Terrain Analysis: This is an advanced, but interesting, article by Dave Pottinger, a professional at Ensemble Studios. This guy coordinated the development of Age of Empires and Age of Kings. Don’t expect to understand everything here, but it is an interesting article that might give you some ideas of your own. It includes some discussion of mip-mapping, influence mapping, and some other advanced AI/pathfinding concepts.

Some other sites worth checking out:

I also highly recommend the following books, which have a bunch of articles on pathfinding and other AI topics. They also have CDs with sample code. I own them both. Plus, if you buy them from Amazon through these links, I'll get a few pennies from Amazon. :)

Well, that’s it. If you happen to write a program that uses any of these concepts, I’d love to see it. I can be reached at 

Until then, good luck!

A*路徑搜尋初探 GameDev.net


最近在Patrick Lester先生的網站看到,他的大作已經被Panic先生翻譯成簡體中文。在取得Panic的同意後,筆者將他的譯槁加以編輯,並做了部分改寫成正體中文版,希望對有興趣的讀者有所幫助。

原文作者:Patrick Lester
簡體中文版譯者:Panic 2005年3月18日(第一版)


這篇文章非常知名,國內應該有不少人翻譯過它,我沒有搜尋過,覺得翻譯本身也是對自身英文水平的鍛煉。經過努力,終於完成了本文,也明白的A*演算法的原理。毫無疑問,作者用形象的描述、簡潔詼諧的語言由淺入深的講述了這一神奇的演算法,相信每個讀過的人都會對此有所認識(如果沒有,那就是偶的翻譯太差了 :wink:)。



A*(唸作A star)演算法對初學者來說的確有些難度。這篇文章並不試圖對這個話題作權威性地陳述。取而代之的是,本文只是描述演算法的原理,讓你可以在進一步的閱讀中理解其他相關的資料。

最後,這篇文章不包含程式實作的細節。你可以用任意的電腦程式語言實作它。如你所願,我在文章的末尾包含了一個範例程式碼的連結。該壓縮檔中包括C++和Blitz Basic兩個語言的版本,如果你只是想看看它的執行效果,裡面還包含了可執行檔。










  1. 從點A開始,並且把它作為待處理點存入一個「開啟列表(open list)」。開啟列表就像一張購物清單。儘管現在列表裡只有一個元素,但以後就會逐漸增多。你的路徑可能會通過它包含的方格,也可能不會。基本上,這是一個待檢查方格的列表。
  2. 尋找起點周圍所有可到達或者可通過的方格,跳過有牆壁、湖水、或其他無法通過地形的方格。也把他們加入開啟列表。把點A當成這些方格的「父方格」儲存下來。當我們想描述路徑的時候,父方格的資料是十分重要的。後面會解釋它的實際用途。
  3. 從開啟列表中刪除點A,把它加入到一個「關閉列表(closed list)」,此列表將儲存所有不需要再次檢查的方格。




路徑評估(Path Scoring


F = G + H


G:代表從起點A,沿著產生的路徑,移動到網格上指定方格的移動代價(movement cost)。   





H值可以用不同的方法估算。這裡使用的方法被稱為「曼哈頓方法(Manhattan method)」,它計算從當前格到目的格之間,水平和垂直的方格的數量總和,忽略對角線方向,然後把結果乘以10。稱之為「曼哈頓方法」是因為它看起來像計算城市中,從一個地方到另外一個地方的街區數,在此,你無法沿對角線方向穿過街區。很重要的一點,我們忽略了一切障礙物。這是對剩餘距離的一個估算,而非實際值,這也是這一方法被稱為「錯誤嘗試」的原因。想知道更多?你可以在這篇文章找到方程式和額外的註解。

F的值是G和H的和。第一步搜尋的結果可以在【圖三】看到。F, G和H的評估(scores)寫在每個方格中。正如緊鄰在起始格右側的方格所示,F值列在左上方、G在左下角、H則在右下角。


現在我們來看看這些方格。在包含字母的方格裡面(也就是中間右側那一個),G = 10。這是因為它只在水平方向偏離「起始格」一個格距。緊鄰起始格的上方、下方和左邊的方格的G值都等於10。對角線方向的G值是14。





  1. 把它從開啟列表中刪除,然後添加到關閉列表中。
  2. 檢查所有相鄰格子。跳過那些已經在關閉列表中,或者不可通過的(有牆和水,或其他無法通過的地形),把他們加入開啟列表,如果他們還不在裡面的話。把選中的方格當成新的方格的父節點。
  3. 如果某個相鄰格已經在開啟列表裡了,檢查現在的這條路徑是否更好。換句話說,檢查如果我們用新的路徑到達它的話,G值是否會更低一些。如果不會,那就什麼都不做。










這樣一來,就剩下了其他5格。目前格子之下的另外兩個格子現在不在開啟列表中,於是我們加入他們,並且把當前格指定為他們的父節點。其餘3格,兩個已 經在關閉列表中(起始格,和當前格上方的格子,在網格中用藍色邊框標示),於是我們略過它們。最後一格,在當前格的左側,將被檢查通過這條路徑,G值是否更低。不必擔心,我們已經準備好檢查開啟列表中的下一格了。








  1. 把起始格加入「開啟列表」。
  2. 重複如下的工作:
    1. 尋找開啟列表中F值最低的格子。我們稱它為「當前格」。
    2. 把它存入「關閉列表」。
    3. 對相鄰的8格中的每一格:
      • 如果它不可通過或者已經在關閉列表中,略過它。反之如下:
      • 如果它不在開啟列表中,把它添加進去。把當前格作為這一格的父節點。記錄這一格的F, G和H值。
      • 如果它已經在開啟列表中,拿G值當作參考,檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣,就把這一格的父節點改成當前格,並且重新計算這一格的G和F值。如果你想讓開啟列表按F值排序,你可能需要在此步驟之後,重新對開啟列表排序。
    1. 停止,當你:
      • 把目標格加入關閉列表(參閱下文的註解),代表找到路徑了,或者:
      • 沒有找到目標格,開啟列表已經空了。這時候,路徑不存在。
  3. 儲存路徑。從目標格開始,沿著每一格的父節點移動直到回到起始格。這就是你的路徑。


離題一下,請見諒,值得一提的是,當你在網路上或者相關論壇看到關於A*的不同的探討,你有時會看到一些被當作A*演算法的程式碼而實際上它們不是。要使用 A*,你必須包含上面討論的所有元素--特定的開啟和關閉列表,用F, G和H當作路徑評價。有很多其他的路徑搜尋演算法,但他們並不是A*,A*被認為是他們當中最好的。Bryan Stout在這篇文章後面的參考文件中論述了一部分,包括它們的一些優點和缺點。在某些特定的場合,其他演算法比較好,但你必須很明確知道你在做什麼。好了,回到文章。


現在你已經明白了基本原理,寫程式的時候還得考慮一些額外的東西。下面這些內容中的一些,引用了我用C++和Blitz Basic寫的程式,但對其他語言寫的程式碼同樣有效。

  1. 其他元素(unit,避免碰撞):如果你恰好看了我的範例程式碼,你會發現它完全忽略了其他元素。我的路徑搜尋程式事實上可以相互穿越。取決於實際的遊戲,這也許可以,也許不行。如果你打算考慮其他元素,希望他們能互相繞過,我建議你只考慮靜止或那些在計算路徑時臨近當前元素的元素,把它們當前的位置標誌為可通過的。對於臨近的運動中的元素,你可以藉由「懲罰」它們各自路徑上的節點,來鼓勵這些路徑搜尋程式找到不同的路徑(更多的說明請參閱#2)。



  2. 不同的地形損耗:在這個教程和我附帶的程式中,地形只能是二者之一:可通過和不可通過的。你可能會需要一些可通過的地形,但是移動代價更高--沼澤、小山、地牢的樓梯…等等。這些都是可通過,但是比「平坦的開闊地形」移動代價更高的地形。同樣地,道路應該比自然地形所需的移動代價更低。


    一種需額外考慮的情況是被專家稱之為"influence mapping"的東西(暫譯為「影響映射圖」)。就像上面描述的不同地形代價一樣,你可以建立一個額外的分數系統,並把它套用到路徑搜尋的AI中。假設你有一張包含大批路徑搜尋程式的地圖,他們都要通過某個山區。每次電腦產生一條通過那個關口的路徑,它就會變得更擁擠。如果你願意,你可以建立一個影響映射圖,對有大量屠殺事件的格子施以不利影響。這會讓電腦更傾向比較安全的路徑,並且幫助它避免總是僅僅因為路徑短(但可能更危險),而持續把隊伍和路徑搜尋程式送到某一特定路徑。

    另一個可能的應用是懲罰周圍移動元素路徑上的節點。A*的一個底限是,當一群元素同時嘗試路徑搜尋到接近的地點時,通常會導致路徑重疊。因為一個或者多個元素都試圖走相同或者近似的路徑到達目的地。對其他元素已經「認領」了的節點增加一些懲罰,會有助於你在一定程度上分離路徑,降低碰撞的可能性。然而,如果有必要,不要把那些節點看成不可通過的,因為你仍然希望多個元素能夠一字縱隊通過擁擠的出口。同時,你只能懲罰那些臨近元素的路徑,而不是所有路徑,否則你就會得到奇怪的躲避行為。例如,元素躲避路徑上其他已經不在那裡的元素。 還有,你應該只懲罰路徑當前節點和隨後的節點,而不應處理已經走過並甩在身後的節點。

  3. 處理未知區域:你是否玩過這樣的PC遊戲,電腦總是知道哪條路是正確的,即使它還沒有偵察過地圖?對於遊戲,路徑搜尋太好會顯得不真實。幸運的是,這是一個可以輕易解決的問題。


  4. 平滑路徑:儘管A*提供了最短、最低代價的路徑,它無法自動提供看起來平滑的路徑。看一下我們的範例最終形成的路徑(圖7)。最初的一步是起始格的右下方,如果這一步是直接往下的話,路徑不是會更平滑一些嗎?

    有幾種方法來解決這個問題。當計算路徑的時候可以對改變方向的格子施加不利影響,對G值增加額外的數值。也可以換種方法,你可以在路徑計算完之後沿著它跑一遍,找那些用相鄰格替換會讓路徑看起來更平滑的地方。想知道完整的結果,請參考Marco Pinter發表在Gamasutra.com的Toward More Realistic Pathfinding文章(免費,但是需要註冊)。

  5. 非方形搜尋區域:在我們的範例裡,我們使用簡單的2D方形圖。你可以不使用這種方式。你可以使用不規則形狀的區域。想想棋類冒險遊戲,及遊戲中的那些國家。你可以設計一個像那樣的路徑搜尋關卡。為此,你可能需要建立一個國家相鄰關係的表格,和從一個國家移動到另一個的G值。你也需要估算H值的方法。其他的事情就 和範例中完全一樣了。當你需要在開啟列表中新增元素時,不需使用相鄰的格子,取而代之的是從表格中尋找相鄰的國家。


    Amit Patel 寫了其他方法的摘要。另一個在非方形區域搜尋RPG地圖的例子,請參考我的文章Two-Tiered A* Pathfinding(譯者註:譯文: A*分層路徑搜尋

  6. 一些速度方面的提示:當你開發自己的A*程式,或者改寫我的,你會發現路徑搜尋佔據了大量的CPU時間,尤其是在大地圖上有大量物件在執行路徑搜尋的時候。如果你閱讀過網路上的其他文件,你會明白,即使是開發了「星際爭霸」或「帝國時代」的專家,這也無可奈何。如果你覺得路徑搜尋太過緩慢,這裡有一些建議也許有效:
    • 使用小一點的地圖,或者減少使用路徑搜尋程式的元素。
    • 不要同時讓多個物件執行路徑搜尋。取而代之的是,將他們加入一個佇列,把路徑搜尋過程分散在幾個遊戲週期中。如果你的遊戲以每秒40週期的速度執行,沒人能察覺。但是當大量路徑搜尋程式計算自己路徑的時候,玩家會發覺遊戲速度突然變慢了。
    • 儘量使用大一點的地圖方格(或者任何形狀的格子)。此舉能降低路徑搜尋中,搜尋的總網格數。你可以取決於路徑的長度,設計兩種或者更多不同的路徑搜尋系統,以便使用在不同場合。這也正是專業人士的做法,用大區域計算比較長的路徑,然後在接近目標的時候,切換到使用小格子∕區域的精細路徑搜尋。如果你對這個觀點感興趣,請參閱我的文章Two-Tiered A* Pathfinding(譯者注:譯文:A*分層路徑搜尋)。
    • 對於比較長的路徑,可以預先計算好並植入(hardwired)遊戲裡面。
    • 預先處理地圖,標示地圖中哪些區域是無法到達的。我把這些區域稱作「孤島」。事實上,他們可以是島嶼或其他被牆壁包圍等無法到達的任意區域。A*的缺點是,當你告訴它要找出通過那些區域的路徑時,它會搜尋整個地圖,只有在每個可連通的方格∕節點都經由「開啟列表」和「關閉列表」處理過,才會停下來。這可能會浪費大量的CPU時間。可以透過預先確定這些區域(比如flood-fill或類似的方法)來避免這種情況的發生,用某些種類的陣列記錄這些資訊,在開始路徑搜尋前檢查它。
    • 在一個擁擠的類似迷宮的場合,把不能連通的節點看作死路。這些區域可以在地圖編輯器中預先手動指定,或者如果你有雄心壯志,開發一個自動識別這些區域的演算法。設定成死路的所有節點,可以被賦予一個唯一的標識數字。然後你就可以在路徑搜尋過程中安全地忽略所有死路,只有當起點或者終點恰好在死路的某個節點的時候,才需要考慮它們。
  7. 維護開啟列表:這是A*路徑搜尋演算法最重要的組成部分。每當你存取開啟列表,你都需要尋找F值最低的方格。實作這項功能的方法有幾種。你可以把路徑元素隨意保存,當需要尋找F值最低的元素的時候,遍覽開啟列表。這很簡單,但是太慢了,尤其是對長路徑來說。這可以藉由維護一個排序好的列表來改善,每次尋找F值最低的方格,只需要選取列表的第一個元素。當我實作程式的時候,這種方法是我的首選。

    在小地圖上,這種方法可以良好地運作,但它並不是最快的解決方案。對速度更苛求的A*程式設計師使用叫做"binary heap"的方法,這也是我在程式碼中使用的方法。憑我的經驗,這種方法在大多數場合會快2~3倍,並且在長路徑上速度呈幾何級數提升(10倍以上速度)。如果你想瞭解更多關於"binary heap"的內容,請參閱我的文章,Using Binary Heaps in A* Pathfinding(譯者注:譯文:在A*路徑搜尋中使用Binary Heap)。
    另一個可能的瓶頸,是在多次路徑搜尋之間清除和保存資料結構的方法。我個人更傾向把所有東西都儲存在陣列裡面。雖然節點可以以物件導向的風格被動態 地產生、記錄和保存,我發現建立和刪除物件所增加的大量時間,以及多餘的管理層次將減慢整個過程的速度。但是,如果你使用陣列,你需要在呼叫之間清理資料。這種情形下,你想做的最後一件事就是在路徑搜尋呼叫之後,花點時間把一切歸零,尤其是你的地圖很大的時候。

    我透過使用一個叫做whichList(x,y)的二維陣列避免這種開銷,陣列的每個元素表明了節點是位於開啟列表還是在關閉列表中。嘗試路徑搜尋之後,我沒有清除這個陣列。取而代之的是,我在新的路徑搜尋中重置onClosedList和onOpenList的數值,每次路徑搜尋兩個都+5或者其他類似的數值。藉由這種方式,演算法可以安全地跳過前面路徑搜尋留下的冗餘資料。我還在陣列中儲存了諸如F, G和H的值。這樣一來,我只需簡單地重寫任何已經存在的值,而無需被清除陣列的操作干擾。將資料儲存在多維陣列中需要更多記憶體,所以這裡需要權衡利弊。最後,你應該使用你最得心應手的方法。

  8. Dijkstra的演算法:儘管A*被認為是通常最好的路徑搜尋演算法(參閱上文的「題外話」),還是外一種演算法有它的可取之處,稱為:Dijkstra演算法。 Dijkstra演算法和A*本質是相同的,只有一點不同,就是Dijkstra演算法沒有錯誤嘗試(H值總是0)。由於沒有錯誤嘗試,它會在各個方向上平均搜尋。正如你所預料,由於Dijkstra演算法在找到目標前通常會探索更大的區域,所以一般會比A*更慢一些。
    那麼為什麼要使用這種演算法呢?因為有時候我們並不知道目標的位置。比如說你有一個資源採集元素,需要獲取某種類型的資源若干。它可能知道幾個資源區 域,但是它想去最近的那個。這種情況,Dijkstra演算法就比A*更適合,因為我們不知道哪個更近。用A*,我們唯一的選擇是依次對每個目標許路並計算距離,然後選擇最近的路徑。我們尋找的目標可能會有不計其數的位置,我們只想找其中最近的,而我們並不知道它在哪里,或者不知道哪個是最近的。


好,現在你對這些進一步的觀點有了初步認識。我建議你研究我的原始程式碼。壓縮檔裡面包含兩個版本,一個是用C++寫的,另一個用Blitz Basic。附帶一題,兩個版本都有詳盡的註解,容易閱讀,壓縮檔的連結如下。

如果你既不用C++也不用Blitz Basic,在C++版本裡有兩個小的可執行檔。Blitz Basic能在從Blitz Basic網站免費下載的Blitz Basic 3D(不是Blitz Plus)試用版上執行。Ben O’Neill提供一個連線範例可以在這裡找到。


  • Amit的 A* 網頁:這是由Amit Patel撰寫,被廣泛引用的網頁,如果你事先未曾閱讀過本文,可能會有點難以理解。值得一看。尤其要看Amit對於這個問題所提出的自己的看法
  • Smart Moves:智慧型路徑搜尋:Bryan Stout發表在Gamasutra.com的這篇文章需要註冊才能閱讀。註冊是免費的而且比起這篇文章和網站的其他資源,是非常物有所值的。Bryan用Delphi寫的程式幫助我學習A*,也是我的A*程式碼的靈感來源。它還描述了A*的幾種變型。
  • 地形分析:這是一個高階,但是有趣的話題,由Ensemble Studios的專家Dave Pottinge所撰寫。這傢伙參與了「帝國時代」和「君王時代(Age of Kings)」的開發。別指望看懂這裡的所有東西,但是這是篇有趣的文章,也許會讓你產生自己的想法。它包含一些對 mip-mapping, influence mapping以及其他一些進階AI路徑搜尋觀點。對"flood filling"的討論讓我有了我自己的「死路」和「孤島」程式碼的靈感,這些包含在我Blitz版本的程式碼中。


我同樣高度推薦下面這幾本書,裡面有很多關於路徑搜尋和其他AI話題的文章。 它們也附帶了實例程式碼的CD。這些書我都買了。另外,如果你透過底下的連結購買了這些書,我會從Amazon得到幾個美分 :-)



 在A*路徑搜尋中使用Binary Heap