Pull to refresh

Обработка 2D столкновений с использованием LibCanvas

Reading time7 min
Views15K

В большинстве современных игр невозможно обойтись без обнаружения и дальнейшей обработки столкновений (выстрел, прыжок, банальный отскок от препятствия). На первый взгляд их реализация представляется довольно просто, но так ли это на самом деле? Попробую вкратце объяснить суть проблем, с которыми я столкнулся.
По традиции, после прочтения нескольких статей начинаешь чувствовать себя богом, способным сделать все что угодно. Думаю, многие сталкивались с подобной проблемой и могут представить, что последует за ней… правильно, череда больших проблем. Но обо всем по порядку.

Подготовка “ландшафта”


Итак, с чего бы начать? Мне кажется, что лучше всего начать со статических объектов, ибо с ними намного проще работать (не надо заботиться о перерисовке, изменении положения/формы и прочих вещах).
var background = new LibCanvas('#canv') .size(512, 512).start(); //создаем объект LibCanvas
background.createShaper({ //и строим на нем некоторое препятствие
  shape : shape,
  stroke: '#00f',
  fill : '#004'
});
на этом все, background завершен. В идеале трогать мы его больше не должны.

Создание концепта объекта


Далее можно рассмотреть, собственно, “объект” (то, что перемещается по холсту и будет отскакивать от препятствий). Я считаю, что рассмотрение объекта стоит начинать с конца, а именно с того, что он должен будет уметь делать в итоге.
У каждого этот список будет свой, но у меня он выглядит так:
  1. объект должен знать свое положение и размер
  2. объект должен знать направление и скорость своего движения
  3. объект должен знать как выглядит
  4. объект должен уметь печататься на холст, а также “перепечатываться” (удаляться с одного места и появляться в другом)
  5. объект должен уметь определять столкновения с границами холста
  6. объект должен уметь определять и обрабатывать столкновения с препятствиями
Со списком “возможностей” объекта мы теперь более или менее знакомы. Приступаем к реализации.

Реализация объекта


Для начала нам необходимо создать отдельный слой для перемещаемых объектов (чтобы каждый раз не перерисовывать другие слои, например, background):
var cont = background.createLayer('cont');

Теперь на этот слой необходимо поместить объект, который будет задан следующим образом:
var object = {
  center: {x, y}, // центр объекта
  speed: {x, y}, // скорость
  size, // его размер
  buffer, // изображение на холсте
  redrawBuffer(), // функция, для изменения object.buffer
  print(), // перенос изображения из буффера на холст
  redraw(), // перенос изображения из одного места холста на другое
  animate(), // определение столкновений с границами холста
  findBounce() // определение и обработка столкновений с препятствиями
};

Возникает следующий вопрос: каким образом нужно заполнять аттрибуты этого объекта? Пойдем по порядку.

Центр, скорость и размер

Пускай мы ловим 2 клика на холсте – координаты первого это центр объекта, а с помощью координат второго легко будет вычислить составляющие 'x' и 'y' скорости объекта.
Сказано – сделано. Реализовываем:
cont.listenMouse(); // начинаем “слушать” мышь
var mouse = cont.mouse;
var flag = false; // необходим для определения клика – первый или второй
mouse.addEvent('mousedown', function() {
  flag = !flag;
});

cont.addRender(function() {
  if(mouse.inCanvas) {
    if(flag) {
      object.size = size; //устанавливаем необходимый размер объекта
      object.center.center.moveTo( mouse.point );
      object.speed.x = 0; // а также не забываем обнулить скорость
      object.speed.y = 0;
    }
    else { // если второй клик
      object.speed.x = mouse.point.x – object.center.x; // при втором клике устанавливаем скорость объекта
      object.speed.y = mouse.point.y - object.center.y;
    }
  }
});

Итак, поехали дальше.

Что такое object.buffer, object.redrawBuffer, object.redraw и зачем они, собственно, нужны

Немного теории – при вызове функции cont.update() отправляется запрос на перерисовку в ближайший этап рендеринга (если синхронно вызвать «update» пять раз подряд, то перерисовка будет произведена только один раз — когда будет рендериться следующий кадр). Но, так или иначе, начнется перерисовка всего холста, что довольно не эффективно (немного математики: холст(512*512)=262144 точки, размер объекта – пусть даже 50*50=2500 точек что примерно в 10 раз меньше, чем весь холст).
Так как мы будем перемещать наш объект, а значит много раз перерисовывать холст, то намного эффективнее будет просто вырезать изображение из одного места, и вставить в другое. Это самый простой способ, для тех, кто не хочет думать, а хочет решать задачи прямо “в лоб”. Намного более интересен, по крайней мере для меня, следующий вариант: мы не вырезаем изображение объекта из холста и сохраняем его в буффер при каждом перемещении, а имеем две функции — redrawBuffer() и redraw(fromX, fromY, toX, toY). На случай изменения вида объекта подойдет первая: redrawBuffer(), которая изменяет содержимое буффера. Для перемещения же, можно пользоваться функцией redraw(fromX, fromY, toX, toY), которая “чистит” место под объектом в “старом” месте и вставляет изображение из буфера в “новое”:
redraw: function(canvas, beforeX, beforeY, afterX, afterY) {
  var params = {
    fromX: (beforeX - this.size),
    fromY: (beforeY - this.size),
    size: (this.size*2),
    toX:  (afterX - this.size),
    toY:  (afterY - this.size)
  }
  canvas.ctx.clearRect(params.fromX - 1, params.fromY - 1, params.size + 2, params.size + 2);
  canvas.ctx.drawImage(this.buffer, params.toX, params.toY);
}

Реакция объекта на столкновения с границами холста

Это реализуется до ужаса просто – если объект достиг верхнего или нижнего края, то:
object.speed.y = -object.speed.y;

если правого или левого:
object.speed.x = -object.speed.x;

Определение и обработка столкновений с препятствиями

Как понять, куда должен отскочить объект после столкновения с препятствием произвольной формы? Ответ на этот вопрос нам могут дать старые школьные учебники с курсом физики/геометрии — “угол падения равен углу отражения”. Так как физику и геометрию могут помнить не все, то, думаю, стоит напомнить, что эти углы считаются от нормали (перпендикуляра) к поверхности в точке:

Здесь 'H' и 'G' – нормали. 'A' и 'D' – скорости до столкновения. 'C' и 'F' – скорости после столкновения.

Но, как это часто бывает, на словах все довольно просто, а на деле, увы, нет.
Итак, начну с довольно общего алгоритма:
  1. Перемещаем объект, пока он не встречает препятствие
  2. Находим нормаль
  3. Меняем скорости
  4. Возвращаемся к п.1
Начнем разбирать данный алгоритм по пунктам:

Перемещаем объект, пока он не встречает препятствие

С перемещением все просто: рисуем объект, меняем положение его центра, стираем старый, рисуем новый – вот и все перемещение. Но как понять, что два объекта (объект и background) столкнулись? Для этого хочу напомнить, что сейчас гаш холст состоит из двух слоев (“фоновый” – статический и “объектный” – динамический), а нам необходимо понять, что 2 объекта пересеклись (или просто соприкоснулись). Прочитав эту статью, я более или менее представил себе алгоритм нахождения пересечения:
  1. получаем изображение слоя с объектом и изображение слоя с препятствием
  2. вспоминаем, что: “Пиксели хранятся в объектах типа ImageData. Каждый объект имеет три свойства: width, height и data. Свойство data имеет тип CanvasPixelArray и содержит массив элементов размером width*height*4 байт; это означает, что каждый пиксель содержит цвет в формате RGBA.”
  3. пишем простенький цикл, в котором есть всего лишь одно условие
var pixels1 = background.ctx.getImageData( x,y,size,size);
var pixels2 = cont.ctx.getImageData( x,y,size,size);
for(var i = 0; i < pixels2.length; i += 4 ) {
  if((pixels1[i+3] != 0) && (pixels2[i+3] != 0)) {
    /* имеем столкновение */
    break;
  }
}

На данном этапе я бы снова посоветовал задаться вопросом об эффективности – стоит ли при каждом перемещении объекта пробегать 2*512*512 пикселей? Конечно нет. Можно без каких либо последствий уменьшить “зону поиска” до квадрата, в который можно будет вместить объект (конечно же, если перемещаемый объект всего один). Но можно ли уменьшать эту зону еще сильнее, скажем, до 1 пикселя? Да, можно. Но это дальнейшее “уменьшение” будет влиять на точность нахождения столкновения. В качестве примера я приведу картинку, где зеленый круг – объект, а синяя полоска — препятствие:

Если бы для рассчета мы брали “зону поиска” равную (object.size*2)*(object.size*2) (object.size — радиус), то столкновение было бы установлено, но если для рассчета выбран всего 1 пиксель (центр), то столкновение не определено.
Как поступать Вам – дело сугубо личное, но я решил пожертвовать точностью и стал работать с центром объекта.
Столкновение установлено, но что дальше? Как быть со страшным словом “нормаль”?

Находим нормаль

Тут есть два способа – правильный и мой.
Способ 1. Правильный:
  1. находим “зону” касания
  2. находим точки границы препятствия из этой зоны
  3. интерполируем их и находим уравнение нормали в точке касания


Способ 2. Неправильный:
  1. получаем зону пересечения объекта и препятствия.
  2. находим центр этой зоны:
    var avgPoint{x:0, y:0, number:0};
    for(var i = 0; i < pixels2.length; i += 4 ) {
      if((pixels1[i+3] != 0) && (pixels2[i+3] != 0)) {
        avgPoint.x += (i/4)%(this.size*2);
        avgPoint.x += Math.round((i/4)/(this.size*2));
      }
    }
    avgPoint.x = Math.round((avgPoint.x / avgPoint.number) + this.center.x - this.size);
    avgPoint.y = Math.round((avgPoint.y / avgPoint.number) + this.center.y - this.size);
  3. соединяем найденный центр “зоны пересечения” (avgPoint.x, avgPoint.y) с центром объекта. Это и будет нормаль.


Меняем скорости

Итак, снова открываем учебники и узнаем, что при отражении нормальная составляющая скорости меняет знак, а тангенциальная (перпендикулярная нормали) остается неизменной.
Значит имеем задачу – разложить скорости из (x,y) системы координат в (n,t) систему координат. Тут на помощь приходит обычная геометрия из старших классов:
var hyp = Math.hypotenuse((avgPoint.y - object.center.y),(avgPoint.x - object.center.x))
var sinNA = (avgPoint.y – object.center.y)/hyp;
var cosNA = (object.center.x - avgPoint.x)/hyp;
var nSpeed = this.speed.x * cosNA - this.speed.y * sinNA;
var tSpeed = this.speed.x * sinNA + this.speed.y * cosNA;
nSpeed = -nSpeed;
object.speed.x = (tSpeed * sinNA + nSpeed * cosNA);
object.speed.y = (tSpeed * cosNA - nSpeed * sinNA);


Вот и все, наш объект умеет менять направления скоростей в зависимости от формы встреченного препятствия. Остается объединить все функции и объекты в конечном скрипте и увидеть
результат.
На этом моя статься закончена, спасибо за внимание!
Tags:
Hubs:
Total votes 71: ↑65 and ↓6+59
Comments59

Articles