如何实现自动驾驶

Question

我正在用.net构建一个基于文本的空间游戏，我有一个服务器和客户端，在那里我可以在地图上“移动”。地图按扇区分解，每个扇区都有可能连接到它周围的8个其他扇区(也是一个具有对角移动的网格)。它通过列出连接扇区的数组存储在sector类中。目前，所有扇区都存储在一个列表中。当发出移动命令时，检查连接的扇区阵列，如果在阵列中找到所请求的扇区，则加载新的扇区。

我想做的是实现一个自动驾驶功能，但我一直不知道如何用我目前的结构来实现它。每个扇区只知道它连接的扇区。

有没有人有什么建议/想法？

谢谢,

本

Answer 1

我想你需要一个最短路径算法。地段形成一个图形，你想要找到一条通过地段的路线。

要做到这一点，最简单的方法是从船舶的当前位置和您想要获取的位置开始执行两个并行的广度优先搜索。当您找到一个共享节点时，合并从每个位置到该节点的路径，您就有了一条路径。

如果您有任何接近度数据，则可以使用A*对此进行优化。

Answer 2

有几种方法可以做到这一点。你的地图是像空间本身一样，你可以在那里四面八方旅行，还是更像一个迷宫？作为一个太空游戏，我把地图想象成

XXXX
XXXX
XXXX
XXXX

在这种情况下，最好使用二维数组来存储映射。这将允许您通过增加X和Y来自动驾驶，直到找到您的目的地。

然而，如果你的地图比较复杂，你应该研究一下导航的"A*算法“。你所做的就是通过计算每一条可能的路径，并选择最短的路径，来暴力地将你的方式推向最佳路径。例如，如果您的地图是：

 X
XXX
A B

当你试图从A到B时，你会生成一个映射：

(U=up等)

U
UR
URU
URUD
URUDR
URUDRD*
URR
URRD*

它看起来会像这样。*表示路线找到了到达目的地的路径，因此它会查看所有到达目的地的路线，并选择最短的路线。

A*的一个优点是您可以对每个地段应用权重。如果你有一个星云在一个扇区，需要3倍的时间通过，你可以通过比较总的‘努力’而不是操作的数量来将其包括在你的算法中。这在游戏中很酷，因为你的角色通过路径导航，因为路径要快得多:)

网上有很多算法，只需搜索A*寻路即可。祝好运!