说在前面

🎈相信大家对于连连看这款游戏都不陌生了吧？还记得在我小时候，有一段时间周边的人都被这游戏给吸引了，那时候我就在想，我点了两个图片，它怎么知道能不能连线，还有明明有很多条路线可以走，为什么就要走那一条？直到后来我学习了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]}`);

• （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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。