Pixel Perfect Collision Detection в HTML5 Canvas

Question

Я хочу проверить коллизию между двумя спрайтами в холсте HTML5. Итак, ради обсуждения давайте предположим, что оба спрайта являются объектами IMG, а столкновение означает, что альфа-канал не равен 0. Теперь оба этих спрайта могут иметь вращение вокруг центра объекта, но никакое другое преобразование в случае, если это делает это проще.

Теперь очевидное решение, которое я придумал, было бы следующим:

• вычислить матрицу преобразования для обоих
• вычисляет приблизительную оценку области, в которой должен проверяться код (например, смещение обоих + вычисленное дополнительное пространство для поворота)
• для всех пикселей в пересекающемся прямоугольнике, преобразуйте координату и проверьте изображение в вычисленной позиции (с округлением до ближайшего соседа) для альфа-канала. Затем прервите первое попадание.

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

Интересно, я что-то здесь упускаю и есть ли более простое решение для обнаружения столкновений.

Answer 1

Мне нужно повторить то, что я уже должен сделать на чертеже

Ну, вы могли бы создать новый контекст рендеринга, нанести на него одну повернутую белую маску фона, установить операцию компоновки на lighter и нанести другую повернутую маску сверху с заданным смещением.

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

Я должен проверять наличие столкновений в каждом кадре, что делает его довольно дорогим.

Да, я думаю, реально вы будете использовать предварительно рассчитанные таблицы столкновений. Если у вас есть место для этого, вы можете сохранить один бит попадания / отсутствия попадания для каждой комбинации спрайта a, спрайта b, относительного вращения, относительного-x-нормализованного к вращению и относительного-y-нормализованного к вращению , В зависимости от того, сколько у вас спрайтов и сколько шагов вращения или движения, это может быть довольно большим.

Компромисс будет заключаться в том, чтобы хранить предварительно повернутые маски каждого спрайта в массиве JavaScript (из Number, предоставляя 32-битные / легко доступные данные &&) или в виде символа в Sring, давая вам 16 бит) и && каждая строка пересекающихся спрайтовых масок вместе.

Или отказаться от пикселей и начать смотреть, например. пути.

Answer 2

Я не являюсь программистом javascript, но я думаю, что те же приемы оптимизации работают так же хорошо для Javascript, как и для C ++.

Просто вращайте углы спрайта вместо каждого пикселя. По сути, вы будете делать что-то вроде программного отображения текстур. Вы можете определить положение x, y данного пикселя, используя различную информацию о градиенте. Для получения дополнительной информации обратитесь к программному наложению текстур.

Если вы раскладываете дерево квадритов спрайта на области «попадания» и «не попадания», то вы можете эффективно проверить, не является ли данное разложение дерева квадрантов «не попаданием», «все попаданием» или «возможным попаданием» (т.е. содержит попадания и не попадания пикселей. Первые 2 тривиально пройти. В последнем случае вы затем переходите на следующий уровень декомпозиции и повторяете тест. Таким образом, вы проверяете только те пиксели, которые вам нужны, и для больших в областях «не попадание» и «попадание» вам не нужно делать такой сложный набор проверок.

В любом случае, это всего лишь пара мыслей.

Answer 3

Та же проблема, альтернативное решение.Сначала я использую данные getImageData, чтобы найти многоугольник, который окружает спрайт.Осторожно, потому что реализация работает с изображениями с прозрачным фоном, которые имеют один сплошной объект.Как корабль.Следующим шагом является Алгоритм Рамера Дугласа Пекера для уменьшения количества вершин в многоугольнике.Наконец, я могу легко и дешево вращать многоугольник с очень небольшим количеством вершин и проверять столкновения с другими многоугольниками для каждого спрайта.

http://jsfiddle.net/rnrlabs/9dxSg/

var canvas = document.getElementById("canvas");
var context = canvas.getContext("2d");
var img = document.getElementById("img");

context.drawImage(img, 0,0);
var dat = context.getImageData(0,0,img.width, img.height);
// see jsfiddle
var startPixel = findStartPixel(dat, 0);
var path = followPath(startPixel, dat, 0);
// 4 is RDP epsilon
map1 = properRDP(path.map, 4, path.startpixel.x, path.startpixel.y);

// draw

context.beginPath();
context.moveTo(path.startpixel.x, path.startpixel.x);
for(var i = 0; i < map.length; i++) {
    var p = map[i];
    context.lineTo(p.x, p.y);
}
context.strokeStyle = 'red';
context.closePath();
context.stroke();