1

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

一个*

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，它们就不再正确行走，所以我不知道这里出了什么问题。

4

1 回答 1

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;
}

祝你好运..

于 2013-08-26T08:55:03.643 回答