玉溪网站开发公司sem营销推广

一、A*算法介绍

A*算法是一种路径搜索算法，用于在图形网络中找到最短路径。它结合了Dijkstra算法和启发式搜索的思想，通过综合利用已知的最短路径和估计的最短路径来优化搜索过程。在游戏自动寻路得到广泛应用。

二、A*算法的基本思想

1. 在图形网络中选择一个起点和终点。
2. 维护两个列表：开放列表和关闭列表。开放列表用于存储待考虑的节点，关闭列表用于存储已考虑过的节点。
3. 将起点加入开放列表
4. 开始循环
5. 从开放列表中选择最佳节点current（总代价f最小）
6. 如果找到目标，则搜索结束，输出结果
7. 否则，将所有相邻节点加入到开放列表
8. 假如某临近点，即没在开放列表，也不在关闭列表，则计算出g值和h值，并设父节点为当前节点，将该点放入开放列表
9. 如果开放列表为空但没有找到终点，则表示无法到达终点，算法结束。

其中，价值函数f(n)=g(n)+h(n)，如下图所示。在只知道当前点和目标点的路径情况下，无法精确计算h值，故h(n)是一种预估值。选择方案为曼哈顿距离、欧几里距离等，最常用的是使用曼哈顿距离。

三、代码演示 

3.1迷宫生成工具

直接使用代码生成迷宫（起点统一为左上角某点）

public class MazeGenerator {pri