Java游戏服务器开发之A星算法

偏执的太偏执、 2022-05-22 23:11 185阅读 0赞

Java游戏服务器开发之A星算法  
   学习这个主要是用于寻路算法。  
   参考资料主要是siki学院的视频，A计划--人工智能--A星算法。  
网址http://www.sikiedu.com/course/62/tasks  
   代码也是大部分参考里面，原本是C\#的，用Java实现了一遍。  
   一般看视频的话，基本一知半解，自己敲一遍，基本就能了解了  
     
我先直接放代码，先跑成功后，再说明下整个实现  
首先，需要将我们的地图虚拟化，我们用Point表示。  
其次，创建整个地图，按照长宽来初始化。initMap  
接着，写出计算FGH的值(先不用管是什么)的函数。calcF  
再者，就是书写查找路径的方法。 findPath  
1.循环"开启列表"，while (openList.size() > 0)   
2.找到列表中F值最小的点M。findMinFOfPoint  
3.找到M点周边可以到达的点数组L。getSurroundPoints  
4.使用相关条件过滤掉一部分L中的点。pointsFilter  
5.循环L，判断里面的G值是否比原来的更小(更优)for (Point surroundPoint : surroundPoints)

最后，就是输出结果showLoad

看具体的代码

Point类

package com.lizhao.astar.siki;
    
    public class Point implements Comparable<Point> {
      private Point parent;
      private int x;
      private int y;
    
      private float F;
      private float G;
      private float H;
    
      private boolean isWall = false;
      private boolean isLoad = false;
    
      public Point(int x, int y) {
        this(x, y, null);
      }
    
      public Point(int x, int y, Point parent) {
        this.x = x;
        this.y = y;
        this.parent = parent;
      }
    
      public void UpdateParent(Point parent, float g) {
        this.parent = parent;
        this.G = g;
        F = G + H;
      }
    
      public void updateFGH(float f, float g, float h) {
        this.F = f;
        this.G = g;
        this.H = h;
      }
    
      public Point getParent() {
        return parent;
      }
    
      public void setParent(Point parent) {
        this.parent = parent;
      }
    
      public int getX() {
        return x;
      }
    
      public void setX(int x) {
        this.x = x;
      }
    
      public int getY() {
        return y;
      }
    
      public void setY(int y) {
        this.y = y;
      }
    
      public float getF() {
        return F;
      }
    
      public void setF(float f) {
        F = f;
      }
    
      public float getG() {
        return G;
      }
    
      public void setG(float g) {
        G = g;
      }
    
      public float getH() {
        return H;
      }
    
      public void setH(float h) {
        H = h;
      }
    
      public boolean isWall() {
        return isWall;
      }
    
      public void setWall(boolean wall) {
        isWall = wall;
      }
    
      public boolean isLoad() {
        return isLoad;
      }
    
      public void setLoad(boolean load) {
        isLoad = load;
      }
    
      @Override
      public int compareTo(Point point) {
        return Float.compare(F, point.getF());
      }
    
      @Override
      public String toString() {
        return "Point " + (getX() + 1) + "," + (getY() + 1);
      }
    }

initMap方法

public void initMap() {
        for (int x = 0; x < mapWith; x++) {
          for (int y = 0; y < mapHeight; y++) {
            map[x][y] = new Point(x, y);
          }
        }
    //    map[6][3].setWall(true);
        map[6][4].setWall(true);
        map[6][5].setWall(true);
        map[6][6].setWall(true);
        //    map[4][5].setWall(true);
        //    map[4][6].setWall(true);
      }

calcF方法

/*************************************************************
       *第一步，写出计算FGH的值
       **********************************************************/
      /**
       * 计算F值
       *
       * @param now 当前点
       * @param end 终点
       */
      private void calcF(Point now, Point end) {
        //F = G + H
        // H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以
        //上下左右移动).
        //G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).
        float h = calcH(now, end);
        float g = calcG(now, now.getParent());
        float f = g + h;
        now.updateFGH(f, g, h);
    
      }
    
      /**
       * 获取H值
       * H 表示从指定的方格移动到终点 B 的预计耗费
       * (H 有很多计算方法, 这里我们设定只可以上下左右移动).
       *
       * @param start
       * @param end
       * @return
       */
      private float calcH(@NotNull Point start, @NotNull Point end) {
        return Math.abs(end.getX() - start.getX()) + Math.abs(end.getY() - start.getY());
      }
    
      /**
       * 获取G值
       * G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).
       * 父节点到走到该节点的消耗
       *
       * @param start
       * @param parent
       * @return
       */
      private float calcG(@NotNull Point start, @NotNull Point parent) {
        float g = 0;
        if (start.getParent() == null) {
          g = 0;
        } else {
          g = PointUtil.getDistance(start, parent) + parent.getG();
        }
        return g;
      }

findPath方法

findMinFOfPoint 方法

/**
       * 开启列表中F值最小的点
       *
       * @param openList
       * @return
       */
      private Point findMinFOfPoint(List<Point> openList) {
        float f = Float.MAX_VALUE;
        Point temp = null;
        for (Point p : openList) {
          if (p.getF() < f) {
            temp = p;
            f = p.getF();
          }
        }
        return temp;
      }

getSurroundPoints 方法、

/**
       * 周围的点
       *
       * @param point
       * @return
       */
      private List<Point> getSurroundPoints(Point point) {
        Point up = null, down = null, left = null, right = null;
        Point lu = null, ru = null, ld = null, rd = null;
        if (point.getY() < mapHeight - 1) {
          up = map[point.getX()][point.getY() + 1];
        }
        if (point.getY() > 0) {
          down = map[point.getX()][point.getY() - 1];
        }
        if (point.getX() > 0) {
          left = map[point.getX() - 1][point.getY()];
        }
        if (point.getX() < mapWith - 1) {
          right = map[point.getX() + 1][point.getY()];
        }
        if (up != null && left != null) {
          lu = map[point.getX() - 1][point.getY() + 1];
        }
        if (up != null && right != null) {
          ru = map[point.getX() + 1][point.getY() + 1];
        }
        if (down != null && left != null) {
          ld = map[point.getX() - 1][point.getY() - 1];
        }
        if (down != null && right != null) {
          rd = map[point.getX() + 1][point.getY() - 1];
        }
        List<Point> list = new ArrayList<Point>();
        if (down != null && down.isWall() == false) {
          list.add(down);
        }
        if (up != null && up.isWall() == false) {
          list.add(up);
        }
        if (left != null && left.isWall() == false) {
          list.add(left);
        }
        if (right != null && right.isWall() == false) {
          list.add(right);
        }
        if (lu != null && lu.isWall() == false && left.isWall() == false && up.isWall() == false) {
          list.add(lu);
        }
        if (ld != null && ld.isWall() == false && left.isWall() == false && down.isWall() == false) {
          list.add(ld);
        }
        if (ru != null && ru.isWall() == false && right.isWall() == false && up.isWall() == false) {
          list.add(ru);
        }
        if (rd != null && rd.isWall() == false && right.isWall() == false && down.isWall() == false) {
          list.add(rd);
        }
        return list;
      }

pointsFilter 方法

/**
       * 过滤掉周围的点
       *
       * @param src
       * @param closeList
       */
      private void pointsFilter(List<Point> src, List<Point> closeList) {
        for (Point p : closeList) {
          if (src.indexOf(p) > -1) {
            src.remove(p);
          }
        }
      }

findPath具体

private void findPath(Point start, Point end) {
    
        List<Point> openList = new ArrayList<Point>();
        List<Point> closeList = new ArrayList<Point>();
        openList.add(start);
        while (openList.size() > 0) {
          Point point = findMinFOfPoint(openList);
          openList.remove(point);
          closeList.add(point);
          List<Point> surroundPoints = getSurroundPoints(point);
          pointsFilter(surroundPoints, closeList);
    
          for (Point surroundPoint : surroundPoints) {
            if (openList.indexOf(surroundPoint) > -1) {
              float nowG = calcG(surroundPoint, point);
              if (nowG < surroundPoint.getG()) {
                surroundPoint.UpdateParent(point, nowG);
              }
            } else {
              surroundPoint.setParent(point);
              calcF(surroundPoint, end);
              openList.add(surroundPoint);
            }
          }
          //判断一下
          if (openList.indexOf(end) > -1) {
            break;
          }
        }
      }

showLoad方法

private void showLoad() {
        for (int i = 0; i < map.length; i++) {
          for (int j = 0; j < map[i].length; j++) {
            if (map[i][j].isLoad()) {
              System.out.print("$");
            } else if (map[i][j].isWall()) {
              System.out.print(1);
            } else if (map[i][j].getParent() != null) {
              System.out.print(3);
            } else {
              System.out.print(0);
            }
            System.out.print(",");
          }
          System.out.println();
        }
      }

写个测试方法：

//测试A星算法
      public static void testAStar() {
        AStar aStar = new AStar();
    
        aStar.initMap();
        Point start = aStar.map[4][4];
        Point end = aStar.map[8][5];
    
        aStar.findPath(start, end);
        aStar.showPath(start, end);
        aStar.showLoad();
        System.out.println("Hello World! ");
      }

最后的输出结果，0是地图，1是墙，3是被探索过的区域，$是具体的路径

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,3,3,0,0,0,0,0,0,0,0,0,
     0,0,3,3,3,3,1,0,0,0,0,0,0,0,0,
    6 0,0,3,3,3,3,1,3,$,3,0,0,0,0,0,
    5 0,0,3,3,$,3,1,3,$,3,0,0,0,0,0,
    4 0,0,0,3,3,$,$,$,3,3,0,0,0,0,0,
     0,0,0,0,3,3,3,3,3,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     5,6 
     
     6,4 14+50
     6,5 10+40
     6,6 14+30
     6,7 24+40

nice  
上面的代码在码云上 https://gitee.com/lizhaoandroid/BehaviorTree，在com.lizhao.astar.siki包下面  
可以加qq群一起学习讨论Java游戏服务器开发的相关知识676231524