1 func absInt(x int) int {2 if x < 0 {3 return -x4 }5 return x6 }
下面会用到此方法, 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_item11 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].f18 }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_item26 for i := 1; i < len(sp); i++ {27 newSps = append(newSps, sp[i])28 }29 return newSps30 }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 i36 }37 }38 return -139 }
这是open列表(带检索的列表)
Len()
Less(i, j int)
Swap(i, j int)
上面三个方法是自定义排序(sp_item.f从小到大排序)exceptFirst()
复制 sp_open 数组并返回, 不包含第一个 sp_itemgetIndex(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 false10 }
这是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 -110 }11 12 func (sp *sp_dots) put(x, y int) {13 _x := x - 114 x_ := x + 115 _y := y - 116 y_ := y + 117 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 - 122 x_ := x + 123 _y := y - 124 y_ := y + 125 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 + 14105 if g < dot.g {106 dot.g = g107 dot.f = g + dot.h108 dot.p = node109 isSort = true110 }111 continue112 }113 114 //索引点是否合法115 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) {116 close = append(close, node.x, node.y)117 continue118 }119 120 is := true121 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 continue126 }127 if !state[g/2] {128 is = false129 break130 }131 }132 if is {133 g = node.g + 14134 h := absInt(x1-dx)*10 + absInt(y1-dy)*10135 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node})136 isSort = true137 }138 }139 }140 141 var path []int142 for nd != nil {143 path = append(path, nd.x, nd.y)144 nd = nd.p145 }146 147 return path148 }
外部可实例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 return27 }28 29 length := len(param.Disables)30 lenMax := param.LenX * param.LenY31 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超出最大边界就返回false38 if x >= param.LenX || y >= param.LenY {39 return false40 }41 //Disables[bool] 由客户端随机生成的障碍42 if length == lenMax {43 return param.Disables[x*param.LenY+y]44 }45 return true46 },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 //end80 cis.bindScrolls();81 cid.list.push(imgS, imgE);82 cid.render();83 }84 85 main();
结果图:
源码下载地址:https://www.123pan.com/s/ylTuVv-nwhpH.html
修复了一个已知BUG:
1 func (sp SeekPath) GetPath(x, y, x1, y1 int) []int { 2 sTime := time.Now() 3 eTime := time.Now().Add(sp.Timeout) 4 5 var close sp_close //不在检测的列表 6 var dots, dotsA, dotsB sp_dots //周围的点 7 var isSort bool //如果为 true 则表示 open 列表已改变 8 9 node := &sp_item{ 10 x: x, y: y, 11 h: absInt(x1-x)*10 + absInt(y1-y)*10, 12 } 13 open := sp_open{node} 14 node.f = node.h 15 nd := node 16 17 for { 18 if len(open) == 0 || sTime.After(eTime) { 19 break 20 } 21 22 //sp_item.f 从小到大排序 23 if isSort { 24 isSort = false 25 sort.Sort(open) 26 } 27 28 //node 如果是目标就结束 29 node = open[0] 30 if node.x == x1 && node.y == y1 { 31 nd = node 32 break 33 } 34 35 if nd.h > node.h { 36 nd = node 37 } 38 39 open = open.exceptFirst() //从 open 列表删除第一个 40 close = append(close, node.x, node.y) //把 node 加入 close 列表 41 42 var state [4]bool //记录四个面是否合法 43 var dx, dy int 44 45 //四个面 46 dots.put(node.x, node.y) 47 for i := 0; i < 8; i += 2 { 48 dx, dy = dots[i], dots[i+1] 49 50 //在close列表 51 if close.contains(dx, dy) { 52 continue 53 } 54 55 //索引点是否合法 56 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) { 57 close = append(close, dx, dy) 58 continue 59 } 60 61 //已在open列表 62 g := open.getIndex(dx, dy) 63 if g != -1 { 64 dot := open[g] 65 g = node.g + 10 66 if g < dot.g { 67 dot.g = g 68 dot.f = g + dot.h 69 dot.p = node 70 isSort = true 71 } 72 state[i/2] = true 73 continue 74 } 75 76 g = node.g + 10 77 h := absInt(x1-dx)*10 + absInt(y1-dy)*10 78 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node}) 79 isSort = true 80 state[i/2] = true 81 } 82 83 //四个角 84 dotsA.putA(node.x, node.y) 85 for i := 0; i < 8; i += 2 { 86 dx, dy = dotsA[i], dotsA[i+1] 87 88 //在close列表 89 if close.contains(dx, dy) { 90 continue 91 } 92 93 //索引点是否合法 94 if dx < 0 || dy < 0 || !sp.Junction(dx, dy) { 95 close = append(close, dx, dy) 96 continue 97 } 98 99 is := true100 g := 0101 dotsB.put(dx, dy)102 for i := 0; i < 8; i += 2 {103 g = dots.getIndex(dotsB[i], dotsB[i+1])104 if g == -1 {105 continue106 }107 if !state[g/2] {108 is = false109 break110 }111 }112 113 if !is {114 continue115 }116 117 //已在open列表118 g = open.getIndex(dx, dy)119 if g != -1 {120 dot := open[g]121 g = node.g + 14122 if g < dot.g {123 dot.g = g124 dot.f = g + dot.h125 dot.p = node126 isSort = true127 }128 continue129 }130 131 g = node.g + 14132 h := absInt(x1-dx)*10 + absInt(y1-dy)*10133 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node})134 isSort = true135 }136 }137 138 var path []int139 for nd != nil {140 path = append(path, nd.x, nd.y)141 nd = nd.p142 }143 144 return path145 }
SeekPath.GetPath方法
注意:https://www.123pan.com/s/ylTuVv-nwhpH.html共享的源码需要手动更换 SeekPath 下的 GetPath 方法才能解决这个BUG