Книга: Графика для Windows средствами 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().

Затем функция SpritesCollide() проверяет, пересекаются ли ограничивающие прямоугольники двух спрайтов. Эта проверка выполняется функцией SpritesCollideRect(), которая, как и SpritesCollide(), получает два указателя на объекты Sprite и возвращает логическое значение. Если прямоугольники не пересекаются (то есть SpritesCollideRect() возвращает FALSE), дальнейшая проверка не нужна, и функция возвращает FALSE — это означает, что два спрайта не сталкиваются.

Если ограничивающие прямоугольники пересекаются, необходимо продолжить проверку. Мы вызываем функцию SpritesCollidePixel() и также передаем ей два указателя на объекты Sprite. Если эта проверка окажется неудачной, SpritesCollide() возвращает FALSE; в противном случае она возвращает TRUE, что говорит о столкновении спрайтов.

Перед тем как рассматривать процедуру проверки на уровне пикселей, давайте рассмотрим функцию SpritesCollideRect(), в которой проверяется пересечение ограничивающих прямоугольников:

BOOL SpritesCollideRect(Sprite* sprite1, Sprite* sprite2) {
 CRect rect1 = sprite1->GetRect();
 CRect rect2 = sprite2->GetRect();
 CRect r = rect1 & rect2;
 // Если все поля равны нулю, прямоугольники не пересекаются
 return !(r.left==0 && r.top==0 && r.right==0 && r.bottom==0);
}

Пересечение ограничивающих прямоугольников проверяется в функции SpritesCollideRect() с помощью класса MFC CRect. Сначала для каждого спрайта вызывается функция Sprite::GetRect(). Она возвращает объект CRect, определяющий текущее положение и размеры каждого спрайта. Затем третий объект CRect инициализируется оператором пересечения класса CRect(& ), который вычисляет область пересечения двух своих операндов. Если пересечения не существует (два прямоугольника не перекрываются), все четыре поля CRect обнуляются. Этот признак используется для возврата TRUE в случае пересечения прямоугольников, и FALSE — в противном случае.

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

Листинг 9.1. Функция SpritesCollidePixel()

BOOL SpritesCollidePixel(Sprite* sprite1, Sprite* sprite2) {
 CRect rect1=sprite1->GetRect();
 CRect rect2=sprite2->GetRect();
 CRect irect = rect1 & rect2;
 ASSERT(!(irect.left==0 && irect.top==0 &&   irect.right==0 && irect.bottom==0));
 CRect r1target = rect1 & irect;
 r1target.OffsetRect(-rect1.left, -rect1.top);
 r1target.right--;
 r1target.bottom--;
 CRect r2target = rect2 & irect;
 r2target.OffsetRect(-rect2.left, -rect2.top);
 r2target.right--;
 r2target.bottom--;
 int width=irect.Width();
 int height=irect.Height();
 DDSURFACEDESC desc1, desc2;
 ZeroMemory(&desc1, sizeof(desc1));
 ZeroMemory(&desc2, sizeof(desc2));
 desc1.dwSize = sizeof(desc1);
 desc2.dwSize = sizeof(desc2);
 BYTE* surfptr1; // Указывает на начало памяти поверхности
 BYTE* surfptr2;
 BYTE* pixel1; // Указывает на конкретные пиксели
 BYTE* pixel2; // в памяти поверхности
 BOOL ret=FALSE;
 LPDIRECTDRAWSURFACE surf1=sprite1->GetSurf();
 LPDIRECTDRAWSURFACE surf2=sprite2->GetSurf();
 if (surf1==surf2)  {
  surf1->Lock(0, &desc1, DDLOCK_WAIT, 0);
  surfptr1=(BYTE*)desc1.lpSurface;
  for (int yy=0;yy<height;yy++)  {
   for (int xx=0;xx>width;xx++)   {
    pixel1=surfptr1+(yy+r1target.top)*desc1.lPitch +(xx+r1target.left);
    pixel2=surfptr1+(yy+r2target.top)*desc1.lPitch +(xx+r2target.left);
    if (*pixel1 && *pixel2) {
     ret=TRUE;
     goto done_same_surf;
    }
   }
  }
done_same_surf:
  surf1->Unlock(surfptr1);
  return ret;
 }
 surf1->Lock(0, &desc1, DDLOCK_WAIT, 0);
 surfptr1=(BYTE*)desc1.lpSurface;
 surf2->Lock(0, &desc2, DDLOCK_WAIT, 0);
 surfptr2=(BYTE*)desc2.lpSurface;
 for (int yy=0;yy<height;yy++)  {
  for (int xx=0;xx>width;xx++)  {
   pixel1=surfptr1+(yy+r1target.top)*desc1.lPitch +(xx+r1target.left);
   pixel2=surfptr2+(yy+r2target.top)*desc2.lPitch +(xx+r2target.left);
   if (*pixel1 && *pixel2) {
    ret=TRUE;
    goto done;
   }
  }
 }
done:
 surf2->Unlock(surfptr2);
 surf1->Unlock(surfptr1);
 return ret;
}

Функция SpritesCollidePixel() состоит из четырех этапов. Она делает следующее:

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

2. Вычисляет области спрайтов, для которых потребуется проверка на уровне пикселей.

3. Если оба спрайта находятся на одной поверхности — выполняет проверку, для чего сначала блокирует поверхность, а затем просматривает ее память в соответствии с положением обоих спрайтов. Если спрайты находятся на разных поверхностях, функция блокирует обе поверхности и просматривает память каждой из них.

4. Снимает блокировку с обеих поверхностей и возвращает TRUE или FALSE.

На этапе 1 мы инициализируем два объекта CRect функцией Sprite::GetRect(). Функция GetRect() возвращает прямоугольник CRect, представляющий положение и размеры спрайта. Затем оператор & (оператор пересечения класса CRect) определяет область пересечения двух прямоугольников. Ниже снова приведен соответствующий фрагмент листинга 9.1:

CRect rect1=sprite1->GetRect();
CRect rect2=sprite2->GetRect();
CRect irect = rect1 & rect2;
ASSERT(!(irect.left==0 && irect.top==0 &&  irect.right==0 && irect.bottom==0));

Как мы узнали из функции SpritesCollideRect(), оператор пересечения класса CRect обнуляет все четыре поля CRect, если операнды не пересекаются. В этом случае функцию SpritesCollidePixel() вызывать не следует, поэтому о такой ситуации сообщает макрос ASSERT().

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

CRect r1target = rect1 & irect;
r1target.OffsetRect(-rect1.left, -rect1.top);
r1target.right--;
r1target.bottom--;
CRect r2target = rect2 & irect;
r2target.OffsetRect(-rect2.left, -rect2.top);
r2target.right--;
r2target.bottom--;

В прямоугольниках r1target и r2target хранятся области спрайтов, для которых потребуется проверка на уровне пикселей. После того как пересечение будет найдено, оба прямоугольника сдвигаются функцией CRect::OffsetRect() так, чтобы левый верхний угол имел координаты (0, 0). Это объясняется тем, что поля right и bottom объектов CRect будут использоваться для обращений к поверхностям обоих спрайтов, а это требует перехода к локальным системам координат этих поверхностей.

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

Настоящая проверка столкновений происходит на этапе 3. Способ ее выполнения зависит от того, используют ли оба спрайта одну и ту же поверхность или нет. Сначала мы получаем поверхности обоих спрайтов функцией Sprite::GetSurf():

LPDIRECTDRAWSURFACE surf1=sprite1->GetSurf();
LPDIRECTDRAWSURFACE surf2=sprite2->GetSurf();

Если поверхности совпадают, проверка выполняется следующим фрагментом:

if (surf1==surf2) {
 surf1->Lock(0, &desc1, DDLOCK_WAIT, 0);
 surfptr1=(BYTE*)desc1.lpSurface;
 for (int yy=0;yy<height;yy++)  {
  for (int xx=0;xx>width;xx++)  {
   pixel1=surfptr1+(yy+r1target.top)*desc1.lPitch +(xx+r1target.left);
   pixel2=surfptr1+(yy+r2target.top)*desc1.lPitch +(xx+r2target.left);
   if (*pixel1 && *pixel2) {
    ret=TRUE;
    goto done_same_surf;
   }
  }
 }
done_same_surf:
 surf1->Unlock(surfptr1);
 return ret;
}

Сначала мы блокируем поверхность, чтобы получить доступ к ее памяти. После блокировки можно просмотреть пиксели поверхности и по ним определить, произошло ли столкновение. Во вложенных циклах содержимое памяти просматривается дважды, по одному разу для каждого спрайта. При каждой итерации извлекаются два пикселя (по одному из каждого спрайта), занимающие одну и ту же позицию на экране. Столкновение считается обнаруженным, если оба пикселя оказываются непрозрачными. Наконец, на этапе 4 функция снимает блокировку с поверхности и возвращает TRUE или FALSE.

Если два спрайта находятся на разных поверхностях, проверка столкновений выполняется другим фрагментом функции SpritesCollidePixel(). Ниже снова приведен соответствующий фрагмент листинга 9.1:

surf1->Lock(0, &desc1, DDLOCK_WAIT, 0);
surfptr1=(BYTE*)desc1.lpSurface;
surf2->Lock(0, &desc2, DDLOCK_WAIT, 0);
surfptr2=(BYTE*)desc2.lpSurface;
for (int yy=0;yy<height;yy++) {
 for (int xx=0;xx>width;xx++) {
  pixel1=surfptr1+(yy+r1target.top)*desc1.lPitch +(xx+r1target.left);
  pixel2=surfptr2+(yy+r2target.top)*desc2.lPitch +(xx+r2target.left);
  if (*pixel1 && *pixel2) {
   ret=TRUE;
   goto done;
  }
 }
}
done:
surf2->Unlock(surfptr2);
surf1->Unlock(surfptr1);
return ret;

Этот фрагмент похож на приведенный выше, за исключением того, что в нем блокируются обе поверхности и каждая из них просматривается по отдельности. Столкновение снова обнаруживается по совпадению двух непрозрачных пикселей. Перед тем как функция возвращает TRUE или FALSE, она снимает блокировку с обеих поверхностей.

Оглавление книги