修复PathFinding代码

Question

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

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|

所以基本上它并不是在计算总价值。它只是增加了移动成本，而不是启发式的。

这是什么问题？我是不是漏掉了一步？

Answer 1

我认为你错过了继任者名单。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);
    }

最后但并非最不重要的是，您需要从openlist中删除Q音符，并将其添加到close ist中。

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

一些更小的改进是，您确实向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;
}

还要覆盖它的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可以是一个PriorityQueue<Node>，并且您从得到的第一个对象总是带有最小h的那个。

别忘了返回我们的final Node来遍历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;
}