A*，A星算法Go lang实现

之前发表一个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. }

来自为知笔记(Wiz)