A*(A星)算法Go lang实现

nobugtodebug · · 2067 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

之前发表一个A*的python实现,连接:点击打开链接

最近正在学习Go语言,基本的语法等东西已经掌握了。但是纸上得来终觉浅,绝知此事要躬行嘛。必要的练手是一定要做的。正好离写python版的A*不那么久远。这个例子复杂度中等。还可以把之前用python实现是没有考虑的部分整理一下。

这一版的GO实现更加模块化了,同时用二叉堆来保证了openlist的查找性能。可以说离应用到实现工程中的要求差距不太远了。

  1. package main
  2. import (
  3. "container/heap"
  4. "fmt"
  5. "math"
  6. "strings"
  7. )
  8. import "strconv"
  9. type _Point struct {
  10. x int
  11. y int
  12. view string
  13. }
  14. //========================================================================================
  15. // 保存地图的基本信息
  16. type Map struct {
  17. points [][]_Point
  18. blocks map[string]*_Point
  19. maxX int
  20. maxY int
  21. }
  22. func NewMap(charMap []string) (m Map) {
  23. m.points = make([][]_Point, len(charMap))
  24. m.blocks = make(map[string]*_Point, len(charMap)*2)
  25. for x, row := range charMap {
  26. cols := strings.Split(row, " ")
  27. m.points[x] = make([]_Point, len(cols))
  28. for y, view := range cols {
  29. m.points[x][y] = _Point{x, y, view}
  30. if view == "X" {
  31. m.blocks[pointAsKey(x, y)] = &m.points[x][y]
  32. }
  33. } // end of cols
  34. } // end of row
  35. m.maxX = len(m.points)
  36. m.maxY = len(m.points[0])
  37. return m
  38. }
  39. func (this *Map) getAdjacentPoint(curPoint *_Point) (adjacents []*_Point) {
  40. if x, y := curPoint.x, curPoint.y-1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  41. adjacents = append(adjacents, &this.points[x][y])
  42. }
  43. if x, y := curPoint.x+1, curPoint.y-1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  44. adjacents = append(adjacents, &this.points[x][y])
  45. }
  46. if x, y := curPoint.x+1, curPoint.y; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  47. adjacents = append(adjacents, &this.points[x][y])
  48. }
  49. if x, y := curPoint.x+1, curPoint.y+1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  50. adjacents = append(adjacents, &this.points[x][y])
  51. }
  52. if x, y := curPoint.x, curPoint.y+1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  53. adjacents = append(adjacents, &this.points[x][y])
  54. }
  55. if x, y := curPoint.x-1, curPoint.y+1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  56. adjacents = append(adjacents, &this.points[x][y])
  57. }
  58. if x, y := curPoint.x-1, curPoint.y; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  59. adjacents = append(adjacents, &this.points[x][y])
  60. }
  61. if x, y := curPoint.x-1, curPoint.y-1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
  62. adjacents = append(adjacents, &this.points[x][y])
  63. }
  64. return adjacents
  65. }
  66. func (this *Map) PrintMap(path *SearchRoad) {
  67. fmt.Println("map's border:", this.maxX, this.maxY)
  68. for x := 0; x < this.maxX; x++ {
  69. for y := 0; y < this.maxY; y++ {
  70. if path != nil {
  71. if x == path.start.x && y == path.start.y {
  72. fmt.Print("S")
  73. goto NEXT
  74. }
  75. if x == path.end.x && y == path.end.y {
  76. fmt.Print("E")
  77. goto NEXT
  78. }
  79. for i := 0; i < len(path.TheRoad); i++ {
  80. if path.TheRoad[i].x == x && path.TheRoad[i].y == y {
  81. fmt.Print("*")
  82. goto NEXT
  83. }
  84. }
  85. }
  86. fmt.Print(this.points[x][y].view)
  87. NEXT:
  88. }
  89. fmt.Println()
  90. }
  91. }
  92. func pointAsKey(x, y int) (key string) {
  93. key = strconv.Itoa(x) + "," + strconv.Itoa(y)
  94. return key
  95. }
  96. //========================================================================================
  97. type _AstarPoint struct {
  98. _Point
  99. father *_AstarPoint
  100. gVal int
  101. hVal int
  102. fVal int
  103. }
  104. func NewAstarPoint(p *_Point, father *_AstarPoint, end *_AstarPoint) (ap *_AstarPoint) {
  105. ap = &_AstarPoint{*p, father, 0, 0, 0}
  106. if end != nil {
  107. ap.calcFVal(end)
  108. }
  109. return ap
  110. }
  111. func (this *_AstarPoint) calcGVal() int {
  112. if this.father != nil {
  113. deltaX := math.Abs(float64(this.father.x - this.x))
  114. deltaY := math.Abs(float64(this.father.y - this.y))
  115. if deltaX == 1 && deltaY == 0 {
  116. this.gVal = this.father.gVal + 10
  117. } else if deltaX == 0 && deltaY == 1 {
  118. this.gVal = this.father.gVal + 10
  119. } else if deltaX == 1 && deltaY == 1 {
  120. this.gVal = this.father.gVal + 14
  121. } else {
  122. panic("father point is invalid!")
  123. }
  124. }
  125. return this.gVal
  126. }
  127. func (this *_AstarPoint) calcHVal(end *_AstarPoint) int {
  128. this.hVal = int(math.Abs(float64(end.x-this.x)) + math.Abs(float64(end.y-this.y)))
  129. return this.hVal
  130. }
  131. func (this *_AstarPoint) calcFVal(end *_AstarPoint) int {
  132. this.fVal = this.calcGVal() + this.calcHVal(end)
  133. return this.fVal
  134. }
  135. //========================================================================================
  136. type OpenList []*_AstarPoint
  137. func (self OpenList) Len() int { return len(self) }
  138. func (self OpenList) Less(i, j int) bool { return self[i].fVal < self[j].fVal }
  139. func (self OpenList) Swap(i, j int) { self[i], self[j] = self[j], self[i] }
  140. func (this *OpenList) Push(x interface{}) {
  141. // Push and Pop use pointer receivers because they modify the slice's length,
  142. // not just its contents.
  143. *this = append(*this, x.(*_AstarPoint))
  144. }
  145. func (this *OpenList) Pop() interface{} {
  146. old := *this
  147. n := len(old)
  148. x := old[n-1]
  149. *this = old[0 : n-1]
  150. return x
  151. }
  152. //========================================================================================
  153. type SearchRoad struct {
  154. theMap *Map
  155. start _AstarPoint
  156. end _AstarPoint
  157. closeLi map[string]*_AstarPoint
  158. openLi OpenList
  159. openSet map[string]*_AstarPoint
  160. TheRoad []*_AstarPoint
  161. }
  162. func NewSearchRoad(startx, starty, endx, endy int, m *Map) *SearchRoad {
  163. sr := &SearchRoad{}
  164. sr.theMap = m
  165. sr.start = *NewAstarPoint(&_Point{startx, starty, "S"}, nil, nil)
  166. sr.end = *NewAstarPoint(&_Point{endx, endy, "E"}, nil, nil)
  167. sr.TheRoad = make([]*_AstarPoint, 0)
  168. sr.openSet = make(map[string]*_AstarPoint, m.maxX+m.maxY)
  169. sr.closeLi = make(map[string]*_AstarPoint, m.maxX+m.maxY)
  170. heap.Init(&sr.openLi)
  171. heap.Push(&sr.openLi, &sr.start) // 首先把起点加入开放列表
  172. sr.openSet[pointAsKey(sr.start.x, sr.start.y)] = &sr.start
  173. // 将障碍点放入关闭列表
  174. for k, v := range m.blocks {
  175. sr.closeLi[k] = NewAstarPoint(v, nil, nil)
  176. }
  177. return sr
  178. }
  179. func (this *SearchRoad) FindoutRoad() bool {
  180. for len(this.openLi) > 0 {
  181. // 将节点从开放列表移到关闭列表当中。
  182. x := heap.Pop(&this.openLi)
  183. curPoint := x.(*_AstarPoint)
  184. delete(this.openSet, pointAsKey(curPoint.x, curPoint.y))
  185. this.closeLi[pointAsKey(curPoint.x, curPoint.y)] = curPoint
  186. //fmt.Println("curPoint :", curPoint.x, curPoint.y)
  187. adjacs := this.theMap.getAdjacentPoint(&curPoint._Point)
  188. for _, p := range adjacs {
  189. //fmt.Println("\t adjact :", p.x, p.y)
  190. theAP := NewAstarPoint(p, curPoint, &this.end)
  191. if pointAsKey(theAP.x, theAP.y) == pointAsKey(this.end.x, this.end.y) {
  192. // 找出路径了, 标记路径
  193. for theAP.father != nil {
  194. this.TheRoad = append(this.TheRoad, theAP)
  195. theAP.view = "*"
  196. theAP = theAP.father
  197. }
  198. return true
  199. }
  200. _, ok := this.closeLi[pointAsKey(p.x, p.y)]
  201. if ok {
  202. continue
  203. }
  204. existAP, ok := this.openSet[pointAsKey(p.x, p.y)]
  205. if !ok {
  206. heap.Push(&this.openLi, theAP)
  207. this.openSet[pointAsKey(theAP.x, theAP.y)] = theAP
  208. } else {
  209. oldGVal, oldFather := existAP.gVal, existAP.father
  210. existAP.father = curPoint
  211. existAP.calcGVal()
  212. // 如果新的节点的G值还不如老的节点就恢复老的节点
  213. if existAP.gVal > oldGVal {
  214. // restore father
  215. existAP.father = oldFather
  216. existAP.gVal = oldGVal
  217. }
  218. }
  219. }
  220. }
  221. return false
  222. }
  223. //========================================================================================
  224. func main() {
  225. presetMap := []string{
  226. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  227. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  228. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  229. "X . X X X X X X X X X X X X X X X X X X X X X X X X X",
  230. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  231. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  232. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  233. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  234. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  235. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  236. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  237. "X X X X X X X X X X X X X X X X X X X X X X X X . X X",
  238. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  239. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  240. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  241. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  242. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  243. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  244. ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
  245. }
  246. m := NewMap(presetMap)
  247. m.PrintMap(nil)
  248. searchRoad := NewSearchRoad(0, 0, 18, 10, &m)
  249. if searchRoad.FindoutRoad() {
  250. fmt.Println("找到了, 你看!")
  251. m.PrintMap(searchRoad)
  252. } else {
  253. fmt.Println("找不到路径!")
  254. }
  255. }





本文来自:博客园

感谢作者:nobugtodebug

查看原文:A*(A星)算法Go lang实现

入群交流(和以上内容无关):加入Go大咖交流群,免费领全套学习资料或添加微信:muxilin131420 备注:入群;或加QQ群:729884609

2067 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传