qt-a星算法

vtor

【0】序
学习视频网址：https://www.bilibili.com/video/BV1Cv411x76X
gitee网址：https://gitee.com/vtor3478/AStar
github网址：https://github.com/vtor3478/Astar
此为a星算法工程，用qt绘制ui
能实现寻路，但还存在会绕路的bug
看懂此文，你需要掌握：c语言基础，qt基础，数据结构基础
具体内容是：二维数组，多叉树，指针，qt信号与槽，qt窗口坐标系
本文发布于vtor3478博客园，52破解论坛，影子论坛，vtor3478_offical微信公众号

【01】a星算法基础
f代价：总代价，为g+h+w（w暂时不考虑）
g代价：gCost：表示从起点到当前点的代价
g代价：hCost：表明从此点到终点的预估代价，在程序中使用曼哈顿距离进行运算
代价一般使用距离进行表示，所以找最小代价的路径，就是寻找最短距离
每次寻找终点，都从代价最小的点去找，从而使得本次寻路代价最小
当找到终点后，从终点回溯，如果能找到起点，那么说明寻路成功
如果所有的最小代价点都用完了，还是没有找到终点，说明寻路失败（路径不存在）

【02】代码基础
char snakeOccury[ROW][COL]，地图，0为空地，可行走，1为墙壁，不可行走
QPoint startPos,endPos，从起点出发，前往终点
char walkMark[ROW][COL]数组表示当前空地节点是否探索（墙不在考虑范围内）
Cell_Struct* cellCost[ROW * COL]用于存储可探索节点的指针，用于寻找最小代价点

地图上每个格子可以看作一个节点，取名结构体CELL_t

[C++] 纯文本查看 复制代码

// 设计一个节点模式，
typedef struct Cell_Struct{
    QPoint pos; // 当前格子的坐标
    int gCost; // g代价，表明已走代价
    int hCost; // h代价，表明预估到终点代价
    struct Cell_Struct* parent; // 走到当前格子的父格子
    struct Cell_Struct* Childs[4]; // 此格子往4个方向，走向4个不同的格子
}Cell_t;

Cell_Struct* prootCell：坐标为起点的节点结构体指针
Cell_Struct* pnowCell：树中的当前节点结构体指针

// 定义对数组的方向，前面坐标控制上下，后面坐标控制左右
#define DIR_UP      QPoint(-1,0)等等，具体看完整代码吧
使用qpoint可以快捷的计算坐标

行数与列数，使用ROW与COL宏进行表示


【03】代码模块化设计
【03.01】PushCostCell
【03.02】PopMinCostCell
把可探索的节点塞入一段buffer内，
每次使用都弹出代价最小的节点的指针并返回，弹出就会将此节点删除
不需要过度关注这里怎么实现

【04】代码逻辑设计
【04.01】AStarInit
好像依然存在内存泄漏，，，以后再补救吧
主要工作是释放内存，清除路径，生成地图等
清空cellCost数组与walkMark数组，重新指向指针等操作，
一开始内部代码很少，只是后来加了许多优化，导致代码变多
创建prootCell节点、赋值，并装入costCell内，便于寻路时取出
【04.02】AStarSearch
从costCell获取最小代价点，
判断是否存在最小代价节点，判断是否已经走到了终点
原本是死循环，后来改为单次，并由定时器进行调用，便于实时打印探索路径
具体寻路操作：当前节点4个方向，寻路，判断4个方向是否可以走
（如果是数组越界，不可走，如果是墙壁，不可走，如果已走过不必要走）
如果可走：申请内存，命名为pchildCell，对坐标赋值，计算gCost与hCost，
并建立与其父节点（与就是当前节点）的指针联系，需要双向指针都进行指向
并将pchildCell装入costCell内，用于下次寻址


【05】代价调试优化
runTimer定时器逐次调用AStarSearch，手动控制寻路速度
updateTimer定时器实时更新绘图事件，绘制ui
startBtn按钮启动寻路
mousePressEvent计算坐标，实现对墙壁与空地的翻转
randMapCheckBox复选框判断是否随机生成路径

【06】阶段性截图
文字描述在前，图片在后
寻路是动态的，但是52不支持gif文件和wmv格式，
所以只好使用博客园的链接用于展示
03-正常寻路
[url=]https://img2022.cnblogs.com/blog/2472635/202203/2472635-20220329001132590-1177791240.gif[/url]
04-堵住上路，自动切换到下路
https://img2022.cnblogs.com/blog/2472635/202203/2472635-20220329001146098-142996683.gif
05-恶意障碍
https://img2022.cnblogs.com/blog/2472635/202203/2472635-20220329001204322-893348470.gif
06-绕路缺陷
https://img2022.cnblogs.com/blog/2472635/202203/2472635-20220329001219371-678109534.gif

【07】代码待优化
好像还存在内存泄漏bug，暂时懒得修复
寻路可能出现绕路，见阶段性截图
应该在可探索节点旁边进行判断，
如果相邻节点有代价低于2的，那么重新建立父链接，暂时不清楚怎么实现

【08】修订记录
20220328-初始版本

ciker_li

学习学习，学不懂啊

海尔波普彗星

学习学习

vtor

ciker_li 发表于 2022-3-29 10:07
学习学习，学不懂啊

我在【00】内说明了查看此文所需要的基础知识
如果是基础不好，建议重学基础
如果基础好，那么先看看【02】a星算法基础，
再看【04】逻辑设计，逐步理解
还可以装上qt，下载代码，再进行逐步调试

vtor

顶一下自己的贴子
astar，a星算法，这个还是比较冷门啊
还是py与java，c/c++比较火