H5游戏开发:消灭星星

2018/01/25 · HTML5 ·
游戏

原文出处: 凹凸实验室   

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

图片 1

以前做图像处理时用的是matlab,但是matlab有一些不方便支出:

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

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

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

  • 不开源,当时使用的版本是破解版的,至于版权问题,此处就不讨论了;
  • 其一般只能用于实现,如果实现产业化则有很多不便;
  • 程序运行比较慢;
  • 与其他语言结合有点小问题。
    当进入工作岗位之后,做的是大数据方向,接触了java与python后感觉python对于做图像处理会更加好,所以此处简单的对python操作图像做一些简单的介绍。

2. MVC 设计模式

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

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

  1. 首先安装pytyhon,linux系统中
    已经自己带了python,至于在window系统只安装则更加简单,下载一个Anaconda直接就可以安装了,后续的模块安装则直接使用pip安装会更加方便。在此处就不一一讲述了。

3. Model

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

[ 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 ]

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
的核心任务是以下四个:

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

图像打开与显示

from PIL import Image
import numpy as np
import scipy
import matplotlib.pyplot as plt
lena = Image.open('lena.jpg')           //打开图像  
print(lena.mode)                       //打印图像类型
print(lena.getpixel((0,0)))           //打印图像(0,0)处像素值
lena.show()                            //图像显示

3.1 生成砖墙

砖墙分两步生成:

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

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

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

图片 2

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

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

以下是伪代码的实现:

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

图像类型转化convert函数

python图像处理库PIL对于PNG、BMP和JPG彩色图像格式之间的互相转换都可以通过Image模块的open()和save()函数来完成。具体说就是,在打开这些图像时,PIL会将它们解码为三通道的“RGB”图像。用户可以基于这个“RGB”图像,对其进行处理。处理完毕,使用函数save(),可以将处理结果保存成PNG、BMP和JPG中任何格式。这样也就完成了几种格式之间的转换。同理,其他格式的彩色图像也可以通过这种方式完成转换。当然,对于不同格式的灰度图像,也可通过类似途径完成,只是PIL解码后是模式为“L”的图像。我们以图像图片 3为例,分辨率为512×512。

  1. 模式“RGB”转换为其他不同模式

a. 模式“1”
模式“1”为二值图像,非黑即白。但是它每个像素用8个bit表示,0表示黑,255表示白。下面我们将lena图像转换为“1”图像。

lena_1 = lena.convert("1")
print(lena_1.mode)
lena_1.show()

b. 模式“L”
模式“L”为灰色图像,它的每个像素用8个bit表示,0表示黑,255表示白,其他数字表示不同的灰度。在PIL中,从模式“RGB”转换为“L”模式是按照下面的公式转换的:
L = R * 299/1000 + G * 587/1000+ B * 114/1000
下面我们将lena图像转换为“L”图像。

lena_1 = lena.convert("L")
print(lena_1.mode)
lena_1.show()

c模式“P”
模式“P”为8位彩色图像,它的每个像素用8个bit表示,其对应的彩色值是按照调色板查询出来的。下面我们使用默认的调色板将lena图像转换为“P”图像。

lena_1 = lena.convert("P")
print(lena_1.mode)
lena_1.show()

d 模式“RGBA”
模式“RGBA”为32位彩色图像,它的每个像素用32个bit表示,其中24bit表示红色、绿色和蓝色三个通道,另外8bit表示alpha通道,即透明通道。

lena_1 = lena.convert("RGBA")
print(lena_1.mode)
lena_1.show()

e 模式“CMYK”
模式“CMYK”为32位彩色图像,它的每个像素用32个bit表示。模式“CMYK”就是印刷四分色模式,它是彩色印刷时采用的一种套色模式,利用色料的三原色混色原理,加上黑色油墨,共计四种颜色混合叠加,形成所谓“全彩印刷”。
四种标准颜色是:C:Cyan = 青色,又称为‘天蓝色’或是‘湛蓝’M:Magenta =
品红色,又称为‘洋红色’;Y:Yellow = 黄色;K:Key Plate(blacK) =
定位套版色(黑色)。

从实例中可以得知PIL中“RGB”转换为“CMYK”的公式如下: C = 255 – R M = 255 –
G Y = 255 – B K = 0 由于该转换公式比较简单,转换后的图像颜色有些失真。

f 模式“YCbCr”
模式“YCbCr”为24位彩色图像,它的每个像素用24个bit表示。YCbCr其中Y是指亮度分量,Cb指蓝色色度分量,而Cr指红色色度分量。人的肉眼对视频的Y分量更敏感,因此在通过对色度分量进行子采样来减少色度分量后,肉眼将察觉不到的图像质量的变化。
模式“RGB”转换为“YCbCr”的公式如下: Y= 0.257R+0.504G+0.098B+16 Cb =
-0.148
R-0.291G+0.439B+128 Cr = 0.439R-0.368G-0.071*B+128

按照公式,Y = 0.257197+0.564111+0.09878+16= 136.877 Cb=
-0.148
197-0.291111+0.43978+128= 100.785 Cr =
0.439197-0.368111-0.071*78+128 = 168.097
由此可见,PIL中并非按照这个公式进行“RGB”到“YCbCr”的转换。

g 模式“I”
模式“I”为32位整型灰色图像,它的每个像素用32个bit表示,0表示黑,255表示白,(0,255)之间的数字表示不同的灰度。在PIL中,从模式“RGB”转换为“I”模式是按照下面的公式转换的:
I = R * 299/1000 + G * 587/1000 + B * 114/1000

h 模式“F”
模式“F”为32位浮点灰色图像,它的每个像素用32个bit表示,0表示黑,255表示白,(0,255)之间的数字表示不同的灰度。在PIL中,从模式“RGB”转换为“F”模式是按照下面的公式转换的:
F = R * 299/1000+ G * 587/1000 + B * 114/1000

3.2 消除砖块

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

图片 4
前两个组合符合「相邻相连通相同色即可以消除」,所以它们可以被消除;第三个组合虽然「相邻相同色」但是不「相连通」所以它不能被消除。

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

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

JavaScript

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

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

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

图像保存

img.save('d:/lena.jpg')

注:后面的转化代码处理模式不一样,其余都是一样的,所以没有写代码

3.3 夯实砖墙

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

向下夯实 向左夯实 向左下夯实(先下后左)

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

JavaScript

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

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. 砖块移动(夯实)

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

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

JavaScript

function deleteTile(tile) { // 标记空洞 markHollow(tile.index); //
删除砖块逻辑 … }

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

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

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

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

图片 5

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

图片 6

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

JavaScript

/* @ 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
13
/*
@ count – 列砖块数
@ start – 顶部行索引
@ end – 底部行索引
@ pitCount – 坑数
@ topPit – 最顶部的坑
@ bottomPit – 最底部的坑
*/
let wall = [
{count, start, end, pitCount, topPit, bottomPit},
{count, start, end, pitCount, topPit, bottomPit},
];

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

  • 空列
  • 列的连续空洞
  • 列的非连续空洞
JavaScript

// 空列 if(count === 0) { ... } // 连续空洞 else if(bottomPit -
topPit + 1 === pitCount) { ... } // 非连续空洞 else { ... }

<table>
<colgroup>
<col style="width: 50%" />
<col style="width: 50%" />
</colgroup>
<tbody>
<tr class="odd">
<td><div class="crayon-nums-content" style="font-size: 13px !important; line-height: 15px !important;">
<div class="crayon-num" data-line="crayon-5b8f3d2c2df29914802382-1">
1
</div>
<div class="crayon-num crayon-striped-num" data-line="crayon-5b8f3d2c2df29914802382-2">
2
</div>
<div class="crayon-num" data-line="crayon-5b8f3d2c2df29914802382-3">
3
</div>
<div class="crayon-num crayon-striped-num" data-line="crayon-5b8f3d2c2df29914802382-4">
4
</div>
<div class="crayon-num" data-line="crayon-5b8f3d2c2df29914802382-5">
5
</div>
<div class="crayon-num crayon-striped-num" data-line="crayon-5b8f3d2c2df29914802382-6">
6
</div>
<div class="crayon-num" data-line="crayon-5b8f3d2c2df29914802382-7">
7
</div>
<div class="crayon-num crayon-striped-num" data-line="crayon-5b8f3d2c2df29914802382-8">
8
</div>
<div class="crayon-num" data-line="crayon-5b8f3d2c2df29914802382-9">
9
</div>
<div class="crayon-num crayon-striped-num" data-line="crayon-5b8f3d2c2df29914802382-10">
10
</div>
<div class="crayon-num" data-line="crayon-5b8f3d2c2df29914802382-11">
11
</div>
<div class="crayon-num crayon-striped-num" data-line="crayon-5b8f3d2c2df29914802382-12">
12
</div>
</div></td>
<td><div class="crayon-pre" style="font-size: 13px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
<div id="crayon-5b8f3d2c2df29914802382-1" class="crayon-line">
// 空列
</div>
<div id="crayon-5b8f3d2c2df29914802382-2" class="crayon-line crayon-striped-line">
if(count === 0) { 
</div>
<div id="crayon-5b8f3d2c2df29914802382-3" class="crayon-line">
 ...
</div>
<div id="crayon-5b8f3d2c2df29914802382-4" class="crayon-line crayon-striped-line">
}
</div>
<div id="crayon-5b8f3d2c2df29914802382-5" class="crayon-line">
// 连续空洞
</div>
<div id="crayon-5b8f3d2c2df29914802382-6" class="crayon-line crayon-striped-line">
else if(bottomPit - topPit + 1 === pitCount) { 
</div>
<div id="crayon-5b8f3d2c2df29914802382-7" class="crayon-line">
 ...
</div>
<div id="crayon-5b8f3d2c2df29914802382-8" class="crayon-line crayon-striped-line">
}
</div>
<div id="crayon-5b8f3d2c2df29914802382-9" class="crayon-line">
// 非连续空洞
</div>
<div id="crayon-5b8f3d2c2df29914802382-10" class="crayon-line crayon-striped-line">
else {
</div>
<div id="crayon-5b8f3d2c2df29914802382-11" class="crayon-line">
 ...
</div>
<div id="crayon-5b8f3d2c2df29914802382-12" class="crayon-line crayon-striped-line">
}
</div>
</div></td>
</tr>
</tbody>
</table>

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

图片 7

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

图片 8

其实「空列」放大于墙体上,也会有「空洞」类似的分布形态 ——
连续与非连续。
图片 9

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

图像通道分离与合并

还是以lena.jpg图像为例,实现图像通道分离合并的操作

from PIL import Image
import numpy as np
import scipy
import matplotlib.pyplot as plt

img = Image.open('len.jpg')
print(img.mode)
print(img.getpixel((0, 0)))
gray = img.convert("L")
r, g, b = img.split()  # 分离三通道
pic = Image.merge('RGB', (r, g, b))  # 合并三通道
plt.figure("beauty")
plt.subplot(2, 3, 1), plt.title('origin')
plt.imshow(img), plt.axis('off')
plt.subplot(2, 3, 2), plt.title('gray')
plt.imshow(gray, cmap='gray'), plt.axis('off')
plt.subplot(2, 3, 3), plt.title('merge')
plt.imshow(pic), plt.axis('off')
plt.subplot(2, 3, 4), plt.title('r')
plt.imshow(r, cmap='gray'), plt.axis('off')
plt.subplot(2, 3, 5), plt.title('g')
plt.imshow(g, cmap='gray'), plt.axis('off')
plt.subplot(2, 3, 6), plt.title('b')
plt.imshow(b, cmap='gray'), plt.axis('off')
plt.show()

结果如图所示 ![图片 10]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图