Форум Flasher.ru - Как узнать объекты на условной линии

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Как узнать объекты на условной линии (http://www.flasher.ru/forum/showthread.php?t=180089)

Коллижн луча и окружности
Все о наиболее популярных коллиженах есть здесь http://www.geometrictools.com/LibMat...ersection.html

там на С++ но нужно практически только математика, она думаю будет понятна :)

Луч - Круг смотрим это:
Wm5IntrLine2Circle2.cpp

Korchy, спасибо, но там только код без теории. С haxe-ом wvxvw я разобрался, но в С++ я ничего не понимаю :)

Цитата:

Код AS3:

           private inline function lineIntersects(target:Target,

        clickX:Float, clickY:Float):Bool

        {

                var clickAngle:Float = Math.atan2(clickX, clickY - _hunter.y);

                var cos:Float = Math.cos(target.angle);

                var sin:Float = Math.sin(target.angle);

                var radius:Float = target.radius;

                var low:Float = Math.atan2(target.x - cos * radius,

                target.y + sin * radius - _hunter.y);

                var high:Float = Math.atan2(target.x + cos * radius,

                target.y - sin * radius - _hunter.y);

                return clickAngle >= low && clickAngle <= high;

        }

Можно понадежнее (может даже попроще - ни одной тригонометрической операции):

Код AS3:

           private inline function lineIntersects(target:Target,

        clickX:Float, clickY:Float):Bool

        {

                      var raySizeX:Float = clickX - _hunter.x;

                      var raySizeY:Float = clickY - _hunter.y;

                      var raySize:Float = Math.sqrt(raySizeX * raySizeX + raySizeY * raySizeY);

                      var rayCos:Float = raySizeX / raySize;

                      var raySin:Float = raySizeY / raySize;

                      // Проекция перпендикуляра от центра цели на луч

                      // Оно же может использоваться как расстояние от охотника до объекта

                      var rayProection = rayCos * (_target.x - _hunter.x) + raySin * (_target.y - _hunter.y);

                      if (rayProection < 0) {

                              // Цель находится за спиной

                              return false;

                      }

                      // Проекция координат цели на перпендикуляр к лучу

                      var normalProection = raySin * (_target.x - _hunter.x) - rayCos * (_target.y - _hunter.y);

                      if (Math.abs(normalProection) > _target.radius) {

                             // Цель не касается луча

                             return false;

                      }

                      return true;

        }

Если правильно пнял код wvxvw, то ситуация выглядит так:
Вложение 28012

Задача сводится к:
1) пересечению отрезков, это, я думаю очевидно
2) Оптимизации перебора отрезков

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

Проверить пересечение отрезком можно так:
- проверить на пересечение прямоугольники, описывающие отрезки
- проверить что обе точки одного отрезка находятся по разные стороны другого отрезка

Цитата:

Сообщение от HardCoder (Сообщение 1081656)

wvxvw, спасибо, тоько вот как узнать какой из них был первым на пути?

В случае как в моем примере (где стреляющий двигается только вертикально) достаточно отсоритовать всех, в кого попали по Х. Нов общем случае сортировать нужно будет по расстоянию до стреляющего (что, опять же, практически уже сделано в коде в функции которая проверяет попадание уже считается расстояние до цели).
Если мишеней не много (не много, это порядка сотни), то писать алгоритмы сортировки и разбиения на кластеры, построение деревьев и т.п. - я думаю, себя не оправдает. Но если бы это была карта звездного неба в натуральную величину ;) то наверное имело бы смысл например, проверять на попадание постепенно, сдвигая границу, по которой проверять горизонтально или вертикально. Как только зафиксировано попадение - можно быть уверенным, что оно ближе всего к стреляющему. Но для этого во время движения все мишени нужно было бы пересортировывать так. И тут нужно смотреть что чаще меняется, и избегать его менять :)

Цитата:

Сообщение от expl (Сообщение 1081668)

Можно понадежнее (может даже попроще - ни одной тригонометрической операции):

Код AS3:

           private inline function lineIntersects(target:Target,

        clickX:Float, clickY:Float):Bool

        {

                      var raySizeX:Float = clickX - _hunter.x;

                      var raySizeY:Float = clickY - _hunter.y;

                      var raySize:Float = Math.sqrt(raySizeX * raySizeX + raySizeY * raySizeY);

                      var rayCos:Float = raySizeX / raySize;

                      var raySin:Float = raySizeY / raySize;

                      // Проекция перпендикуляра от центра цели на луч

                      // Оно же может использоваться как расстояние от охотника до объекта

                      var rayProection = rayCos * (_target.x - _hunter.x) + raySin * (_target.y - _hunter.y);

                      if (rayProection < 0) {

                              // Цель находится за спиной

                              return false;

                      }

                      // Проекция координат цели на перпендикуляр к лучу

                      var normalProection = raySin * (_target.x - _hunter.x) - rayCos * (_target.y - _hunter.y);

                      if (Math.abs(normalProection) > _target.radius) {

                             // Цель не касается луча

                             return false;

                      }

                      return true;

        }

Если правильно пнял код wvxvw, то ситуация выглядит так:
Вложение 28012

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

Цитата:

wvxvw, спасибо, тоько вот как узнать какой из них был первым на пути?

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