11.A星寻路算法
14.A星寻路算法标题
迷宫寻路需求，在一个迷宫游戏中，有一些怪物攻击主角，现在盼望小怪物，能自动绕过迷宫中的障碍物，探求到主角的所在。
思路
A星寻路算法(A*search algorithm)，是一种用于探求有效路径的算法。
简单的场景举例(简化问题)，看一看A星寻路算法的工作过程。
https://img2024.cnblogs.com/blog/2883613/202502/2883613-20250213232229746-529779432.jpg
小怪物从绿色的小方块开始每次只能移动一步，且不能穿越墙壁，求到达红色小方块的最少步数。
引入两个聚集和一个公式。
聚集：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步，直到找到尽头，或把全部可达的格子用尽为止。
代码
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
public class AStar {
public static final int[][] MAZE = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};
/**
* A*寻路主逻辑
*
* @param start 起点
* @param end 终点
*/
public static Grid aStarSearch(Grid start, Grid end) {
List<Grid> openList = new ArrayList<>();
List<Grid> closeList = new ArrayList<>();
openList.add(start);
while (openList.size() > 0) {
Grid currentGrid = findMinGrid(openList);//在openList找到F值最小的点
openList.remove(currentGrid);//在openList移除当前格子
closeList.add(currentGrid);//添加到closeList
List<Grid> neighbors = findNeighbors(currentGrid, openList, closeList);
for (Grid grid : neighbors) {
if (!openList.contains(grid)) {
//相邻节点不在openList，标记"父节点"，G,H,F并放入openList
grid.initGrid(currentGrid, end);
openList.add(grid);
}
}
for (Grid grid : openList) {//终点在openList中，直接返回终点格子
if ((grid.x == end.x) && (grid.y == end.y))
return grid;
}
}
return null;//openList用尽，找不到终点，说明终点不可达，返回null
}
/**
* 寻找在OpenList集合中F值最小的
*/
private static Grid findMinGrid(List<Grid> openList) {
Grid grid = openList.get(0);
for (Grid _grid : openList) {
if (_grid.f < grid.f)
grid = _grid;
}
return grid;
}
/**
* 寻找在格子，周围的格子(在边界内，没有走过的)
*/
private static List<Grid> findNeighbors(Grid grid, List<Grid> openList, List<Grid> closeList) {
List<Grid> gridList = new ArrayList<>();
int x = grid.x;
int y = grid.y;
if (isValidGrid(x, y - 1, openList, closeList))
gridList.add(new Grid(x, y - 1));
if (isValidGrid(x, grid.y + 1, openList, closeList))
gridList.add(new Grid(x, y + 1));
if (isValidGrid(x - 1, y, openList, closeList))
gridList.add(new Grid(x - 1, y));
if (isValidGrid(x + 1, y, openList, closeList))
gridList.add(new Grid(x + 1, y));
return gridList;
}
private static boolean isValidGrid(int x, int y, List<Grid> openList, List<Grid> closeList) {
if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE.length)//是否越过边界
return false;
if (MAZE == 1)//是否有障碍物
return false;
if (containGrid(openList, x, y))//是否在openList
return false;
return !containGrid(closeList, x, y);//在closeList，返回false 不在时不满足所有情况，返回true
/**
*return !containGrid(closeList, x, y); <==>
*if(containGrid(closeList, x, y))
* return false;
*return true;
*/
}
private static boolean containGrid(List<Grid> grids, int x, int y) {
for (Grid grid : grids) {
if (grid.x == x && grid.y == y)
return true;
}
return false;
}
static class Grid {
//演示代码，不符合Java Bean规范
public int x;
public int y;
public int f;
public int g;
public int h;
public Grid parent;
public Grid(int x, int y) {
this.x = x;
this.y = y;
}
public void initGrid(Grid parent, Grid end) {
this.parent = parent;//设置当前节点的父节点，方便回溯路径
this.g = Objects.nonNull(parent) ? (parent.g + 1) : 1;//设置G属性值
this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);//设置H属性值
this.f = this.g + this.h;//设置F属性值
}
}
public static void main(String[] args) {
Grid startGrid = new Grid(2, 1);//起点
Grid endGrid = new Grid(2, 5);//终点
Grid resultGrid = aStarSearch(startGrid, endGrid);
//回溯迷宫路径
List<Grid> path = new ArrayList<>();
while (Objects.nonNull(resultGrid)) {
path.add(new Grid(resultGrid.x, resultGrid.y));
resultGrid = resultGrid.parent;
}
//输出迷宫和路径，路径用*表示
for (int i = 0; i < MAZE.length; i++) {
for (int j = 0; j < MAZE.length; j++) {
if (containGrid(path, i, j))
System.out.print("*,");
else
System.out.print(MAZE + ",");
}
System.out.println();
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]