最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

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), ¶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  2  3      4      5          6           7         12     13 14     15 16         
go A*寻路测试: 点击第一次为起点, 第二次点击为终点
17 18         <script src = "./js/main.js" type = "module"></script>19         20     21 22
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

                 

关键词：         
       取绝对值 
              
       服务器的