go A*寻路笔记

1 func absInt(x int) int {
2     if x < 0 {
3         return -x
4     }
5     return x
6 }

 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 }

 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 }

 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 }

  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 }

 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 }

 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     //end
80     cis.bindScrolls();
81     cid.list.push(imgS, imgE);
82     cid.render();
83 }
84 
85 main();

  1 import (
  2     "sort"
  3     "time"
  4 )
  5 
  6 // go A*寻路算法
  7 
  8 func absInt(x int) int {
  9     if x < 0 {
 10         return -x
 11     }
 12     return x
 13 }
 14 
 15 type sp_item struct {
 16     x int
 17     y int
 18     g int
 19     h int
 20     f int
 21     p *sp_item
 22 }
 23 
 24 type sp_open []*sp_item
 25 
 26 func (sp sp_open) Len() int {
 27     return len(sp)
 28 }
 29 
 30 func (sp sp_open) Less(i, j int) bool {
 31     return sp[i].f < sp[j].f
 32 }
 33 
 34 func (sp sp_open) Swap(i, j int) {
 35     sp[i], sp[j] = sp[j], sp[i]
 36 }
 37 
 38 func (sp sp_open) exceptFirst() sp_open {
 39     var newSps []*sp_item
 40     for i := 1; i < len(sp); i++ {
 41         newSps = append(newSps, sp[i])
 42     }
 43     return newSps
 44 }
 45 
 46 func (sp sp_open) get(x, y int) int {
 47     for i, v := range sp {
 48         if v.x == x && v.y == y {
 49             return i
 50         }
 51     }
 52     return -1
 53 }
 54 
 55 type sp_close []int
 56 
 57 func (sp sp_close) contains(x, y int) bool {
 58     for k := 0; k < len(sp); k += 2 {
 59         if sp[k] == x && sp[k+1] == y {
 60             return true
 61         }
 62     }
 63     return false
 64 }
 65 
 66 type sp_dots [8]int
 67 
 68 func (sp sp_dots) get(x, y int) int {
 69     for i := 0; i < 8; i += 2 {
 70         if sp[i] == x && sp[i+1] == y {
 71             return i
 72         }
 73     }
 74     return -1
 75 }
 76 
 77 func (sp *sp_dots) put(x, y int) {
 78     _x := x - 1
 79     x_ := x + 1
 80     _y := y - 1
 81     y_ := y + 1
 82     sp[0], sp[1], sp[2], sp[3], sp[4], sp[5], sp[6], sp[7] = x, _y, _x, y, x_, y, x, y_
 83 }
 84 
 85 func (sp *sp_dots) putA(x, y int) {
 86     _x := x - 1
 87     x_ := x + 1
 88     _y := y - 1
 89     y_ := y + 1
 90     sp[0], sp[1], sp[2], sp[3], sp[4], sp[5], sp[6], sp[7] = _x, _y, x_, _y, _x, y_, x_, y_
 91 }
 92 
 93 // A*寻路
 94 type Astar struct {
 95     Timeout  time.Duration       //超时
 96     Junction func(x, y int) bool //过滤
 97 }
 98 
 99 func (sp Astar) GetPathF(x, y, x1, y1 int) []int {
100     sTime := time.Now()
101     eTime := time.Now().Add(sp.Timeout)
102 
103     var close sp_close //不在检测的列表
104     var dots sp_dots   //周围的点
105     var isSort bool    //如果为 true 则表示 open 列表已改变
106     var dx, dy int
107 
108     node := &sp_item{
109         x: x, y: y,
110         h: absInt(x1-x)*10 + absInt(y1-y)*10,
111     }
112 
113     node.f = node.h
114     nd := node
115     open := sp_open{node}
116 
117     for len(open) != 0 && sTime.Before(eTime) {
118         //sp_item.f 从小到大排序
119         if isSort {
120             isSort = false
121             sort.Sort(open)
122         }
123 
124         //node 如果是目标就结束
125         node = open[0]
126         if node.x == x1 && node.y == y1 {
127             nd = node
128             break
129         }
130 
131         if nd.h > node.h {
132             nd = node
133         }
134 
135         open = open.exceptFirst()             //从 open 列表删除第一个
136         close = append(close, node.x, node.y) //把 node 加入 close 列表
137 
138         //四个面
139         dots.put(node.x, node.y)
140         for i := 0; i < 8; i += 2 {
141             dx, dy = dots[i], dots[i+1]
142 
143             //在close列表
144             if close.contains(dx, dy) {
145                 continue
146             }
147 
148             //索引点是否合法
149             if dx < 0 || dy < 0 || !sp.Junction(dx, dy) {
150                 close = append(close, dx, dy)
151                 continue
152             }
153 
154             //已在open列表
155             g := open.get(dx, dy)
156             if g != -1 {
157                 d := open[g]
158                 g = node.g + 10
159                 if g < d.g {
160                     d.g = g
161                     d.f = g + d.h
162                     d.p = node
163                     isSort = true
164                 }
165             } else {
166                 g = node.g + 10
167                 h := absInt(x1-dx)*10 + absInt(y1-dy)*10
168                 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node})
169                 isSort = true
170             }
171         }
172     }
173 
174     var path []int
175     for nd != nil {
176         path = append(path, nd.x, nd.y)
177         nd = nd.p
178     }
179 
180     return path
181 }
182 
183 func (sp Astar) GetPath(x, y, x1, y1 int) []int {
184     sTime := time.Now()
185     eTime := time.Now().Add(sp.Timeout)
186 
187     var close sp_close
188     var dots, dotsA, dotsB sp_dots
189     var state [4]bool
190     var isSort bool
191     var dx, dy, i int
192 
193     g := absInt(x1-x)*10 + absInt(y1-y)*10
194     node := &sp_item{x: x, y: y, h: g, f: g}
195     nd := node
196     open := sp_open{node}
197 
198     for len(open) != 0 && sTime.Before(eTime) {
199         if isSort {
200             isSort = false
201             sort.Sort(open)
202         }
203 
204         node = open[0]
205         if node.x == x1 && node.y == y1 {
206             nd = node
207             break
208         }
209 
210         if nd.h > node.h {
211             nd = node
212         }
213 
214         open = open.exceptFirst()
215         close = append(close, node.x, node.y)
216         dots.put(node.x, node.y)
217         dotsA.putA(node.x, node.y)
218         state[0], state[1], state[2], state[3] = false, false, false, false
219 
220         for i = 0; i < 8; i += 2 {
221             dx, dy = dots[i], dots[i+1]
222 
223             if close.contains(dx, dy) {
224                 continue
225             }
226 
227             if dx < 0 || dy < 0 || !sp.Junction(dx, dy) {
228                 close = append(close, dx, dy)
229                 continue
230             }
231 
232             state[i/2] = true
233             g = open.get(dx, dy)
234             if g != -1 {
235                 dot := open[g]
236                 g = node.g + 10
237                 if g < dot.g {
238                     dot.g = g
239                     dot.f = g + dot.h
240                     dot.p = node
241                     isSort = true
242                 }
243             } else {
244                 g = node.g + 10
245                 h := absInt(x1-dx)*10 + absInt(y1-dy)*10
246                 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node})
247                 isSort = true
248             }
249         }
250 
251     B:
252         for i = 0; i < 8; i += 2 {
253             dx, dy = dotsA[i], dotsA[i+1]
254 
255             if close.contains(dx, dy) {
256                 continue
257             }
258 
259             if dx < 0 || dy < 0 || !sp.Junction(dx, dy) {
260                 close = append(close, dx, dy)
261                 continue
262             }
263 
264             dotsB.put(dx, dy)
265             for k := 0; k < 8; k += 2 {
266                 g = dots.get(dotsB[k], dotsB[k+1])
267                 if g != -1 && !state[g/2] {
268                     continue B
269                 }
270             }
271 
272             g = open.get(dx, dy)
273             if g != -1 {
274                 dot := open[g]
275                 g = node.g + 14
276                 if g < dot.g {
277                     dot.g = g
278                     dot.f = g + dot.h
279                     dot.p = node
280                     isSort = true
281                 }
282             } else {
283                 g = node.g + 14
284                 h := absInt(x1-dx)*10 + absInt(y1-dy)*10
285                 open = append(open, &sp_item{x: dx, y: dy, g: g, h: h, f: g + h, p: node})
286                 isSort = true
287             }
288         }
289     }
290 
291     var path []int
292     for nd != nil {
293         path = append(path, nd.x, nd.y)
294         nd = nd.p
295     }
296 
297     return path
298 }

完整的go码