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=https://www.cnblogs.com/weihexinCode/archive/2023/02/26/${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
修復了一個已知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 := true 100 g := 0 101 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 continue 106 } 107 if !state[g/2] { 108 is = false 109 break 110 } 111 } 112 113 if !is { 114 continue 115 } 116 117 //已在open串列 118 g = open.getIndex(dx, dy) 119 if g != -1 { 120 dot := open[g] 121 g = node.g + 14 122 if g < dot.g { 123 dot.g = g 124 dot.f = g + dot.h 125 dot.p = node 126 isSort = true 127 } 128 continue 129 } 130 131 g = node.g + 14 132 h := absInt(x1-dx)*10 + absInt(y1-dy)*10 133 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node}) 134 isSort = true 135 } 136 } 137 138 var path []int 139 for nd != nil { 140 path = append(path, nd.x, nd.y) 141 nd = nd.p 142 } 143 144 return path 145 }SeekPath.GetPath方法
注意: https://www.123pan.com/s/ylTuVv-nwhpH.html共享的原始碼需要手動更換 SeekPath 下的 GetPath 方法才能解決這個BUG
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/545107.html
標籤：其他
上一篇：Java刷題常用的資料結構總結