OSI

54

66

48

N2

62

AT1:42

38

AD2

14

82

N1

56

N3

24

A_1_M1_M1

A_2_D1:68

A_1_M1

AT2:48

B

A

A_2_M1

28

68

A_1_M1_M1:54

N4

AT1

N5

52

AD2:62

图10：第8次寻找

AD3

A_3_M1_D1

黄色：代表下次将要选中的方块

N6

AM2:62

20

A_1_T2_T3:68

AD1

30

74

开放列表

A:0

10

AT3

40

A_2_M1_D1:74

AM1

58

A_4_M1_M1

AM2

不可行走区域

图8：第6次寻找

AT2

AM1:48

42

AT3:62

AD3:70

关闭列表

A_1_M1:48

70

A_1_D1

图1：A*寻路

A_3_M1_DD

A_1_M1_T1

A_2_M1_D1

A_4_M1_D1

1.获取F值最小的方块AM1=48，将其加入关闭列表2.寻找AM1周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.如果AM1周围的方块存在开放列表中，则计算经AT2到达该方块的G值(从A走，按照父子关系)，如果计算的G值比存在开放列表中的该方块的G值要小的话，则更新开放列表中该方块的G值和F值，且改变该物体的父物体为AM1，如果计算G值大于开放列表中的G值，则不改变开放列表中该方块的值4.将可行走的方块加入开放列表，F值顺序排列5.将可行走的方块的父物体全部设为AM16.选取F值最小的，如果F最小，则比价H值，选取H值最小的********************************************************此次操作更新的开放的列表中的方块有：A_1_D1:G值变化:28-20F值变化:62-54父物体变化：从AT1变为AM1名称变换：从A_1_D1变为A_1_M1_M1

AD1:62

A_2_M1_M1

34

44

A_1_T2_T3

A_2_D1

A_3_T1_T1

图3：第1次寻找

命名规则：A_1_T1 ：A:起始点1：距离A的层级T1：位于父级的方向第一个M1:如果是同级父物体，单靠数字无法唯一定义物体，所以增加M1来辨识

A_3_M1_M1:68

A_3_M1_M1

A_1_T1

72

1.获取F值最小的方块AT2=48，将其加入关闭列表2.寻找AT2周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.如果AT2周围的方块存在开放列表中，则计算经AT2到达该方块的G值(从A走，按照父子关系)，如果计算的G值比存在开放列表中的该方块的G值要小的话，则更新开放列表中该方块的G值和F值，且改变该物体的父物体为AT2，如果计算G值大于开放列表中的G值，则不改变开放列表中该方块的值4.将可行走的方块加入开放列表，F值顺序排列5.将可行走的方块的父物体全部设为AT26.选取F值最小的，如果F最小，则比价H值，选取H值最小的********************************************************此次操作更新的开放的列表中的方块有：无

88

60

A_2_M1:54

A_1_T3_T3

1.将A加入关闭列表中2.寻找A周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.将可行走的方块的父物体全部设为A4.将可行走的方块加入开放列表，F值顺序排列

红色：代表本次寻找过程中改变的值

A_3_M1_DD:88

A_1_M1_T1:62

A_2_M1_M1:60

A_5_M1_M1

A_2_T3_T3

A_1_D1:62

A_3_T1_T3

1.获取F值最小的方块A_2_M1=54，将其加入关闭列表2.寻找A_2_M1周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.如果A_2_M1周围的方块存在开放列表中，则计算经A_2_M1到达该方块的G值(从A走，按照父子关系)，如果计算的G值比存在开放列表中的该方块的G值要小的话，则更新开放列表中该方块的G值和F值，且改变该物体的父物体为A_2_M1，如果计算G值大于开放列表中的G值，则不改变开放列表中该方块的值4.将可行走的方块加入开放列表，F值顺序排列5.将可行走的方块的父物体全部设为A_2_M16.选取F值最小的，如果F最小，则比价H值，选取H值最小的********************************************************此次操作更新的开放的列表中的方块有：无

A_4_M1_T1

图4：第2次寻找

A_1_M2_D3

图2：初始化

A_3_M1_D1:82

76

90

1.获取F值最小的方块AT1=42，将其加入关闭列表2.寻找AT1周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.如果AT1周围的方块存在开放列表中，则计算经AT1到达该方块的G值(从A走，按照父子关系)，如果计算的G值比存在开放列表中的该方块的G值要小的话，则更新开放列表中该方块的G值和F值，且改变该方块的父物体为AT1，如果计算G值大于开放列表中的G值，则不改变开放列表中该方块的值4.将可行走的方块加入开放列表，F值顺序排列5.将可行走的方块的父物体全部设为AT16.选取F值最小的，如果F最小，则比价H值，选取H值最小的********************************************************此次操作更新的开放的列表中的方块有：无

96

A_3_T1_T2

A_2_T3_T1

命名规则：A_1_T1 ：A:起始点1：距离A的层级T1：位于父级的方向

1.获取F值最小的方块A_2_M1_M1=60，将其加入关闭列表2.寻找A_2_M1_M1周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.如果A_2_M1_M1周围的方块存在开放列表中，则计算经A_2_M1_M1到达该方块的G值(从A走，按照父子关系)，如果计算的G值比存在开放列表中的该方块的G值要小的话，则更新开放列表中该方块的G值和F值，且改变该物体的父物体为A_2_M1_M1，如果计算G值大于开放列表中的G值，则不改变开放列表中该方块的值4.将可行走的方块加入开放列表，F值顺序排列5.将可行走的方块的父物体全部设为A_2_M1_M16.选取F值最小的，如果F最小，则比价H值，选取H值最小的********************************************************此次操作更新的开放的列表中的方块有：A_3_M1_D1:G值变化:48-40F值变化:82-74父物体变化：从A_2_M1变为A_3_M1_D1

图6：第4次寻找

A_2_T3_T2

A_3_M1_D1:74

A_1_M2_T3

图9：第7次寻找

1.获取F值最小的方块A_1_M1=48，将其加入关闭列表2.寻找A_1_M1周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.如果A_1_M1周围的方块存在开放列表中，则计算经A_1_M1到达该方块的G值(从A走，按照父子关系)，如果计算的G值比存在开放列表中的该方块的G值要小的话，则更新开放列表中该方块的G值和F值，且改变该方块的父物体为A_1_M1，如果计算G值大于开放列表中的G值，则不改变开放列表中该方块的值4.将可行走的方块加入开放列表，F值顺序排列5.将可行走的方块的父物体全部设为A_1_M16.选取F值最小的，如果F最小，则比价H值，选取H值最小的********************************************************此次操作更新的开放的列表中的方块有：无

A_1_M2_M2

50

图11：最终图

1.获取F值最小的方块A_1_M1_M1=54，将其加入关闭列表2.寻找A_1_M1_M1周围的可行走的方块，通过与不可行走区域列表和关闭列表进行比较获得3.如果A_1_M1_M1周围的方块存在开放列表中，则计算经A_1_M1_M1到达该方块的G值(从A走，按照父子关系)，如果计算的G值比存在开放列表中的该方块的G值要小的话，则更新开放列表中该方块的G值和F值，且改变该物体的父物体为A_1_M1_M1，如果计算G值大于开放列表中的G值，则不改变开放列表中该方块的值4.将可行走的方块加入开放列表，F值顺序排列5.将可行走的方块的父物体全部设为A_1_M1_M16.选取F值最小的，如果F最小，则比价H值，选取H值最小的********************************************************此次操作更新的开放的列表中的方块有：A_2_D1:G值变化:38-30F值变化:68-60父物体变化：从A_1_M1变为A_1_M1_M1名称变换：从A_2_D1变为A_2_M1_M1

图7：第5次寻找

A_3_T1_M1

图5：第3次寻找