




已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 第3课 秦朝大一统格局的建立说课稿-2025-2026学年中职基础课-中国历史(全一册)-高教版-(历史)-60
- 考点解析-人教版九年级物理《内能》定向练习试题(含答案解析版)
- 五、插入影片说课稿-2025-2026学年初中信息技术(信息科技)八年级下册沪科版
- Starter Unit 2 课时说课稿 2024-2025学年人教版(2024)七年级英语上册
- 一年级语文上册 识字(一)5《对韵歌》说课稿 新人教版
- 考点攻克人教版八年级物理《功和机械能》难点解析试卷(含答案详解版)
- 全国电子工业版初中信息技术第四册第2单元2.4活动1《生活中的人脸识别应用》说课稿
- 精准温控杀菌机行业跨境出海项目商业计划书
- 拉勾勾说课稿-2025-2026学年小学音乐人音版五线谱一年级上册-人音版(五线谱)
- 03 11 短文二篇2024-2025学年八年级语文上册同步说课稿(河北专版)
- 药品类体外诊断试剂专项培训课件
- 水处理设备运行与维护保养手册
- 高中数学新教材选择性必修第二册《4.2等差数列》课件
- 2025年九省联考新高考 数学试卷(含答案解析)
- 2025年九省联考新高考 语文试卷(含答案解析)
- 建筑识图与构造 课件 项目8 识读建筑详图
- 《湖南省职工基本医疗保险门诊慢特病基础用药指南(第一批)》
- 四年级上册道德与法治学科质量分析报告
- 2024风电齿轮箱润滑油生物基滤芯
- 未被列入违法失信名单承诺书
- 工业互联网技术基础 课件 第4、5章 PaaS层与工业大数据治理、应用层与工业APP开发
评论
0/150
提交评论