说在前面
🎈相信大家对于连连看这款游戏都不陌生了吧？还记得在我小时候，有一段时间周边的人都被这游戏给吸引了，那时候我就在想，我点了两个图片，它怎么知道能不能连线，还有明明有很多条路线可以走，为什么就要走那一条？直到后来我学习了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找出路径
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]}`);- （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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
