Как узнать объекты на условной линии

[Korchy]

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

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

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

[HardCoder]

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

[expl]

           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;
	}

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

           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, то ситуация выглядит так:

[gloomyBrain]

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

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

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

[wvxvw]

Сообщение от HardCoder

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

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

Сообщение от expl

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

           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

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

[expl]

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

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