11.A星寻路算法

14.A星寻路算法

标题

迷宫寻路需求，在一个迷宫游戏中，有一些怪物攻击主角，现在盼望小怪物，能自动绕过迷宫中的障碍物，探求到主角的所在。
思路

A星寻路算法(A*search algorithm)，是一种用于探求有效路径的算法。
简单的场景举例(简化问题)，看一看A星寻路算法的工作过程。

小怪物从绿色的小方块开始每次只能移动一步，且不能穿越墙壁，求到达红色小方块的最少步数。
引入两个聚集和一个公式。
聚集：OpenList(可到达的格子)，CloseList(已到达的格子)。
公式：F = G + H
每一个格子都具有F，G，H这3个属性，G(从起点走到当前格子的成本，既是从起点走大当前格子，已经走的步数)，H(在不考虑障碍物的情况下，从当前格子走到目标格子的距离，也就是离目标另有多远)，F(G和H之和，既是从起点到达当前格子，再从当前格子到达目标格子的总步数)。
第一步，把起点放入OpenList，也就是刚才所说的可到达格子的聚集。第2步，找出OpenList中F值最小的方格作为当前方格。虽然我们没有直接计算 起点方格的F值，但此时OpenList中只有唯一的方格Grid(1,2)，把当前格子移出 OpenList，放入CloseList。代表这个格子已到达并查抄过了。第3步，找出当前方格（刚刚查抄过的格子）上、下、左、右全部可到达的格 子，看它们是否在OpenList或CloseList当中。假如不在，则将它们加入 OpenList，计算出相应的G、H、F值，并把当前格子作为它们的“父节点”。一个格子的“父节点”代表它的来路，在输出终极蹊径时会用到。刚才的1-3步，就是局部寻路的步骤。重复2，3步，直到找到尽头，或把全部可达的格子用尽为止。
代码

1. import java.util.ArrayList;
2. import java.util.List;
3. import java.util.Objects;
5. public class AStar {
7.     public static final int[][] MAZE = {
8.             {0, 0, 0, 0, 0, 0, 0},
9.             {0, 0, 0, 1, 0, 0, 0},
10.             {0, 0, 0, 1, 0, 0, 0},
11.             {0, 0, 0, 1, 0, 0, 0},
12.             {0, 0, 0, 0, 0, 0, 0}
13.     };
15.     /**
16.      * A*寻路主逻辑
17.      *
18.      * @param start 起点
19.      * @param end   终点
20.      */
21.     public static Grid aStarSearch(Grid start, Grid end) {
22.         List<Grid> openList = new ArrayList<>();
23.         List<Grid> closeList = new ArrayList<>();
25.         openList.add(start);
26.         while (openList.size() > 0) {
27.             Grid currentGrid = findMinGrid(openList);//在openList找到F值最小的点
28.             openList.remove(currentGrid);//在openList移除当前格子
29.             closeList.add(currentGrid);//添加到closeList
30.             List<Grid> neighbors = findNeighbors(currentGrid, openList, closeList);
31.             for (Grid grid : neighbors) {
32.                 if (!openList.contains(grid)) {
33.                     //相邻节点不在openList，标记"父节点"，G,H,F并放入openList
34.                     grid.initGrid(currentGrid, end);
35.                     openList.add(grid);
36.                 }
37.             }
38.             for (Grid grid : openList) {//终点在openList中，直接返回终点格子
39.                 if ((grid.x == end.x) && (grid.y == end.y))
40.                     return grid;
41.             }
42.         }
43.         return null;//openList用尽，找不到终点，说明终点不可达，返回null
44.     }
46.     /**
47.      * 寻找在OpenList集合中F值最小的
48.      */
49.     private static Grid findMinGrid(List<Grid> openList) {
50.         Grid grid = openList.get(0);
51.         for (Grid _grid : openList) {
52.             if (_grid.f < grid.f)
53.                 grid = _grid;
54.         }
55.         return grid;
56.     }
58.     /**
59.      * 寻找在格子，周围的格子(在边界内，没有走过的)
60.      */
61.     private static List<Grid> findNeighbors(Grid grid, List<Grid> openList, List<Grid> closeList) {
62.         List<Grid> gridList = new ArrayList<>();
63.         int x = grid.x;
64.         int y = grid.y;
65.         if (isValidGrid(x, y - 1, openList, closeList))
66.             gridList.add(new Grid(x, y - 1));
67.         if (isValidGrid(x, grid.y + 1, openList, closeList))
68.             gridList.add(new Grid(x, y + 1));
69.         if (isValidGrid(x - 1, y, openList, closeList))
70.             gridList.add(new Grid(x - 1, y));
71.         if (isValidGrid(x + 1, y, openList, closeList))
72.             gridList.add(new Grid(x + 1, y));
73.         return gridList;
74.     }
76.     private static boolean isValidGrid(int x, int y, List<Grid> openList, List<Grid> closeList) {
77.         if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE[0].length)//是否越过边界
78.             return false;
79.         if (MAZE[x][y] == 1)//是否有障碍物
80.             return false;
81.         if (containGrid(openList, x, y))//是否在openList
82.             return false;
83.         return !containGrid(closeList, x, y);//在closeList，返回false 不在时不满足所有情况，返回true
84.         /**
85.          *  return !containGrid(closeList, x, y); <==>
86.          *  if(containGrid(closeList, x, y))
87.          *      return false;
88.          *  return true;
89.          */
90.     }
92.     private static boolean containGrid(List<Grid> grids, int x, int y) {
93.         for (Grid grid : grids) {
94.             if (grid.x == x && grid.y == y)
95.                 return true;
96.         }
97.         return false;
98.     }
100.     static class Grid {
101.         //演示代码，不符合Java Bean规范
102.         public int x;
103.         public int y;
104.         public int f;
105.         public int g;
106.         public int h;
107.         public Grid parent;
109.         public Grid(int x, int y) {
110.             this.x = x;
111.             this.y = y;
112.         }
114.         public void initGrid(Grid parent, Grid end) {
115.             this.parent = parent;//设置当前节点的父节点，方便回溯路径
116.             this.g = Objects.nonNull(parent) ? (parent.g + 1) : 1;//设置G属性值
117.             this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);//设置H属性值
118.             this.f = this.g + this.h;//设置F属性值
119.         }
121.     }
123.     public static void main(String[] args) {
124.         Grid startGrid = new Grid(2, 1);//起点
125.         Grid endGrid = new Grid(2, 5);//终点
126.         Grid resultGrid = aStarSearch(startGrid, endGrid);
127.         //回溯迷宫路径
128.         List<Grid> path = new ArrayList<>();
129.         while (Objects.nonNull(resultGrid)) {
130.             path.add(new Grid(resultGrid.x, resultGrid.y));
131.             resultGrid = resultGrid.parent;
132.         }
133.         //输出迷宫和路径，路径用*表示
134.         for (int i = 0; i < MAZE.length; i++) {
135.             for (int j = 0; j < MAZE[0].length; j++) {
136.                 if (containGrid(path, i, j))
137.                     System.out.print("*,");
138.                 else
139.                     System.out.print(MAZE[i][j] + ",");
140.             }
141.             System.out.println();
142.         }
143.     }
145. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。