对角启发函数
private function diagonal(node:Node):Number
{
var dx:Number = Math.abs(node.x - _endNode.x );
var dy:Number = Math.abs(node.y - _endNode.y);
var diag:Number = Math.min(dx,dy);
var straight:Number = dx + dy;
return _diagCost * diag + _straightCost * (straight – 2 * diag);
}
对角启发函数解释:对角启发函数计算出从起始
节点到终止节点x 轴,y 轴变化数的绝对值dx ,
dy 。
Diag 为dx,dy 中的小值,为了使选择的路径
最短必须走diag 次数个对角,剩下的|dx - dy|次
全都水平或者竖直移动。
那么,该节点的f 值就
是diag 乘以 2加上|dx - dy|*1。
A*算法解释:首先检查起始节点周围节点的f 值,
如果该节点属于已查列表或者待查列表,那么如
果计算出的f 值比该节点原有的f 属性值小,则
将该值用新计算出来的f 值替代。
这样做是为了防止从当前节点移至下一个节点并重新计算其周围节点的f 值时,出现已查列表中的某个节点原有f 属性比新计算出来的大。
这时,我们就需要重新修正该节点的f 值,以保证准确。
虽然,我现在还不知道不这样做会出现什么错误,但这样做至少保证每一步都是没有差错的,绝对正确的。
所以建议你每次都检查,并修正已查列表中被重新计算f 值的节点的f 值。
倘若该节点不在已查列表或者待查列表之中那么给该节点的f 值赋值,并将该节点添加到待查列表中,并将当前节点添加到已查列表。
等将周围的节点全部计算完后,取已查列表中f 值最小的节点作为下一个初始节点,并将当前节点添加到路径数组中。
接着重复执行上面的操作直到到达终止节点停止。
但是
有一种情况被忽略了,如下图所示,初始节点找到f 值最小的节点1并将其设置为当
前节点,1节点找到f 值最小的2节点并将其设置为当前节点,到3节点时因为前面
黑色区域不能穿过,又返回到2节点,2节点有找到3
节点,如此循环。
这是改程序
的一个漏洞,有待改进。