A* 寻路非常慢

Question

我为android写了一个寻路算法。运行ning 似乎很慢，我不明白为什么。我以前问过类似的问题，但没有得到我想要的答案（从那以后我更改了代码）。这是我的寻路 class :

public class Pathfinding {

    private static Node[][] grid;

    private static NodeComparator nodeComparator;

    static{
        nodeComparator = new NodeComparator();
    }

    public static class NodeComparator implements Comparator<Node> {

        @Override
        public int compare(Node node1, Node node2) {

            if(node1.F > node2.F){
                return 1;
            }
            else if(node1.F < node2.F){
                return -1;
            }
            else{
                return 0;
            }

        }
    }

    public static Array<Node> findPath(Node start, Node finish, Node[][] _grid) {

        Array<Node> path = new Array<Node>();
        Array<Node> openList = new Array<Node>();
        Array<Node> closedList = new Array<Node>();

        grid = _grid;

        if(start == null){

            return path;
        }
        if(finish == null){

            return path;
        }

        Node currentNode = start;
        currentNode.G = 0;
        currentNode.H = getHeuristic(currentNode, finish);
        currentNode.parent = null;
        openList.add(currentNode);

        System.out.println("PATHFINDING STARTED ||| startPos : " + start.position + " finishPos : " + finish.position);

        while (openList.size > 0) {

            //Sorts open nodes lowest F value to heighest
            openList.sort(nodeComparator);

            currentNode = openList.first();

            //If path is found, return
            if (currentNode == finish) {
                System.out.println("PATH FOUND...RETURNING -gat5");

                return constructPath(currentNode);
            }

            openList.removeValue(currentNode, true);
            closedList.add(currentNode);

            int counter = 0;
            for (Node neighbor : getNeighbors(currentNode)) {
                if (!closedList.contains(neighbor, true)) { //If neighbor not in closed list
                    if(neighbor != null) { //If neighbor not wall

                        if(counter == 4){
                            counter++;
                        }

                        int movementCost = checkMovementCost(counter);

                        if (openList.contains(neighbor, true)) {
                            if (currentNode.G + movementCost < neighbor.G) {
                                neighbor.parent = currentNode;
                            }
                        } else {
                            openList.add(neighbor);
                            neighbor.parent = currentNode;
                            neighbor.H = getHeuristic(currentNode, finish);
                            neighbor.G = neighbor.parent.G + movementCost;
                        }
                        counter++;
                    }
                }
            }

            System.out.println(counter);

        }

        System.out.println("NO FINAL");
        System.out.println("NO PATH FOUND RETURNING...");
        path.add(start);
        return path;

    }

    private static int checkMovementCost(int neighbor) {
        int movementCost = 0;
        switch (neighbor) {
            //Diagonal
            case 0:
            case 2:
            case 6:
            case 8:
                movementCost = 16;
                break;
            //Not Diagonal
            case 1:
            case 3:
            case 5:
            case 7:
                movementCost = 10;
                break;
        }

        return movementCost;
    }

    public static Array<Node> constructPath(Node finish) {
        Array<Node> pathNodes = new Array<Node>();

        Node currentNode = finish;
        pathNodes.add(currentNode);

        while (currentNode.parent != null) {
            currentNode = currentNode.parent;
            pathNodes.add(currentNode);
        }

        return pathNodes;
    }

    private static float getHeuristic(Node start, Node finish){
        int H = 0;

        H += Math.abs(start.position.x - finish.position.x);
        H += Math.abs(start.position.y - finish.position.y);

        return H;
    }

    private static Array<Node> getNeighbors(Node node){
        Array<Node> neighbors = new Array<Node>();

        int x = (int)node.position.x;
        int y = (int)node.position.y;

        if(x - 1 > 0 && x - 1 < grid.length && y + 1 < grid.length && y + 1 > 0){
            neighbors.add(grid[x - 1][y + 1]);
        }
        else{
            neighbors.add(null);
        }
        if(x > 0 && x < grid.length && y + 1 < grid.length && y + 1 > 0){
            neighbors.add(grid[x][y + 1]);
        }
        else{
            neighbors.add(null);
        }
        if(x + 1 > 0 && x + 1 < grid.length && y + 1 < grid.length && y + 1 > 0){
            neighbors.add(grid[x + 1][y + 1]);
        }
        else{
            neighbors.add(null);
        }


        if(x - 1 > 0 && x - 1 < grid.length && y < grid.length && y > 0){
            neighbors.add(grid[x - 1][y]);
        }
        else{
            neighbors.add(null);
        }
        if(x > 0 && x < grid.length && y < grid.length && y > 0){
            neighbors.add(grid[x][y]);
        }
        else{
            neighbors.add(null);
        }
        if(x + 1 > 0 && x + 1 < grid.length && y < grid.length && y > 0){
            neighbors.add(grid[x + 1][y]);
        }
        else{
            neighbors.add(null);
        }


        if(x - 1 > 0 &&  x - 1 < grid.length && y - 1 < grid.length && y - 1> 0){
            neighbors.add(grid[x - 1][y - 1]);
        }
        else{
            neighbors.add(null);
        }
        if(x > 0 && x < grid.length && y - 1 < grid.length && y - 1 > 0){
            neighbors.add(grid[x][y - 1]);
        }
        else{
            neighbors.add(null);
        }
        if(x + 1 > 0 && x + 1 < grid.length && y - 1 < grid.length && y - 1 > 0){
            neighbors.add(grid[x + 1][y - 1]);
        }
        else{
            neighbors.add(null);
        }

        return neighbors;

    }

}

非常感谢您的帮助！

**更多信息：**当我只运行这个算法一次时，它工作正常。但是一旦我运行它 3 次以上，它就会开始快速丢失帧率。我使用的网格是 200x200。

Answer 1

如果您对路径的评估像您指出的那样简单，那么算法的缓慢可能与您在算法的每次迭代中所做的排序有关。

        //Sorts open nodes lowest F value to heighest
        openList.sort(nodeComparator);

仅使用 PriorityQueue 来命令要由算法扩展的节点会导致更有效的实现。如果需要，请查看 the A* algorithm implemented in the library hipster4j 的实现细节。这也适用于 Android。

希望我的回答对您有所帮助。

A* 寻路非常慢

A* Pathfinding very slow

java

android

optimization

a-star