java - A* 如果无法到达某个点则捕获

Question

我实现了一个简单的 A*，并注意到如果我的角色周围的所有 4 个点都被填满，它确实会进入无限循环。目前我不知道如何让它工作，所以他们开始跑到最近的可能地点。有什么猜测吗？ (抱歉代码太长)

A*

private Node aStarSearch(int startX, int startY) {
        openList.clear();
        closeList.clear();
        successor.clear();
        Node startNode = new Node(null, startX, startY, 0, 0);
        openList.add(startNode);
        while (openList.size() != 0) {
            // sort the list
            Collections.sort(openList, nodeComperator);
            Node q = openList.remove(0); // get the first object
            int qx = q.x;
            int qy = q.y;
            // start adding the successors
            // left

            Node left = createNeighbor(q, qx - 1, qy);
            if (left != null && !closeList.contains(left))
                successor.add(left);

            // right
            Node right = createNeighbor(q, qx + 1, qy);
            if (right != null && !closeList.contains(right))
                successor.add(right);

            // // down
            Node down = createNeighbor(q, qx, qy - 1);
            if (down != null && !closeList.contains(down))
                successor.add(down);

            // up
            Node up = createNeighbor(q, qx, qy + 1);
            if (up != null && !closeList.contains(up))
                successor.add(up);

            // calc
            for (Node suc : successor) {
                if (suc.x == (int) this.screen.character.mapPos.x
                        && suc.y == (int) this.screen.character.mapPos.y)
                    return suc;
                boolean add = true;
                if (betterIn(suc, openList)) // openList und der
                    add = false;
                if (betterIn(suc, closeList)) // closedList
                    add = false;
                if (add)
                    openList.add(suc);
            }
            closeList.add(q);
        }
        return null;
    }
   private Node createNeighbor(Node parrent, int x, int y) {
        if (x >= 0 && y >= 0 && x < this.screen.map.width
                && y < this.screen.map.height
                && this.screen.map.mapArray[x][y] != Config.CANTMOVEONPOSITION
                && this.screen.map.mapArray[x][y] != Config.MONSTERSTATE) {
            Node n = new Node(parrent, x, y);
            n.g = calcG(n);
            n.h = calcH(n, (int) this.screen.character.mapPos.x,
                    (int) this.screen.character.mapPos.y);
            return n;
        }
        return null;
    }

    private float calcG(Node n) {
            Node p = n.getParrent();
            return p.g + 1;
        }

        private float calcH(Node n, int targetX, int targetY) {
            float dx = Math.abs(n.x - targetX);
            float dy = Math.abs(n.y - targetY);
            return (float) Math.sqrt((float) (dx * dx) + (dy * dy));
        }

        private boolean betterIn(Node n, List<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;
        }

我的节点:

public class Node {
    public int x, y;
    public float g, h;
    private Node parrent;

    public Node(Node parrent, int x, int y, float g, float h) {
        this.parrent = parrent;
        this.x = x;
        this.y = y;
        this.g = g;
        this.h = h;
    }

    public Node(Node parrent, int x, int y) {
        this.parrent = parrent;
        this.x = x;
        this.y = y;
    }

    public Node getParrent() {
        return parrent;
    }

    public void setParrent(Node parrent) {
        this.parrent = parrent;
    }
    @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() {
        // if x and y are the same they are the same
        return x + y;
    }
}

如果我确实使用被阻止的节点，但给它们一个高 h，它们就不再正确行走，所以我不知道这里出了什么问题。

Answer 1

你的 A* 算法看起来有点奇怪。但代码不是很清楚——对于 UP、DOWN、LEFT、RIGHT，您重复相同的部分(应该分解为一个方法)。

尚不清楚“发现的”节点是否被清楚地表示——它们应该是一个集合——而你有“开放”、“封闭”和“后继”。

检查每个 UP、DOWN、LEFT、RIGHT 邻居应分解为一个方法，您使用 neighborX 和 neighborY 位置调用该方法 4 次。

没有一条明确的线可以正确测试给定邻居(它是邻居，而不是后继者)是否已被“发现”。

我也不确定后继者的后处理。可视化:

        // calc
        for (Node suc : successor) {
            if (suc.x == (int) this.screen.character.mapPos.x
                    && suc.y == (int) this.screen.character.mapPos.y)
                return suc;
            boolean add = true;
            if (betterIn(suc, openList)) // openList und der
                add = false;
            if (betterIn(suc, closeList)) // closedList
                add = false;
            if (add)
                openList.add(suc);
        }

由于您在每次迭代时对“开放节点”进行排序并选择可能最好的节点，因此这对我来说并没有真正意义并且可能是错误的。

当角色周围的所有四个方向都被阻挡时，算法应该立即终止。未能终止意味着 openList 未正确处理/或添加了不正确的节点。

放入一些 Log4J 日志记录并编写一个简单的单元测试来验证它在这些条件下的正确行为。

<小时/>

我还建议将“createNeighbor”、“发现的检查”和“添加到后继列表”代码滚动到一个方法中 exploreNeighbor( Node q, int offsetX, int offsetY)。

我稍微改进了样式和变量命名。您还应该转向使用 getter —— 例如 getX()、getY()。

exploreNeighbor( q, -1, 0);  // left
exploreNeighbor( q, +1, 0);  // right
exploreNeighbor( q, 0, -1);  // up
exploreNeighbor( q, 0, +1);  // down

protected boolean exploreNeighbor (Node parent, int offsetX, int offsetY) {
    int x = q.getX() + offsetX;
    int y = q.getY() + offsetY;
    if (x < 0 || x >= screen.map.width)
        return null;
    if (y < 0 || y >= screen.map.height)
        return false;
    int content = screen.map.mapArray[x][y];
    if (content == Contents.CANTMOVEONPOSITION ||
            content == Contents.MONSTERSTATE) {
        return false;
    }

    // represent Neighbor Position;
    //  
    Node n = new Node(parent, x, y);
    n.g = calcG(n);
    n.h = calcH(n, (int) this.screen.character.mapPos.x,
            (int) this.screen.character.mapPos.y);

    // check if Discovered yet;
    //
    if (discoveredSet.contains( n)) {
        // already queued or visited.
        return false;
    }

    // queue it for exploration.
    openQueue.add( n);
    return true;
}

祝你好运..