隔壁老吕
本帖最后由 隔壁老吕 于 2021-2-16 18:36 编辑

虽然说寻路算法在一般插件开发中很少用，但是因为某些客户奇奇怪怪的要求不得不研究了这个东西，
顺便与大家分享一下。



一.寻路算法的种类
比较适合MC这类开放地图的寻路算法是A*，BFS，Dijkstra

A*兼具高速度与较高的准确性，所以本文会主要讲A*算法


二.开始寻路之旅
A*算法的始祖是Dijkstra
Dijkstra算法的实质就是不断向四周搜索，
向四周搜索的具体方法是维护
  1. HashMap<Block, Node> open;
  2. HashSet<Node> close;
复制代码
首先，g表示离出发点的距离
1.将开始节点put入open
2.循环获取离初始节点最近并且未到达的节点#getMinGNode()
3.判断该节点是否为终点(终点直接跳出循环输出结果)
  否则从open中remove该节点(HashMap的作用在此体现，快速删除减少时间损耗)
      并且将该节点存入close中(表示已经到达过这个节点)
4.随后获取该节点四周的节点，即为子节点判断close中是否存在(HashSet快速判断)
5.接下来是非常重要的一步，更新子节点
    如果这个子节点已经到达过了(判断open中是否存在这个节点的Block)
      若该节点到子节点比过去的路径更近，就需要更新子节点实现最短路径
    否则直接将节点存入open
  1. Node start = new Node(begin, 0, BlockUtil.getDistance(begin, target), null);
  2. open.put(start.block, start);
  3. while (!open.isEmpty()) {
  4.     Node n = getMinGNode();
  5.     if (n.equals(target)) {
  6.         result = n;
  7.         //完成
  8.         break;
  9.     } else {
  10.         open.remove(n.block);
  11.         close.add(n);
  12.         for (Node m : n.getNextNodes(target)) {
  13.             if (!close.contains(m)) {
  14.                 if (open.containsKey(m.block)) {
  15.                     open.get(m.block).update(m);
  16.                 } else {
  17.                     open.put(m.block, m);
  18.                 }
  19.             }
  20.         }
  21.     }
  22. }
复制代码


三.从Dijkstra进入A*

Dijkstra算法是由起点向四周发散搜索，浪费了大量的时间搜索没有必要的节点，
那么就需要为他指明道路，于是，A*算法诞生了
由Dijkstra进入A*很简单。
在“二”中已经提到，g定义了由当前节点到初始节点的距离，
于是再定义h为当前节点到终节点的理论距离，这里用曼哈顿路径处理
定义f=h+g，表示理论上这条路径的距离
随后将"2.循环获取离初始节点..."修改成获取理论路径最小的节点#getMinFNode()
曼哈顿距离
  1. public static double getDistance(Location begin, Location target) {
  2.     int x1 = begin.getBlockX();
  3.     int y1 = begin.getBlockY();
  4.     int z1 = begin.getBlockZ();
  5.     int x2 = target.getBlockX();
  6.     int y2 = target.getBlockY();
  7.     int z2 = target.getBlockZ();
  8.     return Math.abs(x1 - x2) + Math.abs(y1 - y2) + Math.abs(z1 - z2);
  9. }
复制代码

此外就是获取四周子节点时连通性的判断，在样例插件中已经提供了我写的样本当然，也欢迎大佬来优化
到此，A*算法就完成了附参考插件样本以及源代码：
src.rar (5.98 KB, 下载次数: 8)
Pathfinder.jar (23 KB, 下载次数: 5)
插件使用：
/pf astar x y z 对从玩家所处点向该点A*寻路
/pf dijks x y z 对从玩家所处点向该点Dijkstra寻路
/pf bfs x y z 对从玩家所处点向该点BFS寻路




夏日冰熊
最喜欢dijkstra了~~~
A*我记得是依赖于估值的

ABlueCat
不过使用堆优化Dijkstra算法的话其时间复杂度可以从O(n^2)降到O(nlogn)的，实际上还是挺快的
隔壁老吕
dengyu 发表于 2021-2-16 18:33
不过使用堆优化Dijkstra算法的话其时间复杂度可以从O(n^2)降到O(nlogn)的，实际上还是挺快的 ...

Dijkstra用在mc地图里就和广搜差不多了，效率较低
另外那几句争议性的话先去掉了，尚待考证