是的，数据结构可以帮助你解决这类问题。我将尝试解释 A* 是如何工作的，然后给出一些更好的伪代码。
A* 是最佳优先搜索算法。这意味着它应该猜测哪些选项是最好的，并首先尝试探索这些选项。这需要您跟踪选项列表，通常称为“前线”（如前线）。它不会跟踪到目前为止找到的路径，就像在您当前的算法中一样。该算法分两个阶段工作......
阶段1
基本上，你从起始位置开始S，所有相邻的位置（北、西、南和东）都将在前面。然后，该算法在 Front 中找到最有希望的选项（我们称之为P），并在此基础上进行扩展。该位置P已从 Front 中移除，但其所有相邻位置均被添加。好吧，不是所有的邻居；只有那些是实际选择去的邻居。我们不能走进一座塔楼，我们也不想回到我们以前见过的地方。从新的前线中，选择最有希望的选项，依此类推。当最有希望的选项是目标C时，算法停止并进入阶段 2。
通常，最有希望的选择是最接近目标的选择，因为乌鸦会飞（忽略障碍物）。所以通常情况下，它总是会首先探索最接近目标的那个。这导致算法以某种直线走向目标。但是，如果该线被某些障碍物阻挡，则该障碍物的位置不应添加到 Front。它们不是可行的选择。因此，在下一轮中，前面的其他位置将被选为最佳选项，然后从那里继续搜索。这就是它如何摆脱死胡同，就像你的例子中的那样。看看这个插图来了解我的意思：https ://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif前面是空心的蓝点，它们标记了它们已经在从红色到绿色的阴影中的点，以及用粗蓝点标记无法通行的地方。
在第 2 阶段，我们将需要一些额外的信息来帮助我们找到返回目标时的最短路径。为此，我们在每个位置存储我们来自的位置。如果算法有效，那么我们来自的位置必然S比任何其他邻居都更接近。如果您不明白我的意思，请查看下面的伪代码。
阶段2
找到城堡C后，下一步就是找到回到起点的路，收集最佳路径。在第 1 阶段，我们将来自的位置存储在我们探索的每个位置中。我们知道这个位置必须总是更接近S（而不是忽略障碍）。因此，第 2 阶段的任务非常简单：每次都沿着回到我们来自的位置的路，并在列表中跟踪这些位置。最后，您将获得一个列表，该列表构成从C到的最短路径S。然后你只需要反转这个列表，你就有了答案。
我会给出一些伪代码来解释它。互联网上有大量真实的代码示例（Java 也是如此）。此伪代码假定您使用 2D 数组来表示网格。另一种方法是使用 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;
}
}
}
我希望这有帮助。随时问！
