<<葵花宝典>>2000黄金版
翻译：SEVECOL
RLE Sprite指南 作者:Jonathan Griffiths(jpg@wave.co.nz)
介绍:
Sprite是游戏中最常用的一种元素,只在最近才被3D多边形引擎所超越.聪明的sprite系统将给游戏带来很大的帮助.这有一篇短文章介绍一个智能很高,且很有效率的RLESprite系统.
这里所讨论的sprite是指矩形的子位图,子位图中的一种任意的颜色可被定义成透明的.当渲染sprite到屏幕上的时候,被定义为透明色的象素并不绘出.sprite在场景的上面就产生了上面的效果.
RLE Sprite是一种使向屏幕绘图高效和节省内存的保存sprite的方法.下面 的讨论将说明如何实现基于RLE Sprite的引擎.*所有的代码都是用C写的.其中有一些用到了JLib(一个可移植的图形库.),它们能很容易的改到别的图形库.这些文档都是我用JLib和我对于RLE Sprite的经验编写的.你可以检查代码的完整性.剪贴下来可以编译.*JLib可以在下面找到:
你应该用不成比例的字体阅读文件中的图表,否则ASCII图表将会混乱.
简单的Sprite：
让我们从简单的sprite开始.最简单的sprite系统是用一个2维数组来储存 sprite中每
一个点的颜色.一个太空船的sprite看上去会是下面的样子:
XXXXXXXXXXXXXXXX
XXXXXXX XXXXXXX
XXXXXXX XXXXXXX
XXXXXX XXXXXX
XXXXX XXXXX 'X' = 颜色值0 (在本例中是黑的)
XXXX XXXX XXXX ' ' = 其他的颜色 (Say Green)
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 一个15X14 Cheesy太空船sprite.*
如果你用这太空船做sprite,你应当创建一个15X14的数组,并且按上面的图片颜色填充它,如下:
#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,
...
}
你可一用以下的代码来绘制sprite:
int x,y;
int xpos,ypos;
...
for (y = 0; y < SHIP_HEIGHT; y++ ) /*图形的每一行*/
for (x = 0; x < SHIP_HEIGHT; x++ ) /*这行上的每一个象素*/
if (ship_sprite[y*SHIP_HEIGHT+x] != 0) /*透明?*/
draw_point(xpos+x,ypos+y,ship_sprite[y*SHIP_HEIGHT+x]);
我们画了sprite中的每一象素,如果像素不透明,我们就画它.检查是不是0要快于其它值,所以我们把透明色设为0.
用着种方法可以画任意的sprite,还能检查点是否在屏幕中,但它很慢,不是个好方法.
第一个问题是你必须去检查每一个像素,看看它是否是透明色,不是便画它.
*让我们跳到理论的大陆一会儿,思考理论上画sprite的速度极限.我们选一个接近它的算法.
画sprite最快的方法是不检查任何一个像素,并且能正确的画在屏幕上,我们一个接一个的画需要画的像素,然后停止.你没有浪费时间在循环和比较上.有一种方法能象上面所说的一样,我们称它为编辑了的sprite.
编辑了的sprite实际上是程序,如下:
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);
...
}
*第二个问题是这方法是困难的和危险的.并且不能移植到所有的计算机上.
然而这方法给了我们对于怎么样才能更快的画出sprite在屏幕上很大的启示.我们应该想办法去排除检查象素,只画不透明的像素.
进入RLE Sprite
RLE是Run Length Encoding.是一种简单的压缩重复数据的方法.它提供了很好的压缩/解码时间比.
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来保存sprite,它可以很容易的实现忽略透明的像素,我们再也不要检查每一个像素在我们画它们之前.让我们看看如何实现RLE Sprite
首先,我们用RLE编码来保存sprite,然后:
我们的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序列对应sprite的每一行.(这能帮助我们用裁剪,下面会讨论)
我们可以通过下面的代码画出sprite的一行:
while 代码没结束得到下一个值
if 值 is blank
skip count pixels
else
draw count pixels
end
end
代码和RLE有所不同,第一个代码我用了两个字节:is_solid,length.如果is_solid是0,则是连续lenght个blank,否则是连续个颜色.我还有个更好的代码,它不用判断是否为blank.
新的代码用一个字节来存颜色的信息和重复的次数.低4位.第5位为非透明色是置1,其它的3位没用上(7,6,4),它最多能存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
为了更好的用RLE我们存的时候加入RLE代码的起点,最后这行代码输出为:
最后的RLE 3,6,37,5
第一个实现的步骤是从sprite数据中建立RLE数据.基本的算法:
for each line in the sprite
write a dummy value for the number of runs in this line
while there is data left
if data is solid
count until not solid, or no data, or run len > 16
else
count until solid, or no data, or run len > 16
end
put code and count
end
write the real value for the number of runs in this line
end
你应该设一指针指向每一行RLE数据的起点.这样你可以更好用裁剪.
ptr Pointer to RLE line pointers for each line
|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数据,画出它就可以用下面的代码:
for (y = 0; y < height_of_sprite ; y++){
Read the number of RLE codes in this line
while RLE codes remain
if bit 5 of the RLE code is set
draw (RLE code & 15) pixels to the screen
end
add (RLE code & 15) to "foo"
end
end
它看起来并不比上个版本快,是的.*
让我们假定我们可以直接用指针在屏幕上画点.假设256色的显示*
我们的RLE代码让我们可以不要检查是否是透明色如果我们用switch语句按下面的宏:
#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则什么都不做,否则画多个点在屏幕上(不用循环),这样就可以节省很多的时间.我们的sprite这样实现:
Setup a pointer "foo" to the X by Y array of data
for (y = 0; y < height_of_sprite ; y++){
Setup a pointer "bar" to the screen xpos,ypos+ line Y
Read the number of RLE codes in this line
while RLE codes remain
SPR_STENCIL_COPY(bar,foo,RLE code) { add (RLE code & 15) to "foo"
add (RLE code & 15) to "bar"
end
聪明的读者以经注意到我们可以省去每一行最后的blank,它们什么都不做,这样有能省不少:-)在JLib中你能画出sprite的背景,而我们现在的还不能.
好了,我们的sprite已经有很高的效率了.
一个问题有在我们眼前,如何裁剪?如何把sprite的一部分画在屏幕上?当sprite走出屏幕,我们应当如何画出sprite应该被看见的部分?
裁剪总是不能被排除的.看看下面的代码:
if ( (sprite_x + sprite_width < 0) /* Off LHS of screen */
| (sprite_x > SCREEN_WIDTH) /* Off RHS of screen */
| (sprite_y + sprite_height < 0) /* Off TOP of screen */
| (sprite_y > SCREEN_HEIGHT) ) /* Off BOTTOM of screen */
return; /* Don't draw it */
end
从上面的循环可看出Y方向的比X方向的简单一些.裁剪能公平的加入消耗给画出sprite.*
怎样决定sprite是否裁剪:
#define CLIPPED_X 0x1
#define CLIPPED_Y 0x2
int clipped=0;
if (sprite_y > + sprite_height > SCREEN_HEIGHT) /* Hits screen BOTTOM? */
clipped = CLIPPED_Y;
}
if (sprite_y < 0) /* Hits screen TOP? */
clipped = CLIPPED_Y;
}
if (sprite_x > + sprite_width > SCREEN_WIDTH) /* Hits screen RIGHT? */
clipped |= CLIPPED_X;
}
if (sprite_x < 0) /* Hits screen LEFT? */
clipped |= CLIPPED_X;
}
/* If not clipped, use a faster non-clipping function */
if (!clipped) {
draw_sprite_without_clipping(...);
return;
}
If a sprite is clipped only in the y direction, we can clip the sprite by
altering the outer Y loop:
if(!(clipped & CLIPPED_X)){
if (y < 0)
top_lines = -y;
else
top lines = 0;
Setup a pointer "foo" to the X by Y array of data + top_lines * data_width
if (bottom needs clipping){
max_y = SCREEN_HEIGHT;
else
max_y = height_of_sprite
for (y = 0; y < max_y ; y++){
Setup a pointer "bar" to the screen xpos,ypos+ line Y
Read the number of RLE codes in this line
while RLE codes remain
SPR_STENCIL_COPY(bar,foo,RLE code) { add (RLE code & 15) to "foo"
add (RLE code & 15) to "bar"
end
end
return;
}
Y方向的裁剪几乎和不裁剪一样,只是多了*有几种方法处理X方向的裁剪,最简单的在X裁剪是用原始的算法检查每一个像素.它是能够被改进的.
另一个方法不管是X方向还是Y方向的裁剪都要比上面的要快.如下:
如果左边被裁剪,我们要算出每一行有多少像素在屏幕的左边,可以略过这些点,画这一行下面的像素.
如果右边被裁剪,我们算出第几行在屏幕的边上,就可以画其他在屏幕上的线这要比原始的X方向的裁剪算法复杂不少.
width = width_of_sprite
if (x < 0) {
left = -x;
width+=x; /* decriment width */
}
else
left = 0;
Setup a pointer "foo" to the X by Y array of data + left
if (rhs needs clipping)
width+= SCREEN_WIDTH-rhs_xpos
for (y = 0; y < height_of_sprite ; y++){
Setup a pointer "bar" to the screen xpos,ypos+ line Y
while width--
if(sprite_data_array_value != 0)
*bar = sprite_data_array_value; /* draw the point */
bar++;
end
end
X和Y方向的裁剪只需把上面的两方面组合就行了.
你按上面的代码再结合JLib就能写出你的RLE Sprite引擎了．其中X方向的裁剪最重要．记住你的引擎要在sprite的下面留一些地方，这样可以移动*
/*+------------------------------------------------------------------------+
*/
/*|Draw a sprite in a buffer without clipping | */
/*+------------------------------------------------------------------------+
*/
void buff_draw_spriteNC(sprite_system * ssys, int snum, buffer_rec * obuff)
{
int frame = ssys->sprites[snum]->frame, x = ssys->sprites[snum]->x;
int y = ssys->sprites[snum]->y, bwidth = B_X_SIZE(obuff) -
ssys->sprite_data[frame]->width,
height = ssys->sprite_data[frame]->height;
UBYTE *pattern = ssys->sprite_data[frame]->pattern, *data =
ssys->sprite_data[frame]->data,
*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;
}
Sevecol翻译于1999.10.18
*表示翻译的不好,瞎翻译 ^-^
由于本人英语实在是不怎么样，本版本存在大量bug,心脏病和高血压患者请勿阅读:-)
