Технология Canvas Core — как реализовать обнаружение столкновений

Это изучение и обзор шестой серии CONVAS SIDEL CONVAS, полные подробные примечания:технология сердцевины холста.

в предыдущем постеТехнология Canvas Core — как реализовать сложную анимациюВ примечаниях мы подробно обсудили необходимость учитывать факторы времени, физические факторы и т. д. при создании сложных анимаций, а также рассмотрели, как использовать функции плавности для искажения временной шкалы для достижения нелинейного движения, такого как обычное ускорение, ослабление. , и легкость. Медленный вход и выход и т. д. В играх или анимации движущиеся объекты могут сталкиваться друг с другом в процессе изменения.В этой статье мы подробно узнаем, как выполнять обнаружение столкновений.

Обнаружение граничного значения

Простейшим методом обнаружения является обнаружение граничных значений, которое заключается в условной оценке некоторых признаков движущегося объекта, если это условие выполняется, это означает, что произошло столкновение. Например, в примере из предыдущей статьи мяч падает свободно.При определении того, сталкивается ли мяч с землей, мы определяем, достигает ли высота падения мяча fh высоты dh самого мяча от земли.Если fh > dh, значит, мяч столкнулся с землей.

    let distance = ball.currentSpeed * t; 
    if (ball.offset + distance > ball.verticalHeight) {
      //落到地面了，发生了碰撞
      // ...
    } else {
      // 还没有落到地面，没有发生碰撞
      ball.offset += distance;
    }

Вот полный онлайн-пример моего мяча в свободном падении.

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

Обнаружение внешней графики

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

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

Столкновение прямоугольника и прямоугольника,

Вот все ситуации, в которых сталкиваются два прямоугольника.Конкретная реализация кода в холсте выглядит следующим образом:

  /* 判断是否两个矩形发生碰撞 */
  private didRectCollide(sprite: RectSprite, otherSprite: RectSprite) {
    let horizontal = sprite.left + sprite.width > otherSprite.left && sprite.left < otherSprite.left + otherSprite.width;
    let vertical = sprite.top < otherSprite.top + otherSprite.height && sprite.top + sprite.height > otherSprite.top;
    return horizontal && vertical;
  }

На самом деле, нужно определить, перекрываются ли два прямоугольника в горизонтальном и вертикальном направлениях соответственно.

случай столкновения круга и круга,

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

Конкретная реализация кода в холсте выглядит следующим образом:

  /* 判断是否两个圆发生碰撞 */
  private didCircleCollide(sprite: CircleSprite, otherSprite: CircleSprite) {
    return distance(sprite.x, sprite.y, otherSprite.x, otherSprite.y) < sprite.radius + otherSprite.radius;
  }

Случаи столкновения прямоугольников и кругов,

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

В этом случае координата ближайшей точки по оси X равна координате по оси X левого верхнего угла прямоугольника и равна координате по оси Y центра окружности, поэтому можно полученный, (rect_x,circle_y) . Конкретная реализация кода в холсте выглядит следующим образом:

  /* 判断是否矩形和圆形发生碰撞 */
  private didRectWidthCircleCollide(rectSprite: RectSprite, circleSprite: CircleSprite) {
    let closePoint = { x: undefined, y: undefined };
    if (circleSprite.x < rectSprite.left) {
      closePoint.x = rectSprite.left;
    } else if (circleSprite.x < rectSprite.left + rectSprite.width) {
      closePoint.x = circleSprite.x;
    } else {
      closePoint.x = rectSprite.left + rectSprite.width;
    }
    if (circleSprite.y < rectSprite.top) {
      closePoint.y = rectSprite.top;
    } else if (circleSprite.y < rectSprite.top + rectSprite.height) {
      closePoint.y = circleSprite.y;
    } else {
      closePoint.y = rectSprite.top + rectSprite.height;
    }
    return distance(circleSprite.x, circleSprite.y, closePoint.x, closePoint.y) < circleSprite.radius;
  }

Вот онлайн-пример моего обнаружения столкновений с внешней графикой..

Обнаружение Raycast

Метод Raycasting: нарисуйте линию, совпадающую с вектором скорости объекта, а затем начните с другого объекта, который нужно обнаружить, нарисуйте вторую линию и определите, происходит ли столкновение в соответствии с пересечением двух линий.

Метод приведения лучей обычно использует обнаружение граничных значений, чтобы делать строгие и точные суждения.Этот метод требует, чтобы мы непрерывно вычисляли координаты пересечения двух векторов скорости в обновлении анимации и оценивали, выполняются ли условия столкновения в соответствии с координатами пересечения. Условие, нам также необходимо использовать метод обнаружения граничного значения, чтобы определить, удовлетворяет ли движущийся объект условию граничного значения, и только когда оно одновременно выполняется, это будет рассматриваться как столкновение. Этот тип обнаружения обычно имеет высокую точность, особенно для объектов с высокой скоростью движения. Пример метания ведра с маленьким мячиком, код обнаружения следующий,

  /* 是否发生碰撞 */
  public didCollide(ball: CircleSprite, bucket: ImageSprite) {
    let k1 = ball.verticalVelocity / ball.horizontalVelocity;
    let b1 = ball.y - k1 * ball.x;
    let inertSectionY = bucket.mockTop; //计算交点Y坐标
    let insertSectionX = (inertSectionY - b1) / k1; //计算交点X坐标
    return (
      insertSectionX > bucket.mockLeft &&
      insertSectionX < bucket.mockLeft + bucket.mockWidth &&
      ball.x > bucket.mockLeft &&
      ball.x < bucket.mockLeft + bucket.mockWidth &&
      ball.y > bucket.mockTop &&
      ball.y < bucket.mockTop + bucket.mockHeight
    );
  }
}

Вот мой онлайн-пример обнаружения raycast.

Отдельное обнаружение вала

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

Основы вектора:

В плоской двумерной системе координат мы можем использовать вектор для представления местоположения точки. Представление вектора должно указывать от начала координат (0, 0) до целевой точки (x, y).
Два вектора вычитаются, и в результате получается еще один новый вектор.
Сделайте скалярное произведение двух векторов, чтобы получить прогнозируемое значение.
Единичный вектор — это вектор длиной 1, и его фактическая функция — представлять направление.
Вектор, перпендикулярный другому вектору, называется вектором нормали.

Как видно на рисунке, $\overrightarrow{oa} -\overrightarrow{ob} = \overrightarrow{ba}$ , $\overrightarrow{oa} * \overrightarrow{ob} = |od|$ . Каждую вершину избыточного выпуклого многоугольника мы можем представить в виде вектора.

Идея обнаружения оси разделения,

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

  /* 判断是否发生碰撞 */
  public didCollide(sprite: Sprite, otherSprite: Sprite) {
    let axes1 = sprite.type === 'circle' ? (sprite as Circle).getAxes(otherSprite as Polygon) : (sprite as Polygon).getAxes();
    let axes2 = otherSprite.type === 'circle' ? (otherSprite as Circle).getAxes(sprite as Polygon) : (otherSprite as Polygon).getAxes();
    // 第一步：获取所有的投影轴
    // 第二步：获取多边形在各个投影轴的投影
    // 第三步：判断是否存在一条投影轴上，多边形的投影不相交，如果存在不相交的投影则直接返回false，如果有所的投影轴上的投影都存在相交，则说明相碰了。
    let axes = [...axes1, ...axes2];
    for (let axis of axes) {
      let projections1 = sprite.getProjection(axis);
      let projections2 = otherSprite.getProjection(axis);
      if (!projections1.overlaps(projections2)) {
        return false;
      }
    }
    return true;
  }
}

Далее мы выполним эти три шага, чтобы шаг за шагом реализовать метод обнаружения оси разделения.

Получить ось проекции

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

//获取凸多边形的投影轴  
public getAxes() {
    let points = this.points;
    let axes = [];
    for (let i = 0, j = points.length - 1; i < j; i++) {
        let v1 = new Vector(points[i].x, points[i].y);
        let v2 = new Vector(points[i + 1].x, points[i + 1].y);
        axes.push(
            v1
            .subtract(v2)
            .perpendicular()
            .normalize(),
        );
    }
    let firstPoint = points[0];
    let lastPoint = points[points.length - 1];
    let v1 = new Vector(lastPoint.x, lastPoint.y);
    let v2 = new Vector(firstPoint.x, firstPoint.y);
    axes.push(
        v1
        .subtract(v2)
        .perpendicular()
        .normalize(),
    );
    return axes;
 }

После получения оси проекции графика, который нужно обнаружить, нам нужно рассчитать проекцию графика на каждую ось проекции.

  public getProjection(v: Vector) {
    let min = Number.MAX_SAFE_INTEGER;
    let max = Number.MIN_SAFE_INTEGER;
    for (let point of this.points) {
      let p = new Vector(point.x, point.y);
      let dotProduct = p.dotProduct(v);
      min = Math.min(min, dotProduct);
      max = Math.max(max, dotProduct);
    }
    return new Projection(min, max);
  }

Наконец, определите, перекрываются ли проекции

  /* 投影是否重叠 */
  overlaps(p: Projection) {
    return this.max > p.min && p.max > this.min;
  }

Среди них, если это круговой и выпуклый многоугольник, он особенный, и есть только один выпускной вал, когда проекционная ось, соответствующая кругу, и круг окружен до грани самой последней вершины от полигона. Отказ

  //获取圆的投影轴
  public getAxes(polygon: Polygon) {
    // 对于圆来说，获取其投影轴就是将圆心与他距离多边形最近顶点的连线
    let { x, y } = this;
    let nearestPoint = null;
    let nearestDistance = Number.MAX_SAFE_INTEGER;
    for (let [index, point] of polygon.points.entries()) {
      let d = distance(x, y, point.x, point.y);
      if (d < nearestDistance) {
        nearestDistance = d;
        nearestPoint = point;
      }
    }
    let v1 = new Vector(x, y);
    let v2 = new Vector(nearestPoint.x, nearestPoint.y);
    return [v1.subtract(v2).normalize()];
  }

Вот мой онлайн-пример обнаружения оси разделения.

резюме

В этой заметке подробно описываются методы обнаружения столкновений в 2D-графике.Более простыми методами являются метод внешней графики и метод обнаружения граничных значений, которые являются относительно неточными.Более сложные и точные методы – это метод луча и метод осей разделения. . В соответствии с различными сценариями и требованиями к точности мы выбираем разные методы. Другие, в дополнение к вышеперечисленным, существуют также такие методы, как обнаружение пикселей, которые также могут обеспечить обнаружение столкновений.Обнаружение пикселей обнаруживается в единицах пикселей.Если есть непрозрачные пиксели, перекрывающиеся по одной и той же координате, это означает, что произошло столкновение , Конкретную реализацию можно проверитьPixel accurate collision detection with Javascript and Canvas.

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

Ссылаться на

«Подождите, я касаюсь!» — обычное обнаружение 2D-столкновений [Некоторые изображения относятся к этой статье, эта статья хорошо написана, читателям рекомендуется взглянуть]
«Основная технология HTML5 Canvas: графика, анимация и разработка игр»