WPF: поиск элемента по пути

Question

Я не отмечал этот вопрос Ответил пока.
Текущий принятый ответ был принят автоматически из-за ограничения по времени Bounty

---

Применительно к этой программируемой игре Я сейчас строю.

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

---

Теперь мне нужен способ определить, обнаружил ли робот другого робота под определенным углом (в зависимости от того, куда может быть направлена ​​турель):

альтернативный текст http://img21.imageshack.us/img21/7839/robotdetectionrg5.jpg

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

Боты - это просто полотна, которые постоянно переводятся на Боевой Арене (еще один холст).

Я знаю заголовок турели (то, как она будет в настоящее время смотреть), и с этим мне нужно выяснить, есть ли на ее пути какие-либо боты (и путь должен быть определен в виде «точки обзора», изображенный на изображении выше в форме красного «треугольника». Я надеюсь, что изображение проясняет то, что я пытаюсь передать.

Я надеюсь, что кто-то может подсказать мне, как математика участвует в решении этой проблемы.

---

[UPDATE]

Я пробовал расчеты, которые вы мне сказали, но они не работают должным образом, поскольку, как видно из изображения, бот1 не должен видеть бот2. Вот пример:

альтернативный текст http://img12.imageshack.us/img12/7416/examplebattle2.png

В приведенном выше сценарии Бот 1 проверяет, видит ли он Бот 2. Вот подробности (согласно ответу Уэйлона Флинна ):

angleOfSight = 0.69813170079773179 //in radians (40 degrees)
orientation = 3.3 //Bot1's current heading (191 degrees)

x1 = 518 //Bot1's Center X
y1 = 277 //Bot1's Center Y

x2 = 276 //Bot2's Center X
y2 = 308 //Bot2's Center Y

cx = x2 - x1 = 276 - 518 = -242
cy = y2 - y1 = 308 - 277 =  31

azimuth = Math.Atan2(cy, cx) = 3.0141873380511295

canHit = (azimuth < orientation + angleOfSight/2) && (azimuth > orientation - angleOfSight/2)
       = (3.0141873380511295 < 3.3 + 0.349065850398865895) && (3.0141873380511295 > 3.3 - 0.349065850398865895)
       = true

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

Что я делаю не так в приведенных выше расчетах?

Answer 1

угол между роботами равен arctan (x-distance, y-distance) (большинство платформ предоставляют этот arctan с двумя аргументами, который выполняет регулировку угла за вас. Затем вам просто нужно проверить, меньше ли этот угол, чем некоторое число от текущего курса.

РЕДАКТИРОВАТЬ: извините за смутный ответ, но вот некоторые из моих заметок по вашему обновлению:

• координаты будут в декартовой системе, а не в оконной системе. Это приводит к некоторым различным числам

  Ориентация: 3.3 <- это неправильно, бот1 выглядит так, как будто он ориентирован около 4 или около того. 191 градус будет примерно в положении 8:30 на часах, которые почти прямо направлены на резервуар 2. Неудивительно, что система возвращает «Видимый»! </p>

  азимут: cy будет -31 (под 31 единицей), а не 31.

С этими изменениями вы должны получить правильные результаты.

Answer 2

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

http://en.wikipedia.org/wiki/Dot_product

Это может выглядеть пугающе, но это не так уж и плохо. Это самый правильный способ справиться с проблемой FOV, и прелесть в том, что одна и та же математика работает независимо от того, работаете ли вы с 2D или 3D (именно тогда вы знаете, что решение верное).

(ПРИМЕЧАНИЕ. Если что-то не понятно, просто спросите в разделе комментариев, и я заполню недостающие ссылки.)

Шаги:

1) Вам нужны два вектора, один из которых является вектором курса основного танка. Еще один вектор, который вам нужен, зависит от положения рассматриваемого резервуара и основного резервуара.

Для нашего обсуждения предположим, что вектор курса для основного танка равен (ax, ay), а вектор между позицией основного танка и целевым танком (bx, by). Например, если основной танк находится в точке (20, 30), а целевой танк - в (45, 62), то вектор b = (45 - 20, 62 - 30) = (25, 32).

Опять же, для целей обсуждения предположим, что вектор курса основного танка равен (3,4).

Основная цель здесь - найти угол между этими двумя векторами, и точечное произведение может помочь вам получить это.

2) Точечный продукт определяется как

a * b = | a || b | сов (угол) * * тысяча двадцать-две

читается как (точечное произведение) b, поскольку a и b не являются числами, они являются векторами.

3) или выражается иначе (после некоторой алгебраической манипуляции):

угол = acos ((a * b) / | a || b |)

угол - это угол между двумя векторами a и b, поэтому одна только эта информация может сказать вам, может ли один танк видеть другой или нет.

| | является величиной вектора a, которая согласно теореме Пифагора является просто sqrt (ax * ax + ay * ay), то же самое относится к | b |.

Теперь возникает вопрос, как вы узнаете a * b (точечное произведение b), чтобы найти угол.

4) Здесь приходит спасение. Оказывается, что скалярное произведение также можно выразить так:

a * b = топор * bx + ay * на

То есть угол = acos ((ax * bx + ay * by) / | a || b |)

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

Итак, используя приведенные выше примеры чисел:

На основе наших примеров:

a = (3, 4) b = (25, 32)

| | = sqrt (3 * 3 + 4 * 4)

| б | = sqrt (25 * 25 + 32 * 32)

угол = acos ((20 * 25 + 30 * 32) / | a || b |

(Обязательно конвертируйте полученный угол в градусы или радианы, прежде чем сравнивать его с вашим значением поля зрения)

Answer 3

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

/// assumming canvas1 is firing on canvas2

// positions of canvas1 and canvas2, respectively
// (you're probably tracking these in your Tank objects)
int x1, y1, x2, y2;

// orientation of canvas1 (angle)
// (you're probably tracking this in your Tank objects, too)
double orientation;
// angle available for firing
// (ditto, Tank object)
double angleOfSight;

// vector from canvas1 to canvas2
int cx, cy;
// angle of vector between canvas1 and canvas2
double azimuth;
// can canvas1 hit the center of canvas2?
bool canHit;

// find the vector from canvas1 to canvas2
cx = x2 - x1;
cy = y2 - y1;

// calculate the angle of the vector
azimuth = Math.Atan2(cy, cx);
// correct for Atan range (-pi, pi)
if(azimuth < 0) azimuth += 2*Math.PI;

// determine if canvas1 can hit canvas2
// can eliminate the and (&&) with Math.Abs but this seems more instructive
canHit = (azimuth < orientation + angleOfSight) &&
    (azimuth > orientation - angleOfSight);

Answer 4

Пара предложений после реализации чего-то подобного (давно!):

Следующее предполагает, что вы проходите через всех ботов на поле битвы (не очень хорошая практика, но быстро и легко заставить что-то работать!)

1) Намного проще проверить, находится ли бот в радиусе действия, чем если его можно увидеть в поле зрения, например,

int range = Math.sqrt( Math.abs(my.Location.X - bots.Location.X)^2 + 
            Math.abs(my.Location.Y - bots.Location.Y)^2 );

if (range < maxRange)
{
    // check for FOV
}

Это гарантирует, что он потенциально может коротко замкнуть большую часть проверки FOV и ускорить процесс запуска симуляции. Как предостережение, вы можете иметь некоторую случайность здесь, чтобы сделать его более интересным, например, что после определенного расстояния шанс увидеть линейно пропорционален радиусу действия бота.

2) В этой статье , кажется, есть материал для расчета FOV.

3) Будучи выпускником искусственного интеллекта ... раньше вы пробовали Нейронные сети, вы могли бы научить их распознавать, находится ли робот в зоне действия и является ли действительной целью. Это сведет на нет любую ужасно сложную и запутанную математику! У вас может быть многослойный персептрон [1] , [2] , который подается в координаты ботов и цели, и в конце получает хорошее решение о пожаре / отсутствии огня. , ВНИМАНИЕ: Я чувствую себя обязанным сказать вам, что эта методология не самая легкая для достижения и может быть ужасно разочаровывающей, когда она идет не так. Из-за (простой) недетерминированной природы этой формы алгоритма отладка может быть проблемой. Кроме того, вам понадобится какая-то форма обучения либо Back Propogation (с обучающими случаями), либо генетический алгоритм (еще один сложный процесс для совершенствования)! Если бы у меня был выбор, я бы использовал номер 3, но его нет для всех!

Answer 5

Примерно так в классе вашего бота (код C #):

/// <summary>
/// Check to see if another bot is visible from this bot's point of view.
/// </summary>
/// <param name="other">The other bot to look for.</param>
/// <returns>True iff <paramref name="other"/> is visible for this bot with the current turret angle.</returns>
private bool Sees(Bot other)
{
    // Get the actual angle of the tangent between the bots.
    var actualAngle = Math.Atan2(this.X - other.X, this.Y - other.Y) * 180/Math.PI + 360;

    // Compare that angle to a the turret angle +/- the field of vision.
    var minVisibleAngle = (actualAngle - (FOV_ANGLE / 2) + 360);
    var maxVisibleAngle = (actualAngle + (FOV_ANGLE / 2) + 360); 
    if (this.TurretAngle >= minVisibleAngle && this.TurretAngle <= maxVisibleAngle)
    {
        return true;
    }
    return false;
}

Примечания:

• Значения + 360 предназначены для принудительного задания любых отрицательных углов до соответствующих им положительных значений и для сдвига граничного случая угла 0 в более легкое для проверки расстояние.
• Это может быть выполнимо, используя только радианные углы, но я думаю, что они грязные и трудно читаемые: /
• Подробнее см. Документацию Math.Atan2 .
• Я настоятельно рекомендую изучить XNA Framework , так как он создан с учетом игрового дизайна. Однако он не использует WPF.

Это предполагает, что:

• нет препятствий, мешающих обзору
• Класс бота имеет свойства X и Y
• Свойства X и Y находятся в центре бота.
• Bot-класс - свойство TurretAngle, которое обозначает положительный угол башни относительно оси x против часовой стрелки.
• Бот-класс имеет статический угол константы, называемый FOV_ANGLE, обозначающий поле зрения башни.

Отказ от ответственности: Это не проверено и даже не проверено для компиляции, адаптируйте его при необходимости.

Answer 6

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

Единственной сложностью будет обработка граничного случая, когда угол изменяется от 2pi радиан до 0.

Answer 7

Похоже, что ваша обновленная проблема возникла с разных «нулевых» направлений, равных orientation и azimuth: orientation, равное 0, кажется, означает «прямо вверх», но azimuth, равное 0, «прямо вправо».

Answer 8

Действительно ли у вашей башни такая большая стрельба? Путь, по которому идет пуля, будет прямой линией, и она не станет больше по мере движения. У вас должен быть простой вектор в направлении башни, представляющей зону поражения башни. Каждый танк будет иметь ограничивающий круг, представляющий их уязвимую область. Затем вы можете продолжить, как они делают с трассировкой лучей. Простое пересечение луча / круга. Посмотрите на раздел 3 документа Пересечение линейных и круговых компонентов в 2D .

Answer 9

Глядя на оба ваших вопроса, я думаю, что вы можете решить эту проблему, используя предоставленную математику, затем вам придется решать многие другие вопросы, связанные с обнаружением столкновений, стрельбой пулями и т. Д. Это не тривиально, особенно если ваши боты не квадратные Я бы порекомендовал взглянуть на физические движки - farseer на codeplex - хороший пример WPF, но это превращает его в проект, намного больший, чем задача для старшеклассников.

Лучший совет, который я получил для высоких оценок, делай что-то простое действительно хорошо, не делай что-то блестящее.