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

￡神魔★判官ぃ 2024-04-06 13:56 51阅读 0赞

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

![在这里插入图片描述][24eccc939d434a16abe9518c7da94279.png_pic_center]  
![在这里插入图片描述][5d1ee382865f4ffea5f2219fd1be30d2.png_pic_center]  
![在这里插入图片描述][00cd507e1ac544698d210a6987542015.png_pic_center]  
![在这里插入图片描述][3ff8b1ad28ac444993bd216e395e77a6.png_pic_center]  
![在这里插入图片描述][37fa0979a73140f084becd2f5139290e.png_pic_center]  
![在这里插入图片描述][8b25cf1fd9b74d5291dfa70149f8135e.png_pic_center]  
![在这里插入图片描述][218ae61483d640faaf424296d99d6c1f.png_pic_center]  
![在这里插入图片描述][95ed702fbfaf463da880445ad2dc1a19.png_pic_center]  
![在这里插入图片描述][906e364eb51b434081872964df937e70.png_pic_center]  
![在这里插入图片描述][1679014ead0a450c9419200bf4531241.png_pic_center]

[24eccc939d434a16abe9518c7da94279.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/4b4ab67b728d41e29d73bcef680dfbc1.png
[5d1ee382865f4ffea5f2219fd1be30d2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/263c5d56c6ef46b0a591117d77f8bff5.png
[00cd507e1ac544698d210a6987542015.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/bc9223dd56004eab993bad72c063dee9.png
[3ff8b1ad28ac444993bd216e395e77a6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c1cd70e5d8ab48709eebdda60462caea.png
[37fa0979a73140f084becd2f5139290e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/11a66e01ef414d9b9e8b5005e5266cae.png
[8b25cf1fd9b74d5291dfa70149f8135e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a5343939836b45449260d3ea54adfb59.png
[218ae61483d640faaf424296d99d6c1f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/fff6cc57f36143c6b10423235b43f372.png
[95ed702fbfaf463da880445ad2dc1a19.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/5eda348eadf3488db975c86381d91f7c.png
[906e364eb51b434081872964df937e70.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c997e93aed9c4652af2b725186aa8900.png
[1679014ead0a450c9419200bf4531241.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f3396ffc6ab243e2abfc4e23f68c107d.png