C ++ Поиск занятых полей в 2D-карте

Question

У меня есть 2d карта в моем РТС. На карте есть несколько юнитов. Я хочу проверить, есть ли какой-либо юнит в диапазоне другого. Диапазон единиц указан в полях. Смотрите изображение:

На рисунке ни один из юнитов (красный, синий, зеленый) не может атаковать друг друга. Я хочу, например, проверить, например, есть ли какие-либо единицы в диапазоне синего цвета. Ответ - нет. Я знаю диапазон и позицию синих, я также знаю позиции остальных. Я также знаю, занята ли карта xy. Как я могу это проверить?

Answer 1

Вы хотите перебрать все точки (x + i, y + j) вокруг вашего отряда на (x, y), чтобы

|i| + |j| <= R ,

, где R - диапазон атаки.(Это диск в метрике L ¹ .) Таким образом, вот так:

for (i = -R; i <= +R;  ++i)
{
    jRange = R - abs(i);
    for (j = -jRange; j <= +jRange; ++j)
    {
        // access (x + i, y + j)
    }
}

В качестве альтернативы, вы можете вдвое сократить внешний цикл, развернув

for (i = 0; i <= R; ++i)
{
    jRange = R - i;
    for (j = -jRange; i <= +jRange; ++j)
    {
        // access (x - i, y + j)
        // if (i > 0) access (x + i, y + j)
    }
}

Как говорит @Alink, вам придется так или иначе обработать границу карты.

Answer 2

На других ответах (слишком долго, как комментарий):

Поиск пути здесь действительно неправильный.Прежде всего, у нас есть сетка без ограничений и равных затрат.Использование любого вида поиска пути не является необходимым или вообще не имеет смысла.Я понял, что вы думаете о том, что это точное свойство может измениться / обычно отличается для игр RTS, но я действительно думаю, что мы должны придерживаться точной проблемы, если автор выполнил ее точно и довольно хорошо.

Особенно, A * - ужасный, ужасный выбор: Dijkstra вычисляет кратчайшие пути ко всем пунктам назначения из данного исходного узла.A * использует тот факт, что у вас часто есть один отдельный пункт назначения, и эвристика может использоваться, чтобы «направить» Дейкстру в правильном направлении.Это заставляет вас добраться до интересного места назначения раньше, и поэтому вы платите небольшие накладные расходы.Если вы хотите проверить области «вокруг» какого-либо исходного узла (единицы здесь), это просто контрпродуктивно.

Битовые карты будут иметь проблему с выравниванием их по сетке.В любом случае, конечно, есть способы оптимизировать и проверять больше, чем когда-то, но это всего лишь оптимизации, imho.

По самой проблеме:

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

Простая проверка всех полей вокруг блока, как предлагает Kerrek SB, довольно хороша.Никакие ненужные поля не отмечены, и все поля доступны напрямую.Думаю, я бы предложил то же самое.

Если число проверок в вопросе значительно превосходит количество движений юнитов (я сомневаюсь, это из-за вещи в реальном времени), это можетможно было предварительно вычислить эту проблему для каждого юнита и обновлять ее всякий раз, когда юнит перемещается.Я предложу что-то более голодное к памяти и, скорее всего, уступающее прямолинейному подходу, предложенному Kerrik SB:

Если юнит U переместится в поле F, он будет:

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

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

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

Answer 3

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

Упрощенный пример:

char range1[] = 
"010"
"111"
"010";

char range2[] = 
"00100"
"01110"
"11111"
"01110"
"00100";

И так далее ...

, затем просто проверьте, лежит ли точка на растровом изображении (вы должны сами это выяснить).

Answer 4

Я бы использовал алгоритм поиска пути, тем более что квадраты карты могут быть заняты, рано или поздно вам понадобится алгоритм поиска пути. A *, вероятно, будет проще всего реализовать и выполнить достаточно хорошо для вашего сценария. Это очень хорошо описано в википедии , и поиск в Google должен дать вам много результатов, а также пример кода.

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