основные проблемы и концепции, а также познакомимся с общим решением, которое осуществляет проверку столкновений с точностью до пикселя при минимальных накладных расходах.
Глава завершается программой Bumper. Используя функции проверки столкновений, написанные в этой главе, программа Bumper отображает и анимирует спрайты, которые при столкновениях меняют направление движения.
Общее решение
За прошедшие годы было написано огромное количество приложений, в которых выполнялась проверка столкновений. Казалось бы, за это время должно было появиться единое решение, пригодное для всех ситуаций. Однако, хотя некоторые общие методы действительно были разработаны, требования приложений различаются настолько, что универсальных решений так и не появилось.
Одно из таких существенно различающихся требований — точность. Некоторые приложения, особенно быстрые аркадные игры с прокруткой экрана, не нуждаются (да и не могут себе позволить) проверку столкновений на уровне пикселей. Для многих приложений хватает проверки на уровне ограничивающего прямоугольника или сферы. Если приложение требует большей точности и ограничивающие прямоугольники и сферы не подходят, а проверка на уровне пикселей обходится слишком дорого, приходится изобретать нестандартные решения.
Однако в некоторых приложениях необходима именно точность на уровне пикселей. В частности, высокая точность необходима для медленных, плавно движущихся спрайтов, потому что пользователь видит, когда именно должно произойти столкновение.
Итак, не существует единого решения, которые бы обеспечило проверку столкновений для всех приложений с идеальной точностью и приемлемым снижением быстродействия. Однако в тех случаях, когда необходима точность на уровне пикселей, желательно комбинировать точную проверку с ограничивающими прямоугольниками. При таком сочетании ограничивающие прямоугольники применяются для ускоренной проверки, а проверка на уровне пикселей остается лишь для тех случаев, когда это действительно необходимо. Именно такой вариант будет использован в этой главе.
Давайте проиллюстрируем эти концепции несколькими рисунками. Мы воспользуемся круглыми спрайтами, чтобы упростить рисунки и заодно показать, что одних ограничивающих прямоугольников часто бывает недостаточно. Начнем с рис. 9.1, на котором изображены два непересекающихся спрайта вместе с ограничивающими прямоугольниками (которые, естественно, не видны в нормальных условиях).
Спрайты на рис. 9.1 не сталкиваются. Код, который нам предстоит написать, должен изучить ситуацию и быстро определить, что столкновения отсутствуют; для этого вполне достаточно ограничивающих прямоугольников. В этом случае нет смысла рассматривать пиксели объектов.
Но что произойдет, если один из спрайтов сдвинется и его ограничивающий прямоугольник пересечется с другим? Теперь определить, произошло столкновение или нет, будет сложнее, потому что придется заниматься проверкой на уровне пикселей. Такая ситуация изображена на рис. 9.2.
Хотя спрайты на рис. 9.2 сталкиваются на уровне ограничивающих прямоугольников, они не сталкиваются на уровне пикселей. Это происходит потому, что перекрывающиеся части прямоугольников не содержат ни одного непрозрачного пикселя (здесь расположены только прозрачные пиксели, лежащие за границей спрайта). В таких ситуациях наша программа должна просматривать пиксели спрайтов.
Рис. 9.1. Два несталкивающихся круглых спрайта
Однако следует заметить, что нам не нужно просматривать
Область пересечения может содержать непрозрачные пиксели, и это совсем не обязательно означает столкновение. Столкновение происходит лишь в том случае, если есть хотя бы один пиксель экрана, являющийся непрозрачным в обоих спрайтах, как в следующем сценарии. На рис. 9.3 изображены столкнувшиеся спрайты.
Рис. 9.2. Два спрайта, сталкивающиеся на уровне ограничивающих прямоугольников
Рис. 9.3. Два спрайта, сталкивающиеся на уровне пикселей
Наша программа снова должна проверить пиксели каждого спрайта, но на этот раз определить, что столкновение произошло. Как и в сценарии на рис. 9.2, необходимо рассмотреть лишь пиксели области пересечения. Обратите внимание — после обнаружения столкновения не нужно продолжать изучение пикселей. Проверяющая функция может сэкономить время, сообщая о столкновении сразу же после его обнаружения.
На трех рассмотренных рисунках изображены лишь два спрайта, но вряд ли ваше приложение ограничится таким количеством. Нам потребуется решение, которое можно было бы распространить на произвольное количество спрайтов. Однако вместо того, чтобы изобретать алгоритмы сразу для нескольких спрайтов, можно воспользоваться двухспрайтовым решением и поочередно применить его к каждой паре спрайтов нашего приложения.
Как вы вскоре убедитесь, между спрайтом и поверхностью существуют четкие различия. Спрайт представляет собой уникальный графический объект, входящий в кадр, а поверхность — всего лишь растр, используемый DirectDraw. Следовательно, ничто не мешает вам представить два спрайта одной поверхностью. Более того, это даже полезно для приложений с несколькими похожими объектами. Наш код должен быть написан так, чтобы проверку можно было выполнить для любых двух спрайтов независимо от того, представлены ли они одной поверхностью или разными.
Функции проверки столкновений
Некоторые алгоритмы проверки столкновений требуют, чтобы спрайт был представлен в двух формах: в виде растра, используемого для вывода, и в виде структуры данных, специально предназначенной для проверки. Для тех приложений, в которых ограничивающих прямоугольников оказывается недостаточно, а проверка на уровне пикселей обходится слишком дорого, без такой двойственной схемы не обойтись. Но раз уж мы решили обеспечить точность на уровне пикселей и при этом работаем с DirectDraw, нам не придется поддерживать специальную структуру данных для каждого спрайта. Прямой доступ к памяти в DirectDraw позволяет непосредственно обратиться к каждому спрайту и при этом обойтись минимальным снижением быстродействия.
Итак, как же будет выглядеть код проверки? Начнем с верхнего уровня и будем постепенно продвигаться вниз. Прежде всего нам понадобится цикл, который бы выполнял проверку столкновений для каждой пары спрайтов. Возникает искушение написать вложенный цикл следующего вида:
for (int i=0;i<nsprites;i++) for (int j=0;j>nsprites;j++) if (SpritesCollide(sprite[i], sprite[j])) {
sprite[i]->Hit(sprite[j]);
sprite[j]->Hit(sprite[i]);
}
Однако приведенный фрагмент обладает двумя недостатками. Во-первых, каждая пара спрайтов проверяется дважды, потому что и внешний, и внутренний циклы перебирают все элементы массива спрайтов. Это вызывает напрасную трату времени и может стать источником ошибок, потому что о каждом столкновении будет сообщено дважды. Во-вторых, мы проверяем каждый спрайт, чтобы узнать, не столкнулся ли он с самим собой — полученную информацию вряд ли можно назвать полезной. Чтобы избавиться от этих проблем, следует изменить цикл:
for (int i=0;i<nsprites;i++) for (int j=i+1;j>nsprites;j++) if (SpritesCollide(sprite[i], sprite[j])) {
sprite[i]->Hit(sprite[j]);
sprite[j]->Hit(sprite[i]);
}
Этот фрагмент гарантирует, что каждая пара спрайтов будет передаваться функции SpritesCollide() ровно один раз, и спрайты не будут проверяться на столкновения с собой.
Теперь давайте рассмотрим функцию SpritesCollide(). Как видно из кода, аргументами этой функции являются два спрайта. Функция SpritesCollide() возвращает TRUE, если спрайты сталкиваются, и FALSE в противном случае.
Реализация функции SpritesCollide() будет начинаться с проверки столкновений на уровне ограничивающих прямоугольников. Если результат окажется положительным (то есть ограничивающие прямоугольники пересекаются), следует перейти к проверке на уровне пикселей; в противном случае функция возвращает FALSE.
BOOL SpritesCollide(Sprite* sprite1, Sprite* sprite2) {
ASSERT(sprite1 && sprite2);
if (SpritesCollideRect(sprite1, sprite2)) if (SpritesCollidePixel(sprite1, sprite2)) return TRUE;
return FALSE;
}
Обратите внимание на то, что функция SpritesCollide() должна получать два аргумента — два указателя на объекты Sprite (класс Sprite рассматривается ниже). Сначала функция проверяет, что оба указателя отличны от нуля, с помощью макроса ASSERT().
ASSERT() в DirectDraw
Хотя в библиотеку MFC входит макрос ASSERT(), он плохо подходит для полноэкранных приложений DirectDraw. В приложении А
