一. 简介
借助在前面stm32完成的贪吃蛇小游戏，现在借助A算法，来完成贪吃蛇的一个自动寻找食物的过程，从而解放我们的双手。终于从完成功能代码，到了算法的部分啦。经过这里例子，可以很好的感受将我们学习到的算法应用到实际的项目当中去。例如这里的寻路算法可以利用深度优先和广度优先搜索算法来完成，都是寻路入门级的算法。在A算法中，可以感受到排序算法的用处，以及数据结构的魅力。需要的可以关注哦



二. 算法简介
算法的详细过程就不细细介绍了，主要来说一下实现的具体步骤，这样根据步骤，也可以自己实现出来，而不用看很多很多文章。

1.创建两个列表，一个为待访问列表，另外一个为已经访问列表
2.将起始点加入到待访问列表中，并计算其预估值F。
3.从待访问列表中选择预估值最小的点，作为当前节点，并在待访问列表中删除。
4.寻找当前节点附近的点，并计算其预估值，已经将当前节点，设置为它们的父节点，然后将这些点加入到待访问列表中
5.将当前节点加入到已经访问列表中
6.重复执行3-5。直到寻找到目标点。然后通过该点的父节点依次递推，几个获取到起始点到目标点的路径。
F = G + H.
H表示当前节点到目标点之间的距离值
G表示当前节点到起始点之间的距离值
计算得过程中，可以在前面加上权重，表示当前节点到那个点更为重要。

三. 代码实现
通过上面的步骤，一步一步就可以实现A*算法。

1.节点的定义，主要是定义了节点的预估值和父节点

1. //A*算法的节点
   
2. typedef struct Node
   
3. {
   
4.         int F;   
   
5.         Point2 p;
   
6.         struct Node* father;
   
7. }Node;

复制代码

2.待访问列表和已经访问列表，这样比较消耗内存，特别是对于单片机带说，后面再改善吧

1. Node nodeLists[140];   //待访问列表
   
2. Node visitedNodeLists[140];  //已经访问的列表
   
3. uint16_t   nodeListsIndex = 0;
   
4. uint16_t   visitedNodeListsIndex = 0;
   
5. uint16_t   CurrListIndex = 0;

复制代码

3.A*算法
主要流程入下，和上面的实现步骤是一致的，很好理解。

对待访问列表的排序是从大到小进行排序。这样我每次只需要取出最后一个就是最小的那个了，对于的Index值减一，就表示将其从待访问列表中移除，非常方便。 这个思想非常重要。
同时这里需要注意的是malloc可能申请不到内存，这也是头疼的一个问题。ε=(´ο｀*)))唉

1. uint8 AutoEateByAStar()
   
2. {
   
3.     uint16 i;
   
4.     nodeListsIndex = 0;
   
5.         visitedNodeListsIndex = 0;
   
6.     CurrListIndex = 0;
   
7.     PathLen = 0;
   
8.     //目标位置
   
9.     end.x = FoodPosition.x;
   
10.     end.y = FoodPosition.y;
    
11. 
    
12.     //起始位置
    
13.     start.p.x = head->postion.x;
    
14.     start.p.y = head->postion.y;
    
15.     start.father = NULL;
    
16.     start.F = Assess(start.p, start.p, end);
    
17. 
    
18.     //将起始点，添加到待访问点
    
19.     nodeLists[nodeListsIndex] = start;
    
20.         nodeListsIndex += 1;
    
21. 
    
22.     while (nodeListsIndex > 0)
    
23.         {
    
24.                
    
25.                 Curr = (Node*)malloc(sizeof(Node));
    
26.                 Curr->F = nodeLists[nodeListsIndex - 1].F;
    
27.                 Curr->p = nodeLists[nodeListsIndex - 1].p;
    
28.                 Curr->father = nodeLists[nodeListsIndex - 1].father;
    
29.                 nodeListsIndex -= 1;
    
30. 
    
31.                 searchNeighboor();
    
32.                 visitedNodeLists[visitedNodeListsIndex] = *Curr;
    
33.                 visitedNodeListsIndex += 1;
    
34. 
    
35. 
    
36.         //保存申请到的内存
    
37.         CurrList[CurrListIndex] = Curr;
    
38.                 CurrListIndex += 1;
    
39.         if (Curr->p.x == end.x && Curr->p.y == end.y)  //查找到路径
    
40.         {
    
41. 
    
42.             //保存路径
    
43.             while (Curr->father != NULL)
    
44.             {
    
45.                 PathByAStar[PathLen].x =  Curr->p.x;
    
46.                 PathByAStar[PathLen].y =  Curr->p.y;
    
47.                 PathLen += 1;
    
48.                 printf("%d %d \r\n",Curr->p.x,Curr->p.y);
    
49.                 Curr = Curr->father;
    
50. 
    
51.             }
    
52.             PathByAStar[PathLen].x =  Curr->p.x;
    
53.             PathByAStar[PathLen].y =  Curr->p.y;
    
54.             PathLen += 1;
    
55.             //释放申请到的内存
    
56.             for (i = 0; i < CurrListIndex; i++)
    
57.                         {
    
58.                                 free(CurrList<i>);
    
59.                                 CurrList<i> = NULL;
    
60.                         }
    
61.            return 0;
    
62.         }
    
63.     }
    
64.     return 1;
    
65. }</i></i>

复制代码

到这里A*寻路算法就差不多完成了，主要是在贪吃蛇中进行路径解析。

四. 贪吃蛇路径解析
这里解析也是非常容易的，因为在PathByAStar中已经保存到了路径值。所以只需要在每一次移动的时候，蛇头和下一个位置进行对比，就可以确定移动的方向了。代码如下，

1. if( PathByAStar[PathLen-1].y == head->postion.y)
   
2. {
   
3.       if(PathByAStar[PathLen-1].x == head->postion.x -1)
   
4.           MoveDirection = MoveLeft;
   
5.       else
   
6.           MoveDirection = MoveRight;
   
7.   }
   
8. else
   
9.   {
   
10.       if(PathByAStar[PathLen-1].y == head->postion.y -1)
    
11.           MoveDirection = MoveUp;
    
12.       else
    
13.           MoveDirection = MoveDown;
    
14.   }
    
15.   PathLen -= 1;
    

复制代码