Более быстрый метод, чем Point.distance для расчета столкновения между объектами?

Question

Я разрабатываю игру, в которой у меня много столкновений, и я быстро заметил, что мое узкое место - это линия:

if(Point.distance(_point1, _point2) < collisionDistance){
  //do stuff
}

где _point1 и _point2 - статические переменные, в которых хранятся позиции объектов, которые могут столкнуться, если collisionDistance достаточно низкое.

Знаете ли вы какой-либо более эффективный метод для проверки простого столкновения между двумя кругами?

Answer 1

Встроенная функция Point.distance очень медленная, поэтому предоставьте свою собственную.

Есть много оптимизаций для расстояния между двумя 2D точками (вы используете круги, поэтому отрегулируйте расстояние столкновения по радиусу круга), и многое зависит от того, как оптимизируют разные компиляторы, но в этом случае мы только говорить о компиляторе asc.

Первый базовый путь - евклидово (пифагорейское) расстояние, которое каждый изучает в триг. учебный класс. Другие методы, такие как метод Таксикаб / Манхэттен, хорошо работают для игр на основе сетки / тайла. Использование быстрого обратного квадратного корня очень быстро, но сложно (невозможно?) Реализовать в прямом ActionScript, но это можно сделать в байт-коде ABC (через ALCHEMY, device, As3c и т. Д.) (Так я и делал действительно сложная проблема на расстоянии... но обычно это не стоит дополнительной работы).

Вот часть теста, который я сделал давным-давно, когда оптимизировал игру. Я немного исправил это и перезапустил некоторые основные методы расстояний, чтобы дать вам преимущество:

Помните, что никогда не тестировали время с помощью проигрывателя DEBUG, всегда используйте версию Release (время выполнения проигрывателя отладки может варьироваться в зависимости от функции / функции относительно проигрывателя release, в 10 раз медленнее в некоторых случаях)...

Air / Flash v19 - релиз плеера:

• Общее время (мс): 243 (Point.distance)
• Общее время (мс): 82 (PythaDistance)
• Общее время (мс): 72 (PythaDistanceNoSqrt)
• Общее время (мс): 79 (ManhattanTaxiCab)

• Общее время (мс): 106 (ManhattanTaxiCabNoAbs)

  private var p1:Point = new Point(5, -6);
  private var p2:Point = new Point(-2.5, 3.5);
  private var d1:Number = 0.0;
  private var collisionDistance:Number = 10.0;
  private var collisionDistanceD:Number = collisionDistance * collisionDistance;
  
  private var t1:int = 0;
  private var t2:int = 0;
  private var t3:int = 0;
  
  private function pointDistance(x:int):int {
      t1 = getTimer();
      for (var i:int = 0; i < x; i++) {
          d1 = Point.distance(p1, p2);
      }
      if (d1 < collisionDistance) {
          trace("Collision");
      }
      t2 = getTimer();
      return t2 - t1;
  }
  
  private var dx;
  Number;
  private var dy:Number;
  
  private function PythaDistance(x:int):int {
      t1 = getTimer();
      for (var i:int = 0; i < x; i++) {
          dx = p1.x - p2.x;
          dy = p1.y - p2.y;
          d1 = Math.sqrt(dx * dx + dy * dy);
      }
      if (d1 < collisionDistance) {
          trace("Collision");
      }
      t2 = getTimer();
      return t2 - t1;
  }
  
  private function PythaDistanceNoSqrt(x:int):int {
      t1 = getTimer();
      for (var i:int = 0; i < x; i++) {
          dx = p1.x - p2.x;
          dy = p1.y - p2.y;
          d1 = (dx * dx + dy * dy);
      }
      if ((d1 * d1) < collisionDistanceD) {
          trace("Collision");
      }
      t2 = getTimer();
      d1 = d1 / 2; // show dist. compared to other ways
      return t2 - t1;
  }
  
  private function ManhattanTaxiCab(x:int):int {
      t1 = getTimer();
      for (var i:int = 0; i < x; i++) {
          dx = p1.x - p2.x;
          dy = p1.y - p2.y;
          d1 = Math.abs(dx) + Math.abs(dy);
      }
      if ((d1 * d1) < collisionDistance) {
          trace("Collision");
      }
      t2 = getTimer();
      return t2 - t1;
  }
  
  private function ManhattanTaxiCabNoAbs(x:int):int {
      t1 = getTimer();
      for (var i:int = 0; i < x; i++) {
          dx = p1.x - p2.x;
          if (dx < 0) dx *= -1;
          dy = p1.y - p2.y;
          if (dy < 0) dy *= -1;
          d1 = dx + dy;
      }
      if ((d1 * d1) < collisionDistance) {
          trace("Collision");
      }
      t2 = getTimer();
      return t2 - t1;
  }
  

Существует много способов вычислить расстояние между точками 2D, и многое может зависеть от того, насколько точным вам должно быть расстояние / столкновение. В зависимости от вашей частоты кадров, размера объектов, размера экрана, скорости / движения спрайтов и т. Д.... при большом количестве подделок чисел может происходить без уведомления пользователя (т. Е. Использование целочисленной математики в сравнении с плавающей запятой может иметь огромное значение).