2013-07-04 342 views
0

我最近在Lua中實現了A *尋路,但是由於在成本中使用曼哈頓方法,我遇到了不好的路徑。A *在Lua尋找路徑

我想知道是否有計算節點的成本的任何其他方法。以下是我目前正在使用:

function CalcG(A,B) 
    if type(A) == "table" then 
     A = A.Pos 
    end 
    if type(B) == "table" then 
     B = B.Pos 
    end 
    return (A-B).Magnitude 
end 

function CalcH(A,B) 
    if type(A) == "table" then 
     A = A.Pos 
    end 
    if type(B) == "table" then 
     B = B.Pos 
    end 
    return math.abs(A.X - B.X) + math.abs(A.Z - B.Z) 
end 

function GetCost(A,B,C) 
    return CalcG(A,B) + CalcH(B,C) 

end 

,並計算成本:

GetCost(Start,CurrentNode,End) 

如果有人能指導我走向更美好的啓發式方法,我將不勝感激。

+3

使用啓發式曼哈頓不應導致這條道路。我想你可能還有其他問題。 – WuTangTan

回答

0

(注:WuTangTan在評論中說什麼仍然適用,這看起來像在您的實現,以及一個bug)

正確A *的實施是保證,只要找到最短路徑啓發式是可接受,或不高估路徑的實際成本(有關更多詳細信息,請參閱Wikipedia's entry on A*)。對於無法對角移動的網格,曼哈頓距離滿足此條件。但從你的形象來看,它看起來像你也可以沿對角線移動,所以曼哈頓距離不再準確地判斷距離。想想這樣的畫面:

Example image

藍是曼哈頓距離,綠色是「正確」的距離。如你所見,當我們增加對角移動的能力時,兩點之間的距離變短。曼哈頓距離現在高估了距離,現在不被接受,導致A *不總是找到最短路徑。

那麼有沒有一種啓發式方法可以用來建模對角線網格運動?你打賭!它叫做Chebyshev distance。它考慮了對角線運動,所以在這種情況下建模距離會更好。想象棋盤上的國王。

它的實現很簡單:

function chebyshevDistance(dx, dy) 
    return math.max(dx, dy) 
end