/** 将(新加入开放别表或修改了路径评分的)节点向前移动 */
private function aheadNote(p_index : int) : void
{
var father : int;
var change : int;
//如果节点不在列表最前
while(p_index > 1)
{
//父节点的位置
father = Math.floor(p_index ／ 2);
//如果该节点的F值小于父节点的F值则和父节点交换
if (this.getScore(p_index) < this.getScore(father))
{
change = this.m_openList[p_index - 1];
this.m_openList[p_index - 1] = this.m_openList[father - 1];
this.m_openList[father - 1] = change;
p_index = father;
} else
{
break;
}
}
}
/** 将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动 */
private function backNote() : void
{
//尾部的节点被移到最前面
var checkIndex : int = 1;
var tmp : int;
var change : int;
while(true)
{
tmp = checkIndex;
//如果有子节点
if (2 * tmp <= this.m_openCount)
{
//如果子节点的F值更小
if(this.getScore(checkIndex) > this.getScore(2 * tmp))
{
//记节点的新位置为子节点位置
checkIndex = 2 * tmp;
}
//如果有两个子节点
if (2 * tmp + 1 <= this.m_openCount)
{
//如果第二个子节点F值更小
if(this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
{
//更新节点新位置为第二个子节点位置
checkIndex = 2 * tmp + 1;
}
}
}
//如果节点位置没有更新结束排序
if (tmp == checkIndex)
{
break;
}
//反之和新位置交换，继续和新位置的子节点比较F值
else
{
change = this.m_openList[tmp - 1];
this.m_openList[tmp - 1] = this.m_openList[checkIndex - 1];
this.m_openList[checkIndex - 1] = change;
}
}
}
其中 getScore() 方法：
/**
* 获取某节点的路径评分F值
* @param p_index 节点在开启列表中的索引(从1开始)
*/
private function getScore(p_index : int) : int
{
//开启列表索引从1开始，ID从0开始，数组索引从0开始
return this.m_pathScoreList[this.m_openList[p_index - 1]];
}
经典论坛讨论:
http://bbs.blueidea.com/thread-2738527-1-1.html
