一. 简介
借助在前面stm32完成的贪吃蛇小游戏，现在借助A算法，来完成贪吃蛇的一个自动寻找食物的过程，从而解放我们的双手。终于从完成功能代码，到了算法的部分啦。经过这里例子，可以很好的感受将我们学习到的算法应用到实际的项目当中去。例如这里的寻路算法可以利用深度优先和广度优先搜索算法来完成，都是寻路入门级的算法。在A算法中，可以感受到排序算法的用处，以及数据结构的魅力。需要的可以关注哦
演示视频
欢迎关注微信公众号 FPGA之旅 回复 A*STM32贪吃蛇
获取下载链接
这里我是先在软件上实现，然后将其移植到stm32当中去。
二. 算法简介
算法的详细过程就不细细介绍了，主要来说一下实现的具体步骤，这样根据步骤，也可以自己实现出来，而不用看很多很多文章。
创建两个列表，一个为待访问列表，另外一个为已经访问列表
将起始点加入到待访问列表中，并计算其预估值F。
从待访问列表中选择预估值最小的点，作为当前节点，并在待访问列表中删除。
寻找当前节点附近的点，并计算其预估值，已经将当前节点，设置为它们的父节点，然后将这些点加入到待访问列表中
将当前节点加入到已经访问列表中
重复执行3-5。直到寻找到目标点。然后通过该点的父节点依次递推，几个获取到起始点到目标点的路径。
F = G + H.
H表示当前节点到目标点之间的距离值
G表示当前节点到起始点之间的距离值
计算得过程中，可以在前面加上权重，表示当前节点到那个点更为重要。
三. 代码实现
通过上面的步骤，一步一步就可以实现A*算法。
节点的定义，主要是定义了节点的预估值和父节点
//A*算法的节点 typedef struct Node { int F; Point2 p; struct Node* father; }Node;
待访问列表和已经访问列表，这样比较消耗内存，特别是对于单片机带说，后面再改善吧
Node nodeLists[140]; //待访问列表 Node visitedNodeLists[140]; //已经访问的列表 uint16_t nodeListsIndex = 0; uint16_t visitedNodeListsIndex = 0; uint16_t CurrListIndex = 0;
A*算法
主要流程入下，和上面的实现步骤是一致的，很好理解。
对待访问列表的排序是从大到小进行排序。这样我每次只需要取出最后一个就是最小的那个了，对于的Index值减一，就表示将其从待访问列表中移除，非常方便。 这个思想非常重要。
同时这里需要注意的是malloc可能申请不到内存，这也是头疼的一个问题。ε=(´ο｀*)))唉
uint8 AutoEateByAStar() { uint16 i; nodeListsIndex = 0; visitedNodeListsIndex = 0; CurrListIndex = 0; PathLen = 0; //目标位置 end.x = FoodPosition.x; end.y = FoodPosition.y; //起始位置 start.p.x = head->postion.x; start.p.y = head->postion.y; start.father = NULL; start.F = Assess(start.p, start.p, end); //将起始点，添加到待访问点 nodeLists[nodeListsIndex] = start; nodeListsIndex += 1; while (nodeListsIndex > 0) { Curr = (Node*)malloc(sizeof(Node)); Curr->F = nodeLists[nodeListsIndex - 1].F; Curr->p = nodeLists[nodeListsIndex - 1].p; Curr->father = nodeLists[nodeListsIndex - 1].father; nodeListsIndex -= 1; searchNeighboor(); visitedNodeLists[visitedNodeListsIndex] = *Curr; visitedNodeListsIndex += 1; //保存申请到的内存 CurrList[CurrListIndex] = Curr; CurrListIndex += 1; if (Curr->p.x == end.x && Curr->p.y == end.y) //查找到路径 { //保存路径 while (Curr->father != NULL) { PathByAStar[PathLen].x = Curr->p.x; PathByAStar[PathLen].y = Curr->p.y; PathLen += 1; printf("%d %d \r\n",Curr->p.x,Curr->p.y); Curr = Curr->father; } PathByAStar[PathLen].x = Curr->p.x; PathByAStar[PathLen].y = Curr->p.y; PathLen += 1; //释放申请到的内存 for (i = 0; i < CurrListIndex; i++) { free(CurrList[i]); CurrList[i] = NULL; } return 0; } } return 1; }
到这里A*寻路算法就差不多完成了，主要是在贪吃蛇中进行路径解析。
四. 贪吃蛇路径解析
这里解析也是非常容易的，因为在PathByAStar中已经保存到了路径值。所以只需要在每一次移动的时候，蛇头和下一个位置进行对比，就可以确定移动的方向了。代码如下，
if( PathByAStar[PathLen-1].y == head->postion.y) { if(PathByAStar[PathLen-1].x == head->postion.x -1) MoveDirection = MoveLeft; else MoveDirection = MoveRight; } else { if(PathByAStar[PathLen-1].y == head->postion.y -1) MoveDirection = MoveUp; else MoveDirection = MoveDown; } PathLen -= 1;
这样就完成。完整代码可以关注微信公众号 FPGA之旅 获取。
公众号：FPGA之旅
