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


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

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


Итак, с чего бы начать? Мне кажется, что лучше всего начать со статических объектов, ибо с ними намного проще работать (не надо заботиться о перерисовке, изменении положения/формы и прочих вещах).
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);


Вот и все, наш объект умеет менять направления скоростей в зависимости от формы встреченного препятствия. Остается объединить все функции и объекты в конечном скрипте и увидеть
результат.
На этом моя статься закончена, спасибо за внимание!
Поделиться публикацией

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 59

    +4
    Я правильно понимаю, что в статье описывается поддержка объектов исключительно в форме круга? Мне было бы интересно работать с объектом произвольной формы, заданной, например растром. И с возможностью поворота.
      +1
      нет, увы, понимаете не совсем правильно.
      Я просто рассмотрел пример с кругом, хотя сам объект может быть любой формы (той, что Вы запихнете в object.buffer).
      Соответственно после этого немного изменится просчет «нормали», поэтому объект себя будет вести, опять же, более или менее правдоподобно.
      Вот так может считаться «нормаль» при форме, отличной от круга:
      не круг
        +2
        При форме, отличной от круга, будет ещё важна угловая скорость и угол поворота. И для расчёта скорости после столкновения мало будет посто инвертировать нормальную составляющую.
        0
        картинку плохо вставил:
        0
        То как обьект выглядит это одно, то как работает физика — совсем другое.
        Для физики нужно использовать физ движки или если так хочется изобретать велосипед — писать свой физический движок.
        Но нельзя мешать в одну кучу рисование и физическое поведение.
          0
          не спорю, поэтому и пишу:
          «более или менее правдоподобно», а не «как надо»
            0
            А зачем писать топик о том, как НЕнадо делать? Ктото возьмет и сделает, все будет дико тормозить, человек потратит кучу времени, играть будет невозможно…
              +1
              Вообще-то иногда другого варианта и нет. С другой стороны, такой вариант — не всегда плохой.

              Что, если надо обрабатывать столкновения со спрайтом, когда мы не знаем, какая фигура в нём? Или это какая-то хитрая фигура. С чего вы взяли, что решить её математически будет дешевле, чем решить графически?

              Согласен, возможно, такой подход не совсем по феншую, но это зависит от условий.

              И да, я думаю, что в тех же Worms столкновения просчитываются подобным образом.
                0
                другой вариант есть всегда. И дело в том, что «правильный» вариант будет проще для написания.

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

                «решить графически» — графически итак ничего не решается. Зато немеряно процессорного времени теряется на выгребание пикселей из канваса.

                как считают в вормсах ни я не вы не знаем, но подозреваю там считают какраз по феншую
                  +1
                  Ну в математике ведь некоторые задачи решаются графическим методом ;)
                  Я согласен, что отделение логики от представления — это правильно.
                  Выгребание небольшого количества пикселей из канваса — не трудоёмкая операция.
                    –1
                    графический метод решения — например рисуете две прямые и «на глаз» смотрите где они пересекаются.
                    Подходит для человека, так как даже простейшие арифметические операции человек в уме (и на бумаге) решает с громадным трудом.

                    Вы действительно думаете, что «графический» метод подходит для компьютера?
                      +1
                      Когда точность — не критична, то вполне может подходить.
                        0
                        ???
                        Для того чтоб найти пересечение аналитически — достаточно функции в 2 строчки.
                        Для того чтоб найти графически надо нарисовать 2 прямые в памяти, что уже тяжелая операция, пробежать по пикселам и посмотреть закрашены ли пиксели в обоих прямых.

                        Результат — хуже точность, в 10 раз больше кода, на многие порядки больше нагрузка на проц, используется куча памяти. Профит? Сделать себе больно?
                          +1
                          Для двух прямых — не подходит) Для сложной фигуры, которая отрисовывается один раз и много раз считывается — подходит)
                            0
                            для сложной фигуры тоже можно считать просто. Но если месье любит писать в 10 раз больше кода, который при этом будет тормозитб, то не мне ему советовать.
                              +1
                              Простите, как посчитать пересечение фигуры слева и фигуры справа? Или даже фигуры справа с точкой. У меня с алгоритмами плохо, если расскажете — буду рад услышать:

                                0
                                Разбить на полигоны.

                                А вы думаете метод указаный в статье будет адекватно просчитывать физику для этих двух фигур? Вы очень ошибаетесь. Тот метод и для материальной точки очень плохо считает, что можно увидеть ниже в коментах.
                                  0
                                  Просто как факт. Во флеше для подобных изображений используется именно попиксельное сравнение на базе BitmapData и hitTest ;) Это называется "Pixel-level collision detection".
                                    0
                                    А физика? Задача стояла физику считать, а не просто пересечение пикселов.
                                    Да. если стоит задача найти пересечение пикселов, то надо просто найти пересечение пикселов. Но задача ведь стоит другая.

                                    В играх на флеше это никто не использует ибо очень тормознуто.
                                    0
                                    для точки он вообще не работает… а «баги» всплывают, как я сказал ниже, изза того, что я пытаюсь работать с фигурой как с точкой (для увеличения быстродействия)
                      0
                      На счёт другого варианта. Допустим, пользователь присылает картинку, нарисованную в фотошопе, а мы по ней должны прыгать шариком. Есть ли метод нахождения коллизий кроме графического? ;)
                        +4
                        есть — пробежать по графике, построить 1 раз по ней физику и работать с физикой.
                    0
                    под словами «не надо» подразумевалось не «тормознутость» алгоритмов или еще что-либо, а всего-навсего банальная неточность в определении направления отскока.
                    Вот пример:
                    если мы считаем полет ракеты, или еще что-нибудь важное, то не будем производить рассчеты «на глаз», так ведь?
                    верно и обратное, зачем нам знать точное направление отскока мячика, если необходимо всего лишь показать «видимость» правильного движения? (как в случае с данным примером)
                    Я показал всего лишь одну из возможных реализаций… использовать ее или нет — дело каждого. Лично меня она пока что устраивает.

                    Но за замечание спасибо, высказывание «Способ 2. Неправильный» действительно может ввести в заблуждение. Исправлюсь :)
                +2
                Это круто, жду от автора еще чего нить про физику в канвасе и все такое.
                  0
                  спасибо, попробую оправдать ожидания :)
                  –1
                  “угол падения равен углу отражения”

                  Обычно говорят «угол отражения равен углу падения», ибо иначе немного нелогично.
                    0
                    Перезалейте фото с дропбокса пожалуйста.
                      0
                      да, конечно, через несколько минут
                        +2
                        сделано :)
                        +2
                        У меня от стенок отскакивает замечательно, а вот от «горки» с глюками и некрасиво, проваливаясь до центра в препятствие…
                          +2
                          Особенно скользящие столкновения
                            0
                            еще можно получить скорость (NaN; NaN)
                              0
                              при вылете объекта за пределы поля. Почему он может вылететь — описал ниже.
                            0
                            да, я знаю о подобной проблеме.
                            попробую доходчиво объяснить, в чем ее суть:
                            после определения касания, шарик необходимо «выдвинуть» за пределы ландшафта.
                            Сейчас я это делаю так:
                            while(imgData[3] != 0) {
                            toX = (toX — stepX);
                            toY = (toY — stepY);
                            imgData = where.ctx.getImageData(toX,toY, 1,1).data;
                            }

                            то есть выгоняю только центр объекта за пределы ландшафта. Это неправильно. Как избавиться? есть 2 варианта:
                            1) более точно считать касание (а не по 1 пикселю как сейчас).
                            2) сильнее «выдвигать» объект из препятствия.
                            при первом способе мы теряем быстродействие. При втором шарик будет «дергаться» при каждом отскоке.
                            Оперируя этими двумя способами можно добиться желаемого эффекта. У каждого этот «желаемый эффект» будет своим.
                            +3
                            Есть еще третий (почти правильный), но более простой для реализации способ.
                            image
                            Найти точки пересечения контуров препятствия и объекта (A и B).
                            Найти серединку этого отрезка (С).
                            Провести перпендикуляр из этой точки и найти точку пересечения этого перпендикуляра с контуром препятствия (D).
                            Луч DN и будет той самой нормалью.

                              0
                              спасибо, первый раз слышу о подобном способе.
                                0
                                Кстати форма самого объекта может быть и не круглой (сферической)
                                  0
                                  да, я уже обратил внимание. Знал бы раньше о таком способе — сделал бы так, а не по-своему.
                                0
                                На картинке это все круто, а в коде как будет выглядеть?
                                  +1
                                  довольно красиво:
                                  1) находим две точки (элементарно?)
                                  2) по двум точкам прямую (девятый, если не ошибаюсь, класс)
                                  3) эта прямая — и есть перпендикуляр к нормали. А дальше как у меня.
                                    0
                                    Совершенно верно. Самое сложное — это как раз найти те точки A, B и D
                                      0
                                      Точка D — это точка «касания». ее тоже нужно найти, и уже к этой точке строить «углы» падения и отражения
                                        0
                                        A&B ищутся довольно просто. С точкой «касания» дела обстоят сложнее. Да и нужна ли она нам? нормаль можно (не совсем точно) найти, используя только A&B, или я не прав?
                                          0
                                          Дело в том что сами A и B уже вносят искажение.
                                          Если еще и D проигнорировать, то точность еще больше пострадает.
                                          Кстати, D найти проще чем А и B.
                                            0
                                            «Кстати, D найти проще чем А и B.»
                                            не сильно затруднит описать нахождение? :)
                                              0
                                              Вообще, контуры как самих объектов, так и препятствий лучше сделать векторными, описав линии контуров отрезками и дугами окружностей. Другими словами нарисовать все (обвести все контуры) «циркулем-и-линейкой». Это позволит полностью отказаться от «попиксельной физики» и любую траекторию движения рассчитать чисто аналитически (без прорисовки на холсте). Точки пересечения двух линий, двух окружностей и одной линии с окружностью можно найти очень просто и главное — быстро, а расчет будет более точным!
                                              И, кстати, сами контуры можно не очень точно задавать — лишь бы получилась непрерывная линия (по-возможности). Начать «обводку» лучше с «округлостей», потом ответить на окружностях (и на остальных кусочках контура) точки, которые потом соединить.
                                                0
                                                просто мне интересен способ определения (и обработки) взаимодействий предметов любой формы (в том числе меняющейся) с препятствиями любой формы (в т.ч. меняющейся). Я считаю, что постоянно пересчитывать уравнения для изменившихся форм довольно долгое занятие… или я не прав?

                                                Зачем мне это нужно? хочу сделать игрушку, похожую на worms, но немного доработанную (например поиграть на самостоятельно нарисованной карте).
                                                  0
                                                  В игре Worms контур ландшафта меняется либо прямыми линиями, либо окружностями (воронки от взрывов).
                                                  Сами объекты меняются совсем даже не произвольным образом: заранее готовятся несколько изображений одного объекта, которые чередуются в заданной последовательности.
                                                  Никто не мешает одновременно с рисованием самих объектов одновременно векторизовать их контуры.
                                                    0
                                                    «векторизовать их контуры» не знаю как это сделать… что посоветуете почитать на эту тему?
                                                      0
                                                      Можно и «вручную» мышкой «потыкаться» в картинку в том же самом «пейнте», и записать в «блокноте» пары координат «х и у» для каждой точки в контуре.
                                                      То есть в итоге должен получиться один (или несколько) полигонов (многоугольники).
                                                      что-то вроде того:
                                                      10,15
                                                      20,12
                                                      25,35
                                                      25,48
                                                      8,50
                                                      10,15

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

                                                        в фотошопе делается довольно просто… но как это реализовывать на javascript? не смогли бы вы посоветовать литературы на этот счет?
                                +1
                                Почему после каждого перемещения нужно определять касания или пересечения с объектами? Почему нельзя, зная параметры движения, вычислить точку соприкосновения заранее?
                                  0
                                  Фон может поменяться в течении движения?
                                    0
                                    Ну и что, если его движение описывается какой-то функцией, что мешает решить уравнение или систему уравнений?
                                    0
                                    во первых да, фон не обязательно может быть статическим.
                                    а во вторых для проверки я беру всего 1 пиксель. По-моему это не сильно затратно.
                                    А проссчитывать я пытался, только есть проблема — округления. То ли у меня руки кривые, то ли на самом деле они так сильно влияют, но при рассчете «заранее» возникали своеобразные проблемы…
                                      0
                                      Бинго это и есть правильный способ. Если делать что-то другое то рано или поздно увеличение скорости приведет к проскакиванию объектов друг через друга. Почему автор статьи его не выбрал — не знаю.
                                        0
                                        Спасибо. Думал, что так оно и делается, поэтому этот пост меня немного удивил
                                      +1
                                      отличная программа.
                                      было бы здорово, если бы добавили туда
                                      1. гравитацию, то есть затухания полёта в направлении «вверх»
                                      2. коэффициент упругости, то есть замедление скорости при каждом соударении.

                                      хочется поймать случаи, когда круг «скатывается» по наклонной.
                                      в этом случае должен работать уже не коэффициент упругости, а коэффициент силы трения, когда шарик не «отрывается» от поверхности и исчерпал энергию для отскока. силы для качения должна добавлять гравитация.
                                        0
                                        если я не ошибаюсь, то для этой задачи проще использовать готовые движки, например, Box2D
                                        Рабочий пример.

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое