Листинг 7.1. Дизассемблирование оператора IF

; File if.с; # include <stdio.h>

;

; char far *source, *dest; //области исходных

//и результирующих данных

; main()

;{

; Line 8

_main:

*** 000000 c8 00 00 00 enter OFFSET L00181,OFFSET 0

*** 000004 56 push si

*** 000005 57 push di; index = fffc; data = fffa

;

;int index;

; Line 10

; unsigned data;

; Line 11

; // оператор if

; if (data=source[index]); Line 15

*** 000006 8b 46 fc mov ax, WORD PTR -4[bp]

*** 000009 8b 1e 00 00 mov bx,WORD PTR source

*** OOOOOd 8b 0e 02 00 mov ex,WORD PTR source+2

*** 000011 03 d8 add bx,ax

*** 000013 8e cl mov es,cx

*** 000015 26 8a 07 mov al,BYTE PTR es:[bx]

Cbw

Fa mov WORD PTR -6[bp],ax

LC 3d 00 00 cmp ax,OFFSET 0

Lf 75 03 e9 00 00 je L00180

; dest[index]=data;

; Line 16

*** 000024 8b 46 fa mov ax,WORD PTR -6[bp]

*** 000027 8b 4e fc mov ex,WORD PTR -4[bp]

*** 00002a 8b Ie 00 00 mov bx,WORD PTR _dest

*** 00002e 03 d9 add bx,cx

*** 000030 88 07 mov BYTE PTR [bx],al;

} // end main

; Line 18

L00180;

; Line 18

L00177:

*** 000032 5f pop di

*** 000033 5e pop si

*** 000034 c9 leave

*** 000035 cb

ret OFFSET 0 Local Size: 6; Line 0

Листинг 7.2. Дизассембдирование логической операции OR.

; File or.с

; #include <stdio.h>;

; char far *source, *dest; // области исходных

// и результирующих данных

;

; main()

; {

; Line 8

_main:

*** 000000 c8 00 00 00 enter OFFSET L00180,OFFSET 0

*** 000004 56 push si

*** 000005 57 push di; index = fffc;data = fffa

;int index;

;Line 10;unsigned data;

;Line 11

// логический оператор (OR)

dest[index]=data | source[index];

; Line 15

*** 000006 8b 46 fc mov ax,WORD PTR -4 [bp]

*** 000009 8b Ie 00 00 mov bx,WORD PTR _source

*** 00000d 8b 0e 02 00 mov ex,WORD PTR _source+2

*** 000011 03 d8 add bx,ax

*** 000013 8e c1 mov es,cx

*** 000015 26 8a 07 mov al,BYTE PTR es:[bx]

Cbw

*** 000019 0b 46 fa or ax,WORD PTR -6[bp]

*** OOOOlc 8b 4e fc mov ax,WORD PTR -4[bp}

*** OOOOlf 8b Ie 00 00 mov bx,WORD PTR _dest

*** 000023 03 d9 add bx,cx

*** 000025 88 07 mov BYTE PTR [bx], al

*** 000027 8b 4e fc mov ex,WORD PTR -4[bp]

*** 00002a 8b Ie 00 00 mov bx,WORD PTR _dest

*** 00002e 03 d9 add bx,cx

*** 000030 88 07 mov BYTE PTR [bx],al

;

; } // end main

; Line 17

; Line 17

L00177:

*** 000032 5f pop di

*** 000033 5e pop si

*** 000034 c9 leave

*** 000035 cb ret OFFSET 0 Local Size: 6

; Line 0

Если вы внимательно посмотрите на Листинги 7.1 и 7.2, то увидите, что в каждой программе я выделил некую область. Именно эти куски и определяют принципиальное различие приведенных программ. Мы видим, что код, в котором используется логическая операция OR, почти в два раза короче кода с оператором IF. Однако, мы должны прикинуть и время выполнения обоих фрагментов. Это довольно сложно, так как мы не знаем, какой процессор будет использован: 386, 486 или 586. Тем не менее, мы можем приблизительно подсчитать, что код, содержащий операцию OR, будет выполняться почти в два раза быстрее, чем код, в котором используется IF. Однако если нагородить несколько операторов OR, можно легко потерять эффективность этого приема. Поэтому имеет смысл заменять оператор IF только одной, максимум двумя логическими операциями. Следовательно, мы должны найти возможность получения требуемого результата с применением единственной логической операции.

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

Попробуем создать цветовую модель для того, чтобы проиллюстрировать это. Пусть в нашей игре фон имеет 16 цветов с индексами 0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 200 и 224. Изображение объекта (или спрайт) также содержит 16 цветов, только индексироваться они будут от 0 до 15. Следовательно, когда к исходному и результирующему пикселю применяется логическая операция OR, четыре младших бита результата всегда будут определять цвет фона, в то время как старшая тетрада задаст цвет объекта.

Предположим, мы последовательно скопируем первые 16 значений в таблицу выбора цветов и создадим таким образом несколько банков, содержащих по 16 тонов с одинаковыми значениями RGB, как это показано на рисунке 7.1.

В таком случае банк 0 будет иметь диапазон от 0 до 15, банк 1 — от 16 до 31 и т. д. Каждый банк будет содержать одинаковые значения RGB, поэтому, когда данные фона примут нулевое значение, цвет объекта не изменится. Точнее:

0 OR (0-16) = (0-16)

Однако интереснее, когда исходные данные принимают ненулевое значение. Предположим, что они имеют значение 5 (или цвет 6, с точки зрения исходного изображения), в то время как данные фона равны 32 (или цвет 2). Применив К этим значениям логическую операцию OR, мы получим число 37. Это соответствует пятому цвету в третьем банке. Цвет 37 имеет такое же значение RGB, как цвет 6 или индекс 5, так как в каждый банк мы копировали по 16 цветов. (Не пытайтесь уменьшать количество цветов в игре, их и так всего 16! Но в то же время важно постараться с умом использовать таблицу выбора цвета, чтобы по возможности ускорить процесс бит-блиттинга).

Скорее всего, мы не захотим использовать эту модель в чистом виде. Однако она дала нам в руки новый инструмент и идею, которую мы сможем использовать где-нибудь еще.

Кодирование прозрачности

Как я уже говорил в предыдущей главе, скорость бит-блиттинга можно увеличить, если использовать другие структуры данных. Наша основная проблема в отображении прямоугольных спрайтов заключается в реализации «прозрачности»: когда «прозрачный» пиксель (обычно 0, или черный) встречается в исходном изображении, пиксель фонового изображения остается неизменным (то есть не замещается). Эта операция выполняется с помощью оператора IF, и поэтому на нее тратится достаточно много времени.

Еще одно возможное решение данной проблемы заключается в применении к данным спрайта группового кодирования (run-lenght encoded, RLE), после которого последовательности «прозрачных» пикселей оказываются сгруппированными, как показано на рисунке 7.2.

Если мы разобьем наш отображаемый объект на столбцы или строки, то сможем проанализировать последовательности «прозрачных» пикселей и пометить их соответствующим образом. В этом случае мы могли бы включать и выключать «прозрачность» подобно тому, как с помощью переключателя зажигаем и гасим лампочку. Это происходит в несколько десятков раз быстрее, чем если бы мы тысячи раз повторяли оператор IF. Как осуществить групповое кодирование — решать вам, однако, в качестве отправной точки я предлагаю следующее:

§ Убедитесь, что данные спрайта записаны в формате:

столбец 1, столбец 2,..., столбец N

где каждый из столбцов состоит из «прозрачных» и «непрозрачных» пикселей;

§ Чтобы обозначить каждый из типов пикселей, задайте флаг, например, 255 и 254;

§ Следующий за флагом элемент данных должен определять длину последовательиости в байтах;

§ Затем перечислите значения пикселей выделенной последовательности.

Декодировать столбец данных можно будет по такому алгоритму:

ЕСЛИ

255: непрозрачный

254: прозрачный

тогда

(255 | 254), количество байт данных, данные

Этот шаблон будет повторяться много раз. Например, первый столбец на рисунке 7.2 будет кодироваться так:

254, 7, 0, 0, 0, 0, 0, 0, 0, 255, 2, 50, 50, 254, 1, 0

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

Затем можно провести дополнительную оптимизацию. Мы знаем, что «прозрачным» пикселям соответствуют нулевые значения данных (или любой другой индекс цвета, представляющий «прозрачность»), так зачем тратить место на избыточные нули 8 группах данных спрайта? Мы их можем отбросить. Новый формат будет содержать «непрозрачные» данные, флаги и значения длин последовательностей. В этой схеме возникает лишь одна небольшая проблема: мы не сможем использовать числа 254 и 255 как индекс цвета, поскольку эти значения уже использованы в качестве флагов контроля. (Однако я не думаю, что отсутствие двух цветов из 256 смертельно, не так ли?)

Опять-таки, это только идея, как ускорить процесс блиттинга. Вы можете использовать какой-то другой метод кодирования. Например, можно разбивать изображение не на столбцы, а на строки, но в этом случае могут возникнуть сложности при попытке наложения мира бликов на мир объекта. (О причинах этого вы можете прочесть в шестой главе, «Третье измерение».) Как бы там ни было, ваша копилка пополнилась еще одним секретом. Конечно же, вам понадобится написать дополнительную функцию преобразования стандартного битового изображения таким образом, чтобы ваша функция Draw_Sprite () смогла его обработать.

В этом разделе мы обсудили несколько идей улучшения бит-блиттинга и перемещения спрайтов. Я еще раз хотел бы подчеркнуть, что все сказанное — это только идеи. Я просто попытался продемонстрировать вам новый взгляд на данную проблему. Теперь вы знаете несколько путей ускорения процесса бит-блиттинга, но, по мере того как вы будете набираться опыта и знаний, у вас будут появляться все новые и новые пути. (Я знаю в 20 раз более быстрый способ осуществления бит-блиттинга, чем тот который мы здесь обсуждали, однако он применяется только в специальных случаях и основан на таком алгоритме оптимизации, что я потратил кучу времени, чтобы разобраться с ним — но все же я его победил!) Таким образом, существует далеко не один вариант ускорения блиттинга. И для того чтобы достигнуть уровня игр типа Wolfenstein или DOOM, вы должны быть очень искусны и изобретательны в программировании

Битовое отсечение

Битовое отсечение означает вырезание растрового изображения краями экрана или другими границами. Мы не будет обсуждать здесь общие проблемы отсечения. Нас интересует только прямоугольный или оконный тип отсечения. Даже в играх наподобие Wolfenstein или DOOM используется только прямоугольное отсечение границами экрана или прямоугольниками, находящимися внутри экранной области. На рисунке 7.3 показан пример отсечения растрового изображения.

Каким же образом осуществляется отсечение прямоугольного изображения? И, прежде всего, нужно ли оно нам вообще? На этот вопрос можно ответить и «да» и «нет». Если во время игры изображения ваших объектов и персонажей никогда не выходят за границы экрана, то применять отсечение не обязательно. В этом случае необходимо только выполнять логический контроль за тем, чтобы при движении или трансформации объектов образ никогда не выходил за пределы экрана.

Однако, это не всегда допустимо. Например, в трехмерном DOOM'e монстры часто видны на игровом экране только частично. Скажем, видна только правая половина его тела. Это значит, что его левая часть должна быть отброшена при выводе образа и следует применить какой-либо алгоритм битового отсечения.

Мы всегда должны отсекать растровое изображение в тех случаях, когда оно заезжает за пределы экрана (или за пределы других установленных нами границ). Например, в трехмерной игре Wolfenstein (равно как и в DOOM) играющий может менять размер окна с изображением, но картинка никогда не будет выходить за пределы этого окна, так как она отсекается его краями.

Как же мы можем произвести отсечение изображения? Существует два пути:

§ Мы можем проверять каждый отдельный пиксель, находится ли он внутри отображаемой области. Такое отсечение называется отсечением пространства образа. Другими словами, мы обрабатываем каждый из пикселей внутри всего образа и принимаем решение, рисовать его или нет. Эта техника не принимает во внимание геометрические свойства объекта. Она очень медлительна. (И я подозреваю, что именно такой метод применила фирма Microsoft в своей графике, потому что я никогда не видел блиттинг, работающий более медленно, чем в Microsoft's Graphics Library!) Посему данным методом мы пользоваться не будем;

§ Мы можем учитывать такие геометрические свойства объекта, как его размер, его форма и его положение по отношению к области отсечения. Этот способ называется отсечением области объекта.

Мы воспользуемся вторым приемом. Он довольно прост, по крайней мере, в том виде, в котором я собираюсь показать его на примере. Мы, как всегда, хотим до&тичь максимума производительности и эффективности. А так как отсечение замедляет блиттинг, нужно постараться свести потери времени к минимуму.

Во-первых, мы должны провести предварительный тест и выяснить: находится ли объект внутри ограниченной области? Например, пусть наш объект 16х16 и он находится в точке (1000,1000). Экран ограничен. Поскольку экран имеет размеры 320х200, совершенно ясно, что этот образ окажется невидим, и никакое отсечение здесь не поможет. Таким образом, мы должны проверять каждый объект на предмет того, будет ли он виден хотя бы частично. Алгоритм 7.1 выполняет данный тест.