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=${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
标签：node,记录,int,open,sp,param,go,寻路,size From： https://www.cnblogs.com/weihexinCode/p/17156882.html