Оригинал (английский): Collision detection by Mike.
Перевод: Dmi7ry, ArVorozh. Публикация на других сайтах только с обязательной ссылкой на данное сообщение.
Попытался перевести на сайте translated.by, думал что помогут. Однако только один человек перевёл «начерно» пару абзацев, остальное пришлось мучить самому. С моим ужасным английским результат получается далеко не совершенным. А также несколько странный местами стиль написания автора может затруднить понимание. Продолжением данной статьи является статья Быстрые столкновения в платформере.

Определение столкновений

Итак, я был очень занят HTML5 версией GameMaker и, когда я добавил код для столкновений, стало ясно, что основной популярный способ создания столкновений довольно медленный. Я не говорю о том, что нельзя сделать быструю обработку столкновений в GameMaker, просто таким образом составлены примеры, не удивительно, что некоторые люди иногда считают их медленными. Так что я опишу, как я обычно делаю столкновения. Во-первых, я использовал то, что GameMaker называет «точное столкновение» лишь однажды. И, оглядываясь назад, я понимаю, что мог бы обойтись без этого; опыт имеет свои преимущества…

Итак, для начала… что конкретно означает «точное столкновение«? Ну, проще говоря… это использование пиксельных данных одного изображения для сталкивания с набором пикселей другого изображения, таким образом столкновение будет только тогда, когда два нужных пикселя соприкасаются. Посмотрите на изображения двух кругов: вы можете видеть, что пересекаются их ограничительные рамки, но не круги. Что же это означает? Если вы используете простую систему столкновений ограничительных рамок, то они вызовут событие, в то время, когда точного столкновения на самом деле нет. Теперь может показаться очевидным, если вы используете точные столкновения, то получаете их, когда они на самом деле произошли. Тем не менее… что же требуется сделать GameMaker’у  для того, чтобы определить, что 2 случайных растровых изображения соприкоснулись; запомним, что эти формы могут быть чем угодно, а не только кругами.

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

for (n=0; n<Obj1_Instance_Countl; n++)
{
    for (f=0; f<Obj2_Instance_Countl; f++)
    {
        Test_Collisions( n, j );
    }
}

Теперь, если представить все события столкновения, которые у вас происходят между различными типами объектов, можно увидеть, что на это уйдёт уйма времени. Одно из изменений, которые мы сделаем со временем — блочная сортировка экземпляров (она же карманная, корзинная). Это означает, что мы будем проверять столкновение только  тех объектов, которые на самом деле близки друг к другу. Но мы пока что не сделали это…

Итак… Наконец, мы имеем два экземпляра, которые нужно проверить, что же сделает Test_Collisions() на самом деле? Ну, первое, что он делает — проверяет ограничивающие рамки. Это простая проверка, которая позволяет закончить проверку быстро, если объекты далеко друг от друга.

if ( bbox1.right < bbox2.left ) exit;
if ( bbox1.bottom < bbox2.top ) exit;
if ( bbox1.left > bbox2.right ) exit;
if ( bbox1.top > bbox2.bottom ) exit;

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

Далее, система отрабатывает перекрытия между ограничивающими прямоугольниками (как показано на следующем рисунке). Теперь каждый пиксель в спрайте можно рассматривать как ИСТИНА/ЛОЖЬ, то есть, если это не цвет фона (в данном случае, белый), то там имеется пиксель. Так, изображение показывает два перекрывающихся массива. Один — синий круг, а другой — красный круг. Затем мы в цикле просматриваем соответствующую секцию (медленно) и проверяем, не было ли двух пикселей в одной и той же позиции. Если нет, то мы ничего не делаем, так что событие не происходит. Вот некоторый псевдо-код для обнаружения столкновения между растровыми изображениями…

for ( y=YStartPos;y<YEndPos;y++)
{
    for ( x=XStartPos;x<xendpos;x++)
    {
        if (x < xSprite1Start) || (x> xSprite1End ) continue;
        if(y < ySprite1Start) || (y> ySprite1End ) continue;
        if(x < xSprite2Start) || (x> xSprite2End ) continue;
        if(y < ySprite2Start) || (y> ySprite2End ) continue;
        if(( CollisionMask1[ x+(y*width)]!=0 ) && ( CollisionMask2[ x+(y*width)]!=0 ) )
        {
            return TRUE;
        }
    }
}
return FALSE;

Хотя это и простой псевдо-код, теперь вы можете видеть, что это не будет быстро! Даже если уменьшить проверку до пересекающихся частей, все равно нужно «прогнать» в цикле все это, прежде чем определить, что нет никакого столкновения! А если у вас их много, то вы поставите свой компьютер на колени! Что плохо… GameMaker хочет, чтобы вы использовали точные столкновения по умолчанию. Это ужасно.

Правда в том, что только в очень РЕДКИХ случаях вы захотите делать точную проверку столкновения; Лемминги ходят по фону, или они должны ходить вокруг фигур, это довольно редкие случаи, и обычно это может быть сделано разными способами. Лемминги никогда делают проверку столкновения с фоном всего спрайта, на самом деле делается проверка только одного пикселя у ног лемминга, в маске. И вы можете сделать это прямо в GML, если вы хотите! По факту, Лемминги имели в своём распоряжении игровое поле размером 1600×160, и вы можете легко преобразовать это в битовую маску (бит на пиксель) размером 200×160. Это, в свою очередь означает, что вам нужен массив размером 32000 байт. И это прекрасно вписывается! Если вы не хотите заходить так далеко, вы могли бы использовать 160 массивов, по 1600 байт каждый. Затем иметь контрольный массив с каждым из них в качестве линии столкновения. Тогда можно легко проверить этот массив в GML используя X и Y координаты леммингов.

Но что насчёт нормальных игр? Стрелялок и платформеров? Они никогда не должны использовать точное обнаружение столкновений, в этом просто нет необходимости. Во-первых, при использовании точного определения столкновений, нет возможности для ошибок в пользу игрока. Все должно быть совершенным. Нельзя «залезть» даже на один пиксель на злодея или на фон блока. С точки зрения геймплея, это ужасно. Там всегда должно быть немного пространства для ошибок, потому что как люди, мы просто не точны, когда управляем играми. Джойстики/клавиши не достаточно хороши, и наши решения далеко не достаточно хороши. Так что это означает, что игроки в конечном итоге либо станут сверх осторожными и не приблизятся близко к злодеям/фонам, либо они просто будут расстраиваться и сдаваться.

Итак, какое лучшее решение? Ну, лично я всегда использую либо столкновение с прямоугольником, либо столкновение с окружностью. Оба этих метода быстры и просты в реализации, и, когда вы используете такие вещи, как «корзины», чтобы объединять объекты вместе, вы можете также сократить то, что вы должны проверить в первую очередь! Для тех, кто не знает … «Корзины» — простой способ объединения объектов/экземпляров вместе в группы. Для столкновения, мы стремимся иметь сетку корзин и размещать объекты, во все ячейки корзин, которых они касаются. Это означает, если вы хотите проверить столкновения, вам больше не придется проверять столкновение всех объектов ко всем… Только к тем, которые в окружающих корзинах. Это намного, намного быстрее.

Итак… как определить «справедливый» ограничительный прямоугольник? Обычно я стараюсь задать прямоугольник, который полностью «вписывается» в противника, это помогает избежать случаев (например, 2 абзаца выше), где игроки умирают, даже вообще не касаясь злодеев. Игроки более чем готовы простить те случаи, когда вы столкнетесь с объектом немного, но они весьма неумолимы в тех случаях, когда они умирают, не задев ничего. Итак, как показано на персонаже слева, желтый ограничительный прямоугольник находится в пределах игрока, но его также более чем достаточно, чтобы быть убитым злодеями или пулями. Также тут нет никаких правил, говорящих, что эту ограничительную рамку, вы будете использовать для столкновения с фоном… так что скорее всего, вы будете иметь то, что не позволяет игроку забраться глубоко внутрь фона. Что-нибудь, что хорошо выглядит и удачно соприкасается — это все, что вам нужно; если пистолет залезает на фон, это в действительности не так существенно…

Теперь, когда я сказал, что я бы использовал прямоугольник или окружность, одна вещь, которую я бы не стал делать сам — использование ограничивающего прямоугольника, как выше. Причиной этого является то, что «IF‘ы» медленны, так что если вы можете свести их к минимуму, будет лучше! Поэтому я использую трюк, который я узнал от Дэйва Джонса, когда он делал Blood Money; я использую центр прямоугольника с 1/2 ширины и 1/2 высоты.

Теперь вспомним, что эти прямоугольники — ВНУТРИ спрайтов, таким образом, они, вероятно, будут хорошо друг в друге, означая, что игрок знает, что сейчас его поджарят как гуся. Итак, в этом случае Вы можете видеть 1/2 ширины и 1/2 высоты, 16×32 и 20×20, в то время как расстояние до центров 25×35. Так как же я решаю, что есть столкновение?

Это очень просто… Итак, я буду делать X, и вы легко увидите, как Y работает. Я просто вычитаю 2 X координаты, и это дает расстояние между центрами (в данном случае 25 пикселей), и если это расстояние составляет менее половины сумм ширины, (16 пикселей + 20 пикселей), то столкновение есть! Это позволяет нам сделать проверку X только с одним IF. Глядя на приведенный ниже код вы заметите, ABS (), и обычно вы должны были бы делать IF там, но если вы sneeky, можно сделать ABS() без IF.

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

if( (halfwidth1+halfwidth2) < abs(x1-x2) ) exit;
if( (halfheight1+halfheight2) < abs(y1-y2) ) exit;

Теперь, хотя это нормально для стандартного спрайт-спрайт столкновения, что на счёт спрайта и фона? Ну, GameMaker имеет удобную функцию move_outside_solid(), но когда у вас задана точная проверка столкновения, он будет сидеть в цикле и делать проверку столкновений снова и снова, что будет медленно (на любой заданной вами скорости шага), пока ваш спрайт перемещается за пределы всего, с чем происходит столкновение. Это ужасная функция, particually, если вы оглянетесь назад на то, что вовлечено в выполнение даже единственной точной проверки столкновения.

Снова, мне никогда не нужно это… Для фона в стиле tilemap, я всегда сталкиваюсь с массивом тайлов, а затем перемещаю себя наружу столкновения с фоном. Так как же я делаю это? Хорошо… Если вы используете тайлы, размер которых является степенью двойки (8, 16, 32, и т.п…) тогда переместиться на границу тайла достаточно просто. Например, если я сталкиваюсь с 32×32 тайлом в X=64 и Y=32, и координаты моего экземпляра размером 32×32 составляют 56,12 (тогда это перекрывается в 24,12), затем все, что мне нужно сделать, чтобы переместить образец НАРУЖУ коллизии, это бинарное И с $FFFFFFE0. Это удаляет младшую «дробную» часть битов, так же, как:

x = x-(x%32);

Теперь… даже если вы должны были поддерживать систему, которую GameMaker использует в настоящий момент, это все еще было бы намного быстрее не используя «точные» столкновения, но все еще медленнее, чем нормальный «pro» использовал бы. Сейчас, я мог пойти дальше, по поводу того, как сделать эффективное обнаружение столкновения, но действительно… Я должен действительно сделать отдельную статью о каждом методе, и вы затем легко видели бы, какую систему вам было бы лучше использовать в конкретном случае.. но давайте посмотрим, сколько времени я имею. 🙂

Несколько слов в конце… Так, GameMaker часто обвиняют в медленности, но на самом деле, на современном компьютере это довольно быстрая система для 2D-игр. Однако из-за довольно хороших команд, вроде встроенной сложной системы столкновений, очень легко злоупотреблять ими, и думать, что нет ничего плохого в вашем коде…  Однако, быть хорошим кодером значит знать все о том, как выполняется код, даже если он не Ваш! Если это Ваша игра, это Ваша проблема, и GameMaker имеет все необходимые вам инструменты, чтобы сделать игру восхитительной.