3

解決済み:申し訳ありません。パスを不適切に再構築していました。closedSet には最初から最後まですべてのウェイポイントしかないと思っていましたが、他のウェイポイントもいくつかあります。私は概念を理解していません。今では正常に動作しています！

私はまだA *に問題があります。

私のキャラクターは自分のパスを見つけていますが、マップ上のどこをクリックしたかによって、アルゴリズムが最短パスまたはパスを見つけることがありますが、選択すべきではない多くのノードがあります。

WikipediaとA* Pathfinding for Beginner's implementationに従おうとしましたが、同じ結果が得られました。ヒューリスティックなのかアルゴリズム自体なのかはわかりませんが、何かがおかしいです。

これは、2 つの異なるノードをクリックする際の問題の例です: http://i.imgur.com/gtgxi.jpg

Pathfind クラスは次のとおりです。

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

public class Pathfind {
public Pathfind(){

}

public ArrayList<Node> findPath(Node start, Node end, ArrayList<Node> nodes){

    ArrayList<Node> openSet = new ArrayList<Node>();
    ArrayList<Node> closedSet = new ArrayList<Node>();

    Node current;

    openSet.add(start);

    while(openSet.size() > 0){

        current = openSet.get(0);

        current.setH_cost(ManhattanDistance(current, end));

        if(start == end) return null;           
        else if(closedSet.contains(end)){
            System.out.println("Path found!");
            return closedSet;
        }

        openSet.remove(current);
        closedSet.add(current);

        for(Node n : current.getNeigbours()){           
            if(!closedSet.contains(n)){     
                if(!openSet.contains(n) || (n.getG_cost() < (current.getG_cost()+10))){ 
                    n.setParent(current);
                    n.setG_cost(current.getG_cost()+10);
                    n.setH_cost(ManhattanDistance(n, end));

                        if(!openSet.contains(n))
                            openSet.add(n);

                    Collections.sort(openSet);
                }
            }
        }
    }       

    return null;
}

private int ManhattanDistance(Node start, Node end){
    int cost = start.getPenalty();

    int fromX = start.x, fromY = start.y;
    int toX = end.x, toY = end.y;

    return cost * (Math.abs(fromX - toX) + Math.abs(fromY - toY));
}

}

4

2 に答える 2

1

バグは次の条件にあると思います。

if(n.getCost() < current.getCost()){

g(node)+h(node)コスト（ ）が現在から減少している場合は、前進を妨げるべきではありません。この反例を見てください:(Sはソースで、Tはターゲットです）

_________
|S |x1|x2|
----------
|x3|x4|x5|
---------
|x6|x7|T |
----------

さて、あなたがSにいると仮定すると、まだ移動していないので、g(S) =0マンハッタン距離ヒューリスティックの下で、、h(S) = 4f(S)=4

さて、見てみましょx1,x3う：あなたがそれぞれに一歩を踏み出していると仮定すると、彼らはを持っているでしょうg(x1)=g(x3)=1、そして両方がh(x1)=h(x3)=3同じヒューリスティックの下にあるでしょう。その結果、f(x1)=f(x3)=4-およびif条件によって何も「開かない」ようになります。したがって、反復を終了すると、S何もプッシュせずにopen検索が終了します。

補足として： as
の選択は効率的ではないと思います。各操作は（ここで、は閉じたノードの数です）です。パフォーマンスを向上させるには、を使用する必要があります-Aは賢明な選択であり、挿入の順序を維持したい場合は、を使用する必要があります。（オーバーライドする必要があることに注意してください）closedSetArrayListcontains()O(n)nSetHashSetLinkedHashSetequals()hashCode()Node

于 2012-09-14T08:45:57.347 に答える
0

あなたのユニットは上/下/左/右だけを歩きますか、それとも対角線も取ることができますか?

A* ヒューリスティックの 1 つの要件は、それが許容可能であることです。つまり、実際のパス長を過大評価してはなりません。ユニットが斜めに歩くことができる場合、manhatten-distance は経路長を過大評価するため、A* が機能する保証はありません。

于 2012-09-14T06:11:04.420 に答える