Руководство по RLE спрайтам.

Введение

Спрайты – до недавнего одни из самых употребляемых элементов при создании компьютерных игр, сейчас же их превзошли полигоны, поскольку началась мода на 3-d. Но даже и эти игры могут извлечь пользу от грамотного использования спрайтов. Итак, перед Вами небольшое руководство по разработке программ, основанных на таком методе.

Спрайты являются прямоугольными растрами, в которых один цвет обозначен как прозрачный. При выводе спрайтов на экран, пиксели “прозрачного” цвета не отображаются. Таким образом, получается эффект, будто бы изображение накладывается на уже имеющуюся картинку (или является позади неё в некоторых случаях).

RLE спрайты – наиболее эффективный способ хранения изображений, который использует меньшее количество памяти. В этой статье будет рассмотрено создании таких спрайтов вне зависимости от аппаратного обеспечения.

Приведённые исходные коды написаны на С и могут использовать функции из Jlib – мультиплатформенной графической библиотеки. Они должны легко адаптироваться и к иным библиотекам. Этот файл – результат моих попыток программирования с использованием спрайтов и Jlib.

Jlib можно скачать по адресу: ftp://x2ftp.oulu.fi/pub/msdos/programming/djgpp2/jlib_X-X.zip; где Х-Х – версия библиотеки (при написании статьи последней была 1.7)

Простейшие спрайты

Давайте начнём с простого примера. Легчайший путь к созданию систем, основанных на спрайтах лежит в использовании двухмерных массивов для хранения последних. Спрайт космического корабля вполне может выглядеть так:

XXXXXXXXXXXXXXXX

XXXXXXX XXXXXXX

XXXXXX XXXXXX

XXXXX XXXXX 'X' = Черный цвет

XXXX XXXX XXXX ' ' = Любой другой (зелёный, к примеру)

XXX XXXX XXX

XXX X X XXX

XXX XXXX XXX

XXX XXX

XX X X XX

X XX XX X

XXXXXXXXXXXXXXXX Спрайт размером 15 на 14.

Если Вы хотите использовать это судно как спрайт, следует создать массив 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,

...

}

Чтобы отобразить корабль, можно применить этот код:

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

То есть мы пробегаем в цикле по каждому пикселю в спрайте, и если пиксель имеет не прозрачный цвет – отображаем его. Так как, обычно, быстрее проверить является ли число равным нулю, чем отличным от него, то ноль часто используют для обозначения прозрачности.

Но не нужно быть даже проектантом космических аппаратов, чтобы сообразить, что вышеприведенных код неудобен. Даже если его идеально отладить – рисование по точкам всё равно остаётся сравнительно медленным способом.

Первая проблема – постоянная проверка пикселя на прозрачность. Это приводит к очень большому объему работ. И никакая оптимизация, даже на ассемблере, Вас не спасёт.

Обратимся к теории: представим на мгновение, каков предел скорости рисования спрайта? Затем мы сможем определить, как хорошо наши методы приближаются к этому ограничению.

Самый быстрый способ отображения спрайта – рисовать его без проверки на прозрачность. В этом случае Вы просто по порядку выводите все пиксели на экран без потерь времени на всякие дополнительные условия или сравнения. Есть метод, который позволяет достигнуть этого. Называется он компилируемыми спрайтами.

Компилируемые спрайты – фактически программы, вроде этой:

void draw_spaceship(int x, int y)

{

/* Эти команды отображают непрозрачные пиксели */

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,

с помощью RLE могут быть представлены как

(22 0's),(2 1's),(13 0's),(2 1's),(6 0's)

Тут следует сделать замечание: RLE хорошо работает лишь с данными, которые содержатся повторяющиеся куски. В противном случае, сжатый код получается большим по размеру из-за перегрузки комбинаций кодирования.

В дальнейшем будем предполагать, что данные наших спрайтов удовлетворяют этому требованию. А так же, что в наших данных нулевые значения, в большинстве своём, сгруппированы вместе. Поэтому они легко игнорируются, когда мы рисуем спрайт, что позволяет избегать проверки перед отображением каждого пикселя.

Давайте взглянем на реализацию RLE спрайтов.

Для начала мы сохраним наш спрайт следующим образом:

0,0,0,0,0,0,3,3,3,5,6,0,0,0,0,0

Наш код не будет содержать данных о цвете, а лишь о том, является ли пиксель прозрачным. Получим следующий код:

(пустой 6),(заполненный 5),(пустой 5)

Когда мы “расшифруем” эти RLE данные, мы получим фактические значения пикселей. Так же будем начинать каждую новую RLE последовательность для каждой строки спрайта (это поможет нам с отсечением, которое рассмотрим позже).

Приведенный выше код можно использовать в таком алгоритме:

пока не пришли к концу последовательности

получить следующий код

если код указывает на “пустой”

пропустить заданное число пикселей

иначе

отобразить заданное число пикселей

конец

Коды, используемые в различных реализациях RLE, сильно варьируются. Первый код, который я использовал, занимал 2 байта – пустой/цветной и длина. Если был установлен флаг “пустой”, мы пропускали нужное количество пикселей, иначе эти пиксели считаются окрашенными. Это неплохо работает, однако я придумал намного лучший алгоритм, который избавит нас от необходимости выполнять ветку цикла “если код “пустой”.

Новый код использует один байт для хранения информации о заполненности поля и его длины. Нижние 4 бита в байте содержат длину, в то время как бит 5 содержит флаг “заполненности”. Остальные 3 бита не используются. Максимальная длина участка кода – 16 пикселей, так что для более длинного участка нужно использовать несколько кодов. Причина использования этого алгоритма и его скоростные характеристики будут описаны позже. Пример:

Оригинальные данные 0,0,0,0,0,0,3,3,3,5,6,0,0,0,0,0

RLE (пустой 6),(заполненный 5),(пустой 5)

RLE реализация 6, 5 | 32, 5

Окончательные значения 6, 37, 5

Примечание: Операция "| 32" взводит пятый бит, то есть тот который указывает на заполненность.

С этого момента (для простоты использования) будем указывать ещё и число кодов в строке. Итак, конечный результат получим такой:

Окончательный RLE 3,6,37,5

Первым шагом будет построение RLE спрайта из спрайта оригинального. Вот простейший алгоритм:

Для каждой строки в спрайте

записать любое число как число кодов в этой в строке

пока есть данные слева

если данные заполненные

считать пока не встретятся не заполненные,

или не закончится строка, или длина участка

превысит 16

иначе

считать пока не встретятся заполненные,

или не закончится строка, или длина участка превысит 16

конец

поместите код и счет

конец

запишите действительное значение числа кодов в строке

конец

Так же нужно запомнить массив указателей, указывающих на начало каждой строки в RLE данных. Это нужно для простой работы с отсечениями (смотри ниже).

Можно использовать это:

Ptr Указатель на RLE строку

XXOXXX ptr--------------(Num Codes,Code,...

XXOOXX ptr--------------(Num Codes,Code,...

XOOOXX ptr--------------(Num Codes,Code,...

XXXXXX ptr--------------(Num Codes,Code,...

X на Y массив данных RLE коды для каждой строки

Встроенная библиотечная функция generate_RLE() в Jlib содержит код, выполняющий эту работу. Так что если у Вас есть RLE данные, созданные по вышеописанному алгоритму, рисование спрайта сводится к следующему: установите указатель “foo” на XY массив данных.

for (y = 0; y < height_of_sprite ; y++){

Чтение числа RLE кодов в этой в строке

Пока RLE коды не закончились

Если бит 5 RLE кода установлен

Рисуйте (RLE код & 15) пикселей на экране

Конец

Добавьте (RLE код & 15) к "foo"

Конец

Я знаю, о чём Вы думаете: “По скорости этот метод не сильно отличается от предыдущего варианта!”. В принципе, это так. Но скорость ещё можно увеличить, используя замечательное свойство выбранного нами 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 код. Если он меньше 16 (то есть бит 5 чист), ничего не выводим. В противном случае произойдёт ошибка и на экран будет выведено правильное число пикселей безо всяких итераций. Такой алгоритм избавляет нас от лишней работы. Итак, наш цикл, рисующий спрайт выглядит теперь так:

Установить указатель "foo" на XY массив данных

for (y = 0; y < height_of_sprite ; y++){

Установить указатель "bar" на координаты экрана xpos,ypos+ line Y

Прочесть число RLE кодов в текущей строке

пока в строке остаются RLE коды

SPR_STENCIL_COPY(bar,foo,RLE код) { \

добавить (RLE код & 15) к "foo"

добавить (RLE код & 15) к "bar"

конец

end

Внимательный читатель заметит, что в некоторых реализациях нет необходимости в последнем RLE коде каждой строки, если он пустой, так как он никогда не отображается. Поэтому Вы можете ещё больше оптимизировать алгоритм, не храня последний прозрачный RLE код. В JLib можно рисовать спрайты вместе с их фонами, поэтому там эта оптимизация не реализована.

Хорошо, теперь мы знаем достаточно для того, чтобы вывести RLE спрайт на экран. И наш метод намного более эффективен, нежели самый первоначальный. Особенно это заметно на больших спрайтах. По сути, этот метод близок по быстродействию к компилируемым спрайтам.

Часто возникающая проблема с RLE спрайтами – это их отсечение. Отсечение используется для того, чтобы показывать части спрайта, к примеру, это необходимо для тех спрайтов, которые должны “заезжать” за края экрана.

Для начала нужно хотя бы попробовать удаление, то есть избегать вывода спрайта на экран по возможности. Это может выглядеть так:

if ( (sprite_x + sprite_width < 0) /* Выход за левую границу спрайта */

| (sprite_x > SCREEN_WIDTH) /* За правую границу */

| (sprite_y + sprite_height < 0) /* За верх экрана */

| (sprite_y > SCREEN_HEIGHT) ) /* За низ экрана */

return; /* Не выводим спрайт */

Если Вы внимательно разберётесь в цикле, приведённом ранее, Вам должно стать понятно, что отсечение в направлении Y не будет особо сложным. Но вот отсечение по Х немного сложнее. Так как отсечение может создать дополнительные затраты на вычисления при отображении, хороший алгоритм должен определять, будет ли использоваться отсечение и использовать для него другую функцию, оптимизированную на отсечение.

Чтобы определить, отсекается ли спрайт:

#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" на XY массив данных + top_lines * data_width

if (низ нуждается в отсечении){

max_y = SCREEN_HEIGHT;

else

max_y = height_of_sprite

for (y = 0; y < max_y ; y++){

Установим указатель "bar" на экран xpos,ypos+ line Y

Узнаем число RLE кодов в строчке

while RLE коды остаются

SPR_STENCIL_COPY(bar,foo,RLE code) { \

add (RLE code & 15) to "foo"

add (RLE code & 15) to "bar"

end

return;

}

Отсечение по Y почти так же производительно, как и вывод спрайта, вообще без отсечения, за исключением небольшой работы, которую нужно выполнить перед циклом, чтобы ограничить Y границы.

Есть разные способы отсечения по Х. Самый простой (который я разберу здесь) должен использовать первоначальный алгоритм проверки каждой точки, когда мы рисуем отсекаемый по Х спрайт. Конечно, возможно улучшить его, поэтому я буду объяснять другой способ для тех, кто хочет испытать всё сам.

Этот другой метод будет более быстрым, чем тот, что я буду разбирать. Основан он на определении бока спрайта, который будет отсекаться (левый, правый или оба). Затем делаем следующее:

Если левая сторона отсекается прежде, чем мы рисуем строку, нам нужно отсчитывать RLE коды в строке до тех пор, пока мы не достигнем конца отсекаемой части. Затем отображаем оставшуюся часть как обычно.

Если отсекается правая сторона, мы должны проверять каждый код перед рисованием, чтобы определить, не пора ли отбросить остаток строки и перейти на новую.

Это несколько сложнее, чем простой метод, когда используется отсечение по Х. А выглядит алгоритм так:

width = width_of_sprite

if (x < 0) {

left = -x;

width+=x; /* уменьшаем ширину */

}

else

left = 0;

Устанавливаем указатель "foo" на XY массив данных + left

if (левая часть нуждается в отсечении)

width+= SCREEN_WIDTH-rhs_xpos

for (y = 0; y < height_of_sprite ; y++){

Устанавливаем указатель "bar" на экран xpos,ypos+ line Y

while width--

if(sprite_data_array_value != 0)

*bar = sprite_data_array_value; /* рисуем точку */

bar++;

end

Чтобы нарисовать спрайт с отсечениями и по Х и по Y, нужно объединить оба подхода вместе, то есть вышеприведённый алгоритм с отсечением по Y.

Приведённые выше алгоритмы должны достаточно помочь Вам в создании своего собственного движка. Так же желательно, чтобы Вы ознакомились с исходным кодом JLib.

Не забывайте, что для движка нужно уметь выводить анимированные спрайты, а так же сохранять и восстанавливать область под каждым спрайтом, чтобы перемещать их.

Если Вы обнаружите ошибки, захотите внести предложения или дополнения в этот документ, пишите мне...

Удачи и приятного программирования!

Для полной картины привожу функцию отображения спрайта без отсечения, взятую из JLib:

/*+------------------------------------------------------------------------+ */

/*|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;

}

Верстка и поддержка: Lennart Steinke