基于html和js实现的A_算法实现迷宫寻路功能

一、实验内容
熟悉和掌握 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>

在这里插入图片描述

相关阅读:
GO GMP协程调度实现原理 5w字长文史上最全
Python（10）列表例题重写＜1＞
常见产品结构四大类型优劣势比较
我是如何组织 Go 代码的（目录结构依赖注入 wire）
Allegro SigXplorer 等长设置方法-比较简单
node 获取请求者的ip地址
2022-01-15 开发代码感悟
Kubernetes(k8s)的三种资源管理方式
本地代码上传到gitlab
uni-app多次触发事件，防止重复点击

原文地址：https://blog.csdn.net/newlw/article/details/127085418