Java最短路径

Question

我正在尝试用 Java 制作一个小型塔防游戏。我有一个由 Point2D.Double 数组组成的网格，名为：

FieldArr[h][v]

h 表示水平字段，v垂直垂直字段

这使得像这样的网格

+ + + + + + +
S + X + + + +
+ + + X + + +
+ X + + + + F
+ + X + + + +

S代表开始，F代表完成，X代表塔

现在我想计算最短路线，但我不知道如何开始这个

塔有以下位置变量: 水平编号和垂直编号。

对于绘画我这样做：

public void paint(Graphics2D g2) {
    int Xpos = HorizontalNr * playfield.getSquarewidth() + playfield.GetinitialXPos();
    int Ypos = VerticalNr * playfield.getSquarewidth() + playfield.GetinitialYPos();
    g2.fillRect(Xpos, Ypos, 50, 50);
}

有人有任何建议，关于我应该如何制作我的敌人类别，这样我就不会遇到算法的任何问题吗？ 和/或有关于如何计算最短路径的提示？

已经谢谢了 猕猴桃

Answer 1

最短路径问题已经被研究了很多，并且有很多关于这个问题的文献。最好只使用现有的算法，而不是尝试自己发明算法。

例如，一个简单而高效的算法是Dijkstra算法。来自维基百科：

1. 让我们开始的节点称为初始节点。令节点Y的距离为从初始节点到Y的距离。Dijkstra算法将分配一些初始距离值，并尝试逐步改进它们。
   为每个节点分配一个暂定距离值：将初始节点设置为零，将所有其他节点设置为无穷大。
2. 将所有节点标记为未访问。将初始节点设置为当前节点。创建未访问节点的集合，称为未访问集，由除初始节点之外的所有节点组成。
3. 对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离。例如，如果当前节点 A 的暂定距离标记为 6，并且将其与邻居 B 连接的边的长度为 2，则到 B（通过 A）的距离将为 6+2=8。如果该距离小于之前记录的B的暂定距离，则覆盖该距离。即使邻居已被检查，此时它也不会被标记为已访问，并且仍保留在未访问集中。
4. 当我们考虑完当前节点的所有邻居后，将当前节点标记为已访问并将其从未访问集中删除。访问过的节点将永远不会被再次检查；现在记录的距离是最终的、最小的。
5. 如果目标节点已被标记为已访问（当规划两个特定节点之间的路线时），或者如果未访问集中的节点之间的最小暂定距离为无穷大（当规划完整的遍历时），则停止。算法已经完成。
6. 将暂定距离最小的未访问节点设置为下一个“当前节点”，并返回步骤3。

Answer 2

如果您想避开塔楼，那么您正在寻找从开始到结束的欧几里得路径，这可以通过最短路径方法 ala djkstra 来解决。

Answer 3

正如马克所说，这就是最短路径问题，可以轻松高效地解决。

请注意，由于您的问题没有加权，因此您可以在此处使用 BFS ，即非常容易实现，并且还保证找到未加权图的最佳路径。

BFS 的伪代码：

findShortestPath(source,target):
  queue<- new queue
  visited <- {}
  Map<point,point> parents <- empty map
  queue.push(source)
  while (queue.empty() == false): 
     current <- queue.takeFirst()
     if (current.equals(target)):
         extract the path from source to destination using the map parents(*)
         return
     visited.add(current)
     for each p such that p and current are neighbors: //insert neighbors to queue
          if p is not in visited: 
                if (p is not an obstacle):
                   queue.push(p)
                   parents.put(p,current) //current is the parent of p

(*) 从地图中提取路径很简单：只需遵循 current <-parent.get(current) 直到得到 null，这提取您将使用的确切路径的方式。

请注意，[在大多数情况下]更快的解决方案将是 A* 与 曼哈顿距离启发式，但实现起来要复杂得多。