一、实验内容
熟悉和掌握 A* 算法实现迷宫寻路功能
二、实验设计（原理分析及流程）
原理分析：A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)小于等于n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
流程：
1，从起点A开始, 把它作为待处理的方格存入一个”开启列表”, 开启列表就是一个等待检查方格的列表.
2，寻找起点A周围可以到达的方格, 将它们放入”开启列表”, 并设置它们的”父方格”为A.
3，从”开启列表”中删除起点 A, 并将起点 A 加入”关闭列表”, “关闭列表”中存放的都是不需要再次检查的方格.
4， 从 “开启列表” 中选择 F 值最低的方格C.
5，把它从 “开启列表” 中删除, 并放到 “关闭列表” 中.
6，检查它所有相邻并且可以到达 (障碍物和 “关闭列表” 的方格都不考虑) 的方格. 如果这些方格还不在 “开启列表” 里的话, 将它们加入 “开启列表”, 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的 “父方格”为C .
7， 如果某个相邻方格 D 已经在 “开启列表” 里了, 检查如果用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些, 本文转载自http://www.biyezuopin.vip/onews.asp?id=14790如果新的G值更低, 那就把它的 “父方格” 改为目前选中的方格 C, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做.
8，然后继续找F值最小的，如此循环下去…
把起始格添加到 “开启列表”
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
<title>Astar</title>
<style>
canvas {
margin-top: 10px;
}
#msg {
margin-left: 10px;
}
</style>
</head>
<body>
<div>
<button id="setStart">设置起点</button>
<button id="setEnd">设置终点</button>
<button id="navigate">寻找路径</button>
<span id='msg'></span>
</div>
<canvas id="canvas"></canvas>
<script src="Astar.js"></script>
</body>
</html>
