百木园1 func absInt(x int) int { 2 if x < 0 { 3 return -x 4 } 5 return x 6 }
下面会用到此方法, int类型值取绝对值
1 type sp_item struct { 2 x int 3 y int 4 g int 5 h int 6 f int 7 p *sp_item 8 } 9 10 type sp_open []*sp_item 11 12 func (sp sp_open) Len() int { 13 return len(sp) 14 } 15 16 func (sp sp_open) Less(i, j int) bool { 17 return sp[i].f < sp[j].f 18 } 19 20 func (sp sp_open) Swap(i, j int) { 21 sp[i], sp[j] = sp[j], sp[i] 22 } 23 24 func (sp sp_open) exceptFirst() sp_open { 25 var newSps []*sp_item 26 for i := 1; i < len(sp); i++ { 27 newSps = append(newSps, sp[i]) 28 } 29 return newSps 30 } 31 32 func (sp sp_open) getIndex(x, y int) int { 33 for i, v := range sp { 34 if v.x == x && v.y == y { 35 return i 36 } 37 } 38 return -1 39 }
这是open列表(带检索的列表)
Len()
Less(i, j int)
Swap(i, j int)
上面三个方法是自定义排序(sp_item.f从小到大排序)
exceptFirst()
复制 sp_open 数组并返回, 不包含第一个 sp_item
getIndex(x, y int)
获取与参数x,y匹配的 sp_item,返回其当前索引或-1
1 type sp_close []int 2 3 func (sp sp_close) contains(x, y int) bool { 4 for k := 0; k < len(sp); k += 2 { 5 if sp[k] == x && sp[k+1] == y { 6 return true 7 } 8 } 9 return false 10 }
这是close列表(不在检索的列表)
contains(x, y int)
sp_close 是否包含参数x,y
1 type sp_dots [8]int 2 3 func (sp sp_dots) getIndex(x, y int) int { 4 for i := 0; i < 8; i += 2 { 5 if sp[i] == x && sp[i+1] == y { 6 return i 7 } 8 } 9 return -1 10 } 11 12 func (sp *sp_dots) put(x, y int) { 13 _x := x - 1 14 x_ := x + 1 15 _y := y - 1 16 y_ := y + 1 17 sp[0], sp[1], sp[2], sp[3], sp[4], sp[5], sp[6], sp[7] = x, _y, _x, y, x_, y, x, y_ 18 } 19 20 func (sp *sp_dots) putA(x, y int) { 21 _x := x - 1 22 x_ := x + 1 23 _y := y - 1 24 y_ := y + 1 25 sp[0], sp[1], sp[2], sp[3], sp[4], sp[5], sp[6], sp[7] = _x, _y, x_, _y, _x, y_, x_, y_ 26 }
此类型用于获取参数x,y周围的4个点
put(x, y int)
填充 sp_dots, 周围正对面的四个索引点
putA(x, y int)
填充 sp_dots, 周围四个角的索引点
1 type SeekPath struct { 2 BevelAngle bool //是否可以走斜角 3 Timeout time.Duration //超时 4 Junction func(x, y int) bool //过滤 5 } 6 7 // x,y: 开始索引点; x1,y1: 结束索引点 8 func (sp SeekPath) GetPath(x, y, x1, y1 int) []int { 9 sTime := time.Now() 10 eTime := time.Now().Add(sp.Timeout) 11 12 var close sp_close //不在检测的列表 13 var dots, dotsA, dotsB sp_dots //周围的点 14 var isSort bool //如果为 true 则表示 open 列表已改变 15 16 node := &sp_item{ 17 x: x, y: y, 18 h: absInt(x1-x)*10 + absInt(y1-y)*10, 19 } 20 open := sp_open{node} 21 node.f = node.h 22 nd := node 23 24 for { 25 if len(open) == 0 || sTime.After(eTime) { 26 break 27 } 28 29 //sp_item.f 从小到大排序 30 if isSort { 31 isSort = false 32 sort.Sort(open) 33 } 34 35 //node 如果是目标就结束 36 node = open[0] 37 if node.x == x1 && node.y == y1 { 38 nd = node 39 break 40 } 41 42 if nd.h > node.h { 43 nd = node 44 } 45 46 open = open.exceptFirst() //从 open 列表删除第一个 47 close = append(close, node.x, node.y) //把 node 加入 close 列表 48 49 var state [4]bool //记录四个面是否合法 50 var dx, dy int 51 52 //四个面 53 dots.put(node.x, node.y) 54 for i := 0; i < 8; i += 2 { 55 dx, dy = dots[i], dots[i+1] 56 57 //在close列表 58 if close.contains(dx, dy) { 59 continue 60 } 61 62 //已在open列表 63 g := open.getIndex(dx, dy) 64 if g != -1 { 65 dot := open[g] 66 g = node.g + 10 67 if g < dot.g { 68 dot.g = g 69 dot.f = g + dot.h 70 dot.p = node 71 isSort = true 72 } 73 state[i/2] = true 74 continue 75 } 76 77 //索引点是否合法 78 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) { 79 close = append(close, node.x, node.y) 80 continue 81 } 82 83 g = node.g + 10 84 h := absInt(x1-dx)*10 + absInt(y1-dy)*10 85 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node}) 86 isSort = true 87 state[i/2] = true 88 } 89 90 //四个角 91 dotsA.putA(node.x, node.y) 92 for i := 0; i < 8; i += 2 { 93 dx, dy = dotsA[i], dotsA[i+1] 94 95 //在close列表 96 if close.contains(dx, dy) { 97 continue 98 } 99 100 //已在open列表 101 g := open.getIndex(dx, dy) 102 if g != -1 { 103 dot := open[g] 104 g = node.g + 14 105 if g < dot.g { 106 dot.g = g 107 dot.f = g + dot.h 108 dot.p = node 109 isSort = true 110 } 111 continue 112 } 113 114 //索引点是否合法 115 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) { 116 close = append(close, node.x, node.y) 117 continue 118 } 119 120 is := true 121 dotsB.put(dx, dy) 122 for i := 0; i < 8; i += 2 { 123 g = dots.getIndex(dotsB[i], dotsB[i+1]) 124 if g == -1 { 125 continue 126 } 127 if !state[g/2] { 128 is = false 129 break 130 } 131 } 132 if is { 133 g = node.g + 14 134 h := absInt(x1-dx)*10 + absInt(y1-dy)*10 135 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node}) 136 isSort = true 137 } 138 } 139 } 140 141 var path []int 142 for nd != nil { 143 path = append(path, nd.x, nd.y) 144 nd = nd.p 145 } 146 147 return path 148 }
外部可实例 SeekPath 来获取寻路后的路径
使用示例:
1 // 此结构是用于创建 SeekPath 的参数, 由客户端定义 2 type hh_SeekPath struct { 3 BevelAngle bool `json:\"bevelAngle\"` 4 Disables []bool `json:\"disables\"` 5 LenX int `json:\"lenX\"` 6 LenY int `json:\"lenY\"` 7 X int `json:\"x\"` 8 Y int `json:\"y\"` 9 X1 int `json:\"x1\"` 10 Y1 int `json:\"y1\"` 11 } 12 13 func main() { 14 //设置可同时执行的最大CPU数 15 runtime.GOMAXPROCS(runtime.NumCPU()) 16 http.Handle(\"/\", http.FileServer(http.Dir(\"./\"))) 17 18 http.HandleFunc(\"/hh\", func(w http.ResponseWriter, r *http.Request) { 19 w.Header().Set(\"Access-Control-Allow-Origin\", \"*\") //*允许所有的域头 20 21 value := r.FormValue(\"value\") 22 param := hh_SeekPath{} 23 err := json.Unmarshal([]byte(value), ¶m) 24 if err != nil { 25 fmt.Println(\"hh error: \", err) 26 return 27 } 28 29 length := len(param.Disables) 30 lenMax := param.LenX * param.LenY 31 sp := SeekPath{ 32 BevelAngle: param.BevelAngle, 33 Timeout: time.Second * 10, 34 35 //此回调如果返回false就把x,y添加到不在检索列表(close) 36 Junction: func(x, y int) bool { 37 //如果x,y超出最大边界就返回false 38 if x >= param.LenX || y >= param.LenY { 39 return false 40 } 41 //Disables[bool] 由客户端随机生成的障碍 42 if length == lenMax { 43 return param.Disables[x*param.LenY+y] 44 } 45 return true 46 }, 47 } 48 49 result, _ := json.Marshal(sp.GetPath(param.X, param.Y, param.X1, param.Y1)) 50 fmt.Fprint(w, *(*string)(unsafe.Pointer(&result))) 51 }) 52 53 fmt.Println(\"浏览器地址: http://localhost:8080\") 54 log.Fatal(http.ListenAndServe(\":8080\", nil)) 55 }
下面是客户端代码(HTML)
1 <!DOCTYPE html> 2 <html lang = \"zh-CN\"> 3 4 <head> 5 <meta charset = \"utf-8\" /> 6 <meta name=\"viewport\" content=\"width=device-width, height=device-height, initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no, minimal-ui\"> <!-- 不允许用户缩放 --> 7 <style> 8 *{margin:0;padding:0} 9 body{overflow: hidden;} 10 .title{position: absolute;font-size: 12px; color: #000000; background-color: #ffffff;} 11 </style> 12 </head> 13 14 <body> 15 16 <p class=\"title\">go A*寻路测试: 点击第一次为起点, 第二次点击为终点</p> 17 18 <script src = \"./js/main.js\" type = \"module\"></script> 19 20 </body> 21 22 </html>
index.html
1 import { CanvasEvent, CanvasImageCustom, CanvasImageDraw, CanvasImageScroll, CanvasImage } from \"./lib/ElementUtils.js\" 2 import { Ajax, UTILS } from \"./lib/Utils.js\"; 3 4 function main(){ 5 const size = 50; 6 const imgA = new CanvasImageCustom().size(size, size).rect(2, 1).fill(\"#eeeeee\").stroke(\"#cccccc\"); 7 const imgB = new CanvasImageCustom().size(size, size).rect(2, 1).fill(\"#333333\").stroke(\"#000000\"); 8 const imgS = new CanvasImageCustom().size(size, size).rect(2, 1).fill(\"#00ff00\"); 9 const imgE = new CanvasImageCustom().size(size, size).rect(2, 1).fill(\"#ff0000\"); 10 const imgP = new CanvasImageCustom().size(size, size).rect(size/2, 1).fill(\"#0000ff\"); 11 const cid = new CanvasImageDraw({width: innerWidth, height: innerHeight}); 12 const cis = new CanvasImageScroll(cid, {scrollVisible: \"auto\"}); 13 const cie = new CanvasEvent(cid); 14 15 //发送给服务器的寻路参数 16 const param = { 17 bevelAngle: true, //是否可走斜角 18 disables: [], //禁用点 19 lenX: Math.floor(innerWidth/size), //索引x轴长度 20 lenY: 100, //索引y轴长度 21 x:0, y:0, //起点 22 x1: 0, y1: 0, //终点 23 } 24 var isEnd = true; 25 const pathsCI = [] 26 const ajax = new Ajax({ 27 url: \"http://localhost:8080/hh\", 28 success: v => { 29 v = JSON.parse(v); 30 for(let i = 0; i < v.length; i+=2){ 31 const ci = new CanvasImage(imgP).pos(v[i]*size, v[i+1]*size); 32 pathsCI.push(ci); 33 cid.list.push(ci); 34 } 35 cid.redraw(); 36 isEnd = true; 37 }, 38 }); 39 40 //点击的回调方法 41 var isSend = false; 42 function onclick(event){ 43 if(isEnd === false) return alert(\"等待上一次的结果\"); 44 const ci = event.target; 45 if(isSend === false){ 46 isSend = true; 47 param.x = Math.floor(ci.x / size); 48 param.y = Math.floor(ci.y / size); 49 imgS.pos(ci); 50 const c = pathsCI.length; 51 if(c !== 0){ 52 cid.list.splice(cid.list.indexOf(pathsCI[0]), c); 53 pathsCI.length = 0; 54 } 55 } else { 56 isEnd = isSend = false; 57 param.x1 = Math.floor(ci.x / size); 58 param.y1 = Math.floor(ci.y / size); 59 ajax.send(`name=hh_SeekPath&value=${JSON.stringify(param)}`); 60 imgE.pos(ci); 61 } 62 cid.redraw(); 63 } 64 65 //创建视图和障碍点 66 for(let x = 0, i = 0; x < param.lenX; x++){ 67 for(let y = 0, ci; y < param.lenY; y++, i++){ 68 if(UTILS.random(0, 1) < 0.3){ 69 param.disables[i] = false; 70 ci = cid.list[i] = new CanvasImage(imgB).pos(x * size, y * size); 71 } else { 72 param.disables[i] = true; 73 ci = cid.list[i] = new CanvasImage(imgA).pos(x * size, y * size); 74 ci.addEventListener(\"click\", onclick); 75 } 76 } 77 } 78 79 //end 80 cis.bindScrolls(); 81 cid.list.push(imgS, imgE); 82 cid.render(); 83 } 84 85 main();
结果图:
源码下载地址: https://www.123pan.com/s/ylTuVv-nwhpH.html
下面的go码是改过的
换了一个名字(SeekPath 换成了 Astar)
去掉了一个属性 .BevelAngle:bool 是否可以走斜角
GetPathF(x, y, x1, y1 int) 此方法相当于 .BevelAngle = false
GetPath(x, y, x1, y1 int) .BevelAngle = true
1 import ( 2 \"sort\" 3 \"time\" 4 ) 5 6 // go A*寻路算法 7 8 func absInt(x int) int { 9 if x < 0 { 10 return -x 11 } 12 return x 13 } 14 15 type sp_item struct { 16 x int 17 y int 18 g int 19 h int 20 f int 21 p *sp_item 22 } 23 24 type sp_open []*sp_item 25 26 func (sp sp_open) Len() int { 27 return len(sp) 28 } 29 30 func (sp sp_open) Less(i, j int) bool { 31 return sp[i].f < sp[j].f 32 } 33 34 func (sp sp_open) Swap(i, j int) { 35 sp[i], sp[j] = sp[j], sp[i] 36 } 37 38 func (sp sp_open) exceptFirst() sp_open { 39 var newSps []*sp_item 40 for i := 1; i < len(sp); i++ { 41 newSps = append(newSps, sp[i]) 42 } 43 return newSps 44 } 45 46 func (sp sp_open) get(x, y int) int { 47 for i, v := range sp { 48 if v.x == x && v.y == y { 49 return i 50 } 51 } 52 return -1 53 } 54 55 type sp_close []int 56 57 func (sp sp_close) contains(x, y int) bool { 58 for k := 0; k < len(sp); k += 2 { 59 if sp[k] == x && sp[k+1] == y { 60 return true 61 } 62 } 63 return false 64 } 65 66 type sp_dots [8]int 67 68 func (sp sp_dots) get(x, y int) int { 69 for i := 0; i < 8; i += 2 { 70 if sp[i] == x && sp[i+1] == y { 71 return i 72 } 73 } 74 return -1 75 } 76 77 func (sp *sp_dots) put(x, y int) { 78 _x := x - 1 79 x_ := x + 1 80 _y := y - 1 81 y_ := y + 1 82 sp[0], sp[1], sp[2], sp[3], sp[4], sp[5], sp[6], sp[7] = x, _y, _x, y, x_, y, x, y_ 83 } 84 85 func (sp *sp_dots) putA(x, y int) { 86 _x := x - 1 87 x_ := x + 1 88 _y := y - 1 89 y_ := y + 1 90 sp[0], sp[1], sp[2], sp[3], sp[4], sp[5], sp[6], sp[7] = _x, _y, x_, _y, _x, y_, x_, y_ 91 } 92 93 // A*寻路 94 type Astar struct { 95 Timeout time.Duration //超时 96 Junction func(x, y int) bool //过滤 97 } 98 99 func (sp Astar) GetPathF(x, y, x1, y1 int) []int { 100 sTime := time.Now() 101 eTime := time.Now().Add(sp.Timeout) 102 103 var close sp_close //不在检测的列表 104 var dots sp_dots //周围的点 105 var isSort bool //如果为 true 则表示 open 列表已改变 106 var dx, dy int 107 108 node := &sp_item{ 109 x: x, y: y, 110 h: absInt(x1-x)*10 + absInt(y1-y)*10, 111 } 112 113 node.f = node.h 114 nd := node 115 open := sp_open{node} 116 117 for len(open) != 0 && sTime.Before(eTime) { 118 //sp_item.f 从小到大排序 119 if isSort { 120 isSort = false 121 sort.Sort(open) 122 } 123 124 //node 如果是目标就结束 125 node = open[0] 126 if node.x == x1 && node.y == y1 { 127 nd = node 128 break 129 } 130 131 if nd.h > node.h { 132 nd = node 133 } 134 135 open = open.exceptFirst() //从 open 列表删除第一个 136 close = append(close, node.x, node.y) //把 node 加入 close 列表 137 138 //四个面 139 dots.put(node.x, node.y) 140 for i := 0; i < 8; i += 2 { 141 dx, dy = dots[i], dots[i+1] 142 143 //在close列表 144 if close.contains(dx, dy) { 145 continue 146 } 147 148 //索引点是否合法 149 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) { 150 close = append(close, dx, dy) 151 continue 152 } 153 154 //已在open列表 155 g := open.get(dx, dy) 156 if g != -1 { 157 d := open[g] 158 g = node.g + 10 159 if g < d.g { 160 d.g = g 161 d.f = g + d.h 162 d.p = node 163 isSort = true 164 } 165 } else { 166 g = node.g + 10 167 h := absInt(x1-dx)*10 + absInt(y1-dy)*10 168 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node}) 169 isSort = true 170 } 171 } 172 } 173 174 var path []int 175 for nd != nil { 176 path = append(path, nd.x, nd.y) 177 nd = nd.p 178 } 179 180 return path 181 } 182 183 func (sp Astar) GetPath(x, y, x1, y1 int) []int { 184 sTime := time.Now() 185 eTime := time.Now().Add(sp.Timeout) 186 187 var close sp_close 188 var dots, dotsA, dotsB sp_dots 189 var state [4]bool 190 var isSort bool 191 var dx, dy, i int 192 193 g := absInt(x1-x)*10 + absInt(y1-y)*10 194 node := &sp_item{x: x, y: y, h: g, f: g} 195 nd := node 196 open := sp_open{node} 197 198 for len(open) != 0 && sTime.Before(eTime) { 199 if isSort { 200 isSort = false 201 sort.Sort(open) 202 } 203 204 node = open[0] 205 if node.x == x1 && node.y == y1 { 206 nd = node 207 break 208 } 209 210 if nd.h > node.h { 211 nd = node 212 } 213 214 open = open.exceptFirst() 215 close = append(close, node.x, node.y) 216 dots.put(node.x, node.y) 217 dotsA.putA(node.x, node.y) 218 state[0], state[1], state[2], state[3] = false, false, false, false 219 220 for i = 0; i < 8; i += 2 { 221 dx, dy = dots[i], dots[i+1] 222 223 if close.contains(dx, dy) { 224 continue 225 } 226 227 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) { 228 close = append(close, dx, dy) 229 continue 230 } 231 232 state[i/2] = true 233 g = open.get(dx, dy) 234 if g != -1 { 235 dot := open[g] 236 g = node.g + 10 237 if g < dot.g { 238 dot.g = g 239 dot.f = g + dot.h 240 dot.p = node 241 isSort = true 242 } 243 } else { 244 g = node.g + 10 245 h := absInt(x1-dx)*10 + absInt(y1-dy)*10 246 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node}) 247 isSort = true 248 } 249 } 250 251 B: 252 for i = 0; i < 8; i += 2 { 253 dx, dy = dotsA[i], dotsA[i+1] 254 255 if close.contains(dx, dy) { 256 continue 257 } 258 259 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) { 260 close = append(close, dx, dy) 261 continue 262 } 263 264 dotsB.put(dx, dy) 265 for k := 0; k < 8; k += 2 { 266 g = dots.get(dotsB[k], dotsB[k+1]) 267 if g != -1 && !state[g/2] { 268 continue B 269 } 270 } 271 272 g = open.get(dx, dy) 273 if g != -1 { 274 dot := open[g] 275 g = node.g + 14 276 if g < dot.g { 277 dot.g = g 278 dot.f = g + dot.h 279 dot.p = node 280 isSort = true 281 } 282 } else { 283 g = node.g + 14 284 h := absInt(x1-dx)*10 + absInt(y1-dy)*10 285 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node}) 286 isSort = true 287 } 288 } 289 } 290 291 var path []int 292 for nd != nil { 293 path = append(path, nd.x, nd.y) 294 nd = nd.p 295 } 296 297 return path 298 }
完整的go码
来源：https://www.cnblogs.com/weihexinCode/p/17156882.html
本站部分图文来源于网络，如有侵权请联系删除。