Java实现A*路径规划算法陷入无限循环的问题排查与解决

背景 #

正在2D斜视角（isometric）游戏中实现A*路径规划算法，此前在标准网格游戏中已成功实现，但本次仅部分成功。已完成笛卡尔坐标与网格坐标的转换，当前基于网格系统开发。

问题现象 #

短距离移动（约6-8个格子）或连续小步移动均正常，但长距离移动时程序完全冻结，经确认是寻路算法导致。推测算法错误判断路径代价，偏离正确路径，冻结时长超过30秒（未等待至是否自行结束）。当前仅采用4方向邻接节点，理论计算代价应很小，不应引发冻结。

注意事项 #

因斜视角游戏特性，坐标采用float类型，但通过取整处理，角色移动后的位置始终对应整数网格坐标；节点并非预定义，而是从当前节点动态生成子节点，仅需返回角色移动的坐标列表作为路径。

相关代码 #

PathFinder类 #

public class PathFinder {

private Node nodeStart;
private Node nodeGoal;
private float cost = 10f;


Set<Node> open = new HashSet<>();
Set<Node> closed = new HashSet<>();

public PathFinder(Node start, Node goal){
    this.nodeStart = start;
    this.nodeGoal = goal;
    open.add(nodeStart);
}

public List<Node> findPath(){

    while (!open.isEmpty()){
        Node currentNode = open.stream().min(Comparator.comparing(Node::getF)).get();
        open.remove(currentNode);
        closed.add(currentNode);
        if(currentNode.equals(nodeGoal)){
            return reversePath(currentNode);
        }
        else{
            for(Node child : getAdjacents(currentNode)){
                if(!child.isBlock() && !closed.contains(child)) {
                    child.setNodeData(currentNode, cost);
                    open.add(child);
                }
                else{
                    boolean changed = child.checkBetterPath(currentNode, cost);
                    if (changed) {
                        // Remove and Add the changed node, so that the PriorityQueue can sort again its
                        // contents with the modified "finalCost" value of the modified node
                        open.remove(child);
                        open.add(child);
                    }
                }
            };
        }

    }
    return new ArrayList<>();
}

private List<Node> getAdjacents(Node currentNode){
    ArrayList<Node> children =  new ArrayList<>();

    children.add(new Node(currentNode.getX()+1, currentNode.getY(), currentNode, nodeGoal));
    children.add(new Node(currentNode.getX()-1, currentNode.getY(), currentNode, nodeGoal));
    children.add(new Node(currentNode.getX(), currentNode.getY() - 1, currentNode, nodeGoal));
    children.add(new Node(currentNode.getX(), currentNode.getY() + 1, currentNode, nodeGoal));

    return children;
}

public List<Node> reversePath(Node goal){
    List<Node> finalPath = new ArrayList<>();
    Node tmp;
    Node current;
    current = goal;
    while(current.getParent() != null){
        finalPath.add(0, current);
        current = current.getParent();
    }
    return finalPath;
}}

Node类 #

public class Node {

private boolean isBlock;
private Node parent;
private float x;
private float y;

private float g;
private float f;
private float h;

Node finalNode;

public Node(float x, float y){
    this.x = x;
    this.y = y;
}
public Node(float x, float y, Node parent, Node finalNode){
    this.x = x;
    this.y = y;
    this.parent = parent;
    this.finalNode = finalNode;
    calculateHeuristic(finalNode);
}

public void calculateHeuristic(Node finalNode) {
    this.h = Math.abs(finalNode.getX() - getX()) + Math.abs(finalNode.getY() - getY());
}
public void setNodeData(Node currentNode, float cost) {
    float gCost = currentNode.getG() + cost;
    setParent(currentNode);
    setG(gCost);
    calculateFinalCost();
}

public boolean checkBetterPath(Node currentNode, float cost) {
    float gCost = currentNode.getG() + cost;
    if (gCost < getG()) {
        setNodeData(currentNode, cost);
        return true;
    }
    return false;
}

private void calculateFinalCost() {
    float finalCost = getG() + getH();
    setF(finalCost);
}

public float getX() {
    return x;
}

public float getY() {
    return y;
}

public Node getParent() {
    return parent;
}

public boolean isBlock() {
    return isBlock;
}

public void setBlock(boolean block) {
    isBlock = block;
}

public void setParent(Node parent) {
    this.parent = parent;
}

public void setX(float x) {
    this.x = x;
}

public void setY(float y) {
    this.y = y;
}

public float getG() {
    return g;
}

public void setG(float g) {
    this.g = g;
}

public float getF() {
    return f;
}

public void setF(float f) {
    this.f = f;
}

public float getH() {
    return h;
}

public void setH(float h) {
    this.h = h;
}
@Override
public boolean equals(Object arg0) {
    Node other = (Node) arg0;
    return this.getX() == other.getX() && this.getY() == other.getY();
}

@Override
public String toString() {
    return "Node [row=" + x + ", col=" + y + "]";
}}

Main类 #

public class Main {
public static void main(String[] args) {
    PathFinder pathFinder = new PathFinder(new Node(1,1), new Node(14,1));

    List<Node> path = pathFinder.findPath();
    System.out.println(path);
}}

解决方案 #

最初通过自定义移除函数解决了部分问题，但超远距离（如100+格子）仍会冻结。经调试发现问题根源在于private float cost = 10f;：实际每次仅移动1格，该设置过度放大了路径代价权重，削弱了启发式值的引导作用。将其修改为private float cost = 1f;后，长距离寻路的冻结问题彻底解决。

内容的提问来源于stack exchange，提问作者user2592518