1

最近、Lua で A* パスファインディングを実装しましたが、コストの H にマンハッタン方式を使用しているため、パスが正しくありません。

ノードのコストを計算する他の方法があるかどうか知りたいです。これが私が現在使用しているものです：

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)

誰かがより良いヒューリスティックな方法に向けて私を導くことができれば、私はそれを感謝します.

4

1 に答える 1

0

（注：コメントでWuTangTanが言っていることはまだ適用されます。これは実装のバグのようにも見えます）

適切な A* 実装は、ヒューリスティックが許容できる限り、またはパスの実際のコストを過大評価しない限り、最短パスを見つけることが保証されます (詳細については、A* に関するウィキペディアのエントリを参照してください)。斜めに移動できないグリッドの場合、マンハッタン距離はこの基準を満たします。しかし、あなたの画像から判断すると、斜めにも移動できるように見えるため、マンハッタン距離は距離を正確に判断できなくなりました。この図を考えてみましょう:

サンプル画像

青はマンハッタン距離、緑は「正しい」距離です。

ご覧のとおり、斜めに移動する機能を追加すると、2 点間の距離が短くなります。マンハッタンの距離は距離を過大評価するようになり、許容されなくなりました。その結果、A* は必ずしも最短経路を見つけるとは限りません。

では、斜めのグリッドの動きをモデル化するために使用できるヒューリスティックはありますか? あなたは賭けます！チェビシェフ距離といいます。斜めの動きが考慮されるため、このシナリオでの距離のモデリングにははるかに適しています。チェス盤のキングを思い浮かべてください。

その実装は簡単です:

function chebyshevDistance(dx, dy)
    return math.max(dx, dy)
end
于 2013-07-25T04:37:22.993 に答える