H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

Chase620 等级 314 0 0

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

H5游戏开发:消灭星星

by leeenx on 2018-01-17

详细介绍消灭星星游戏的实现(带源码)

「消灭星星」是一款很经典的「消除类游戏」,它的玩法很简单:消除相连通的同色砖块。

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

1. 游戏规则

「消灭星星」存在多个版本,不过它们的规则除了「关卡分值」有些出入外,其它的规则都是一样的。笔者介绍的版本的游戏规则整理如下:

1. 色砖分布

  • 10 x 10 的表格
  • 5种颜色 —— 红、绿、蓝,黄,紫
  • 每类色砖个数在指定区间内随机
  • 5类色砖在 10 x 10 表格中随机分布

2. 消除规则

两个或两个以上同色砖块相连通即是可被消除的砖块。

3. 分值规则

  • 消除总分值 = n * n * 5
  • 奖励总分值 = 2000 - n * n * 20

「n」表示砖块数量。上面是「总」分值的规则,还有「单」个砖块的分值规则:

  • 消除砖块得分值 = 10 * i + 5
  • 剩余砖块扣分值 = 40 * i + 20

「i」表示砖块的索引值(从 0 开始)。简单地说,单个砖块「得分值」和「扣分值」是一个等差数列。

4. 关卡分值

关卡分值 = 1000 + (level - 1) * 2000;「level」即当前关卡数。

5. 通关条件

  • 可消除色块不存在
  • 累计分值 >= 当前关卡分值

上面两个条件同时成立游戏才可以通关。

2. MVC 设计模式

笔者这次又是使用了 MVC 模式来写「消灭星星」。星星「砖块」的数据结构与各种状态由 Model 实现,游戏的核心在 Model 中完成;View 映射 Model 的变化并做出对应的行为,它的任务主要是展示动画;用户与游戏的交互由 Control 完成。

从逻辑规划上看,Model 很重而View 与 Control 很轻,不过,从代码量上看,View 很重而 Model 与 Control 相对很轻。

3. Model

10 x 10 的表格用长度为 100 的数组可完美映射游戏的星星「砖块」。

1
2
3
4
5
6
7
8
9
10
11
12
[
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P
]

R - 红色,G - 绿色,B - 蓝色,Y - 黄色,P - 紫色。Model 的核心任务是以下四个:

  • 生成砖墙
  • 消除砖块 (生成砖块分值)
  • 夯实砖墙
  • 清除残砖 (生成奖励分值)

3.1 生成砖墙

砖墙分两步生成:

  • 色砖数量分配
  • 打散色砖

理论上,可以将 100 个格子可以均分到 5 类颜色,不过笔者玩过的「消灭星星」都不使用均分策略。通过分析几款「消灭星星」,其实可以发现一个规律 —— 「色砖之间的数量差在一个固定的区间内」。

如果把传统意义上的均分称作「完全均分」,那么「消灭星星」的分配是一种在均分线上下波动的「不完全均分」。

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

笔者把上面的「不完全均分」称作「波动均分」,算法的具体实现可以参见「波动均分算法」。

「打散色砖」其实就是将数组乱序的过程,笔者推荐使用「 费雪耶兹乱序算法」。

以下是伪代码的实现:

1
2
3
4
5
6
7
// 波动均分色砖
waveaverage(5, 4, 4).forEach(
// tiles 即色墙数组
(count, clr) => tiles.concat(generateTiles(count, clr));
);
// 打散色砖
shuffle(tiles);

3.2 消除砖块

「消除砖块」的规则很简单 —— 相邻相连通相同色即可以消除

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」
前两个组合符合「相邻相连通相同色即可以消除」,所以它们可以被消除;第三个组合虽然「相邻相同色」但是不「相连通」所以它不能被消除。

「消除砖块」的同时有一个重要的任务:生成砖块对应的分值。在「游戏规则」中,笔者已经提供了对应的数学公式:「消除砖块得分值 = 10 * i + 5」。

「消除砖块」算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function clean(tile) { 
let count = 1;
let sameTiles = searchSameTiles(tile);
if(sameTiles.length > 0) {
deleteTile(tile);
while(true) {
let nextSameTiles = [];
sameTiles.forEach(tile => {
nextSameTiles.push(...searchSameTiles(tile));
makeScore(++count * 10 + 5); // 标记当前分值
deleteTile(tile); // 删除砖块
});
// 清除完成,跳出循环
if(nextSameTiles.length === 0) break;
else {
sameTiles = nextSameTiles;
}
}
}
}

清除的算法使用「递归」逻辑上会清晰一些,不过「递归」在浏览器上容易「栈溢出」,所以笔者没有使用「递归」实现。

3.3 夯实砖墙

砖墙在消除了部分砖块后,会出现空洞,此时需要对墙体进行夯实:

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」 H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」 H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」
向下夯实 向左夯实 向左下夯实(先下后左)

一种快速的实现方案是,每次「消除砖块」后直接遍历砖墙数组(10x10数组)再把空洞夯实,伪代码表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(let row = 0; row < 10; ++row) {
for(let col = 0; col < 10; ++col) {
if(isEmpty(row, col)) {
// 水平方向(向左)夯实
if(isEmptyCol(col)) {
tampRow(col);
}
// 垂直方向(向下)夯实
else {
tampCol(col);
}
break;
}
}
}

But… 为了夯实一个空洞对一张大数组进行全量遍历并不是一种高效的算法。在笔者看来影响「墙体夯实」效率的因素有:

  1. 定位空洞
  2. 砖块移动(夯实)

扫描墙体数组的主要目的是「定位空洞」,但能否不扫描墙体数组直接「定位空洞」?

墙体的「空洞」是由于「消除砖块」造成的,换种说法 —— 被消除的砖块留下来的坑位就是墙体的空洞。在「消除砖块」的同时标记空洞的位置,这样就无须全量扫描墙体数组,伪代码如下:

1
2
3
4
5
6
function deleteTile(tile) { 
// 标记空洞
markHollow(tile.index);
// 删除砖块逻辑
...
}

在上面的夯实动图,其实可以看到它的夯实过程如下:

  1. 空洞上方的砖块向下移动
  2. 空列右侧的砖块向左移动

墙体在「夯实」过程中,它的边界是实时在变化,如果「夯实」不按真实边界进行扫描,会产生多余的空白扫描:

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

如何记录墙体的边界?
把墙体拆分成一个个单独的列,那么列最顶部的空白格片段就是墙体的「空白」,而其余非顶部的空白格片段即墙体的「空洞」。

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

笔者使用一组「列集合」来描述墙体的边界并记录墙体的空洞,它的模型如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
@ count - 列砖块数
@ start - 顶部行索引
@ end - 底部行索引
@ pitCount - 坑数
@ topPit - 最顶部的坑
@ bottomPit - 最底部的坑
*/
let wall = [
{count, start, end, pitCount, topPit, bottomPit},
{count, start, end, pitCount, topPit, bottomPit},
...
];

这个模型可以描述墙体的三个细节:

  • 空列
  • 列的连续空洞
  • 列的非连续空洞
1
2
3
4
5
6
7
8
9
10
11
12
// 空列
if(count === 0) {
...
}
// 连续空洞
else if(bottomPit - topPit + 1 === pitCount) {
...
}
// 非连续空洞
else {
...
}

砖块在消除后,映射到单个列上的空洞会有两种分布形态 —— 连续与非连续。

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

「连续空洞」与「非连续空洞」的夯实过程如下:

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

其实「空列」放大于墙体上,也会有「空洞」类似的分布形态 —— 连续与非连续。
H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

它的夯实过程与空洞类似,这里就不赘述了。

3.4 消除残砖

上一小节提到了「描述墙体的边界并记录墙体的空洞」的「列集合」,笔者是直接使用这个「列集合」来消除残砖的,伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
function clearAll() {
let count = 0;
for(let col = 0, len = this.wall.length; col < len; ++col) {
let colInfo = this.wall[col];
for(let row = colInfo.start; row <= colInfo.end; ++row) {
let tile = this.grid[row * this.col + col];
tile.score = -20 - 40 * count++; // 标记奖励分数
tile.removed = true;
}
}
}

4. View

View 主要的功能有两个:

  • UI 管理
  • 映射 Model 的变化(动画)

UI 管理主要是指「界面绘制」与「资源加载管理」,这两项功能比较常见本文就直接略过了。View 的重头戏是「映射 Model 的变化」并完成对应的动画。动画是复杂的,而映射的原理是简单的,如下伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
update({originIndex, index, clr, removed, score}) { 
// 还没有 originIndex 或没有色值,直接不处理
if(originIndex === undefined || clr === undefined) return ;
let tile = this.tiles[originIndex];
// tile 存在,判断颜色是否一样
if(tile.clr !== clr) {
this.updateTileClr(tile, clr);
}
// 当前索引变化 ----- 表示位置也有变化
if(tile.index !== index) {
this.updateTileIndex(tile, index);
}
// 设置分数
if(tile.score !== score) {
tile.score = score;
}

if(tile.removed !== removed) {
// 移除或添加当前节点
true === removed ? this.bomb(tile) : this.area.addChild(tile.sprite);
tile.removed = removed;
}
}

Model 的砖块每次数据的更改都会通知到 View 的砖块,View 会根据对应的变化做对应的动作(动画)。

5. Control

Control 要处理的事务比较多,如下:

  • 绑定 Model & View
  • 生成通关分值
  • 判断通关条件
  • 对外事件
  • 用户交互

初始化时,Control 把 Model 的砖块单向绑定到 View 的砖块了。如下:

Object.defineProperties(model.tile, {
    originIndex: {
        get() {...}, 
        set(){
            ...
            view.update({originIndex})
        }
    },  
    index: {
        get() {...}, 
        set() {
            ...
            view.update({index})
        }
    }, 
    clr: {
        get() {...}, 
        set() {
            ...
            view.update({clr})
        }
    }, 
    removed: {
        get() {...}, 
        set() {
            ...
            view.update({removed})
        }
    },  
    score: {
        get() {...}, 
        set() {
            ...
            view.update({score})
        }
    }
}) 

「通关分值」与「判断通关条件」这对逻辑在本文的「游戏规则」中有相关介绍,这里不再赘述。

对外事件规划如下:

name detail
pass 通关
pause 暂停
resume 恢复
gameover 游戏结束

用户交互 APIs 规划如下:

name type deltail
init method 初始化游戏
next method 进入下一关
enter method 进入指定关卡
pause method 暂停
resume method 恢复
destroy method 销毁游戏

6. 问题

在知乎有一个关于「消灭星星」的话题:popstar关卡是如何设计的?

这个话题在最后提出了一个问题 —— 「无法消除和最大得分不满足过关条件的矩阵」

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

「无法消除的矩阵」其实就是最大得分为0的矩阵,本质上是「最大得分不满足过关条件的矩阵」。

最大得分不满足过关条件的矩阵
求「矩阵」的最大得分是一个 「背包问题」,求解的算法不难:对当前矩阵用「递归」的形式把所有的消灭分支都执行一次,并取最高分值。但是 javascript 的「递归」极易「栈溢出」导致算法无法执行。

其实在知乎的话题中提到一个解决方案:

网上查到有程序提出做个工具随机生成关卡,自动计算,把符合得分条件的关卡筛选出来

这个解决方案代价是昂贵的!笔者提供有源码并没有解决这个问题,而是用一个比较取巧的方法:进入游戏前检查是事为「无法消除矩阵」,如果是重新生成关卡矩阵

注意:笔者使用的取巧方案并没有解决问题。

7. 结语

下面是本文介绍的「消灭星星」的线上 DEMO 的二维码:

H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」

游戏的源码托管在:https://github.com/leeenx/popstar

感谢耐心阅读完本文章的读者。本文仅代表笔者的个人观点,如有不妥之处请不吝赐教。
如果对「H5游戏开发」感兴趣,欢迎关注我们的专栏

参考资料

游戏 H5 canvas game 消灭星星 popstar pixijs

H5游戏开发

感谢您的阅读,本文由 凹凸实验室 版权所有。如若转载,请注明出处:凹凸实验室(https://aotu.io/notes/2018/01/17/popstar/

上次更新:2021-02-02 15:48:05

H5游戏开发:FC小蜜蜂

波动均分算法

var gitalkOpts={id:"bm90ZXMvMjAxOC8wMS8xNy9wb3BzdGFyLw==",owner:"o2team",repo:"o2team.github.io",title:"H5游戏开发:消灭星星",body:"https://aotu.io/notes/2018/01/17/popstar/index.html\\n\\n详细介绍消灭星星游戏的实现(带源码)",clientID:"3c4d153e6874260f9c7e",clientSecret:"dd44012504c6168bc05b9266e0554bb28c62ce15",admin:\["leeenx"\]}

本文转自 https://aotu.io/notes/2018/01/17/popstar/,如有侵权,请联系删除。

收藏
评论区

相关推荐

基于React+Koa实现一个h5页面可视化编辑器
前言 前段时间笔者一直忙于数据可视化方面的工作,比如如何实现拖拽式生成可视化大屏,如何定制可视化图表交互和数据导入方案等,这块需求在B端企业中应用非常大,所以非常有探索价值。 本篇文章并非和数据可视化相关,而是通过抽象技术底层,将其应用于H5页面可视化搭建上,通过技术的手段实现拖拽式生成H5页面。这块也有非常多的应用场景,比如我们需要开发一个移动端网站,一
教你用200行代码写一个爱豆拼拼乐H5小游戏(附源码)
前言 本文将带大家一步步实现一个H5拼图小游戏,考虑到H5游戏的轻量级和代码体积,我没有使用react或vue这些框架,而采用我自己写的dom库和原生javascript来实现业务功能,具体库代码可见我的文章如何用不到200行代码写一款属于自己的js类库(https://juejin.im/post/6844903880707293198),构建工具我采
antd popover定位不准闪跳解决+自己实现popover库
前言 我在写H5dooring(https://github.com/MrXujiang/h5Dooring)时,发现我们用的popover会发生闪跳,而且第一次闪跳就算了,每次还会有另一个方向的闪跳。 于是我大概百度了下,基本都说需要给固定宽高即可,让后试了下发现没用,就算触发组件和弹窗元素都给了宽高,也一样闪跳。由于antd的popover底层
JavaScript实现H5接金币功能
今日做出做出一个春节接金币红包的活动,感觉挺不错的分享给大家 这个小游戏采用hilojs实现的,详情(https://hiloteam.github.io/Hilo/docs/apizh/index.html) 第一步:安装插件 npm i hilojs或者yarn add hilojs 第二步:创建一个Asset.js文件 language i
Android WebView加载优化
1.前言 最近几年关于原生WebView与H5混合开发的项目越来越多,这种开发带来了很多便利,但也会有一些缺点,比如说通过WebView加载H5会有一定的卡顿现象,会影响用户体验。下面本文就此问题一一展开讨论。 2. 场景 根据日常需求一般是通过webView.loadUrl()方法加载指定的网页,其大概流程如下: (https://i
Android webview 与 js(Vue) 交互
js 与原生交互分为两种情况:js 调用原生方法,原生调用 js 方法。 本文将对这两种情况分别讲解,H5 端用 vue 实现。 一、前期准备(Vue项目准备) 本文的 H5 端用Vue 实现,所以在正式开始前先把 Vue 项目环境准备好。 项目写好后,执行 npm run serve 命令启动项目,启动成功后会在命令
看了10款文档编辑器之后, 我决定...
作为一名技术工作者, 我们经常会遇到编写技术文档, 技术分享等需求, 网上也有很多现成的文档管理工具, 出于好奇心, 我拉着朋友一起实现了一个, 用来自给自足. 接下来就来介绍一下轻量级且灵活方便的文档编辑工具—— powerNice(http://h5.dooring.cn/powernice). powerNice(http://h5.door
Android通过URL打开Activity
关注公众号 QXF069 为每个 Activity 绑定一个 url 可以方便的让第三方 app 直接打开这些 Activity。也可以方便在 app 内部进行页面跳转,解耦。 背景 举一个常见的案例,假设我们有个产品 A,产品 A 包含 h5 网页端和客户端,当用户在手机打开我们的 h5 网页端的时候,我们会期望如果用户手机安装了我们的客户端,则直接打
移动端H5开发常用技巧总结
html 篇 常用的meta属性设置 meta对于移动端的一些特殊属性,可根据需要自行设置 <meta name"screenorientation" content"portrait" //Android 禁止屏幕旋转 <meta name"fullscreen" content"yes"             //全屏显示
H5游戏开发:FC小蜜蜂 | Aotu.io「凹凸实验室」
H5游戏开发:FC小蜜蜂 by TH(https://github.com/ONESUNDAY) on 20180128 使用 Phaser 游戏引擎开发,主要
H5游戏开发:消灭星星 | Aotu.io「凹凸实验室」
H5游戏开发:消灭星星 by leeenx(https://github.com/leeenx) on 20180
从零开发一款可视化大屏制作平台
几个月前开源的H5页面制作平台H5Dooring(http://h5.dooring.cn/) 收到了很多热心的反馈和交流, 顺着笔者之前的规划, 我们又做了一款可视化大屏编辑器V6.Dooring(https://github.com/MrXujiang/v6.dooring.public). 接下来笔者就来带大家一起看看我们的方案设计和技术实现
vue h5 对接支付宝,微信支付,微信js支付
vue h5 实现支付(支付宝,微信) h5端实现支付难度不大,只是有些小的点需要注意下,其他的看文档撸就行了。 支付宝很简单,后端返回一个 html ,前端插入调用就行了,微信支付分两种:1、微信内支付(jsapi,微信内浏览器)2、微信外支付(h5支付)。 一、支付宝支付 // 前端啥都不用管,交给后端去干,返回 html 调用点击就好了 /
h5 - 总结及踩坑记录
这是近期的一个 h5 项目,由于某些原因,预览地址不能放出来。不过这不是重点,没有 demo 不就可以好好看文章了吗 哈哈哈~文中提到的 pixi 是 pixiJs,精灵是 pixiJs 中的概念。阅读本文假设你已经知道了这些东西,不过这在本篇文章中并没有太多关于这个库的内容觉得这篇文章有帮助到自己,就让它去收藏夹吃灰;觉得没用或觉得写的不好的,可以留下
APP 开发技术该如何选型 ?
目前 按照 APP 开发分类,分为以下三大类 原生 APP  \[ Android Swift  \] WEB APP Hybrid App \[混合 APP  \] 在找工作的当中,很多岗位 要求 会开发 H5 App ,那到底什么是H5 APP 呢?一开始我也有点疑惑,没接触这块,按自己理解 就是 采用 HTML5 技术