canvas-catch the cat

发表于 |
字数统计 3,496 | 阅读时长 16

引言

好久没写博客了,今天来写下上个星期花了几天时间做的这个web端的canvas游戏—-抓猫游戏

游戏介绍

首先,这个游戏是前几年出来的,比较火的一个游戏,虽然我没玩过,最近访问网站时,不小心404了,在404界面有了一个这个flash做的游戏如图


游戏的玩法就是每次点击图中不是灰点的圆点,猫都会走一步,如果猫最终走出图,则失败;若你用灰色点将猫困住,则成功.

思考

  1. 首先,图中圆点的构建,我准备用canvas来绘制
  2. 其次,对于圆点的记数,是用坐标[0,1]这种还是0,1,2这种
  3. 对于圆点的数据结构建模
  4. 圆点的寻路算法

探索过程

先思考数据结构,用什么数据结构呢?多点,有最短路径,有闭环,当然就是图了,二叉树肯定不行.
什么图?看一下游戏玩法,普通的一个点可以向周围6个方向发散,而且可以返回,那就是一个无权无向图了.
什么最短路径算法?最简单的有dfs(Depth First Search)与bfs(Breadth First Search),当然还有Dijkstra算法,A star算法,稍微了解了下,后面两个主要针对有权图,当然无权也可以,之后可以去试一下,这里我用的是bfs算法
圆点怎么个走法?有哪些规律?要将可通过的边界点记录下来,寻找到边界点的最短路径和下一步的走法;普通圆点a(假设是11*11的矩阵),如果是在奇数行的话(第一行为0行),他的6个下一节点位置和在偶数行的下一个节点位置不同,如图

上图的14号节点是在第1行里的,他的左上是14-11=3,左是14-1=13,左下是14+11=25,右上是14-10=4,右是14+1=15,右下是14+12=26
在如下图

上图的26号节点是在第1行里的,他的左上是26-12=14,左是26-1=25,左下是26+10=36,右上是26-11=15,右是26+1=27,右下是26+11=37
用什么语言呢? 先准备用python,后来想想算了,既然放页面上还是用js去实现了
以前数据结构课上学过,图有两种实现方式,一种是邻接表的形式,每个节点后面跟着一个记录者该节点可以到达的下一个节点的数组;还有一种是邻接矩阵的形式,每个节点代表矩阵的横向以及纵向的点,x,y=0的话,则代表x与y之间不连通;x,y=1的话(无权,如果有权的话,则是权值),则代表x与y之间连通,所以一般无向图的都是对称的,中间斜对角线是无穷大,代表自己到自己的距离不可达.
这里我用了邻接数组,二维数组来实现无权无向图
图有顶点Vertex类,还有Graph类,Graph里主要有一些图内自带的属性以及函数方法,比如新增边addEdge,新增节点addVertex,删除节点removeVertex以及init初始化,随机生成灰色点等,闲话少说上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
// 构建图
// 顶点类
function Vertex(label){
    this.label = label;
    // this.distance = distance;
}
// 图类
function Graph(v){
    this.vertices = v;
    this.edges = 0;
    this.adj = [];
    this.marked = []    
// 二维邻接数组初始化
    for(var i = 0;i<this.vertices;++i){
        this.adj[i] = [];
        // this.adj[i].push("");
        this.marked[i] = false;
    }
    this.edgeTo = [];
    this.addEdge = addEdge;
    this.showGraph = showGraph;
    // 深度优先算法
    this.listBorder = listBorder;
    this.dfs = dfs;
    this.removeVertex = removeVertex;
    this.init = init;
    this.bfs = bfs;
    this.getpath=getpath
    this.num = num;
    this.remarker = remarker;
}
function addEdge(v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges++;
}
function removeVertex(v){
    // 1.删除v的邻接表的邻接表里的v
    this.adj[v].forEach(function(value){
        for(var w=0;w<this.adj[value].length;++w){
            if(this.adj[value][w] == v){
                this.adj[value].splice(w,1);
            }
        }
    },this)
    //2.删除v的邻接表
    this.adj[v].splice(0,this.adj[v].length);
}
//indexof自定义数组构建indexof方法,判断某个元素是不是在数组里存在
Array.prototype.indexOf = function(el){
    for (var i=0,n=this.length; i<n; i++){
        if (this[i] === el){
            return i;
        }
    }
    return -1;
}
//显示图,打印
function showGraph(){
    for (var i = 0; i < this.vertices; ++i) {
        str = i + "->";
        for (var j = 0; j < this.vertices; ++j) {
            if (this.adj[i][j] != undefined)
                str += this.adj[i][j] + ' ';
        }
        console.log(str)
    }
}
//深度优先
function dfs(v){
// 用于输出的 if 语句在这里不是必须的
    this.marked[v] = true;
    if (this.adj[v] != undefined)
        // console.log("visit vertex:"+v)
    this.adj[v].forEach(function(value) {
        if (!this.marked[value]) {
            this.dfs(value);
        }
    }, this);
}
// m * m =v 初始化
function init(m){
    var v = m*m;
    for(var i=0;i<v;i++){
        // 去重复
        // 判断奇数行还是偶数行
        if(i+1<v&&i%m!=m-1){
            this.addEdge(i,i+1);
        }
        if(i-1>=0&&i%m!=0){
            this.addEdge(i,i-1);            
        }
        if(i-m>=0){
            this.addEdge(i,i-m);
        }
        if(i-m+1>=0&&i-m+1>=Math.floor(i/m)*m){
            this.addEdge(i,i-m+1);
        }
        if(i+m<v){
            this.addEdge(i,i+m);            
        }
        
        if(Math.floor(i/m)%2==0){
            if(i+m-1<v&&i%m!=0){
                this.addEdge(i,i+m-1);            
            }
        }else if(Math.floor(i/m)%2==1){
            if(i+m+1<v&&i%m!=m-1){
                this.addEdge(i,i+m+1);                                          
            }
        }
        
    }
    //1.去重复操作  
    for(var i=0;i<v;i++){
        this.adj[i] = this.adj[i].unique();
    } 
    // 2.初始化时，从邻接数组里random m+1个，放入数组，遍历数组  remove m+1个顶点，变为不可访问
    this.num = randomNum(m+1);
    // console.log(this.num)
    for (var j=0;j<this.num.length;j++){
        this.removeVertex(this.num[j])
    }
}
//
Array.prototype.contains = function (obj){
  var i = this.length;
  while (i--) {
    if (this[i] === obj) {
      return true;
    }
  }
  return false;
}
function randomNum(n){
    var v = (n-1) *(n-1)-1
    var m = []
    while(m.length<n){
        var number=parseInt(Math.random()*v);  
        if(!m.contains(number)&&number!=60){
            m.push(number)
            arraynum.push(number)
        }
    }
    return m
}
Array.prototype.unique = function(){
    var res = []
    var json = {}
    for (var i=0;i<this.length;i++){
        if(!json[this[i]]){
            res.push(this[i])
            json[this[i]]=1
        }
    }
    return res
}
// 列出边界点的数组
function listBorder(m){
    for(var i =0;i<m;i++){
        if(this.adj[i * m].length!=0) {
            borderVertext.push(i * m);
        }
        if(this.adj[(i + 1) * m - 1].length!=0){
            borderVertext.push((i + 1) * m - 1)
        }
    }
    for(var i = 1;i<=m-2;i++){
        if(this.adj[i].length!=0){
            borderVertext.push(i)
        }
    }
    for(var i=m*(m-1)+1;i<=m*m-1;i++){
        if(this.adj[i].length!=0){
            borderVertext.push(i);
        }
    }
}
//再列出到边界点的最短距离算法
// 使用bfs求解无权无向图的最短路径
// a为当前点的位置
// length数组，路径或者得出下一步的最优解数组
//广度优先
//把最短路径和长度给我算出来
function bfs(s){
    arrlength[s] = 0
    isInPath.splice(0)
    var queue = [];//队列
    this.marked[s] = true;
    queue.push(s);    //添加到队尾,如果用unshift则会由右往左遍历，显示0 2 1 3 4   
    while(queue.length > 0){  
        var v = queue.shift();//从队首移除  
        isInPath.push(v)
        if(typeof(v) != 'string'){  
            // console.log("Visited vertex:" + v);
        };
        for(var w of this.adj[v]){  
            if(!this.marked[w]){  
                this.edgeTo[w] = v;
                arrlength[w] = arrlength[v]+1
                this.marked[w] = true;
                queue.push(w);  
            }
        }
    }
}
//复位marker
function remarker() {
    for(var i =0;i<this.vertices;i++){
        this.marked[i] = false;
    }
}
//每次点击的时候,调用,获取最短路径以及下一步点
function getpath(arr,local){
//    宽度优先,他相同length 的 path是同级的?
//    找到第一个属于bordervertex的即可
    var count;
    var minlength = arrlength[borderVertext[0]];
    var minindex = 0;
    // console.log(arrlength)
    /*
    * todo 会有问题
    * */
    for(var i=1;i<borderVertext.length;i++){
        if(minlength>arrlength[borderVertext[i]])
        {
            minlength = arrlength[borderVertext[i]];
            minindex = i;
        }
    }
    console.log(borderVertext)
    console.log("minidnex:"+minindex+" minnum:"+borderVertext[minindex])
    console.log("minlength:"+minlength)
    console.log(arrlength)
    for(var i=0;i<arr.length;i++){
        //不能使用第一个,第一个不一定是最优解
        //需要找到最短长度的那个边缘节点
        if(arr[i]==borderVertext[minindex]){
            count = arr[i];
            break;
        }
    }
    while(this.edgeTo[count]!=local&&this.edgeTo[count]!=undefined){
        count = this.edgeTo[count]
    }
    if(count!=undefined){
        return count
    }else{
        return -1
    }
}
// 数据填入 0~120个顶点
// 1.首先121个点都默认
//test
var borderVertext = []
var arraynum = []
//已经点击的点
var num = []
// var dfsarr = []
// //记录每一层的个数
// var floorcount = []
//最短长度
var arrlength = []
//最短路径
var path = []
var isInPath = []
// var nextNode
// var finalNodenum

canvas实现

核心的算法实现就上面所说,当然我们还得用canvas去实现他,在canvas实现的过程中也有一些坑.

  1. 每次点击的重绘过程如何实现
  2. 小猫图片的移动或者变换如何实现
    首先,需要对你所点击的canvas做监听操作,需要在callback函数里面做判断,如果点击的在绿色点区域内,则重绘,否则不做操作.
    其次,小猫图片我首先想到的也用canvas来做,后来发现行不通,无法实现变换和移动操作,后来干脆直接用html的image标签来做,对其的position进行dom操作,并且一同放在canvas的监听事件里面.上代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    /**
     * Created by Saintyun on 2017/5/12.
     */
    var container = document.getElementById("container")
    var tips = document.getElementById("tips")
    document.write(returnCitySN["cip"]+','+returnCitySN["cname"])
    var timer = document.getElementById("timer")
    function startop(){
        var speed = 0.2;
        var start = self.setInterval(function(){
            container.style.opacity = speed.toString();
            speed+=0.2;
            console.log(speed)
            if(speed>=1){
                window.clearInterval(start)
            }
        },200)
    }
    function endop(){
        var speed = parseInt(container.style.opacity);
        var end = setInterval(function(){
            container.style.opacity = speed.toString();
            speed-=0.2;
            console.log(speed)
            if(speed<=0){
                window.clearInterval(end)
                location.reload()
            }
        },200)
    }
    window.onload  = function(){
        startop()
    }
    var g = new Graph(121);
    //    定义当前猫的位置的数组
    var localvertex = 60
    var prevertex
    g.init(11);
    g.listBorder(11);
    var canvas = document.getElementById("canvas")
    var ctx = canvas.getContext('2d')
    var circle = {
        x: 64,
        y: 64,
        r: 20
    }
    var imagelocation = {
        x: 298,
        y: 268
    }
    var arr = []
    var myimage = document.getElementById("myimage")
    myimage.style.position = "absolute";
    myimage.style.left = imagelocation.x + "px";
    myimage.style.top = imagelocation.y + "px";
    myimage.src = '/canvas/image/stand_cat1.png'
    for (var i = 0; i < 11; i++) {
        for (var j = 0; j < 11; j++) {
            if (i % 2 == 0) {
                arr.push({
                    x: circle.x + j * (2 * circle.r + 4),
                    y: circle.y + i * (2 * circle.r + 4),
                    r: 20,
                    vertex: i * 11 + j
                })
            } else {
                arr.push({
                    x: circle.x + j * (2 * circle.r + 4) + 22,
                    y: circle.y + i * (2 * circle.r + 4),
                    r: 20,
                    vertex: i * 11 + j
                })
            }
        }
    }
    canvas.addEventListener('click', function (e) {
        p = getEventPosition(e);
        reDraw(p, ctx);
    //
    //      console.log(g.num)
    }, false)
    //    为了实现循环重绘，所以就要将图形的基本参数事先保存下来
    //    点击重新绘制
    //得到点击的坐标
    function getEventPosition(ev) {
        var x, y;
        if (ev.layerX || ev.layerX == 0) {
            x = ev.layerX;
            y = ev.layerY;
        } else if (ev.offsetX || ev.offsetX == 0) { // Opera
            x = ev.offsetX;
            y = ev.offsetY;
        }
        return {x: x, y: y};
    }
    //重绘
    function reDraw(p, ctx) {
        var date1 = new Date().getTime();
        var whichObject = [];
        for (var i = 0; i < arr.length; i++) {
    //            点击的不在当前 localvertex 圆下
            if (p && (arr[i].x + arr[i].r) >= p.x && p.x >= arr[i].x - arr[i].r
                && (arr[i].y + arr[i].r) >= p.y && p.y >= arr[i].y - arr[i].r
                && i != localvertex&& !g.num.contains(i)) {
                whichObject.push(i);
                //每次点击一次,image坐标改变一次
                ctx.fillStyle = '#728401';
                ctx.beginPath();
                ctx.arc(arr[i].x, arr[i].y, arr[i].r, 0, Math.PI * 2, true);
                ctx.fill();
                g.num.push(i)
    //                还有图片移动的6个方向的情况,第一次点击,反方向情况,之后根据路径来
                //然后获取图片移动之后的位置!
    //                1.记录点击的位置 :i
    //              2.将其canvas颜色改变,
    //              3.将其图的顶点去除 相关数组
    //
                g.removeVertex(i)
                if (borderVertext.indexOf(i) != -1) {
                    borderVertext.splice(borderVertext.indexOf(i), 1)
                }
    //              console.log(borderVertext)
                g.remarker()
                if(borderVertext.contains(localvertex)){
                    console.log("猫跑出去咯!")
                    tips.innerHTML = "额,就差一点,猫跑出去咯!"
                    myimage.style.display = 'none'
                }else {
                    g.bfs(localvertex)
                    //   nextnode
                    prevertex = localvertex
                    localvertex = g.getpath(isInPath, localvertex)
    //                }
                    if (localvertex != -1) {
                        console.log("localvertex:" + localvertex + "prevertex:" + prevertex)
    //                解决每点击一次,往已点击数组里加
    //                偶数行奇数行问题
    //               优化!把imagelocation的操作单独列出6个方向操作
                        if (localvertex == prevertex + 11) {
                            if (Math.floor(prevertex / 11) % 2 == 0) {
                                //斜向右下
                                imagelocation = {
                                    x: imagelocation.x + 22,
                                    y: imagelocation.y + 44
                                }
                            } else {
                                imagelocation = {
                                    x: imagelocation.x - 22,
                                    y: imagelocation.y + 44
                                }
                            }
                        } else if (localvertex == prevertex + 10) {
    //                    斜向左下
                            imagelocation = {
                                x: imagelocation.x - 22,
                                y: imagelocation.y + 44
                            }
                        } else if (localvertex == prevertex + 12) {
                            //斜向右下
                            imagelocation = {
                                x: imagelocation.x + 22,
                                y: imagelocation.y + 44
                            }
                        }
                        else if (localvertex == prevertex - 12) {
                            //
                            imagelocation = {
                                x: imagelocation.x - 22,
                                y: imagelocation.y - 44
                            }
                        }
                        else if (localvertex == prevertex + 1) {
    //                    向右
                            imagelocation = {
                                x: imagelocation.x + 44,
                                y: imagelocation.y
                            }
                        } else if (localvertex == prevertex - 1) {
    //                    向左
                            imagelocation = {
                                x: imagelocation.x - 44,
                                y: imagelocation.y
                            }
                        } else if (localvertex == prevertex - 11) {
                            if (Math.floor(prevertex / 11) % 2 == 0) {
    //                    斜向右上
                                imagelocation = {
                                    x: imagelocation.x + 22,
                                    y: imagelocation.y - 44
                                }
                            } else {
                                imagelocation = {
                                    x: imagelocation.x - 22,
                                    y: imagelocation.y - 44
                                }
                            }
                        } else if (localvertex == prevertex - 10) {
                            imagelocation = {
                                x: imagelocation.x + 22,
                                y: imagelocation.y - 44
                            }
                        }
                        myimage.style.left = imagelocation.x + "px"
                        myimage.style.top = imagelocation.y + "px"
                    }else{
                        myimage.src='/canvas/image/catch_cat.png'
                        tips.innerHTML = "好耶！你抓住猫啦!"
                        console.log("你抓住猫啦!")
                    }
                }
                //注意图片所移动的位置 一定是没有点击过的 √
    //                到边界时候的处理
    //                包围起来,没有路走的处理
                break;
            }
        }
        //   接下来的问题是如何移动图片,或者是如何消除之前的图片
    //        var date2 = new Date().getTime();
    //        timer.innerHTML += "draw所耗费时间"+(date2-date1)+"ms"+"<br/>"
    }
    //    按照i*j = v
    for (var i = 0; i < 11; ++i) {
        for (var j = 0; j < 11; ++j) {
    //            ctx.clearRect(0, 0, canvas.width, canvas.height);
            if (g.num.contains(i * 11 + j)) {
                ctx.fillStyle = '#728401';
            } else {
                ctx.fillStyle = '#ccff00';
            }
            if (i % 2 == 0) {
                ctx.beginPath()
                ctx.arc(circle.x + j * (2 * circle.r + 4), circle.y + i * (2 * circle.r + 4), circle.r, 0, Math.PI * 2, true)
                ctx.fill()
                ctx.beginPath()
                ctx.fillStyle = 'black'
                ctx.fillText(i * 11 + j, circle.x + j * (2 * circle.r + 4), circle.y + i * (2 * circle.r + 4));
            } else {
                ctx.beginPath()
                ctx.arc(circle.x + j * (2 * circle.r + 4) + 22, circle.y + i * (2 * circle.r + 4), circle.r, 0, Math.PI * 2, true)
                ctx.fill()
                ctx.beginPath()
                ctx.fillStyle = 'black'
                ctx.fillText(i * 11 + j, circle.x + j * (2 * circle.r + 4) + 22, circle.y + i * (2 * circle.r + 4));
            }
        }
    }

实现的效果

实现的效果去这个网站地址就可以去看了,我把部署到vps上了
http://saintyun.cn/canvas
效果还行的,你可以打开控制台,看下每一步的路径以及目标点,我也没删掉这些,算是个小作弊吧~~~

优化

  1. 寻找下一步的走法时,只是单纯的根据最短路径的第一个值来,如果有多条最短路径,但是A路径的下一个节点a0是有点”自投罗网”的意思,就是a0方向的灰色节点较多,这样就比较容易围住,所以以后可以做个某方向灰色点分布趋势的判断,得出哪一个是最优点
  2. 目前只是单机版的,没有排行榜,难度切换,访问用户以及用户ip记录,步数记录,得分转化等功能
  3. 代码上冗余的有点多,需要优化

下期预告

我准备做一些android的ui控件或者效果或者实现一些小框架如网络连接之类的或者如下图所示的效果