查看内容

H5游戏开发:消灭星星

  • 2019-12-12 14:15
  • 新浦京Web前端
  • Views

3.1 生成砖墙

砖墙分两步生成:

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

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

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

图片 1

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

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

以下是伪代码的实现:

JavaScript

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

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

自动识图

笔者在录入关卡配置时,发现一个7条边以上的连通图很容易录错或录重线段。笔者在思考能否开发一个自动识别图形的插件,毕竟「一笔画」的图形是有规则的几何图形。

图片 2

上面的关卡「底图」,一眼就可以识出三个颜色:

  • 白底
  • 端点颜色
  • 线段颜色

并且这三种颜色在「底图」的面积大小顺序是:白底 > 线段颜色 > 端点颜色。底图的「采集色值表算法」很简单,如下伪代码:

JavaScript

let imageData = ctx.getImageData(); let data = imageData.data; // 色值表 let clrs = new Map(); for(let i = 0, len = data.length; i < len; i += 4) { let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]]; let key = `rgba(${r}, ${g}, ${b}, ${a})`; let value = clrs.get(key) || {r, g, b, a, count: 0}; clrs.has(key) ? ++value.count : clrs.set(rgba, {r, g, b, a, count}); }

1
2
3
4
5
6
7
8
9
10
let imageData = ctx.getImageData();
let data = imageData.data;
// 色值表
let clrs = new Map();
for(let i = 0, len = data.length; i < len; i += 4) {
let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]];
let key = `rgba(${r}, ${g}, ${b}, ${a})`;
let value = clrs.get(key) || {r, g, b, a, count: 0};
clrs.has(key) ? ++value.count : clrs.set(rgba, {r, g, b, a, count});
}

对于连通图来说,只要把端点识别出来,连通图的轮廓也就出来了。

7. 结语

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

图片 3

游戏的源码托管在:

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

性能优化

由于「自动识图」需要对图像的的像素点进行扫描,那么性能确实是个需要关注的问题。笔者设计的「自动识图算法」,在识别图像的过程中需要对图像的像素做两次扫描:「采集色值表」 与 「采集端点」。在扫描次数上其实很难降低了,但是对于一张 750 * 1334 的底图来说,「自动识图算法」需要遍历两次长度为 750 * 1334 * 4 = 4,002,000 的数组,压力还是会有的。笔者是从压缩被扫描数组的尺寸来提升性能的。

被扫描数组的尺寸怎么压缩?
笔者直接通过缩小画布的尺寸来达到缩小被扫描数组尺寸的。伪代码如下:

JavaScript

// 要压缩的倍数 let resolution = 4; let [width, height] = [img.width / resolution >> 0, img.height / resolution >> 0]; ctx.drawImage(img, 0, 0, width, height); let imageData = ctx.getImageData(), data = imageData;

1
2
3
4
5
// 要压缩的倍数
let resolution = 4;
let [width, height] = [img.width / resolution >> 0, img.height / resolution >> 0];
ctx.drawImage(img, 0, 0, width, height);
let imageData = ctx.getImageData(), data = imageData;

把源图片缩小4倍后,得到的图片像素数组只有原来的 4^2 = 16倍。这在性能上是很大的提升。

3.4 消除残砖

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

JavaScript

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; } } }

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;
}
}
}

线段识别

笔者分两个步骤完成「线段识别」:

  1. 给定的两个端点连接成线,并采集连线上N个「样本点」;
  2. 遍历样本点像素,如果像素色值不等于线段色值则表示这两个端点之间不存在线段

如何采集「样式点」是个问题,太密集会影响性能;太疏松精准度不能保证。

在笔者面前有两个选择:N 是常量;N 是变量。
假设 N === 5。局部提取「样式点」如下:

图片 4

上图,会识别出三条线段:AB, BC 和 AC。而事实上,AC不能成线,它只是因为 AB 和 BC 视觉上共一线的结果。当然把 N 值向上提高可以解决这个问题,不过 N 作为常量的话,这个常量的取量需要靠经验来判断,果然放弃。

为了避免 AB 与 BC 同处一直线时 AC 被识别成线段,其实很简单 —— 两个「样本点」的间隔小于或等于端点直径
假设 N = S / (2 * R),S 表示两点的距离,R 表示端点半径。局部提取「样式点」如下:

图片 5

如上图,成功地绕过了 AC。「线段识别算法」的伪代码实现如下:

JavaScript

for(let i = 0, len = vertexes.length; i < len - 1; ++i) { let {x: x1, y: y1} = vertexes[i]; for(let j = i + 1; j < len; ++j) { let {x: x2, y: y2} = vertexes[j]; let S = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)); let N = S / (R * 2); let stepX = (x1 - x2) / N, stepY = (y1 - y2) / n; while(--N) { // 样本点不是线段色 if(!isBelongLine(x1 + N * stepX, y1 + N * stepY)) break; } // 样本点都合格 ---- 表示两点成线,保存 if(0 === N) lines.push({x1, y1, x2, y2}) } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(let i = 0, len = vertexes.length; i < len - 1; ++i) {
let {x: x1, y: y1} = vertexes[i];
for(let j = i + 1; j < len; ++j) {
let {x: x2, y: y2} = vertexes[j];
let S = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
let N = S / (R * 2);
let stepX = (x1 - x2) / N, stepY = (y1 - y2) / n;
while(--N) {
// 样本点不是线段色
if(!isBelongLine(x1 + N * stepX, y1 + N * stepY)) break;
}
// 样本点都合格 ---- 表示两点成线,保存
if(0 === N) lines.push({x1, y1, x2, y2})
}
}

4. View

View 主要的功能有两个:

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

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

JavaScript

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; } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 会根据对应的变化做对应的动作(动画)。

结语

下面是本文介绍的「一笔画」的线上 DEMO 的二维码:

图片 6

游戏的源码托管在:
其中游戏实现的主体代码在:
自动识图的代码在:

感谢耐心阅读完本文章的读者。本文仅代表笔者的个人观点,如有不妥之处请不吝赐教。

感谢您的阅读,本文由 凹凸实验室 版权所有。如若转载,请注明出处:凹凸实验室()

1 赞 1 收藏 评论

图片 7

2. MVC 设计模式

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

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

交互绘制

在画布上绘制路径,从视觉上说是「选择或连接连通图端点」的过程,这个过程需要解决2个问题:

  • 手指下是否有端点
  • 选中点到待选中点之间能否成线

收集连通图端点的坐标,再监听手指滑过的坐标可以知道「手指下是否有点」。以下伪代码是收集端点坐标:

JavaScript

// 端点坐标信息 let coords = []; lines.forEach(({x1, y1, x2, y2}) => { // (x1, y1) 在 coords 数组不存在 if(!isExist(x1, y1)) coords.push([x1, y1]); // (x2, y2) 在 coords 数组不存在 if(!isExist(x2, y2)) coords.push([x2, y2]); });

1
2
3
4
5
6
7
8
// 端点坐标信息
let coords = [];
lines.forEach(({x1, y1, x2, y2}) => {
// (x1, y1) 在 coords 数组不存在
if(!isExist(x1, y1)) coords.push([x1, y1]);
// (x2, y2) 在 coords 数组不存在
if(!isExist(x2, y2)) coords.push([x2, y2]);
});

以下伪代码是监听手指滑动:

JavaScript

easel.addEventListener("touchmove", e => { let x0 = e.targetTouches[0].pageX, y0 = e.targetTouches[0].pageY; // 端点半径 ------ 取连通图端点半径的2倍,提升移动端体验 let r = radius * 2; for(let [x, y] of coords){ if(Math.sqrt(Math.pow(x - x0, 2) + Math.pow(y - y0), 2) <= r){ // 手指下有端点,判断能否连线 if(canConnect(x, y)) { // todo } break; } } })

1
2
3
4
5
6
7
8
9
10
11
12
13
14
easel.addEventListener("touchmove", e => {
let x0 = e.targetTouches[0].pageX, y0 = e.targetTouches[0].pageY;
// 端点半径 ------ 取连通图端点半径的2倍,提升移动端体验
let r = radius * 2;
for(let [x, y] of coords){
if(Math.sqrt(Math.pow(x - x0, 2) + Math.pow(y - y0), 2) <= r){
// 手指下有端点,判断能否连线
if(canConnect(x, y)) {
// todo
}
break;
}
}
})

在未绘制任何线段或端点之前,手指滑过的任意端点都会被视作「一笔画」的起始点;在绘制了线段(或有选中点)后,手指滑过的端点能否与选中点串连成线段需要依据现有条件进行判断。

图片 8

上图,点A与点B可连接成线段,而点A与点C不能连接。笔者把「可以与指定端点连接成线段的端点称作有效连接点」。连通图端点的有效连接点从连通图的线段中提取:

JavaScript

coords.forEach(coord => { // 有效连接点(坐标)挂载在端点坐标下 coord.validCoords = []; lines.forEach(({x1, y1, x2, y2}) => { // 坐标是当前线段的起点 if(coord.x === x1 && coord.y === y1) { coord.validCoords.push([x2, y2]); } // 坐标是当前线段的终点 else if(coord.x === x2 && coord.y === y2) { coord.validCoords.push([x1, y1]); } }) })

1
2
3
4
5
6
7
8
9
10
11
12
13
14
coords.forEach(coord => {
// 有效连接点(坐标)挂载在端点坐标下
coord.validCoords = [];
lines.forEach(({x1, y1, x2, y2}) => {
// 坐标是当前线段的起点
if(coord.x === x1 && coord.y === y1) {
coord.validCoords.push([x2, y2]);
}
// 坐标是当前线段的终点
else if(coord.x === x2 && coord.y === y2) {
coord.validCoords.push([x1, y1]);
}
})
})

But…有效连接点只能判断两个点是否为底图的线段,这只是一个静态的参考,在实际的「交互绘制」中,会遇到以下情况:

图片 9
如上图,AB已串连成线段,当前选中点B的有效连接点是 A 与 C。AB 已经连接成线,如果 BA 也串连成线段,那么线段就重复了,所以此时 BA 不能成线,只有 AC 才能成线。

对选中点而言,它的有效连接点有两种:

  • 与选中点「成线的有效连接点」
  • 与选中点「未成线的有效连接点」

其中「未成线的有效连接点」才能参与「交互绘制」,并且它是动态的。

图片 10

回头本节内容开头提的两个问题「手指下是否有端点」 与 「选中点到待选中点之间能否成线」,其实可合并为一个问题:手指下是否存在「未成线的有效连接点」。只须把监听手指滑动遍历的数组由连通图所有的端点坐标 coords 替换为当前选中点的「未成线的有效连接点」即可。

至此「一笔画」的主要功能已经实现。可以抢先体验一下:

图片 11

参考资料

  • Knapsack problem
  • NP-completeness
  • popstar关卡是如何设计的?
  • 费雪耶兹乱序算法
  • 波动均分算法

    1 赞 收藏 评论

图片 12

H5游戏开发:一笔画

by leeenx on 2017-11-02

一笔画是图论[科普](https://zh.wikipedia.org/wiki/%E5%9B%BE%E8%AE%BA)中一个著名的问题,它起源于柯尼斯堡七桥问题[科普](https://zh.wikipedia.org/wiki/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98)。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题。用图论的术语来说,对于一个给定的连通图[科普](https://zh.wikipedia.org/wiki/%E8%BF%9E%E9%80%9A%E5%9B%BE)存在一条恰好包含所有线段并且没有重复的路径,这条路径就是「一笔画」。

寻找连通图这条路径的过程就是「一笔画」的游戏过程,如下:

图片 13

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. 通关条件

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

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

使用「自动识图」的建议

尽管笔者在本地测试的时候可以把所有的「底图」识别出来,但是并不能保证其它开发者上传的图片能否被很好的识别出来。笔者建议,可以把「自动识图」做为一个单独的工具使用。

笔者写了一个「自动识图」的单独工具页面:
可以在这个页面生成对应的关卡配置。

上一篇:H5 游戏开发:决胜三分球 下一篇:没有了