Java

Question

问题已解决。

我已经在一个简单的基于网格的游戏中实现了用于路径查找的 A* 搜索算法。这是我第一次这样做，大多数时候实施效果都很好。然而，有时（尽管很少）它会在有可用路径时卡住。当然，它完全卡住的事实使它不符合目的。我假设我的实现中遗漏了一些东西。

这个问题我找了好几天了，没找到。我的截止日期快到了，还有很多事情要做，我不想再浪费时间来修复这个错误。

编辑： 我创建了 a quick video 来演示这个问题，这样您就可以准确地看到发生了什么。它包括字幕。
编辑： 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;
}

}

此方法 returns 一个 'ACTIONS' 列表，头像可以用来丰富目标磁贴。如果您想查看任何其他方法，请询问。

我在阅读了 Patrick Lester 在 policyalmanac.org ("A* Pathfinding for Beginners") 中找到的 explanation/tutorial 后编写了这个实现。

如果您能浏览一下我的实现并指出任何问题，我将不胜感激，尤其是如果您对 A* 搜索算法有经验的话。我认为代码是非常自我记录的，但如有必要，请随时让我详细说明。

感谢您的宝贵时间。

Answer 1

有几件事看起来很可疑：

一个

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

这应该是 >= 而不是 >？

两个

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

平方距离不是一种可接受的启发式方法，因为它可能会高估距离。尝试使用曼哈顿距离（或简单地将启发式设置为 0 以获得效率较低但更可靠的搜索）。

Answer 2

我已经对它进行了排序 - 我在关闭磁贴时添加了对生成的检查。它现在稍微回溯而不是卡住。

解决方案：

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

很高兴我已经修复了它。非常感谢任何花时间阅读 and/or 回答问题的人！ :)

Java - A* 搜索问题

Java - A* Search Issue

algorithm

search

a-star

一个

两个