在A*寻路中使用二叉堆
2006-07-23 11:33:11 来源：WEB开发网 闂傚倸鍊搁崐鎼佸磹妞嬪孩顐芥慨姗嗗厳缂傛氨鎲稿鍫罕闂備礁婀遍搹搴ㄥ窗閺嶎偆涓嶆い鏍仦閻撱儵鏌ｉ弴鐐测偓鍦偓姘炬嫹
闂傚倸鍊搁崐鎼佸磹妞嬪海鐭嗗〒姘ｅ亾妤犵偛顦甸弫鎾绘偐閹绘帞鈧參姊哄Ч鍥х仼闁诲繑鑹鹃悾鐑藉蓟閵夛妇鍘甸梺瑙勵問閸犳牠銆傛總鍛婄厱閹艰揪绱曟牎闂侀潧娲ょ€氫即鐛幒妤€绠ｆ繝闈涘暙娴滈箖鏌ｉ姀鈶跺湱澹曟繝姘厵闁绘劦鍓氶悘杈ㄤ繆閹绘帞澧涚紒缁樼洴瀹曞崬螖閸愬啠鍓濈换娑樼暆婵犱胶鏁栫紓浣介哺閹瑰洤鐣烽幒鎴僵闁瑰吀鐒﹂悗鎼佹⒒娴ｇ儤鍤€闁搞倖鐗犻獮蹇涙晸閿燂拷
濠电姷鏁告慨鐑藉极閸涘﹥鍙忔い鎾卞灩缁狀垶鏌涢幇闈涙灈鐎瑰憡绻冮妵鍕箻鐎靛摜鐣奸梺纭咁潐濞茬喎顫忕紒妯肩懝闁逞屽墮宀ｈ儻顦查悡銈夋煏閸繃鍋繛宸簻鎯熼梺瀹犳〃閼冲爼宕濋敃鈧—鍐Χ閸℃鐟愰梺鐓庡暱閻栧ジ宕烘繝鍥у嵆闁靛骏绱曢崢顏堟⒑閹肩偛鍔楅柡鍛⊕缁傛帟顦寸紒杈ㄥ笚濞煎繘鍩℃担閿嬵潟闂備浇妗ㄩ悞锕傚箲閸ヮ剙鏋侀柟鍓х帛閺呮悂鏌ㄩ悤鍌涘闂傚倸鍊搁崐鎼佸磹妞嬪孩顐芥慨姗嗗厳缂傛氨鎲稿鍫罕闂備礁婀遍搹搴ㄥ窗閺嶎偆涓嶆い鏍仦閻撱儵鏌ｉ弴鐐测偓鍦偓姘炬嫹 闂傚倸鍊搁崐鎼佸磹閻戣姤鍤勯柤鍝ユ暩娴犳氨绱撻崒娆掑厡缂侇噮鍨堕妴鍐川閺夋垹鍘洪悗骞垮劚椤︻垶宕￠幎鑺ョ厪闊洦娲栨牎闂佽瀵掗崜鐔奉潖閾忓湱纾兼俊顖氭惈椤矂姊洪崷顓涙嫛闁稿妫濋幆鈧い蹇撴祩濡嫰姊洪崫鍕拱婵炲弶岣块幑銏犫攽婵犲嫮鏉搁梺鍝勬川婵兘鎮伴妷鈺傗拻濞达絽鎼敮璺侯熆閻熷府鏀荤紒鍌氱Т楗即宕煎锝呬壕闁哄啫鐗嗙粈鍐┿亜韫囧海顦﹀ù婊堢畺閺屻劌鈹戦崱娑扁偓妤€顭胯閸犳牠婀侀梺缁樕戦悷銉р偓姘煎枤缁粯銈ｉ崘鈺冨幈濡炪倖鍔戦崐鏇㈠几鎼淬劍鐓熼煫鍥ь儏閸旀粓鏌曢崶褍顏€殿喗娼欒灒闁告繂瀚濠碉紕鍋戦崐鎴﹀垂濞差亝鍋￠柍鍝勬噹缁犳牠鏌嶉埡浣告殲闁稿海鍠栭弻鏇㈠炊瑜嶇花濠氭煙閸戙倖瀚�
核心提示： 使用指针现在我们有了正确大小的数组，几乎可以开始用来寻路了，在A*寻路中使用二叉堆(6)，不过，在进一步的添加或者删除操作之前，这个元素的F值是Fcost(5) = 10，x坐标是openX(5) = 12，我们再看看原始的堆，现在
使用指针
现在我们有了正确大小的数组，几乎可以开始用来寻路了。不过，在进一步的添加或者删除操作之前，我们再看看原始的堆。
现在，它只是个F值的列表，而且已经被正确安排。但是我们忽略了一个重要的元素。是的，我们有一系列的F值按顺序保存在堆里，但是我们没有他们代表哪一格的任何线索。基本上，我们只是知道10是堆中最低的F值。但那指的是那个格子？
为了解决这个问题，我们必须改变数组中元素的值。我们不储存排序好的F值，取而代之的是保存关联到地图网格的唯一标志。我的方法是为每个新加入堆的元素创建一个唯一ID叫做squaresChecked。每次往开启列表中添加新元素，我们给squaresChecked增加1，并把它作为列表中新元素的唯一ID。第一个添加进列表的是#1，第二个是#2，依此类推。
最后，我们把具体的F值存储在单独的一维数组中，我把它叫做 Dcost()。和开启列表相同，我们把它的大小定为(地图宽 x 地图高)。我们同时存储节点的x和y坐标在类似的一维数组中，叫做 openX() 和 openY()。看起来就像下面的图：
尽管这看起来有点复杂，但它和前面讲的堆是相同的。只是储存的信息更多了。
#5元素，有最低的F值10，仍然在堆顶，在一维数组的第一列。不过现在我们在堆里存储它的唯一ID 5，而不是它的F值。换句话说，openList(1) = 5。这个唯一数值用来查找元素的F值，以及地图x和y坐标。这个元素的F值是Fcost(5) = 10，x坐标是openX(5) = 12，y坐标是openY(5) = 22。
中查找“在A*寻路中使用二叉堆”更多相关内容
中查找“在A*寻路中使用二叉堆”更多相关内容更多精彩
赞助商链接
