简单A星算法塔防路径困境

Question

简单A星算法塔防路径困境

3

首先，我正在上一门使用Java编程语言的100级计算机科学课程。我们的作业是制作一个防御塔游戏，但我在路径规划方面遇到了麻烦。通过搜索，我发现A*算法似乎是最适合此任务的。然而，当我在路径周围画一个U形时，我的路径会卡住。因为我还没有学过数据结构课程，所以我的代码看起来很混乱（我正在努力改进）。请注意，我不会使用对角线移动。

while(Castle not reached){
    new OpenList
    if(up, down, left, right == passable && isn't previous node){
         //Adds in alternating order to create a more diagonal like path
         Openlist.add(passable nodes)
    }
    BestPath.add(FindLeasDistancetoEnd(OpenList));
    CheckCastleReached(BestPath[Last Index]);
{

private node FindLeastDistancetoEnd(node n){
    return first node with Calculated smallest (X + Y to EndPoint)
}

我已经将A*算法精简了（可能过度），所以我要为我的节点添加父节点并计算正确的父节点，但我不认为这会解决我的问题。以下是我的问题的可视化图像。

X = 不可通过的（防御塔）

O = 开放列表

b = 关闭列表（最佳路径）

C = 城堡（终点）

S = 起点

OOOOXX
SbbbBX   C
OOOOXX

现在问题出在大写字母 B 上。当塔被放置在该配置中并且我的导航路径被重新计算时，程序会卡住。由于之前的节点被忽略并且其余节点都无法通过，因此没有任何内容被放入 OpenList 中。

现在我想起来可以将 B 设为无法通过并回溯...哈哈。尽管我的教授称之为"篡改代码"，我还是经常不停地添加补丁来解决问题，因为我不想删除"宝贝"并从头开始。虽然我愿意重做，但看着我的代码有多么混乱和不组织，让我很烦恼，迫不及待想学数据结构。

如果您有任何建议，请告诉我。

- Spero

2个回答

0

正确实现A*算法。请参见：http://en.wikipedia.org/wiki/A%2A_search_algorithm

在每次迭代中，您需要：

将开放节点按启发式顺序排序，
选择最佳节点；
-- 检查是否已到达目标，如果是，则可能终止；
现在将其标记为“关闭”，因为它将被完全探索。
从中探索所有邻居（通过添加到开放节点映射/或列表中，如果尚未关闭）。

根据您发布的ASCII图表，不完全清楚板的高度是否超过3且是否实际存在路径-但让我们假设存在。

正确的A*算法不会“卡住”-当开放列表为空时，不存在路径，它将终止并返回无路径null。

我怀疑您可能没有关闭打开的节点（应在开始处理它们时执行此操作），或者可能没有在每次迭代中处理所有打开的节点。

使用 Map<GridPosition, AStarNode> 可以提高性能，检查所有相邻的位置，无论它们是否在开放或关闭的集合/列表中。

- Thomas W

感谢回复。“正确实现A*算法。”是的，我发现在算法方面不能走捷径。 - Spero

我编辑了我的帖子以反映正确的A*算法，思考了一下我的代码并意识到我误导了你，让你在每次迭代中探索哪些节点（只是最好的一个）。是的，你需要正确地实现算法--否则它们会执行其他操作。希望这可以帮助你。@Spero - Thomas W

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ghostkeeper · Accepted Answer

是的，数据结构会对这种问题有很大帮助。我将尝试解释一下A*算法的工作原理，并随后提供更好的伪代码。

A*是一种最佳优先搜索算法。这意味着它应该猜测哪些选项是最好的，并尝试首先探索这些选项。这要求您跟踪一个选项列表，通常称为“前端”（如前线）。它不像您当前的算法那样跟踪迄今为止找到的路径。该算法分为两个阶段...

第一阶段：

基本上，您从起始位置S开始，所有相邻位置（北，西，南和东）都将在前端。然后，算法会找到前端中最有前途的选项（我们称之为P），并展开该选项。位置P从前端中删除，但所有邻居代替它被添加。好吧，不是所有的邻居;只有实际可行的邻居。我们不能走进塔楼，也不想回到以前见过的地方。从新的前端中，选择最有前途的选项，等等。当最有前途的选项是目标C时，算法停止并进入第二阶段。

通常，最有前途的选项是离目标最近的选项，就像乌鸦飞行一样（忽略障碍物）。因此，通常会首先探索最靠近目标的那个选项。这导致算法沿着一条直线走向目标。但是，如果该线路被某个障碍物阻挡，则不应将障碍物的位置添加到前端。它们不是可行的选项。因此，在下一轮中，前端中的其他位置将被选择为最佳选项，并从那里继续搜索。这就是如何走出您示例中的死胡同。请查看此动画以了解我的意思：https://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif 前端是空心蓝点，它们标记了已经到达的点，从红色到绿色变化，而无法通过的地方则用粗蓝点标记。

在第二阶段，我们需要一些额外的信息来帮助我们找到找到目标后返回的最短路径。为此，在每个位置上存储我们来自哪个位置的信息。如果算法有效，则我们来自的位置必然比任何其他邻居更接近S。如果不明白我的意思，请查看下面的伪代码。

第二阶段：

当找到城堡C时，下一步是找回起点，并收集最佳路径。在第1阶段中，我们在探索的每个位置中存储了我们来自哪个位置的信息。我们知道这个位置必须始终更靠近S（不忽略障碍物）。因此，在第2阶段中，任务非常简单：每次跟随返回来的路线，并在列表中跟踪这些位置。最后，你将拥有一个形成从C到S的最短路径的列表。然后只需反转此列表即可得到答案。

以下是伪代码以解释它。在互联网上有很多真正的代码示例（也有Java）。这个伪代码假设您使用一个二维数组来表示网格。另一种选择是使用Node对象，这在Pseudocode中更容易理解，但在编程方面更难，我怀疑您仍会使用2D数组。

//Phase 1
origins = new array[gridLength][gridWidth]; //Keeps track of 'where we came from'.
front = new Set(); //Empty set. You could use an array for this.
front.add(all neighbours of S);
while(true) { //This keeps on looping forever, unless it hits the "break" statement below.
    best = findBestOption(front);
    front.remove(best);
    for(neighbour in (best's neighbours)) {
        if(neighbour is not a tower and origins[neighbour x][neighbour y] == null) { //Not a tower, and not a position that we explored before.
            front.add(neighbour);
            origins[neighbour x][neighbour y] = best;
        }
    }
    if(best == S) {
        break; //Stops the loop. Ends phase 1.
    }
}

//Phase 2
bestPath = new List(); //You should probably use Java's ArrayList class for this if you're allowed to do that. Otherwise select an array size that you know is large enough.
currentPosition = C; //Start at the endpoint.
bestPath.add(C);
while(currentPosition != S) { //Until we're back at the start.
    currentPosition = origins[currentPosition.x][currentPosition.y];
    bestPath.add(currentPosition);
}
bestPath.reverse();

关于伪代码中的findBestOption方法：

findBestOption(front) {
    bestPosition = null;
    distanceOfBestPosition = Float.MAX_VALUE; //Some very high number to start with.
    for(position in front) {
        distance = Math.sqrt(position.x * position.x - C.x * C.x + position.y * position.y - C.y * C.y); //Euclidean distance (Pythagoras Theorem). This does the diagonal thing for you.
        if(distance < distanceOfBestPosition) {
            distanceOfBestPosition = distance;
            bestPosition = position;
        }
    }
}

我希望这些能对你有所帮助。如需进一步了解，请随时提问！