R·ex / Zeng


音游狗、安全狗、攻城狮、业余设计师、段子手、苦学日语的少年。

雪碧图的应用场景 & 一种生成算法

注意:本文发布于 2063 天前,文章中的一些内容可能已经过时。

CSS 雪碧图

相信上古时期搞过前端的同学都知道,可以通过合并一些小图片、使用 CSS 控制 background-position 的方式来减少 HTTP 请求次数,从而优化网页加载时间,这就是 CSS 雪碧图(Spritesmith)。不过自从 HTTP/2 出来之后,这个用途就已经没什么意义了。当然,它也可以避免当正常状态与 hover 状态使用不同的图片时,首次 Hover 要现场加载图片的问题,所以雪碧图还是有一些用武之地的。

CSS 雪碧图的优缺点以及其它资料网上太多,这儿就不写了。

其它种类的雪碧图

游戏开发中的瓷砖

除了 CSS 雪碧图以外,在游戏开发中也会用到“雪碧图”,只是这儿应该叫瓷砖(Tileset)。以十年前比较著名的 RPG Maker 系列为例,它自带的瓷砖是这样子的:

1

只需要在瓷砖栏选中瓷砖,就可以在地图编辑器中绘制了。

SVG Sprite

当然,还有一种不算雪碧图的东西,叫 SVG Sprite。SVG 中有两个标签:<symbol><use>,前者可以定义各种图形(不显示出来),后者可以调用并显示已经定义好的图形。好处是可以避免重复编写相同的部分。值得注意的是,<use> 可以跨 SVG 调用,只要 ID 正确即可,

具体的用法可以看 这篇博客。现在有一些图标库也已经抛弃了字体图标,转而使用 SVG Sprite,因为 SVG 比字体编辑起来简单很多,也可以只将使用的 SVG 打包成一个 Sprite,打包还特别方便,大概只需要这样的思路:

function pack(usedFiles) {
    const symbols = usedFiles.map(file => `
        <symbol
            viewBox="0 0 ${file.width} ${file.height}"
            id="${file.iconName}"
        >
            ${file.content}
        </symbol>
    `).join('');
    return `<svg xmlns="http://www.w3.org/2000/svg">${symbols}</svg>`;
}

常用的生成工具

SVG Sprite 的生成方法上面已经写了,因此这里只讨论 CSS 雪碧图与瓷砖两种情况。为了节省资源,我们需要让生成的雪碧图尽可能小。这里要考虑的不是文件字节数的大小,因为这跟图片的压缩算法有关,无法泛泛而谈(例如网页中 WebP 格式一般会更小一些,但有些地方不支持 WebP),以及图片在解压之后,实际在内存中还是要占用压缩前的体积(接近 BMP 格式的体积),因此我们需要考虑如何让最终图片的尺寸最小。

手工拼接是最古老的办法,使用目测大法,手动修改图片以及 CSS(或游戏代码)中的坐标,缺点太多所以不吐槽了。

随着技术的发展(以及人们吐槽的声音越来越大),在前端领域,诞生了一些专门用来做雪碧图以及帮忙修改 CSS 代码的工具,例如 spritesmithgulp.spritesmithwebpack-spritesmith 等,名字长得很像(其实就是同一个东西针对不同打包工具的版本),使用方法也很简单,只需要在打包工具的配置文件中添加几行代码即可。

在游戏开发领域,则有 TexturePacker 这种强大的工具,支持多种图片类型,可以输出 Unity、Cocos2D、Starling 等平台支持的瓷砖及 JSON 文件;它使用的打包方法有两种,基础算法是将所有的图块放到一行,除非大于了指定的最大宽度;高级打包算法可以智能组合不同的图块,甚至在平台支持旋转的时候会尝试旋转一部分图块以获得更高的空间利用率!然而高级的打包算法是收费的……

一种可行的生成算法

这个问题可以被规约到 Bin Packing Problem,但后者是个 NP Complete 问题,因此不考虑完美算法,只考虑近似算法。由于遗传算法等通用的近似算法没有什么需要特别讲的,只要套用模型即可,因此也不写了。我比较喜欢的是一种专门针对此问题的算法,英文原文在 这儿

首先我们考虑一块足够大的画布,把一个图块放到最左上角,这个画布就被分成了三部分:图块占用部分、图块的正右方与图块等高的那个部分、整块画布的下半部分,即下图中的三个红框内部。

2

这相当于一棵二叉树,一个节点代表一块足够大的画布,如果它被图块覆盖了左上角,则可能有一个左孩子,也可能有一个右孩子,当然也可能都有或都没有,取决于图块的大小。左孩子表示将画布下面的区域当作一块新画布,右孩子表示将图块正右方的部分当作一块新画布。

我们按某种顺序依次取每一个图块。当拿到一个图块时,先序遍历枚举树的每个叶子结点,如果节点没被占,且节点对应的画布可以容纳这个图块,就将图块放到画布左上角,然后将画布分裂为三块(就是为该节点添加孩子节点),以此类推。

这里的“某种顺序”可以有很多选择,例如宽度从长到短、最大边长从长到短、面积从大到小等等,可以分别按照多种顺序跑一遍算法,得到一个画布占用率最高的答案。

先序遍历其实是一种贪心,反映在图像上,就是我们每次从左到右、从上到下寻找一个可以放置的空隙,然后将图块放上去。

然而有个问题:一开始的画布有多大?并没有一个很好的方法可以让我们猜出合理的画布初始大小。例如如果用

[math]\left \{ \begin{matrix} w = average(width) \cdot \sqrt{n} \\ h = average(height) \cdot \sqrt{n} \end{matrix} \right.[/math]

来设置宽高,很容易就被一个特别长或者特别高的图块 break 掉。于是我们可以考虑不使用固定宽高的画布,而是让画布一开始恰好只能容纳第一个图块,在之后的过程中,如果无法往画布中继续放置元素,则考虑将新元素放到画布的右边或下边,同时扩展画布,在扩展的时候选择让画布更接近正方形的方案。如下图所示,红框是使用该方案扩展画布之后多出来的未被占用的部分。

3

4

5

需要注意一个细节:扩展整个画布的时候,首先先在树中合适的位置添加一块空白的画布节点,然后将图块放置进去,还需要遍历所有的叶子节点,将其中的一些节点对应的画布尺寸进行修改。

具体的代码在原文中有,原文甚至还给出了一个 Demo,可以让我们直观的看到算法的运行结果以及最终画布的占用比例。

6

算法的优化

其实这个算法还有一个常数优化。由于我们每次只关心叶子节点,因此可以将先序遍历到的叶子节点依次通过单链表连接起来,这样就无需再次先序遍历了,直接遍历链表即可。

更进一步,我们可以直接抛弃树结构而完全改用链表,这样就可以将遍历非叶子节点的时间砍掉,而且维护链表跟维护树结构修改的指针数量几乎相同。方法如下:

一开始链表中只有一个元素(第一个图块);当需要给节点添加孩子节点的时候,直接用孩子节点(先左后右,可能缺失一个孩子甚至两个孩子)替换掉该节点即可。如果要扩展画布,往下方扩展的时候将画布节点插入到链表合适位置,往右方扩展的时候直接将其插入到链表末尾即可。

除去遍历以外,时间复杂度都是 O(1)。当树的深度比较深的时候,这个优化可以大大减少程序的运行时间。


参考资料

Disqus 加载中……如未能加载,请将 disqus.com 和 disquscdn.com 加入白名单。

这是我们共同度过的

第 3040 天