二叉堆在A-star路径搜索应用 英文.doc

Using Binary Heaps in A* PathfindingBy Patrick Lester ( Updated April 11, 2003)This article is a sidebar for my main article, “A* Pathfinding for Beginners.” You should read that article, or understand A* thoroughly, before proceeding with this article.One of the slowest parts of the A* pathfinding algorithm is finding the square or node on the open list with the lowest F score. Depending on the size of your map, you could have dozens, hundreds or even thousands of nodes to search through at any given time when you are using A*. Needless to say, repeatedly searching through a list this big can slow things down a lot. The amount of time it takes to do this, however, can be greatly influenced by the way you choose to save your open list items.Sorted and Unsorted Open Lists: A Simple ApproachA really simple way to save the open list is to save each item as needed, and go through the whole list each time you need to grab something off of the list, looking for the lowest cost item. This provides fast insertions into the list, but the slowest possible removal time, since you need to check each item on the list to make sure you have the lowest F cost item.You can generally improve your performance by keeping your list sorted. This takes a little more up-front work, however, because every time you add an item to the list, you need to insert it in the proper place. Removing items, however, is fast. You just grab the first item off of the list, which will have the lowest possible F cost.There are lots of ways to keep your data sorted (selection sorts, bubble sorts, quick sorts, etc.) and you can find articles on these on the internet by simply searching on those terms in your favorite search engine. But we can at least touch on some ideas here. A really simple approach would be to start at the beginning of your list every time you need to add a new item, and then successively compare the F cost of the current node you are adding to the list with each item already on the list. Once you find a node on the open list with an equal or higher F cost, you could insert the new item before that item on the list. Depending on the computer language you are using, linked lists using classes or structs (types in Blitz) are probably a good method here.This approach could be improved by keeping track of the average F cost of items already on your list, and using that to decide whether to start at the beginning of the list (as described above) or to start at the end of the list and work toward the front of the list. In general, insertions of new items with lower than average F costs would start at the beginning of the list and work forwards, while insertions of new items with higher than average F costs would start at the end and work backwards. This approach will cut your search time in half.A more complicated, but faster approach could be to take this idea to the next level and use a quick sort, which basically starts by comparing the F cost of the new item to the item at the middle of the list. If the new item has a lower F cost, you would then compare it to the item 1/4 of the way through the list, if lower than that you would compare it to the one 1/8 of the way, and so on, successively dividing your list in half and comparing the new item to the current items on the list until it finds its proper spot. This is a pretty generic description, so you will want to look up quick sorting on the internet to find out more about how it works. Suffice it to say, this will generally be quicker than any of the techniques described so far.Binary HeapsBinary heaps are very similar to the quick sort method just described, and they are often used by people who are serious about keeping their A* functions as fast as possible. In my experience, using a binary heap will speed up your pathfinding by 2-3 times on average, and more on larger maps with lots of nodes (say a map 100 x 100 nodes or more). Fair warning, however - binary heaps are a bit tricky, and may not be worth the headache unless you are using a map with lots of nodes, where speed gains are crucial.The rest of this article is devoted to explaining binary heaps and their use in A*. There is also a Further Reading section at the end of the article which will provide you additional perspectives, if mine leaves you totally mystified.Still interested? Okay, here goes .In a sorted list, every item on the list is in its proper order, lowest-to-highest or highest-to-lowest. This is helpful, but is actually more than we really need. We dont actually care if item number 127 is lower than number 128 on the list. All we really want is the lowest F cost item to be easily accessible at the top of the list. The rest of the list can be a jumble, for all we care. Keeping the rest of the list properly sorted is just extra unneeded work until, of course, we need the next lowest F cost item.Basically, what we really need is something called a “heap” or, more specifically, a binary heap. A binary heap is bunch of items where either the lowest or highest value item (depending on what you want) is at the top of the heap. Since we are looking for the lowest F cost item, we will put that at the top of our heap. This item has two children, each of which has an F cost equal to, or a little higher than it, and each of these children has two children of its own that has an F cost that is equal to, or a little higher than it . and so on. Here is what one heap could look like:Notice that the lowest item on the list (10) is at the top and the second lowest (20) is one of its children. After that, however, all bets are off. In this particular binary heap, the third lowest item on the list is 24, which is two steps down from the top, and lower than 30, which is only one step from the top on the left side. Simply put, it doesnt matter what the value of other items are in the heap, each individual item in the heap needs only to be equal to or higher than its parent, and equal to or lower than both of its children. Those conditions are met here, so this is a valid binary heap.All right, you are probably thinking, this is modestly interesting, but how do you actually use it in any practical sense? Well, one of the interesting things about a heap is that you can save it in a simple, one dimensional array.In this array, the item at the top of the heap would be in the first position of the array (position 1, not position zero, which is possible in an array). Its two children would be in positions 2 and 3. The four children of these two items would be in positions 4-7.In general, the two children of any item in the heap can be found in the array by multiplying the items current position in the array by two (to find the first child) and by two and adding one (to find the second child). So, for example, the two children of the third item in our heap (with a value of 20), can be found in positions 2*3 = 6, and 2*3 +1 = 7 of the array. In this case, the numbers in those positions are 30 and 24, respectively, which makes sense when you look at the heap.You dont really need to know this, but it is worth noting that there are no holes in this heap. With 7 items, it completely fills out every row of a three-level heap. This isnt necessary, however. For our heap to be valid, we only need to fill out every row above the bottom level. We can have any number of items on the bottom level itself, however, and new items are added from left to right on that level. The method described in this article does that, so you dont really need to worry about it.Adding Items to the HeapWe will need to consider a few more things before we can actually use a heap for pathfinding purposes, but for now lets just learn the basics of using a binary heap in general. Id suggest skimming through this part to understand the basics. I will give you a formula that takes care of all of this for you a little later on in the article, but it is still important to understand what is going on.In general, to add an item to the heap, we place it at the very end of the array. We then compare it to its parent, which is at location (items in heap)/2, rounding all fractions down. If the new items F score is lower, we swap these two items. We then compare the new item with its new parent, which is at (current position in heap)/2, rounding fractions down. If its F value is lower, we swap again. We repeat this process until the item is not lower than its parent, or until the item has bubbled all the way to the top, which is in position #1 in the array.Lets say we were adding an item with an F score of 17 to our existing heap. We currently have 7 items in the heap, so the new item would be placed in position number 8. This is what the heap looks like. The new item is underlined.10 30 20 34 38 30 2417We would then compare this item it to its parent, which is in position 8/2 = position 4. The F value of the item currently in position 4 is 34. Since 17 is lower than 34, we swap them. Now our heap looks like this:10 30 201738 30 24 34Then we compare it with its new parent. Since we are in position 4 we compare it to the item in position number 4/2 = 2. That item has an F score of 30. Since 17 is lower than 30, we swap them, and now our heap looks like this:101720 30 38 30 24 34We then compare it to its new parent. Since we are now in position #2, we compare it with the item in position number 2/2 = 1, which is the top of the heap. In this case, 17 is not lower than 10, so we stop and leave the heap the way it is.Removing Items from the HeapRemoving items from the heap involves a similar process, but sort of in reverse. First, we remove the item in slot #1, which is now empty. Then we take the last item in the heap, and move it up to slot #1. In our heap above, this is what we would end up with. The previously last item in the heap is underlined.3417 20 30 38 30 24Next we compare the item to each of its two children, which are at locations (current position * 2) and(current position * 2 + 1). If it has a lower F score than both of its two children, it stays where it is. If not, we swap it with the lower of the two children. So, in this case, the two children of the item in slot #1 are in position 1*2 = 2 and 1*2+1 = 3. It turns out that 34 is not lower than both children, so we swap it with the lower of the two, which is 17. This is what we end up with:173420 30 38 30 24Next we compare the item with its two new children, which are in positions 2*2 = 4, and 2*2+1 = 5. It turns out that it is not lower than both of its children, so we swap it with the lower of the two children (which is 30 in slot 4). Now we have this:17 30 203438 30 24Finally we compare the item with its new children. As usual, these children would be in positions 4*2 = 8, and 4*2 +1 = 9. But there arent any children in those positions because the list isnt that big. We have reached the bottom level of the heap, so we stop.Why is a Binary Heap so Fast?Now that you know the basics of insertion and removal from a heap, you should begin to see why it is so much faster than, say, an insertion sort. Imagine that you have an open list with 1000 nodes on it, which is not impossible on a sizable map with a lot of nodes (remember, a map just 100 x 100 nodes has 10,000 nodes on it). If you were to do a simple insertion sort, started at the beginning of the list, and proceeded until you found the proper spot to insert the new item, you would on average need to make 500 comparisons before inserting it in the right place.Using a binary heap, you would only need to make an average of 1-3 comparisons to insert it in the right spot, starting from the bottom. You would also need to make an average of about 9 comparisons to remove an item from the open list and reorder the heap appropriately. In A*, you generally remove one node on every pass (the lowest F cost item), and usually add anywhere from 0 to 5 new nodes (using the 2D approach described in the main article). This can total up to about 1% of the time it takes to do an insertion sort on the same number of nodes. The difference becomes geometrically more important the larger (i.e. more nodes on) your map. Smaller maps, by comparison, gain less and less of an advantage, which is why binary heaps become progressively less worth the trouble the smaller your map, and the fewer nodes you use.By the way, just because you are using a binary heap doesnt mean that your pathfinding algorithm will be 100 times faster (or whatever). There is some overhead involved, which is described below. Plus, there is more to the A* algorithm than simply sorting the open list. Nevertheless, in my experience using a binary heap will still make your pathfinding algorithm 2-3 times faster in most cases, and even more on longer paths.Creating theOpen ListArrayNow that we know what a heap is, how do we use it? The first thing we need to do is dimension our one-dimensional array properly. To do this, first we need to figure out how big it can possibly get. In general, the list cant get any bigger than the total number of nodes on our map (assuming a worst-case scenario where we search the whole map for a path). In a square, two-dimensional map like the one I described in the main pathfinding article, we wont have more than mapWidth x mapHeight nodes. So that is how big our 1 dimensional array should be. For the sake of this example, we will call this arrayopenList().The top item in the heap would be stored in openList(1), the second item in the heap would be openList(2), and so on.Using PointersNow that we have a one-dimensional heap/array that is the right size, we are almost ready to start using it for pathfinding purposes. Before we go any further, however, lets look at our original heap again, before we added or subtracted anything.Currently, it is just a list of F values, and they are arranged properly. But we are missing an important element. Sure, we have a bunch of F values arranged in binary heap order, but we have no clue what squares on our map they are associated with. Basically, what we have right now just tells us that 10 is the lowest F score in the heap. But which square on our pathfinding map does that refer to?To fix this problem, we need to change the values of the items in the array. Instead of storing the F value in the array, we need to store a unique identifying number that tells us what square it is referring to. My approach is to create a unique ID associated with each new item added to the heap calledsquaresChecked. Every time we add an item to the open list, we increasesquaresCheckedby one and use this as the unique ID for the new item added to the open list. The first item added to open list will item #1, the second item is item #2, and so on.Finally, we need to save the actual F cost of that square in a separate one dimensional array, which I callFcost(). As with the openList array, we will dimension it to the size (mapWidth x mapHeight). We will also store the x and y coordinates of the node on the map in similar one-dimensional arrays, which I will callopenX()andopenY(). Visually, this looks like the following illustration:While this looks a little more complicated, it is the same heap we used in the earlier illustration. We just have a lot more information now.Item #5, with the lowest Fcost of 10, is still at the top of the heap, and in the first column of our one dimensional array. But now we are storing its unique ID number of 5, rather than its F cost in the heap. In other words,openList(1)= 5. This unique number is then used to look up the items Fcost, and x and y locations on the map. The Fcost of this item is Fcost(5) = 10, its x location on the map is openX(5) = 12, and its y location on the map is openY(5) = 22.This top item in the heap has two children, items number 2 and 6, which have Fcosts of 30 and 20 respectively and are in slots 2 and 3 inopenList(), and so on. Basically, we have exactly the same heap we had earlier, just with a lot more information about where the item is on the map, what its Fcost is, etc.Adding New Items to the Heap (Part 2)Okay, so lets actually apply this technique to sorting our open list in a way that is usable in an A* pathfinding algorithm. In general, we use exactly the same techniques that were described earlier.The first item we add to the open list, which is generally the starting node, is assigned a unique ID number, which is 1, and then put in position #1 in the open list. In other words, openList(1) = 1. We also keep track of the number of items on our open list, which is also 1 for now. We record this number in a variable callednumberOfOpenListItems.As we add new nodes to the open list, first we figure out their G, H and F scores, as described in the main A* article. Then we add them to the binary heap as described earlier in this article.First we assign the new item a unique ID#, which is the purpose of thesquaresCheckedvariable. We basically add 1 to this every time we add a new node to the open list, and we assign this number to the new node. We then add 1 tonumberOfOpenListItems. Then we add it to the bottom of the open list. Basically, all of this translates into the following: squaresChecked = squaresChecked +1 numberOfOpenListItems = numberOfOpenListItems+1 openList(numberOfOpenListItems) = squaresCheckedThen we make successive comparisons with its parent until it rises to its proper spot in the heap. Here is some code that wil