a*寻路分析

时间:2023-03-09 19:15:24
a*寻路分析

http://dev.gameres.com/Program/Abstract/Arithmetic/A%20Pathfinding%20for%20Beginners.htm

a*寻路分析

a*寻路分析

a*寻路分析

a*寻路分析

定义:

绿色节点为A

红色节点为B

A右边为C

Dst:使用两点距离计算公式

表Op :储存节点用 (开放列表)

表Cl :储存节点用 (开放列表)

节点的上级节点 名为 FN

GL : 节点属性 用于储存与A的距离

下述计算过程定义为 过程1

Strat

  计算 C 与 B 的距离( Dst )  结果为 H

  计算 C 与 A 的距离( Dst )  结果为 G

  F=H+G

将 C 加入 表Op

C 的 FN = A

C 的 GL = FN 的 GL + C与A的距离

End

把 A 周围的节点都使用 过程1 计算一遍(不包含 表Cl 里的节点,及不可通过节点),选择 F 较小的做为新节点(定义:新节点=N)

将 A 加入 表Cl,N 加入 表Cl,从 表Op 移除 N

将 N 当成 A 以 过程1 计算 直至找到 B。

对于 表Op 里的节点的使用:

表Op 里的节点有时会包含 N 周围的节点,包含时这个节点定义为 M

计算 M 的 FN  离 A 近 还是将 N 当为 M 的 FN 离 A 近   (主要使用了 GL)

结果路线为 B 的 FN 的 FN 直到A

http://files.cnblogs.com/mattins/aStar.zip