go A*寻路笔记

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_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 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), &param)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