go A*尋路筆記

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

 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