type
status
date
slug
summary
tags
category
icon
password
a星寻路是寻路算法中比较常用的一种，核心是启发式寻路算法，实际开发中常用于计算最优路径，自动寻路等。
📝 原理
启发式寻路
假设从A点到B点,中间有障碍物；寻路中,肯定要绕过障碍物到达B点,所以,我们要寻找点c为过渡点。所以,引出两个关键词,实际消耗G和预估消耗H。过渡到c点后,实际消耗G为上一个点到c点的距离，然后在c点对目标点B点的距离进行估值,也就是预估消耗H，这边可以用曼哈顿距离去算，也就是从C点到终点忽略障碍物和对角移动要走多少个网格，去求出预估距离H；每走到一个新点时再次进行如上操作。最后得出可表达式最短权值F=G+H。
A星寻路
从起点A开始，把它作为当前待处理点存入一个OPEN表（OPEN表中放所有待处理的点）。
寻找起点周围所有可到达或者可通过的方格，障碍物方格不考虑。把他们加入OPEN表。这些周围节点的父节点设为当前点。(保存父节点是因为我们找到终点时需通过回溯到起点！)
在OPEN表中删除当前点，把它加入到一个CLOSE表中（CLOSE表中放所有不再检查的点）。
接下来通过启发式寻路找出OPEN表中F（权值）最小的点作为当前点（此步可用堆排序处理）；再次判断其周围点，如此循环往复，直到加入CLOSE表的点为终点（寻路结束，找到最优路径）或OPEN表空（没找到路径），找到终点后通过父节点指向回溯到起点得到最优path。
注意事项
判断当前待处理点的周围点时，若其中某个周围点A是障碍物或者已经在CLOSE表中，则不考虑；若其中某个周围点A在OPEN表中，那么要将点A先前的G值和当前待处理点的G值+当前待处理点到点A的距离作比较，若点A先前的G值更小，则说明有比从当前待处理点到达点A更快的点，所以不改变点A的权值和父节点指向，若当前待处理点的G值+当前待处理点到点A的距离更小，则说明有从当前待处理点到达点A是更快的，要改变点A的权值，并且父节点指向当前待处理点。
实例
代码如下：
A星必不可少的就是OPEN表：存放待处理点；CLOSE表：存放不再处理的点；权值F；实际消耗G和预估消耗H；可能再多一个存放路径的PATH表，核心还是启发式寻路！
- Author:lzzd
- URL:https://lazy-zed.com/article/c%2B%2B_1
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
.png?table=block&id=19885e12-7d7c-80e0-9466-ccfdb68a297f&t=19885e12-7d7c-80e0-9466-ccfdb68a297f)
.png?table=block&id=19885e12-7d7c-8090-b2f9-d59fd470ae2a&t=19885e12-7d7c-8090-b2f9-d59fd470ae2a)
