0

我有这个路径查找代码，它只通过一个正方形来完成查找的第一部分

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();

    }

这是我的节点类

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

You are missing the Successor list i think. An A* does have a Successorlist and while the openlist isnt empty you do the following stuff:

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);
    }

Last but not least you do delete the q note from the openlist and add it to the close ist.

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

Some more minor improvmements would be that you do add a compareable to the Node..

@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;
}

also override the equals and the hashCode method for it for example like this:

    @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;
    }

After that your openList can be a PriorityQueue<Node> and the first object you are getting from the is always the one with the smallest h.

Dont forget to return our final Node to iterate over the getparent method to get the path.

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 回答