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

' ^6 t: {+ X6 V  F8 y3 f# |2 O
7 }7 f( _+ P, n' u, C: O7 B/ E
二. 算法简介
算法的详细过程就不细细介绍了，主要来说一下实现的具体步骤，这样根据步骤，也可以自己实现出来，而不用看很多很多文章。
: `1 }2 y1 X' R6 t* m6 M4 [3 S
1.创建两个列表，一个为待访问列表，另外一个为已经访问列表
7 A+ b4 k* G" t9 G4 x2.将起始点加入到待访问列表中，并计算其预估值F。
% ?/ i7 c5 n* I" C; m' ?& E3.从待访问列表中选择预估值最小的点，作为当前节点，并在待访问列表中删除。
4.寻找当前节点附近的点，并计算其预估值，已经将当前节点，设置为它们的父节点，然后将这些点加入到待访问列表中
# t5 P) M8 {8 m( V' h/ O0 ?5.将当前节点加入到已经访问列表中
7 y4 }" k: J8 H; [9 k. l6.重复执行3-5。直到寻找到目标点。然后通过该点的父节点依次递推，几个获取到起始点到目标点的路径。
F = G + H.
$ Z$ P' a! y7 C6 Y0 r/ @. J3 yH表示当前节点到目标点之间的距离值
' x5 ?( A% M6 Y9 R! J+ }2 `( yG表示当前节点到起始点之间的距离值
计算得过程中，可以在前面加上权重，表示当前节点到那个点更为重要。
! d9 R* M$ Z! ^8 Z
9 V( r# P* N- ?& ?三. 代码实现
通过上面的步骤，一步一步就可以实现A*算法。
% W' z9 p! u- V" u2 J
  D2 g0 ^8 Z3 B9 k/ k% ]! q1.节点的定义，主要是定义了节点的预估值和父节点
3 k3 c8 g& o* K0 D' k

1. //A*算法的节点
   
2. typedef struct Node
   
3. {
   
4.         int F;   
   + Q, k* v2 `* Q, E! x- w# Q( p
5.         Point2 p;
   ) O! K5 g# Y$ o! Z, Y
6.         struct Node* father;
   7 ]# a5 f' T( {- Q. T! w
7. }Node;

复制代码

2 x- k' [+ J' @7 `, v5 _& r6 x- t. ?2.待访问列表和已经访问列表，这样比较消耗内存，特别是对于单片机带说，后面再改善吧

1. Node nodeLists[140];   //待访问列表
   ; t( S* |( Z) B5 Z
2. Node visitedNodeLists[140];  //已经访问的列表
   
3. uint16_t   nodeListsIndex = 0;
   
4. uint16_t   visitedNodeListsIndex = 0;
   + V+ H% u: F" D+ ?
5. uint16_t   CurrListIndex = 0;

复制代码

' d+ }/ V2 R' l8 S* {% a5 W3.A*算法
! H6 [7 r, r" q( T- G主要流程入下，和上面的实现步骤是一致的，很好理解。

对待访问列表的排序是从大到小进行排序。这样我每次只需要取出最后一个就是最小的那个了，对于的Index值减一，就表示将其从待访问列表中移除，非常方便。 这个思想非常重要。
同时这里需要注意的是malloc可能申请不到内存，这也是头疼的一个问题。ε=(´ο｀*)))唉
, y+ I( u9 F1 [5 U% G0 a/ C; W' x2 Z
/ K5 Q* L, {7 f) ^% c" _

1. uint8 AutoEateByAStar()
   
2. {
   
3.     uint16 i;
   
4.     nodeListsIndex = 0;
   
5.         visitedNodeListsIndex = 0;
   & ^5 ^8 {- s" ^5 c
6.     CurrListIndex = 0;
   
7.     PathLen = 0;
   
8.     //目标位置
   3 s. n% q# I( z3 N
9.     end.x = FoodPosition.x;
   
10.     end.y = FoodPosition.y;
    
11. 
    
12.     //起始位置
    ; A7 {1 @; A9 A5 W  U
13.     start.p.x = head->postion.x;
      Z& [% z  G  [! C
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;
    9 h2 V0 l0 |; K' k9 {  G* [
21. 
    
22.     while (nodeListsIndex > 0)
    
23.         {
    ( }, h/ e# F. d0 }. T, t! f  y
24.                
    3 Q( G. p7 S* `& G& k5 T
25.                 Curr = (Node*)malloc(sizeof(Node));
    
26.                 Curr->F = nodeLists[nodeListsIndex - 1].F;
    1 Y4 l( B, g7 d- D: [
27.                 Curr->p = nodeLists[nodeListsIndex - 1].p;
    4 S; X" H1 D0 Z% R
28.                 Curr->father = nodeLists[nodeListsIndex - 1].father;
    3 C- K* S' w' N
29.                 nodeListsIndex -= 1;
    
30. 
      Q1 N+ Y7 q! l, r  |# ~' v
31.                 searchNeighboor();
    % s8 q6 b  F0 A; f5 S1 J2 p: s; B8 l
32.                 visitedNodeLists[visitedNodeListsIndex] = *Curr;
    
33.                 visitedNodeListsIndex += 1;
    5 L3 A6 P5 ?6 Z& ?  U- O
34. 
    6 u' L- [! Q/ ?4 `9 S" S
35. 
    
36.         //保存申请到的内存
    
37.         CurrList[CurrListIndex] = Curr;
    4 ^; n% D* l% t2 ~
38.                 CurrListIndex += 1;
    
39.         if (Curr->p.x == end.x && Curr->p.y == end.y)  //查找到路径
    
40.         {
    & H' J* Y2 N; d4 {, y
41. 
    2 C6 a. d1 s. b
42.             //保存路径
    
43.             while (Curr->father != NULL)
    % b  J: X7 `6 v: J  }
44.             {
    " a) f) Y5 p+ [  c) j- u
45.                 PathByAStar[PathLen].x =  Curr->p.x;
    
46.                 PathByAStar[PathLen].y =  Curr->p.y;
    ( r$ S' v- e( P/ T+ F; M
47.                 PathLen += 1;
    / f5 H  I# x% q' G
48.                 printf("%d %d \r\n",Curr->p.x,Curr->p.y);
    
49.                 Curr = Curr->father;
    ' p9 M0 P! l. K  w
50. 
    
51.             }
    ( Z0 m0 ~/ A% Q( A
52.             PathByAStar[PathLen].x =  Curr->p.x;
    6 {! _2 ?& A! {3 P7 Z
53.             PathByAStar[PathLen].y =  Curr->p.y;
    . Q7 |/ ^! W7 x1 o1 K* B, m
54.             PathLen += 1;
      {& Q$ Y  v. d4 ?9 f; [% P. X" H
55.             //释放申请到的内存
    ! I" t7 V8 t" _! h, z3 N# W: r
56.             for (i = 0; i < CurrListIndex; i++)
    
57.                         {
    
58.                                 free(CurrList<i>);
    & K) m& ]4 J5 N+ t
59.                                 CurrList<i> = NULL;
    
60.                         }
    
61.            return 0;
    
62.         }
    1 v/ K4 s" S1 M! N; V1 i, U% l9 e
63.     }
    
64.     return 1;
    
65. }</i></i>

复制代码

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

% x; ]( ~" m5 v: B1 O' W1 Y四. 贪吃蛇路径解析
: ]" I; c2 j* X- O2 A8 I这里解析也是非常容易的，因为在PathByAStar中已经保存到了路径值。所以只需要在每一次移动的时候，蛇头和下一个位置进行对比，就可以确定移动的方向了。代码如下，

1. if( PathByAStar[PathLen-1].y == head->postion.y)
   3 ^" e9 ~0 d1 T* Z+ x
2. {
   
3.       if(PathByAStar[PathLen-1].x == head->postion.x -1)
   9 t3 Y' p' r" `* Y+ {
4.           MoveDirection = MoveLeft;
   # a# O# e+ N) S, Y4 c2 o& a( x% r
5.       else
     q& G2 I) l' G0 v/ E" L
6.           MoveDirection = MoveRight;
   
7.   }
   
8. else
   
9.   {
   
10.       if(PathByAStar[PathLen-1].y == head->postion.y -1)
    + M2 S: `: z. y; S5 V* l3 b
11.           MoveDirection = MoveUp;
    
12.       else
    
13.           MoveDirection = MoveDown;
    ) Z* t3 J3 r; }8 V' T2 }- T
14.   }
    5 I5 x2 G$ c% D* L: L, R5 S; P
15.   PathLen -= 1;
    ' o! {3 X$ O$ t; g* Y/ R

复制代码

$ h: f2 o, i4 P" ~. z4 N3 l