搞定他,就能给面试官吹晕!使用Vue3实现【羊了个羊】的算法方面全面解析!

语言: CN / TW / HK

“我报名参加金石计划1期挑战——瓜分10万奖池,这是我的第1篇文章,点击查看活动详情

image.png

前言

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

大纲

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

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

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

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

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

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

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

在线演示

羊了个羊

初始化的随机位置算法

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

他需要包含 一些必备的属性, 默认的覆盖情况,是否被选中的状态,icon 图标,icon 的唯一id x 坐标 y坐标 js const scene=({ isCover: false, // 默认都是没有被覆盖的 status: 0,// 是否被选中的状态 icon,// 图标 id: randomString(4), // 生成随机id x: column * 100 + offset, //x 坐标 y: row * 100 + offset,// y坐标 }

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

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

image.png

```js // 以下感谢大佬们提供的算法 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; };

```

解释一下, 我们在初始化的时候, 会生成一个范围,来初始化 他的预计位置 js const range = [ [2, 6], [1, 6], [1, 7], [0, 7], [0, 8], ][Math.min(4, curLevel - 1)]; range 最后的结果,就表示格子范围,这里是为了跟关卡结合,在初始化的时候 由于图标少, 所以就会在 在8x8之内的更小的格子

例如这样:

image.png

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

image.png

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

那么如何计算偏移量呢?

js 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行的偏移量

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

检查是否被覆算法

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

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

代码如下:

```js

// 检查是否被覆盖 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; }; ```

碰撞检测

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

image.png

主要算法如下,就是比较他们的各个方向的位置 js   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、由于元数据的渲染,的后方物体天然的会遮挡前方物体,所以当碰撞检测成功之后是只需要遮挡前方方块即可

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

三连匹配算法

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

我们只需要拿到相同的方块的icon名, 凑够三个直接改变方块样式即可 ```js // 点击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 还是在页面中,并没有消失移除,因为元数据没变

队列区排序算法

image.png

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

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

实现如下:

```js

// 队列区排序 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 的样式

总结

我想我已经讲清楚,整体羊了个羊的算法实现了 经历半天的源码查看,将总体的实现算法解读了出来,希望对源码感兴趣的大佬们有些帮助!

赋上vue+ts写的一个动效的效果原理解读: vue3+TS实现满天心飘落动效

也是类似于随机生成的例子,希能帮助各位大佬理解!