java - 寻路问题。返回的奇怪路径

Question

我一直在阅读一些文章来学习 A* 寻路，并且我能够基于它制作一个测试程序，但是我制作的程序给出了奇怪的路径，这不是到目标节点的最短路径。

图中，绿色方 block 单元代表起始节点，红色单元代表目标节点，蓝色单元为不可通行的瓷砖(墙)，紫色单元代表从起始节点到目标节点找到的路径

/image/xwhuk.jpg

/image/B0WxU.jpg

如果有人能发现寻路源代码的问题，我将非常感激。我因为想知道是什么原因导致它表现得很奇怪而精疲力竭。

允许走捷径和走对角线

package com.streak324.pathfinding;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

import com.badlogic.gdx.utils.Array;

public class PathFinder {

    private boolean foundTarget;
    private int width, height;

    //list of nodes that leads from starting node to target node is stored here
    private Array<PathNode> path;

    //all nodes stored in this array
    private PathNode[][] nodes;

    private PriorityQueue<PathNode> open;

    private HashSet<PathNode> closed;

    //nodes that must be referenced
    private PathNode start, target, current;

    //how far the current node can reach for other nodes from its own position
    private int range = 1;

    public PathFinder(int width, int height, boolean map[][]) {
        this.width = width;
        this.height = height;
        nodes = new PathNode[width][height];

        for(int i=0; i<width; i++) {
            for(int j=0; j<height; j++) {
                nodes[i][j] = new PathNode(i, j);
                //if wall tile is spotted, mark the node unwalkable
                if(map[i][j] != true) { nodes[i][j].passable = false; }
            }
        }

        open = new PriorityQueue<PathNode>(new CostComparator());
        closed = new HashSet<PathNode>();
    }

    public Array<PathNode> getPath(int sx, int sy ,int tx, int ty) {
        path = new Array<PathNode>();
        open.clear();
        closed.clear();

        start = nodes[sx][sy];
        start.movementCost = 0;
        addToOpenList(start);

        target = nodes[tx][ty];

        while(foundTarget != true) {
            if(open.size() == 0) { return null; }

            current = open.poll();
            addToClosedList(current);

            checkNeighbors(current);
        }

        traceBack();

        return path;
    }
    // makes its way back adding the parent node until start
    private void traceBack() {
        while(current != start) {
            path.add(current);
            current = current.parent;
        }
    }

    //checks for nodes within certain range
    private void checkNeighbors(PathNode node) {
        //continues loop if i or j goes out of bounds of nodes array
        for(int i = node.x - range; i <= (node.x + range); i++) {

            if(i >= width || i < 0) { continue; }
            for(int j = node.y - range; j <= (node.y + range); j++) {

                if( j >= height || j < 0) { continue; }

                if((i == node.x && j == node.y) )  { continue; }

                PathNode neighbor = nodes[i][j];

                identifyNode(neighbor);

            }
        }
    }

    //if node is not on open list, add node and calculate it
    private void identifyNode(PathNode node) {
        if(!node.passable || closed.contains(node) ) return;

        if(node == target) {
            foundTarget = true;
            System.out.println("Target Found: " + node.x + ", " + node.y);
            return;
        }
        else if(!open.contains(node)) {
            addToOpenList(node);
            calcHeuristic(node);
            updateNode(node, current);
        }
        else {
            checkForReparenting(node);
        }
    }

    //is the movement cost less to go from the current node?
    private void checkForReparenting(PathNode node) {
        float cost = node.movementCost;
        float reCost = calcMovementCost(node, current);

        if(reCost < cost) {
            System.out.println("Reparenting");
            updateNode(node, current);
        }
    }

    //updates parent and cost
    private void updateNode(PathNode child, PathNode parent) {
        child.parent = parent;
        child.movementCost = calcMovementCost(child, parent);       
        child.totalCost = child.movementCost + child.heuristic;
    }

    private float calcMovementCost(PathNode n1, PathNode n2) {
        float dx = n1.x - n2.x;
        float dy = n1.y - n2.y;
        return (float) Math.sqrt( (dx*dx + dy*dy) ) + n2.movementCost;
    }

    private float calcHeuristic(PathNode node) {
        float dx = node.x - target.x;
        float dy = node.y - target.y;
        return (float) Math.sqrt( (dx*dx + dy*dy) );
    }

    private void addToOpenList(PathNode node) {
        if(!open.contains(node) && !closed.contains(node)) {
            open.add(node);
        }
    }

    private void addToClosedList(PathNode node) {
        if(!closed.contains(node)) {
            closed.add(node);
        }
    }

    public class PathNode {
        public int x, y;
        public PathNode parent;
        //g, h and f
        public float movementCost, heuristic, totalCost;
        public boolean passable;

        public PathNode(int x, int y) {
            this.x = x;
            this.y = y;
            passable = true;
        }

    }

    private class CostComparator implements Comparator<PathNode> {

        @Override
        public int compare(PathNode a, PathNode b) {

            if(a.totalCost < b.totalCost) return 1;
            else return -1;
        }

    }

}

没有评论 http://pastebin.com/rSv7pUrB

我猜测优先级队列对元素进行排序的方式有问题，或者我可能没有正确计算出总成本、移动成本和启发式变量，但我认为没有任何问题。

非常感谢能够为我指出可能的问题或解决方案的正确方向的人

Answer 1

您的代码存在几个问题:

1. 你从来没有真正使用过启发式方法。以下语句(对 calcHeuristic 的唯一调用)只是“丢弃结果”。

   calcHeuristic(node);
   

   仅此一点不可能是这里的错误，因为猜测到目标的距离是 0 是一个有效的可接受的启发式方法。 。然而，该算法会以这种方式退化(我认为是 Dijkstra 算法)。

2. 您永远不会更新优先级队列中节点的位置。这意味着节点已更新 totalDistance永远不会在优先队列中向上移动，即使它是 totalCost变得小于totalCost另一个节点的。您必须删除该节点并再次添加它才能使用 PriorityQueue 执行此操作。 :

   open.remove(node);
   // ... update totalDistance
   open.add(node);
   

3. 对于一般 A* 而言，您终止得太早(但是，这在这里不会成为问题，因为 totalDistance 等于实际距离，对于目标的扩展邻居IF，您使用启发式；此处距离实际距离与 sqrt(2) 或 1 不同)。一般来说，最后一步的距离启发式可能是任意糟糕的(这里是糟糕的，请参见(1.))，并且如果您将算法运行到可以扩展目标节点。