说在前面
🎈相信大家对于连连看这款游戏都不陌生了吧？还记得在我小时候，有一段时间周边的人都被这游戏给吸引了，那时候我就在想，我点了两个图片，它怎么知道能不能连线，还有明明有很多条路线可以走，为什么就要走那一条？直到后来我学习了BFS算法
体验地址
大家可以先到体验地址试玩一下，欢迎大家的意见反馈。
JYeontuGame在线体验地址：http://jyeontu.xyz/JYeontuGame/#/
项目介绍
本游戏是基于vue2.0的一个项目，服务端使用node简单的做了两个接口，数据库则是使用的mysql。
功能实现
1、初始化页面
使用js动态生成连连看看板格子。
//初始化页面 initPage() { const row = this.row, column = this.column; const content = document.getElementById("game-content"); content.innerHTML = ""; for (let i = 0; i <= parseInt(column) + 1; i++) { const columnDom = document.createElement("div"); columnDom.classList.add("column"); columnDom.id = `column-${i}`; for (let j = 0; j <= parseInt(row) + 1; j++) { const rowDom = document.createElement("div"); rowDom.classList.add("row"); rowDom.id = `row-${i}-${j}`; const img = document.createElement("img"); img.id = `img-${i}-${j}`; img.classList.add("img-block"); if (i == 0 || j == 0 || i == column + 1 || j == row + 1) { img && img.setAttribute( "src", require("./img/remove.png") ); } else { img && img.setAttribute( "src", this.blockList[(i - 1) * row + j - 1] ); img.onclick = () => { this.imgClick(i, j); }; } rowDom.appendChild(img); columnDom.appendChild(rowDom); } content.appendChild(columnDom); } for (let i = 1; i <= column; i++) { for (let j = 1; j <= row; j++) { const img = document.getElementById(i + "-" + j); img && img.setAttribute( "src", this.blockList[(i - 1) * row + j - 1] ); } } },
2、图片数组初始化
根据行列数初始化图片数组。
//初始化数据 initData() { const row = this.row; const column = this.column; const imgList = this.imgList; let blockList = this.blockList; this.blockMap = new Array(column + 2); for (let i = 0; i < this.blockMap.length; i++) { let temp = []; for (let j = 0; j < row + 2; j++) { if (i == 0 || j == 0 || i == column + 1 || j == row + 1) temp.push(true); else temp.push(false); } this.blockMap[i] = temp; } let nums = row * column; if (nums % 2 == 1) { alert("个数不能为单数"); return; } while (nums / 2 > blockList.length) { const dif = nums / 2 - blockList.length; blockList.push(...imgList.slice(0, dif)); } blockList.push(...blockList); blockList = this.randomSort(blockList); }, //数组打乱 randomSort(arr) { return arr.sort((a, b) => { return Math.random() - 0.5; }); },
3、BFS判断图片是否可以消除
判断两点之间是否存在可通行路径的方法有两种，dfs和bfs，我们需要找到两点之间的最短路径，所以这里使用bfs算法来寻找路径。
关于bfs和dfs算法我之前也有发过一篇文章，这里我就不再过多描述这个算法的实现了，有兴趣的同学可以去一文带你了解dfs和bfs算法了解一下。
//BFS找出路径 getPath(startX, startY, targetX, targetY) { let dx = [0, 1, 0, -1], dy = [1, 0, -1, 0]; let queue = [[startX, startY]]; let flag = new Array(this.blockMap.length); //标记走过的路径 let step = new Array(this.blockMap.length); //存储走过的步数 for (let i = 0; i < flag.length; i++) { flag[i] = new Array(this.blockMap[i].length).fill(false); step[i] = new Array(this.blockMap[i].length).fill(Infinity); } step[startX][startY] = 0; flag[startX][startY] = true; while (queue.length) { let p = queue.shift(); let x = p[0], y = p[1]; if (x == targetX && y == targetY) break; for (let i = 0; i < 4; i++) { let nx = x + dx[i], ny = y + dy[i]; if ( nx < 0 || nx >= this.blockMap.length || ny >= this.blockMap[0].length || ny < 0 || ( ((nx != targetX || ny != targetY) && !this.blockMap[nx][ny]) || flag[nx][ny] == true ) ) { continue; } flag[nx][ny] = true; step[nx][ny] = step[x][y] + 1; queue.push([nx, ny]); if (nx == targetX && ny == targetY) { return this.getStep(step, startX, startY, targetX, targetY); } } } return false; },
4、找出最短路径
在上一步骤中我们通过BFS到达了终点，且对沿途经过的路径走进行了步数的标记，所以我们只需要从终点往回走即可找出最短路径的坐标集合。
//找出最短路径 getStep(step, startX, startY, targetX, targetY) { let steps = []; let dx = [0, 1, 0, -1], dy = [1, 0, -1, 0]; steps.unshift([targetX, targetY]); while (targetX != startX || targetY != startY) { for (let i = 0; i < 4; i++) { let x = targetX + dx[i], y = targetY + dy[i]; if ( x < 0 || x >= step.length || y < 0 || y >= step[0].length ) continue; if (step[x][y] == step[targetX][targetY] - 1) { targetX = x; targetY = y; steps.unshift([x, y]); } } } let lines = this.getLine(steps); },
5、连点成线
在上一步骤中我们获取到了最短路径经过的坐标集合，现在我们需要将同一条轴上的点整合成线，如下图：
需要将上图的点集转换成下图的线集
我们可以这样做：
遇到’x坐标’相等的做个x标记，并将其作为线的起始端点，直到遇到’x坐标’不等的位置，其即为线的结束端点，这样我们可以将同一水平直线上的点集转换成线。
遇到’y坐标’相等的做个y标记，并将其作为线的起始端点，直到遇到’y坐标’不等的位置，其即为线的结束端点，这样我们可以将同竖直直线上的点集转换成线。
具体代码实现如下：
//获取连线集合 getLine(steps) { let lines = []; let temp = { startX: steps[0][0], startY: steps[0][1] }; let flag = ""; for (let i = 1; i < steps.length; i++) { if ( (steps[i][0] != steps[i - 1][0] && flag == "x") || (steps[i][1] != steps[i - 1][1] && flag == "y") ) { temp.endX = steps[i - 1][0]; temp.endY = steps[i - 1][1]; flag = ""; lines.push({ ...temp }); temp = { startX: steps[i - 1][0], startY: steps[i - 1][1] }; } if (steps[i][0] == temp.startX) flag = "x"; if (steps[i][1] == temp.startY) flag = "y"; } let len = steps.length - 1; temp.endX = steps[len][0]; temp.endY = steps[len][1]; lines.push({ ...temp }); return lines; },
6、绘制连线
在上一步骤中的到线段集合后，我们需要在页面上将其绘制出来，我们可以使用一个div标签来绘制每一条线段。
- （1）获取两个端点在页面上的具体位置
我们可以根据端点坐标取得处于端点的两张图片位置。
const img1 = document.getElementById(`row-${p1[0]}-${p1[1]}`); const img2 = document.getElementById(`row-${p2[0]}-${p2[1]}`); • 1 • 2
- （2）设置线段的长度
两个端点的距离即为线段的长度。
const div = document.createElement("div"); div.style.top = img1.offsetTop + 20 + "px"; let flag = ""; if (img1.offsetTop > img2.offsetTop) { flag = "h"; div.style.transform = "rotateZ(180deg)"; div.style.transformOrigin = "top"; } div.style.left = img1.offsetLeft + 20 + "px"; if (img1.offsetLeft > img2.offsetLeft) { flag = "w"; div.style.transform = "rotateZ(180deg)"; div.style.transformOrigin = "left"; } const width = Math.abs(img1.offsetLeft - img2.offsetLeft); const height = Math.abs(img1.offsetTop - img2.offsetTop);
//绘制连线 drawLine(p1, p2) { const content = document.getElementById("game-content"); const div = document.createElement("div"); const img1 = document.getElementById(`row-${p1[0]}-${p1[1]}`); const img2 = document.getElementById(`row-${p2[0]}-${p2[1]}`); div.style.top = img1.offsetTop + 20 + "px"; let flag = ""; if (img1.offsetTop > img2.offsetTop) { flag = "h"; div.style.transform = "rotateZ(180deg)"; div.style.transformOrigin = "top"; } div.style.left = img1.offsetLeft + 20 + "px"; if (img1.offsetLeft > img2.offsetLeft) { flag = "w"; div.style.transform = "rotateZ(180deg)"; div.style.transformOrigin = "left"; } const width = Math.abs(img1.offsetLeft - img2.offsetLeft); const height = Math.abs(img1.offsetTop - img2.offsetTop); if (width == 0) div.style.transition = `height ${this.speed}s`; else div.style.transition = `width ${this.speed}s`; div.classList.add("line-style"); content.appendChild(div); setTimeout(() => { let h = 0, w = 0; if (flag == "h") h = 4; else if (flag == "w") w = 4; div.style.width = width - w + "px"; div.style.height = height - h + "px"; }, 0); this.lineLists.push(div); },
完整代码
Gitee：https://gitee.com/zheng_yongtao/jyeontu_game.git
GitHub：https://github.com/xitu/game-garden
说在后面
🎉这里是JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
