AIとゲーム——豆を食べる人(3)基本的な経路計画アルゴリズム(上)

2699 ワード

今回はコードに含まれるいくつかのパスプランニングアルゴリズムについてお話しします.このゲームでは、パスプランニングは人工知能ではありませんが、AIアルゴリズムを確実に実現するための基礎的な方法について、主な方法とこれらの方法の実現について概説します.
(1)getApproximateNextMoveTowardsTarget:これは開始点から目標点までの大まかな動きを得ることを実現しているが,なぜ大まかと呼ぶのか,ここでは障害物などの要因を考慮していないからである.この関数はA*アルゴリズムにも使用できます(A*アルゴリズムは後で専門に説明します).コードは次のとおりです.

public MOVE getApproximateNextMoveTowardsTarget(int fromNodeIndex, int toNodeIndex,
            MOVE lastMoveMade, DM distanceMeasure) {
        MOVE move = null;

        double minDistance = Integer.MAX_VALUE;

        for (Entry entry : currentMaze.graph[fromNodeIndex].allNeighbourhoods.get(
                lastMoveMade).entrySet()) {
            double distance = getDistance(entry.getValue(), toNodeIndex, distanceMeasure);

            if (distance < minDistance) {
                minDistance = distance;
                move = entry.getKey();
            }
        }

        return move;
    }

パラメータは、開始点、ターゲット点、前回の運動方向、距離メトリック方法です.ここに前回の運動方向をパラメータとして、正直に言うと、このforループの条件文は非常に分かりにくいと言えますが、実はallNeighbourhoodsここはMAPの中にまたMAPがネストされていて、正確には>という形式で、最初のMOVEはfromNodeへの移動が可能で、2つ目はfromNodeが実行できる移動と、その移動を実行して到着した点であるが、前のMOVEは含まれていない.例えば、左上隅座標(0,0)の点について、到達可能な移動は(0,1)から左へ、(1,0)から上へ、または(0,0)で動かないため、最初のMOVEはleft,up,neutralの3つ(neutralは特定の場合のみ実行されるので後で考慮しない)であり、leftについてはleft->であり、だからleftのvalueを巡ると、rightという値はなく、下へ行くしかなく、同じ理屈でup->です.これにより、経路選択時に前の移動を考慮する必要がなくなります.次に、前のステップを除くすべての歩行可能な点を取得し、目標点とのオーステナイト距離を求め、距離が最も小さいものに対応するMOVEが選択される.
(2)getNextMoveTowardsTarget:これは以前との差は多くなく、この考えのMOVEは前のステップのMOVEを考えているのとは異なり、つまりfromNodeについては、すべての走行可能な方向が距離の計算に使われている.前回は主に悪魔の到着目標路線計画に用いられ、この一般ユーザーは豆人を食べた.

for (Entry entry : currentMaze.graph[fromNodeIndex].neighbourhood.entrySet())

ここでは異なるループ文のみが与えられ,従来のallNeighbourhoodsからneighbourhoodとなり,後者は構造がであり,歩き方と到達可能な点からなるMAPである.
(3)getApproximateNextMoveAwayFromTarget:これは最初とあまり差がありませんが、前に求めたのは最小距離で、これは最大距離を求めます.
(4)getNextMoveAwayFromTarget:これは説明しないで、考えてみても違いがわかります...
以上が大まかな方向を得る方法ですが、正確な経路を得る方法はありますか?もちろんありますが、次の部分に置いてからにしましょう.

ヒープソート(再帰的でない)

HDU-6184-counting Stars(広西招待試合C題)(データ構造最適化)