algorithm - 计算圆形地图上两点之间的距离

Question

我目前正在尝试创建一个视频游戏，其中角色是 AI，并且位于带有资源的圆形地图中。

我目前正在尝试计算此地图上 2 点之间的最短距离，但我的问题是地图是圆形的：例如

如果我的地图是 20*20 并且我在 (0,0) 中，则 (19,0) 点的距离仅为 1。我一直在网上寻找，但我没有找到我的问题的答案。我也必须注意我的角色的方向（南北西东），因为他必须转身去点，距离必须更长。

有现成的公式吗？

谢谢阅读 ！

Answer 1

对于每个坐标选择最小距离，然后像往常一样使用它。

int dx = min(abs(x0-x1),20-abs(x0-x1));
int dy = min(abs(y0-y1),20-abs(y0-y1));

对于欧几里得距离：

double dist = sqrt(dx * dx + dy * dy);

对于曼哈顿距离：

int dist = dx + dy;

Answer 2

该问题仍然是图中的最短路径问题，您只需为圆形地图添加边：

G = (V,E)在哪里V = {all squares}和E = { (u,v) | [(u.x + 1 % 20 = v.x or u.x -1 % 20 = v.x) and u.y == v.y] or ... [same for y] }

上面的数学符号表示：当（且仅当）两个正方形之间存在一条边时，它们的 x 或 y 坐标之间的差异在 Z ₂₀（模数 20 环）中为 1 或 -1。由于环 Z ₂₀本身是圆形的 - 它解决了地图的圆形问题。

鉴于此图，您可以使用BFS从单个源中找到最短路径（不需要 dijkstra 算法，因为该图未加权）

注意：如果没有障碍物，只需使用常规距离函数进行计算，但在数学中使用 Z ₂₀环而不是 Z 字段。