Skip to content

xyqh/AStar

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 

Repository files navigation

A*寻路算法

定义:

  1. g=起始点到当前点的距离
  2. h=当前点到终点的距离
  3. f=g+h
  4. s=起点,e=终点
  5. map[][]=地图,1=障碍物,0=可走的点
  6. around[][]=当前节点能到达的下一个节点及附加g值的集合;around[][0]=x偏移,around[][1]=y偏移,around[][2]=附加g
  7. visited[][]=遍历过的点的信息,包括fghxyparentNode
  8. openList=小顶堆(按f排序),记录待遍历的点

原理:

  1. 每次从openList里取f最小的点出发,遍历可到达的下一个点(必须是没走过的点)的集合

    1. 遍历到的点nextgh更新方式:g=parent.g+around[][2] h=(e-next)*10;parentaround遍历过的节点里面g值最小的那个,即使f最小;并更新next.parentNode=parent
  2. 记录visited[next.x][next.y]=next,将next压入优先队列openList

  3. 循环直到next==e时停止遍历

  4. 如果e没被遍历过,则寻路失败;否则,从e出发,不断寻找parentNode并压入结果数组,直到找到s。如果parentNode不存在,也视为寻路失败。

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages