序言
精灵是电脑游戏中使用的最普通的元素之一,直到最近由于3-D浪潮蜂拥而至才被“多边形”所取代。然而,即使3-D游戏也能因设计完美的精灵而得益。这篇文章就是一个关于实现一个高水平的,高效的RLE精灵系统的简短教程。 这里提到的精灵特指矩形位图,这种位图数据中的某种颜色被定义为透明的。当往屏幕上画精灵时,用透明色描述的像素就不画上去。这样造成的效果就是精灵在所描绘的场景的“上面”(有时在“后面”)。 RLE 精灵R是一种使向屏幕绘图高效和节省内存的保存sprite的方法。下面的讨论解释了如何不依赖硬件而完整地实现一个基于RLE的精灵系统。 这里所有的原代码、伪代码都用C语言表示,而且许多用到了JLib(一个小型的图形库)的调用。它们可以很容易地适合其他的图形库。这篇文章的结果来自与我用JLib完成的精灵部分的经验,由于JLib提供了所有的原代码,你可以把这里的精灵代码看作作了适当取舍的一个RLE精灵系统的例子。
jlib 可以在以下地址找到: ftp://x2ftp.oulu.fi/pub/msdos/programming/djgpp2/jlib_X-X.zip; 这里的 X-X 表示JLib的版本号(我写这篇文章时已是1.7 版)。
简单精灵
让我们从构造一个简单精灵开始。构造一个精灵系统的最简单的方法是用包含了精灵颜色信息的2维数组来存放精灵数据。一个太空船精灵看起来就象这样:
XXXXXXXXXXXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXX XXXXXX XXXXX XXXXX XXXX XXXX XXXX XXX XXXX XXX XXX X X XXX XXX X X XXX XXX XXXX XXX XXX XXX XX X X XX X XX XX X XXXXXXXXXXXXXXXX 这就是一个15*14 的太空船精灵(X表示黑颜色,空格代表其他颜色)。
如果你要把此太空船用作一个精灵,你得创建一个15*14的数组,并用上述的颜色来填满它。如下所示:
#define SHIP_WIDTH 15 #define SHIP_HEIGHT 14
unsigned char ship_sprite[SHIP_WIDTH*SHIP_HEIGHT] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, ... }
然后你就可以用下面的伪代码来画这艘船: int x,y; int xpos,ypos;
...
for (y = 0; y < SHIP_HEIGHT; y++ ) /* 船的每一行 */ for (x = 0; x < SHIP_WIDTH; x++ ) /* 行中的每个像素 */ if (ship_sprite[y*SHIP_HEIGHT+x] != 0) /* 透明否? */ draw_point(xpos+x,ypos+y,ship_sprite[y*SHIP_HEIGHT+x]);
也就是我们循环处理精灵的每个像素,如果此像素的颜色是不透明的,就画上去。因为检查一个值是否为0比判断其是否为一个特定的非零值要快,所以0经常被用来作为透明色。 但是即使这个方法能不错地完成任务——能画出任意形状的精灵,可以做到不往屏幕外画点,它仍然是一个慢速且糟糕的画精灵的方法。 这个方法的第一个问题是:对每一个你要画的点,你都得去判断它是否透明,如果是就不去画它。这就意味着你要在这里花大量的精力,而这可以通过采用一些好的方法来避免。如果开始的时候采用了一个坏的算法,那么任何一种优秀的语言都帮不了你。 让我们先从理论出发,考虑一下画一个精灵可以多快的理论极限。然后我们可以根据我们所采用的方法得到的结果与此极限的接近程度来判断方法的优劣。 如果我们在画精灵时根本不用去判断任一像素是否透明,那么这种方法是最快的。在这种情况下,我们只需简单地把要画的像素一个接一个地画上去直到停止。你不需为循环和比较作出开销。有一种方法可以允许你做到这一点,称为“编译好的精灵”。 “编译好的精灵”实际上是一段往屏幕上画精灵的程序,就象这样:
void draw_spaceship(int x, int y) { /* these commands draw the sprites solid pixels */ draw_point(x+20,y+20,1); draw_point(x+21,y+20,2); draw_point(x+22,y+20,2); draw_point(x+23,y+20,1); ... }
通常,在运行时程序被调用,精灵数据就会被编译好画上屏幕。把组合语言装入到一块内存区域并跳到你想要画精灵的地方是一件麻烦而危险的事。用这种方法有两个主要的毛病:这样做很困难而且易出错;对于不同的机器丝毫无可移植性。 然而,这个方法给了我们一些如何提高画精灵的速度的线索。我们可以避免对像素的判断而仍然只画那些不透明的像素。
进入 RLE 精灵教程
RLE 是 Run Length Encoding(行程长度编码)的缩写,是一个针对包含有顺序排列的多次重复的数据的压缩方案。RLE在别的压缩算法(象 LZW, LHA等)作用以前对数据的压缩是有很好的效果的,可以有更大的压缩率。 RLE的原理就是用一个很短的编码来替换一串重复的数据。为得到原始数据,只要把这个编码展开。例如,下面的精灵数据:
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,1,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,
可以通过RLE算法压缩为类似于下面的编码:
(22 0's),(2 1's),(13 0's),(2 1's),(6 0's)
要注意的是,RLE 工作的好坏与其要压缩的数据有关。如果数据没有有序的重复,RLE经常会因为要加入重复的码的开销反而使压缩结果变大。 如果认定了我们的精灵数据是符合RLE的格式的,我们需要的只是一个存储重复码的简洁的方法,而且我们只需要处理很小数量的精灵数据就可以了。更令人兴奋的是,我们让那些需要一个个单独测试的零值集合起来了。这让我们在画精灵时忽略它们变得很简单,而且这允许我们在画像素以前不用逐一去检测它们。
让我们看一个RLE精灵的实现。 首先,我们把精灵的 RLE编码存为下面的样子: 我们的 RLE码不包含任何数据,只包含序列的长度和一个序列是否为实体数据的信息。序列:0,0,0,0,0,0,3,3,3,5,6,0,0,0,0,0 相应的码为:(blank 6),(solid 5),(blank 5) 当我们解释RLE数据时,便从原始数据里得到了真实的像素值。我们将为精灵的每一行开始一个新的RLE序列(这样做有助于裁剪操作,将在后面讨论)。 按照上面的编码,画精灵的一行就象这样:
while( 还有码) { 取下一个码 if (此码为“空”) 跳过几个像素 else 画上几个像素 }
不同的RLE实现方法使用的代码有很大差别。最早我使用的代码用两字节: is_solid ,length。 如果 "is_solid" 为0,这个序列就是 "length" 个空格,否则,就是 "length"个颜色。这个方法挺好,可是我提出了一个更好的,可以省去上述代码中内循环的“if 此码为“空””的判断。 新的编码方式使用一字节表示实体数据信息和序列长度。低4位表示序列的长度,如序列是实体数据则第5位被置1。另外3位则不用。一个序列的最大长度是16个像素,所以为存放更长的序列就需要用两个或更多的编码。后面将解释为何采用这个方案以及它如何带来速度的提升。 原始数据: 0,0,0,0,0,0,3,3,3,5,6,0,0,0,0,0 RLE (blank 6),(solid 5),(blank 5) RLE 实现过程 6, 5 | 32, 5 真正的 RLE 数字: 6, 37, 5
“|”表示逻辑“与”,和32“与”即把第5位置1。 因为还要存储RLE码的个数,所以最终的编码如下所示: 3,6,37,5 第一步需要根据精灵数据建立起RLE编码,基本算法如下:
/***********************************************************************/ /* 王老道怀疑这里是否有错,结合下文分析(参见下面的宏),第5位置1 */ /* 应“与”上16,最终的编码是否应为: 3,6,21,5 */ /***********************************************************************/
for (精灵的每一行) { 对此行的序列个数写一假定值 while( 还有数据) { if (是实体数据) 记数,直到遇到非实体数据,或没有数据了,或序列的长度 > 16 else 记数,直到遇到实体数据,或没有数据了,或序列的长度 > 16 记下一个编码并记编码个数 写入此行的真实的序列个数 }
/**************************************************************************/ /* 这里王老道不懂,颜色值到哪儿去了呢? */ /**************************************************************************/
你还需创建一系列的指针指向每行RLE码的开始处。这在处理裁剪时有用(稍后介绍)。
XXOXXX ptr-------------->(Num Codes,Code,... XXOOXX ptr-------------->(Num Codes,Code,... XOOOXX ptr-------------->(Num Codes,Code,... XOOOXX ptr-------------->(Num Codes,Code,... XOOOXX ptr-------------->(Num Codes,Code,... XOOOXX ptr-------------->(Num Codes,Code,... XXXXXX ptr-------------->(Num Codes,Code,...
X by Y Array of data RLE codes for each line
JLib中的内部库函数 generate_RLE()就做这件事。一旦你创建了如上的RLE数据,画一个精灵就如下所示:
定义指针“foo”指向X*Y数组 for (y = 0; y < height_of_sprite ; y++) { 读入这一行的RLE码个数 while (还有RLE码) if 当前的RLE码的第5位被置1 往屏幕上画 (RLE 码 & 0x0f)个像素 end “foo”加上(RLE 码 & 0x0f) }
你一定在想:“这看上去并不比刚才的版本快多少!”事实上,的确如此,但是它能在使用我们所选择的RLE编码方法的一个很“酷”的特性时取得高速度。 让我们假定可以通过一个指针以直接写屏方式往屏幕上作画。这个例子中的颜色是8位,然而稍作改动就可以用于任意色深。 因为显示只用8位,所以屏幕指针为一个字节,就这样来画一个点。 我们的 RLE 编码允许我们不用对透明与否进行检查,而且在使用了如下的宏(来自JLib)时可以重复地画点:
#define SPR_STENCIL_COPY(d,s,l) { switch(l){ case 31: d[14] = s[14]; case 30: d[13] = s[13]; ... case 17: d[0] = s[0]; } }
这里, "l" 就是 RLE 码。如果l小于16(也就是第5位是0),什么也不画,否则就画相应的正确数目的像素而无需循环。这样就节省了大量的开销。我们的画精灵的循环就变成这样:
/**************************************************************************/ /* 王老道还是不懂,这样为什么可以省掉循环?执行一次宏,只画了一个点呀!? */ /**************************************************************************/
设定指针“foo”指向X*Y数组 for (y = 0; y < height_of_sprite ; y++) { 设定指针"bar" 指向屏幕上每一行的开始处的地址 读入此行的RLE编码个数 while 还有RLE编码 SPR_STENCIL_COPY(bar,foo,当前RLE码)
“foo”加上(当前RLE码 & 0x0f) “bar”加上(当前RLE码 & 0x0f) end }
/**************************************************************************/ /* 惭愧,王老道太笨了,不懂的地方还有,照我的理解,那个X*Y数组中放的 */ /* 就是精灵的颜色值了,如果用RLE 存储了,这个数组怎么来的呢? */ /**************************************************************************/
聪明的读者会注意到,在某些时候如果一行的最后一个RLE码为“空”,那就不需要这个码了,因为它并不需要画像素,这样你就可以省很多事。在 JLib 里画精灵是连着它们的背景的,所以并没有做这步优化。 OK,用此方法在屏幕上画RLE精灵我们已经知道得足够多了,而且比上面提到的最初方法效率好得多,尤其是对大精灵。事实上,这种方法相当接近于“编译好的精灵”。 RLE精灵经常会遇到的一个问题是如何对其进行裁剪操作。所谓裁剪就是只画精灵在屏幕内的部分,所以精灵可以跑出屏幕而只显示可以看到的部分。 裁剪测试的第一步总是检测是否可以一点都不用画。这个测试可以是这样:
if ( (sprite_x + sprite_width < 0) /* 在屏幕左边线以左 */ | (sprite_x > SCREEN_WIDTH) /* 在屏幕右边线以右 */ | (sprite_y + sprite_height < 0) /* 在屏幕上边线以上 */ | (sprite_y > SCREEN_HEIGHT) ) /* 在屏幕底线以下 */ return; /* 不用画 */
你很容易就能看出,在Y方向上的裁剪测试不太困难,而在X方向上的测试要复杂一些。因为裁剪总要对精灵动画占去一些开销,所以一个好的方法是先计算出一个精灵是否要被裁剪,如果不需要,就使用另外的没有裁剪的代码的优化的函数。
判断精灵是否被裁剪:
#define CLIPPED_X 0x1 #define CLIPPED_Y 0x2
int clipped=0;
if (sprite_y + sprite_height > SCREEN_HEIGHT) /* 碰到底线了吗?*/ clipped = CLIPPED_Y; if (sprite_y < 0) /* 碰到顶线了吗?*/ clipped = CLIPPED_Y;
if (sprite_x + sprite_width > SCREEN_WIDTH) /* 碰到右边线了吗?*/ clipped |= CLIPPED_X;
if (sprite_x < 0) /* 碰到左边线了吗?*/ clipped |= CLIPPED_X;
/* 如果不用裁剪,使用一个快速的、没有裁剪代码的函数*/ if (!clipped) { draw_sprite_without_clipping(...); return; }
如果一个精灵只需在y方向进行裁剪,你可以通过改变外层的Y循环来对精灵裁剪。
if(!(clipped & CLIPPED_X)) { if (y < 0) top_lines = -y; else top lines = 0;
foo= X*Y数据矩阵的地址 + top_lines * data_width
if (需要裁剪底部){ max_y = SCREEN_HEIGHT; else max_y = height_of_sprite;
for (y = 0; y < max_y ; y++) { 设定指针"bar" 指向屏幕上每一行的开始处的地址 读入此行的RLE编码个数 while 还有RLE编码 { SPR_STENCIL_COPY(bar,foo,当前RLE码) “foo”加上(当前RLE码 & 0x0f) “bar”加上(当前RLE码 & 0x0f) } } return; }
只在Y方向上裁剪几乎与没有裁剪同样高效,只是需要在循环外先定好Y的上下限。 处理X方向的裁剪有好几种办法,最简单的是我们最初的算法,当精灵需要X裁剪时,逐点进行检测。它当然能够被改进,所以我将为希望作改进工作的人解释另一种方法。 这个方法得依赖于对精灵的左边还是右边(或两者都是)需要裁剪的判断,步骤如下: 如果左边要裁剪,在我们画线之前我们要算出每一行有多少像素在屏幕的左边,可以略过这些点,画余下的像素。如果右边要被裁剪,我们必需在画每一个码前检测它是否超出了右边线,如是则从此不画而直接转入下一行。 这比使用基本算法的简单方法显然要复杂得多,程序如下:
width = width_of_sprite
if (x < 0) { left = -x; width+=x; } else left = 0;
foo = X *Y 数组的地址 + left
if (需要裁剪右边) width+= SCREEN_WIDTH-rhs_xpos; /* RHS——屏幕右边线*/
for (y = 0; y < height_of_sprite ; y++) { 设定指针"bar" 指向屏幕上每一行的开始处的地址
while(width--) { if(sprite_data_array_value != 0) *bar = sprite_data_array_value; /* 画点 */ bar++; } }
如果X、Y方向都要裁剪就把此两者结合起来就可。 上面的伪代码已作了足够的提示,你可以写出自己的精灵引擎了。记住,作为一个正确的精灵引擎,你还应该 ,以便移动和作精灵动画。 Remember that for a proper sprite engine you should save the area under each sprite and restore it again, plus be able to move and animate them....
/*************************************************************************/ /* 这一句不清楚,不过好象无关大局 */ /*************************************************************************/
结束以前,让我们看一个JLib中的无裁剪精灵绘画函数:
/*---------------------------------------------------------------------- */ /* 在缓冲中画一个不用裁剪的精灵 */ /*-----------------------------------------------------------------------*/ void buff_draw_spriteNC(sprite_system * ssys, int snum, buffer_rec * obuff) { int frame = ssys->sprites[snum]->frame; int x = ssys->sprites[snum]->x; int y = ssys->sprites[snum]->y; int bwidth = B_X_SIZE(obuff) - ssys->sprite_data[frame]->width;
height = ssys->sprite_data[frame]->height; UBYTE *pattern = ssys->sprite_data[frame]->pattern; UBYTE *data = ssys->sprite_data[frame]->data; UBYTE *out = B_OFFSET(obuff, y) + x;
JLIB_ENTER("buff_draw_spriteNC");
while (height--) { int width = *pattern++; while (width--) { UBYTE datum = *pattern++; SPR_STENCIL_COPY(out, data, datum); out += (datum & 15); data += (datum & 15); } out += bwidth; } JLIB_LEAVE; }
|