使用Vue3实现羊了个羊的算法

前言

这两天社区很多羊了个羊的web实现，虽然各种实现花里花哨，然而，并没有一个一个jy能给他说清楚到底怎么实现的，由于可怕的求知欲，自己来吧！

大纲

羊了个羊这个现象级游戏之所以能成功，不是因为他像原神一样，靠着质量、体验、剧情你爱不释手

他靠的是烂，让你爱不释手，人家玩的是营销，玩的是人性，也许你压根就过不了关！

他的技术实现，其实相当简单，在技术上从来没有什么高深的东西，

果然，高深的技术总是显得这么朴实无华！

最难的部分也就是算法了,我也大致的钻研了一下，但是这个算法坦率的讲不是我发明的，我只是站在巨人的肩膀上

他的算法实现的难点我以为有四方面

1、初始化的随机位置算法
2、检查是否被覆算法
3、三连匹配算法
4、队列区排序算法

在线演示

https://code.juejin.cn/pen/7144922644788297735

初始化的随机位置算法

在理解算法之前，我们先大致看元数据

他需要包含一些必备的属性，默认的覆盖情况，是否被选中的状态，icon 图标，icon 的唯一id x 坐标 y坐标

const scene=({
      isCover: false, // 默认都是没有被覆盖的
      status: 0,// 是否被选中的状态
      icon,// 图标
      id: randomString(4), // 生成随机id
      x: column * 100 + offset, //x 坐标
      y: row * 100 + offset,// y坐标
    }

然后再来说算法，他的算法，本质上其实就是限定的画布内，随机生成位置

在当前这个算法中他使用一个8x8的网格中，生成方块，然后利用随机偏移量，来造成随机堆叠的样子

// 以下感谢大佬们提供的算法
const makeScene = (level) => {
  // 获取当前关卡
  const curLevel = Math.min(maxLevel, level);
  // 获取当前关卡应该拥有的icon数量
  const iconPool = icons.slice(0, 2 * curLevel);
  // 算出偏移量范围具体细节范围
  const offsetPool = [0, 25, -25, 50, -50].slice(0, 1 + curLevel);
  //  最终的元数据数组
  const scene = [];
  // 确定范围
  //在一般情下 translate 的偏移量，如果是百分比的话，是按照自身的宽度或者高度去计算的，所以最大的偏移范围是百分800%
  // 然后通过Math.random 会小于百分之八百
  // 所以就会形成当前区间的随机数
  const range = [
    [2, 6],
    [1, 6],
    [1, 7],
    [0, 7],
    [0, 8],
  ][Math.min(4, curLevel - 1)];
  const randomSet = (icon: string) => {
    // 求偏移量
    const offset = offsetPool[Math.floor(offsetPool.length * Math.random())];
    // 偏移求列数
    const row = range[0] + Math.floor((range[1] - range[0]) * Math.random());
    // 求偏移行数
    const column = range[0] + Math.floor((range[1] - range[0]) * Math.random());
    console.log(offset, row, column);
    // 生成元数据对象
    scene.push({
      isCover: false, // 默认都是没有被覆盖的
      status: 0,// 是否被选中的状态
      icon,// 图标
      id: randomString(4), // 生成随机id
      x: column * 100 + offset, //x 坐标
      y: row * 100 + offset,// y坐标
    });
  };

  // 如果级别高了就加点icon 花哨一点
  let compareLevel = curLevel;
  while (compareLevel > 0) {
    iconPool.push(...iconPool.slice(0, Math.min(10, 2 * (compareLevel - 5))));
    compareLevel -= 5;
  }
  // 生成元数据，初始状态下 iconPool的内容少生 随着增加，就会越来越难
  for (const icon of iconPool) {
    for (let i = 0; i < 6; i++) {
      randomSet(icon);
    }
  }
  // 返回元数据
  return scene;
};

解释一下，我们在初始化的时候，会生成一个范围，来初始化他的预计位置

  const range = [
    [2, 6],
    [1, 6],
    [1, 7],
    [0, 7],
    [0, 8],
  ][Math.min(4, curLevel - 1)];

range 最后的结果，就表示格子范围，这里是为了跟关卡结合，在初始化的时候由于图标少，所以就会在在8x8之内的更小的格子

例如这样：

当关卡越来越多的时候就会如下图：

以为在后面关卡的时候将所有的格子撑满了为8x8

那么如何计算偏移量呢？

  const randomSet = (icon: string) => {
    // 求偏移量
    const offset = offsetPool[Math.floor(offsetPool.length * Math.random())];
    // 偏移求列数
    const row = range[0] + Math.floor((range[1] - range[0]) * Math.random());
    // 求偏移行数
    const column = range[0] + Math.floor((range[1] - range[0]) * Math.random());
    console.log(offset, row, column);
    // 生成元数据对象
    scene.push({
      isCover: false, // 默认都是没有被覆盖的
      status: 0,// 是否被选中的状态
      icon,// 图标
      id: randomString(4), // 生成随机id
      x: column * 100 + offset, //x 坐标
      y: row * 100 + offset,// y坐标
    });
  };

其实偏移量的核心就是 Math.random这个函数，来生成0-1的随机数,我们需要求 offset基础偏移量 row列的偏移量 column行的偏移量

由于为了导致位置的总体差异，和细节差异，来达到符合预期的乱序效果，所以最终他生成的坐标需要 基础偏移和行列偏移来结合

检查是否被覆算法

检查是否被覆盖算法其实本质上来说，就是祖传的碰撞检测算法

根据是否碰撞，来计算覆盖情况

代码如下:

// 检查是否被覆盖
const checkCover = (value) => {
  // 深拷贝一份
  const updateScene = value.slice();
  // 是否覆盖算法
  // 遍历所有的元数据
  // 双重for循环来找到每个元素的覆盖情况
  for (let i = 0; i < updateScene.length; i++) {
    // 当前item对角坐标
    const cur = updateScene[i];
    // 先假设他都不是覆盖的
    cur.isCover = false;
    // 如果status 不为0 说明已经被选中了，不用再判断了
    if (cur.status !== 0) continue;
    // 拿到坐标
    const { x: x1, y: y1 } = cur;
    // 为了拿到他们的对角坐标，所以要加上100
    //之所以要加上100 是由于 他的总体是800% 也就是一个格子的换算宽度是100
    const x2 = x1 + 100,
      y2 = y1 + 100;
    // 第二个来循环来判断他的覆盖情况
    for (let j = i + 1; j < updateScene.length; j++) {
      const compare = updateScene[j];
      if (compare.status !== 0) continue;


      const { x, y } = compare;
      // 处理交集也就是选中情况
      // 两区域有交集视为选中
      // 两区域不重叠情况取反即为交集
      if (!(y + 100 <= y1 || y >= y2 || x + 100 <= x1 || x >= x2)) {
        // 由于后方出现的元素会覆盖前方的元素，所以只要后方的元素被选中了，前方的元素就不用再判断了
        // 又由于双层循环第二层从j 开始，所以不用担心会重复判断
        cur.isCover = true;
        break;
      }
    }
  }
  scene.value = updateScene;
};

碰撞检测

所谓碰撞检测，就是计算两个东西的坐标有没有重叠，也就是求交集

主要算法如下，就是比较他们的各个方向的位置

function isButt(obj1,obj2){
     var l1=obj1.offsetLeft;
     var t1=obj1.offsetTop;
     var r1=l1+obj1.offsetWidth;
     var b1=t1+obj1.offsetHeight;
     var l2=obj2.offsetLeft;
     var t2=obj2.offsetTop;
     var r2=l2+obj2.offsetWidth;
     var b2=t2+obj2.offsetHeight;
   return!(r1<l2||b1<t2||r2<l1||b2<t1)
}

覆盖算法实现

覆盖算法其实实现也非常简单，就是一个双重for循环 来将每个方块的位置做比较，做一个碰撞检测，从而能筛选出来被遮挡的方块

值得注意的是

1、j的值需要从i+1开始,为了防止已经比较过的方块再次比较
2、由于元数据的渲染，的后方物体天然的会遮挡前方物体，所以当碰撞检测成功之后是只需要遮挡前方方块即可

for (let i = 0; i < updateScene.length; i++) {
  // 第二个来循环来判断他的覆盖情况
  for (let j = i + 1; j < updateScene.length; j++) {
    // 执行碰撞检测
  }
}

三连匹配算法

三连匹配其实相比于前两点，就非常简单了

我们只需要拿到相同的方块的icon名，凑够三个直接改变方块样式即可

// 点击item
const clickSymbol = async (idx: number) => {
  // 如果已经完成了，就不处理
  if (finished.value || animating.value) return;
  // 拷贝一份Scene
  const symbol = scene.value[idx];
  // 覆盖了和已经在队列里的也不处理
  if (symbol.isCover || symbol.status !== 0) return;
  //置为可以选中状态
  symbol.status = 1;
  queue.value.push(symbol);
  // 制造动画效果中防止点击
  animating.value = true;
  //三百毫秒的延迟
  await waitTimeout(300);
  // 拿到与他匹配的所有icon
  const filterSame = queue.value.filter((sb) => sb.icon === symbol.icon);

  // 选中的三个配对成功表示已经是三连了
  if (filterSame.length === 3) {
    // 由于icon的类型一样，留下队列中的不一样的剩余内容重新赋值
    queue.value = queue.value.filter((sb) => sb.icon !== symbol.icon);
    // 隐藏iocn，dom
    for (const sb of filterSame) {
      const find = scene.value.find((i) => i.id === sb.id);
      // 将他们的状态变为2 通过opacity 属性 来隐藏icon
      if (find) find.status = 2;
    }
  }

  // 当格子沾满了，那么久表示已经失败了
  if (queue.value.length === 7) {
    tipText.value = '失败了'
    finished.value = true;
  }

  if (!scene.value.find((s) => s.status !== 2)) {
    // 如果完成所有关卡，那就过了所有关了
    if (level.value === maxLevel) {
      tipText.value = '完成挑战';
      finished.value = true
      return;
    }
    //否则加一关
    level.value = level.value + 1;
    queue.value = []
    // 重新初始化
    checkCover(makeScene(level.value + 1));
  } else {
    // 处理覆盖情况
    checkCover(scene.value);
  }
  // 动画结束
  animating.value = false;
};

以上代码中，我们只需要改变元数据的status的状态值即可，然后再配合css的视觉效果，来达到消失的效果，其实dom 还是在页面中，并没有消失移除，因为元数据没变

队列区排序算法

在队列中我们发现如果凑够三个他需要排序，

比如说在有一个叉子，就会排在米饭的前面然后消失

实现如下：

// 队列区排序
watchEffect(() => {
  const cache = {};
  // 通过当前的icon的标识，将相同的icon归纳到一块
  // 方便后续排序
  for (const symbol of queue.value) {
    if (cache[symbol.icon]) {
      cache[symbol.icon].push(symbol);
    } else {
      cache[symbol.icon] = [symbol];
    }
  }
  const temp = [];
  for (const symbols of Object.values(cache)) {
    temp.push(...(symbols as any));
  }
  const updateSortedQueue = {};
  let x = 50;
  // 拿到更新后的队列区数据，计算权重
  for (const symbol of temp) {
    updateSortedQueue[symbol.id] = x;
    x += 100;
  }
  //赋值 ，这个是为了将选中的排序后的内容移动到队列区
  sortedQueue.value = updateSortedQueue
  // 检查覆盖情况
  checkCover(scene.value);
})

他的实现原理其实就是利用缓存对队列计算先后权重，从而计算他排序的位置，其实他的元数据或者选中顺序并没有变

只是在视觉上更改了css 的样式