前言

连连看规则很简单，匹配相似的图块，且两图块的正交连接路径（不能对角连接路径）最多能通过 3 条直线线段表示（即最多两个转折点，这里简称连连看路径），则匹配成功，消除图块。

版面的所有图块消除则游戏结束。当然也有死局的情况，这里先不讨论。

如何计算这个路径、路径是否在两个转折点内，是连连看算法的核心。

路径检查

所有路径检查都是基于已选择的是相同的图块的情况，否则无需检查连接路径。

相邻

在游戏中会有一些特殊的情况，单独处理可以简化计算，这里相邻就是一种最简单的情况，可以直接消除。

其余情况

问题分析

设目前试图连接的图块分别为 A 和 B。

由于最多允许两个转折点，那么这两个转折点一定是有特殊意义的，对于 2 个转折点的情况，无非以下两种：

从这里可以发现，转折点一定会是在两个图块的正交/十字轴上。

对于只有一个转折点和在一条线上的情况，分别可以认为转折点重合以及在一条直线上。

问题解决

转折点搜索空间

知道转折点都在其十字轴上后，我们就可以大大缩小路径的搜索空间，下图中的灰色方块是转折点的候选点。设两个图块生成的十字路径点集合分别为PathA和PathB

那么我们可以获取两个点对应的正交路径点列表，然后遍历此列表找出符合要求的转折点并（有效转折点）返回即可；

若整个列表遍历完后以及没有找出有效转折点，则表示目前没有能够连接两图块的连连看路径。

有效转折点

以图块 A 为主循环，在遍历其路径点PathAi过程中，执行以下步骤

此路径点是否是障碍物，若是则跳过此路径点
此路径点与 A 间是否有障碍物，若有则跳过此路径点
获取此路径点在PathB上的投影点（与PathAi的 x/y 坐标相等的PathB上的两个路径点PathB1,PathB2）
遍历PathB1,PathB2：
1. PathBi是否是障碍物，若是则跳过此路径点
2. PathBi与 B 间是否有障碍物，若有则跳过此路径点
3. PathAi与PathBi是否能连通，若可行，表示三条线都相通，表示可以消除，返回PathAi与PathBi；否则跳过此路径点.
没有可行转折点，返回false或null

代码实现

/**
 * 检查路径是否可行
 *
 * @param object A
 * @param object B
 *
 * @return boolean
 */

export function feasiblePath(A, B, matrix) {
  let rowNum = matrix.nodes.length;
  let colNum = matrix.nodes[0].length;
  // 检查A点与B点时否是相邻，相邻直接可消除
  if (checkAdjacent(A, B)) {
    return [A, B];
  }

  // 获取a与b的十字线
  var aPaths = getPaths(A, rowNum, colNum);
  var bPaths = getPaths(B, rowNum, colNum);
  //   console.log(aPaths, bPaths);

  // 从A点开始遍历
  for (var i = 0, n = aPaths.length; i < n; i++) {
    // 如果节点上存在图片，则跳过这次循环
    if (!matrix.isWalkableAt(aPaths[i].x, aPaths[i].y)) {
      continue;
    }

    // 检查A点到aPaths[i]点是否可行
    if (!checkTwoLine(aPaths[i], A, matrix)) {
      continue;
    }

    // 获取与A点十字线与B点十字线相交的横向与纵向相交的位置
    var bPosition = getSamePosition(bPaths, aPaths[i]);

    for (var j = 0, jn = bPosition.length; j < jn; j++) {
      // 如果节点上存在图片，则跳过这次循环
      if (!matrix.isWalkableAt(bPosition[j].x, bPosition[j].y)) {
        continue;
      }

      // 检查bPosition点到B点是否可行
      if (!checkTwoLine(bPosition[j], B, matrix)) {
        continue;
      }

      // 检查aPaths[i]点到bPosition点是否可行, 三条线都相通，表示可以消除
      if (checkTwoLine(aPaths[i], bPosition[j], matrix)) {
        // console.log("可行", aPaths[i], bPosition[j]);
        return [aPaths[i], bPosition[j]];
      }
    }
  }
  return false;
}

// 获取某点的十字线
function getPaths(o, rowNum, colNum) {
  var paths = [];
  for (var i = o.y; i < rowNum; i++) {
    paths.push({ x: o.x, y: i });
  }

  for (var i = o.y; i >= 0; i--) {
    paths.push({ x: o.x, y: i });
  }

  for (var i = o.x; i < colNum; i++) {
    paths.push({ x: i, y: o.y });
  }

  for (var i = o.x; i >= 0; i--) {
    paths.push({ x: i, y: o.y });
  }

  // for (var i = 0; i < colNum; i++) {
  //   paths.push({ x: i, y: o.y });
  // }
  return paths;
}

function getSamePosition(targetPaths, o) {
  var paths = new Array({ x: 0, y: 0 }, { x: 0, y: 0 });
  for (var i = 0, n = targetPaths.length; i < n; i++) {
    // X轴相交的位置
    if (targetPaths[i].x == o.x) {
      paths[0] = { x: targetPaths[i].x, y: targetPaths[i].y };
    }

    // Y轴相交的位置
    if (targetPaths[i].y == o.y) {
      paths[1] = { x: targetPaths[i].x, y: targetPaths[i].y };
    }
  }

  return paths;
}

// 检查两点间的线是否可连
// A点必须为空
// B点可以不为空
function checkTwoLine(A, B, matrix) {
  // 如果是同一行
  if (A.x == B.x) {
    for (var i = A.y; A.y < B.y ? i < B.y : i > B.y; A.y < B.y ? i++ : i--) {
      if (!matrix.isWalkableAt(A.x, i)) {
        return false;
      }
    }
  }
  // 如果是同一列
  else {
    for (var i = A.x; A.x < B.x ? i < B.x : i > B.x; A.x < B.x ? i++ : i--) {
      if (!matrix.isWalkableAt(i, A.y)) {
        return false;
      }
    }
  }

  return true;
}

// 检查两个点是否相邻
function checkAdjacent(A, B) {
  var directions = new Array(-1, 1, 1, -1);

  var len = directions.length;
  for (var i = 0; i < len; i++) {
    if (A.x + directions[i] == B.x && A.y == B.y) {
      return true;
    }

    if (A.y + directions[i] == B.y && A.x == B.x) {
      return true;
    }
  }
  return false;
}

连连看的算法

连连看的算法的研究

前言