定义:
- g=起始点到当前点的距离
- h=当前点到终点的距离
- f=g+h
- s=起点,e=终点
map[][]
=地图,1=障碍物,0=可走的点around[][]
=当前节点能到达的下一个节点及附加g值的集合;around[][0]
=x偏移,around[][1]
=y偏移,around[][2]
=附加g值visited[][]
=遍历过的点的信息,包括fgh和xy和parentNodeopenList
=小顶堆(按f排序),记录待遍历的点
原理:
-
每次从openList里取f最小的点出发,遍历可到达的下一个点(必须是没走过的点)的集合
- 遍历到的点next的g和h更新方式:
g=parent.g+around[][2]
h=(e-next)*10
;parent为around里遍历过的节点里面g值最小的那个,即使f最小;并更新next.parentNode=parent
- 遍历到的点next的g和h更新方式:
-
记录
visited[next.x][next.y]=next
,将next压入优先队列openList里 -
循环直到
next==e
时停止遍历 -
如果e没被遍历过,则寻路失败;否则,从e出发,不断寻找parentNode并压入结果数组,直到找到s。如果parentNode不存在,也视为寻路失败。