左转右转命令在地图

Question

我已经实现了一个使用Dijktra's Algorithm的代码。感谢Dijkstra，我可以打印出从期望的源到期望的目的地的最短路径。然而，我想做的是添加一个功能，通过左转，右转命令告诉我们方向。

例子:

从A到D:

假设A位于1号街，B位于2号街，D位于2号街左边60米处。

从A到D:

去2号街。向左转。走大约60米，它就在你的离开。

我需要你的想法。谢谢你！

Answer 1

要从路径生成驾驶指令，您需要用图存储额外的信息:

对于每条路，它的长度。这很简单

对于每个十字路口，每对事故道路之间的关系。

您可以存储十字路口周围每条道路的方位角(道路1-2从十字路口1向西)，然后根据两条道路之间的相对角度，十字路口类型(普通/环形交叉路口)以及所有其他道路的拓扑顺序和相对角度生成驾驶指令。

这种方法有更紧凑的表示的好处，但它需要更多的编程。

或者，您可以单独存储每对之间的关系。这更可靠(只有人类才能真正理解世界上每种可能的十字路口类型的复杂性)，但它更需要手动更新(毕竟，一点AI 理论上可以推迟十字路口类型，即使有错误)。

如果你有一个巨大的地图，你会想要坚持第一种方法。如果您正在手动构建地图，您可能更喜欢第二种方法——只是要确保不要实际存储每个路径对的字符串(除非语言对它们进行了处理)，否则您的内存需求可能会飙升。在将映射序列化到文件时，这需要特别注意(同样，如果您选择ZIP压缩，ZIP压缩可能会在很大程度上减轻这个问题)。

如果你的地图只关注简单的四路十字路口，那么每对存储的信息只是一个left/straight/right枚举(方法#2)，或者只是十字路口周围的边缘排序(方法#1)，其中一些道路可能是null。

例如，您的十字路口可以(最简单的情况，方法#1)看起来像

private Road[] roads = new Road[4];
public enum Direction{
  Left, Straight, Right, Back;
  // utility methods
}
public Direction getDir (Road from, Road to){
  // input checking stripped for clarity
  int iFrom = roads.indexOf(from);
  int iTo = roads.indexOf(to);
  // more input checking
  int iDiff = (iFrom - iTo) % 4;
  if(iDiff < 0) iDiff +=4 ;
  return Direction.getRelative90(iDiff);
  //Direction.getRelative90 is just a switch statement.
}

为生成方向，使用与地图一起存储的信息。记住将逻辑上遵循的道路连接起来(总结它们的长度)(在十字路口没有指示=隐含的"直走"-几条道路可能会遵循一条，但每条道路只能遵循一条)，其余的是直接的。