(A*) Pathfinding

本文关键字：Pathfinding | 更新日期: 2023-09-27 18:00:04

（A*）路径查找

仅适用于上、下、左、右

无论如何，我不确定，我已经检查了一些例子，但是，会是这样吗？：

Point StartTile;
Point EndTile;
List<Point> CheckedPoints;
List<Point> UncheckedPoints;

因此，我将把StartTile添加到UncheckedPoints。

我将循环浏览未选中的点，并将（上、下、左、右）平铺添加到不在已选中的点中。删除我刚刚检查的点，并将其添加到CheckedPoints中。

我也会这样做，直到我在UncheckedPoints中到达EndTile，然后呢？

1如果我不能到达EndTile，它会永远循环吗？我该如何防止这种情况发生

2如果我无法到达EndTile，有办法找到离EndTile最近的tile吗

3如何获取从StartTile到EndTile的磁贴列表？为每个周期保留一个长列表会占用大量内存，对吧

(A*) Pathfinding

1如果我不能到达EndTile，它会永远循环吗？我该如何防止这种情况发生？

不，算法应该只运行，只要有UncheckedPoints。一旦到达EndTile，您可以中止，但这不是必须的。

并且您决不能将已包含在CheckedPoints 中的点添加到UncheckedPoints

2如果我无法到达EndTile，有没有办法找到离EndTile最近的tile？

是的，由于您将所有访问过的ppint存储在CheckedPoints中，因此您可以在其中选择最近的点。

3如何获取从StartTile到EndTile的磁贴列表？为每个周期保留一个长列表会占用大量内存，对吧？

您可以为每个点进行存储，从哪个点开始访问。

这将使所需的内存增加一倍，但不会是"内存负载"，因为无论如何，您已经必须存储所有访问的点，以避免在循环中运行。

--

你可能想在网格上（而不是在图上）看看Dijkstra的算法，它更简单。A*只是一种优化，不以一种随机顺序探索所有标题，而是首先探索最接近末尾瓦片的标题。

相关文章：