1

私はJavaでA*を実装しようとしていますが、レンガの壁にぶつかり、基本的にこの時点からの進め方がわかりません。

私は現在、ウィキペディアの擬似コードをフォローしています。

私のノードは次のように構成されています。

static class Node {
    int col;
    int row;
    int g;
    int h;
    int f;
    public Node(int col, int row, int g, int h) {
        this.col = col;
        this.row = row;
        this.g = g;
        this.h = h;
        this.f = g+h;
    }
}

fノードの作成時に計算されることに注意することが重要です。

不完全な私の現在のA*コード：

public void makeAstar(MapParser parsedMap) {
        // create the open list of nodes, initially containing only our starting node
        ArrayList<Node> openList = new ArrayList<Node>();
        // create the closed list of nodes, initially empty
        Map closedMap = new Map(rowSize, columnSize, "Closed map");
        // Fill closedMap with 0's
        closedMap.buildMapWithValue(0); 
        // Create neighbourlist
        ArrayList<Node> neighbourList = new ArrayList<Node>();

        // Some vars
        int rowTemp = 0;
        int colTemp = 0;
        int currentCost = 0;
        int tempCost = 0;

        //TODO hardcore cost! rowTemp+colTemp

        // Initialize with the first node
        openList.add(new Node(0,0,9,this.getMapValue(0, 0)));

        while(!openList.isEmpty()) {
            // Consider the best node, by sorting list according to F
            Node.sortByF(openList);
            Node currentNode = openList.get(0);
            openList.remove(0);

            // Stop if reached goal (hardcoded for now)
            if(currentNode.getCol() == 4 && currentNode.getRow() == 4) {
                System.out.println("Reached goal");
                break;
            }

            // Move current node to the closed list
            closedMap.setMapValue(currentNode.getRow(), currentNode.getCol(), 1);

            // Get neighbours
            rowTemp = currentNode.getRow()-1;
            colTemp = currentNode.getCol();
            if(!currentNode.isTopRow()) {  // Add value ^
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            } 

            rowTemp = currentNode.getRow();
            colTemp = currentNode.getCol()-1;
            if(!currentNode.isRightColumn()) { // Add value <
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            }

            rowTemp = currentNode.getRow();
            colTemp = currentNode.getCol()+1;
            if(currentNode.isLeftColumn()) { // Add value >
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            }

            rowTemp = currentNode.getRow()+1;
            colTemp = currentNode.getCol();
            if(currentNode.isBottomColumn()) { // Add value v
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            }

            // As long as the neighbour list is not empty
            while(!neighbourList.isEmpty()) {
                Node temp = neighbourList.get(0);
                neighbourList.remove(0);

                if(!isNotInClosedMap(temp.getRow(), temp.getCol())) {
                    continue;
                }

                //Stuck here !          

            }   
        }           
    }

for each neighbor in neighbor_nodes(current)最後の行のコメントは、基本的に私が終了した場所です。これは、擬似コードの近くにあるものに相当します。さらにG、それが開始ノードからの総コストであることを理解していますが、この値を計算するにはどうすればよいですか？

Gネイバーの最初の作成時にハードコードされた値を追加することに気付く人もいるかもしれませんがrow+col、これは開始位置がです0,0。

4

1 に答える 1

1

私はあなたが探している計算は次のとおりだと思います：

tentative_g_score := g_score[current] + dist_between(current,neighbor)

これは、これまでに見つかったノードへの最適なパスに沿ってスコアを保存するために各ノードが必要であることを意味します。現在のノードの新しいスコアがあります。目的は、現在のノードを通るパスが隣接ノードの以前の最高スコアよりも優れている場合に、各隣接ノードの最高スコアを更新することです。

アルゴリズムに対するハードコードされたG値の重要性がわかりません。各ノードに到達するための最良のコストをすでに知っている場合は、A*は必要ないと思います。

作業元の擬似コードの識別子と一致するようにフィールドの名前を変更するようにリファクタリングすることを強くお勧めします。これにより、コードが擬似コードとどのように関連しているかを簡単に確認できます。また、擬似コードをコメントとしてインターリーブするのにも役立ちます。

于 2012-11-06T17:08:39.947 に答える