0

私はこのパス検索コードを持っています。これは、検索の最初の部分を1つの正方形だけで実行します

public class PathFinding {

    static Vector2 start;

    static Vector2 end;

    static Cell[][] cells;

    static Node currentNode;

    static Arena arena;

    public static void calcPAth(Vector2 from, Vector2 to,
            Cell[][] mapCells, Arena a) {
        start = from;
        end = to;
        cells = mapCells;
        arena = a;

        List<Node> openList = new ArrayList<Node>();
        List<Node> closedList = new ArrayList<Node>();
        Gdx.app.log(PArena.LOG, "Lists Created");

        currentNode = new Node(null, start);
        openList.add(currentNode);
        Gdx.app.log(PArena.LOG, "Added start to openList");
        // check squares around this and add

        int startPX = (int) currentNode.parentV.x / 32;
        Gdx.app.log(PArena.LOG, "Start X" + startPX);
        int startPY = (int) currentNode.parentV.y / 32;
        Gdx.app.log(PArena.LOG, "Start Y" + startPY);

        Gdx.app.log("", "");
        //
        int MIN_X = startPX - 1;
        int MIN_Y = startPY - 1;
        int MAX_X = startPX + 1;
        int MAX_Y = startPY + 1;

        int startPosX = (startPX - 1 < MIN_X) ? startPX : startPX - 1;
        int startPosY = (startPY - 1 < MIN_Y) ? startPY : startPY - 1;
        int endPosX = (startPX + 1 > MAX_X) ? startPX : startPX + 1;
        int endPosY = (startPY + 1 > MAX_Y) ? startPY : startPY + 1;

        // Check boundaries on start cell
        for (int rowNum = startPosX; rowNum <= endPosX; rowNum++) {
            for (int colNum = startPosY; colNum <= endPosY; colNum++) {
                // All the neighbors will be grid[rowNum][colNum]

                if (!cells[rowNum][colNum].getTile().getProperties()
                        .containsKey("blocked")) {
                    Node node = new Node(currentNode, new Vector2(
                            rowNum, colNum));
                    if (rowNum != startPX && colNum != startPY) {
                        node.setMovementCost(14);
                    } else
                        node.setMovementCost(10);
                    openList.add(node);

                    System.out.print(node.getFValue() + "|");
                } else
                    System.out.print("B");

            }
            System.out.println("");

        }

        openList.remove(currentNode);
        closedList.add(currentNode);
        int n = openList.get(0).getFValue();
        int index = 0;
        for (Node temp : openList) {
            if (temp.getFValue() < n) {
                n = temp.getFValue();
                index = openList.lastIndexOf(temp);
                Gdx.app.log("n", "n = " + n);
            }
        }
        currentNode = openList.get(index);
        arena.colorSquare(currentNode.getVectorPos());

        // need to calc move cost;

        //

        Gdx.app.log("", "");
        openList.clear();
        closedList.clear();

    }

これは私のNodeクラスです

public static class Node {

        int hVal;

        int gVal;

        int fVal;

        Node parentNode;

        Vector2 parentV;

        private Node(Node node, Vector2 p) {
            setParent(node);
            this.parentV = p;
            calcHValue();
        }

        public void setMovementCost(int c) {
            this.gVal = c;
            calcFVal();
        }

        private void calcFVal() {
            fVal = gVal + hVal;
            // Gdx.app.log("Node", "HVal = " + hVal);
            // Gdx.app.log("Node", "GVal = " + gVal);
            // Gdx.app.log("Node", "FVal = " + fVal);
        }

        private void calcHValue() {
            int x = (int) (parentV.x - end.x);
            if (x < 0)
                x *= -1;
            int y = (int) (parentV.y - end.y);
            if (y < 0)
                y *= -1;

            hVal = (int) (x + y) / 32;
            // Gdx.app.log(PArena.LOG, "Heuristic Value" + hVal);
        }

        private void setParent(Node node) {
            this.parentNode = node;
        }

        public int getFValue() {
            return fVal;
        }

        public Vector2 getVectorPos() {
            return parentV;
        }
    }

私の問題は、デバッグが次のように出力されることです

15|11|15|
11|11|11|
15|11|15|

したがって、基本的には合計値を実際に計算するわけではありません。ヒューリスティックではなく、移動コストを追加するだけです。

問題は何ですか？私はステップを逃していますか？

4

1 に答える 1

2

私が思う後継者リストがありません。A* には Successorlist があり、openlist が空でない間に次のことを行います。

while (openList.size() != 0) {
            successor.clear();
            q = openList.remove(); //first element of the prio queue
// generate your neighbornodes of q and add them to the successorlist
//after this you iterate over the successor and check if its your goalnode. 
//If so you do return it else you add it to the openlist. (still inside of the while!)
//Dont forget to check if the neighbor is inside of the close list! 
//if so you do not need to add it to the successorlist



//Here is how it does look at mine A*. It also contains a check if there is a betterone

// calc

    for (Node suc : successor) {
        if (suc.x == (int) this.screen.character.mapPos.x
                && suc.y == (int) this.screen.character.mapPos.y)
            return suc; //return the goalnode
        boolean add = true;
        if (betterIn(suc, openList))
            add = false;
        if (betterIn(suc, closeList))
            add = false;
        if (add)
            openList.add(suc);
    }

最後に、オープン リストから q ノートを削除し、それをクローズ リストに追加します。

            }
            closeList.add(q);
        }//end of while

いくつかのマイナーな改善点は、ノードに比較可能なものを追加することです..

@Override
public int compareTo(Node o) {
    if ((this.g + this.h) < (o.g + o.h))
        return -1;
    else if ((this.g + this.h) >= (o.g + o.h))
        return 1;
    else
        return 0;
}

また、次のように equals と hashCode メソッドをオーバーライドします。

    @Override
    public boolean equals(Object o) {
        // override for a different compare
        return ((Node) o).x == this.x && ((Node) o).y == this.y;
    }

    @Override
    public int hashCode() {
        return x + y;
    }

その後、あなたopenListは aPriorityQueue<Node>になることができ、から得られる最初のオブジェクトは常に最小の h を持つものです。

getparent メソッドを反復処理してパスを取得するために、最終ノードを返すことを忘れないでください。

private boolean betterIn(Node n, Collection<Node> l) {
    for (Node no : l) {
        if (no.x == n.x && no.y == n.y && (no.g + no.h) <= (n.g + n.h))
            return true;
    }
    return false;
}
于 2013-09-10T07:50:39.160 に答える