Java *搜索问题

Question

问题解决了.

我在一个简单的基于网格的游戏中实现了一个路径查找的A*搜索算法。这是我第一次这么做，而且实现大部分时间都很有效。然而，有时(尽管很少)，当有一条可用的路径时，它就会陷入困境。当然，它被卡住了这一事实使它不符合目的。我认为我在执行过程中遗漏了一些东西。

我找了好几天这个问题，但没有结果。我的最后期限快到了，还有很多事情要做，我不想再浪费时间去修复这个错误了。

编辑：--我创建了快速录像来演示这个问题，这样您就可以准确地了解到底发生了什么。它包括标题。

编辑： getPath方法：

/**
 * @param currentPosition - the vector the avatar currently occupies.
 * @param targetPosition - the vector the avatar is aiming to reach.
 * @param levelMap - a clip map of the level.
 * 
 * @return an {@code ArrayList} of {@link ACTIONS} that the avatar can follow to reach its destination.
 **/
public static ActionPath getPath(Vector2d currentPosition, Vector2d targetPosition, LevelMap levelMap) {
    openTiles = new ArrayList<AStarTile>();
    closedTiles = new ArrayList<AStarTile>();
    targetMet = false;

    AStarTile originTile = AStarTile.fromVector(currentPosition, levelMap.getBlockSize()),
             targetTile = AStarTile.fromVector(targetPosition, levelMap.getBlockSize()),
             currentTile = null,
             parentTile = null;

    ActionPath actionPath = new ActionPath(targetTile);

    if (originTile.equals(targetTile)) {
        targetMet = true;
        return null;
    }

    GVGLogger.logInfo("Creating path from tile " + originTile + " to tile " + targetTile + " (" + currentPosition + " to " + targetPosition + ").");

    /*
     * Start the search.
     */
    openTile(originTile);
    originTile.calculateGeneration();// The origin tile will always be generation 0.
    closeTile(originTile);

    parentTile = originTile;

    while(!targetMet) {
        for (int i = 0; i != 4; i++) {
            currentTile = parentTile.move(i);// Checks an adjacent tile - up, down, left, and right respectively

            if (levelMap.inBounds(currentTile) && levelMap.isAccessible(currentTile) && !isClosed(currentTile)) {
                if (isOpen(currentTile)) {
                    // Check to see if this path to this tile is a better one.
                    currentTile = getOpen(currentTile);

                    if (currentTile.getGeneration() > parentTile.getGeneration() + 1) {
                        // The open version's generation is higher than this version's generation - it's a better path
                        currentTile.setParentTile(parentTile);
                        currentTile.calculateGeneration();
                        currentTile.calculateFinalScore();
                    }
                }
                else {
                    currentTile.setParentTile(parentTile);
                    currentTile.setHeuristic(currentTile.distanceSquared(targetTile));
                    currentTile.calculateGeneration();
                    currentTile.calculateFinalScore();
                    openTile(currentTile);
                }
            }
        }

        if (openTiles.size() > 0) {
            parentTile = getBestOption();
            closeTile(parentTile);

            if (parentTile.equals(targetTile)) {
                targetMet = true;
            }
        }
        else {
            GVGLogger.logWarning("Target unreachable!");
            return null;
        }
    }

    //Convert the path of tiles into ACTIONS that the avatar can take to reach it.

    for (int i = 0; i != closedTiles.size(); i++) {
        Vector2i difference = getDifference(closedTiles.get(i), (i != closedTiles.size() - 1 ? closedTiles.get(i + 1) : targetTile));

        if (difference.equals(1, 0)) {
            actionPath.add(ACTIONS.ACTION_LEFT);
        }
        else if (difference.equals(-1, 0)) {
            actionPath.add(ACTIONS.ACTION_RIGHT);
        }
        else if (difference.equals(0, -1)) {
            actionPath.add(ACTIONS.ACTION_DOWN);
        }
        else if (difference.equals(0, 1)) {
            actionPath.add(ACTIONS.ACTION_UP);
        }
        else if (difference.equals(0, 0)) {
            return actionPath;
        }
        else {
            GVGLogger.logWarning("Error in path-finding - found a difference of " + difference + "!");
        }
    }
    return null;
}

private static Vector2i getDifference(AStarTile tileA, AStarTile tileB) {
    return new Vector2i(tileA.getX() - tileB.getX(), tileA.getY() - tileB.getY());
}

public static boolean targetMet() {
    return targetMet;
}

private static void openTile(AStarTile toOpen) {
    if (isClosed(toOpen)) {
        closedTiles.remove(getOpen(toOpen));
    }
    if (!isOpen(toOpen)) {
        openTiles.add(toOpen);
    }
}

private static void closeTile(AStarTile toClose) {
    if (isOpen(toClose)) {
        openTiles.remove(getOpen(toClose));
    }
    if (!isClosed(toClose)) {
        closedTiles.add(toClose);
    }
}

private static boolean isClosed(AStarTile toCheck) {
    return getClosed(toCheck) != null;
}

private static boolean isOpen(AStarTile toCheck) {
    return getOpen(toCheck) != null;
}

/**
 * @return the open tile with the lowest 'final' score.
 **/
private static AStarTile getBestOption() {
    try {
        Collections.sort(openTiles);
        return openTiles.get(0);
    }
    catch(Exception e) {
    }
    return null;
}

private static AStarTile getClosed(AStarTile t) {
    for (AStarTile p : closedTiles) {
        if (p.equals(t)) {
            return t;
        }
    }
    return null;
}

private static AStarTile getOpen(AStarTile t) {
    for (AStarTile p : openTiles) {
        if (p.equals(t)) {
            return t;
        }
    }
    return null;
}

}

此方法返回一个“动作”列表，阿凡达可以采取该列表丰富目标瓷砖。如果你想看到任何其他方法，请问。

在阅读了Patrick在policyalmanac.org上找到的解释/教程(“初学者的路径查找”)之后，我编写了这个实现。

如果您能浏览一下我的实现并指出任何问题，特别是如果您对A*搜索算法有经验的话，我将非常感激。我认为代码是相当自我文档化的，但是如果有必要的话，请让我详细说明一下。

耽误您时间，实在对不起。

Answer 1

我已经把它整理好了--我在关闭瓷砖时增加了对这一代的检查。现在，它没有被卡住，而是略微倒退了。

解决方案：

    if (!closedTiles.isEmpty() && toClose.getGeneration() != lastClosed().getGeneration() + 1) {
        openTiles.remove(getOpen(toClose));
        return;
    }

我很高兴我修好了。感谢那些花时间阅读和/或回答问题的人！)

Answer 2

有几件事看起来很可疑：

一

currentTile.getGeneration() > parentTile.getGeneration() + 1

这应该是>=而不是>吗？

二

currentTile.setHeuristic(currentTile.distanceSquared(targetTile));

平方距离不是一个可接受的启发式，因为它可以高估距离。尝试使用曼哈顿距离(或者简单地将启发式设置为0，以进行效率较低但更可靠的搜索)。