-2

(A*) 寻路

仅适用于上、下、左、右

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

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

所以，我会将StartTile添加到UncheckedPoints。

我将循环浏览UncheckedPoints，并将 (Up, Down, Left, Right) 磁贴添加到UncheckedPoints（如果它不在CheckedPoints中） 。并删除我刚刚检查的点，并将其添加到CheckedPoints。

在UncheckedPoints到达EndTile之前，我会这样做，然后呢？

1 如果我无法到达 EndTile，它会永远循环吗？我怎样才能防止这种情况？

2 如果我无法到达 EndTile，有没有办法让最接近 EndTile 的瓷砖？

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

4

1 回答 1

1

1 如果我无法到达 EndTile，它会永远循环吗？我怎样才能防止这种情况？

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

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

2 如果我无法到达 EndTile，有没有办法让最接近 EndTile 的瓷砖？

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

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

您可以存储每个点，从哪个点访问它。

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

--

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

于 2013-02-18T18:19:28.930 回答