Эффективное обнаружение столкновений на основе плиток для множества квадратов?

9

в настоящее время я работаю над собственной игрой на основе тайлов (думаю, Terraria, но менее фантастической (я думаю, что это слово? Извините, если это не так)).

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

1000 квадратов, без проблем. 10000 квадратов, для 3-х символов было немного отстает. 100 000 квадратов (действительно огромная карта), для 3 персонажей было невозможно играть.

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

Вот мой алгоритм до сих пор, не стесняйтесь критиковать.

foreach (Block in level)
{
    if (distance from block to player > a specified amount)
        ignore this block;
    else
    {
        get the intersection depth between the two bounding boxes
        if (depth of intersection != Zero-vector)
        {
            check y size vs x size
            resolve on smallest axis
        }
    }
}

Как вы заметите, когда размер уровня становится больше, Порядок этого алгоритма увеличивается на N блоков. Я хотел бы даже не рассматривать блоки, которые даже не рядом с игроком.

Я думаю, что возможно использовать двойной массив блоков (от 0,0) до (mapWidth, mapHeight) вместо списка, вычисляя опасную зону в зависимости от положения человека, например, если позиция игрока находится в (10, 20) оно будет выглядеть от (0, 10) до (20, 30) и т. д.

Любые мысли и соображения потрясающие, спасибо.

Росс
источник
1
И добро пожаловать в stackexchange! :-) Не забудьте прочитать FAQ, если вы не знаете, как работает вся система контроля качества и репутации.
Дэвид Гувейя
Конечно, эти плитки больше, чем 16 на 16 пикселей, в 1920 на 1080 это 8 100 плиток. Конечно, вы знаете, где находятся подвижные объекты, и вы можете проверять только плитки на сетке, которые могут находиться в пределах досягаемости (если один из них 160 * 160, а центр находится в плитке (12,12), вам нужно проверять только между плитками (6 , 6) и (18,18) в общей сложности ~ 150 возможных плиток.). Конечно, плитки под действием силы тяжести только падают, поэтому вам нужно искать только следующую плитку под ней.
DampeS8N
Как вы думаете, 16х16 слишком мал? Мне не составит труда изменить размер плиток, поскольку все, что ссылается на ширину / высоту плиток, является статической константой. Все, что мне нужно сделать, это увеличить их в Paint.NET, что приятно, поскольку добавляет больше деталей.
Росс
Не могли бы вы поделиться своим кодом столкновения? : /
ashes999

Ответы:

7

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

Block[,] level = new Block[width, height];

А поскольку игрок может столкнуться только с окружающими его клетками, количество проверок на столкновение, которое вам нужно сделать, очень мало. Это, конечно, зависит от размера игрока. Образец платформер делает это следующим образом :

int leftTile = (int)Math.Floor((float)characterBounds.Left / tileWidth);
int rightTile = (int)Math.Ceiling(((float)characterBounds.Right / tileWidth)) - 1;
int topTile = (int)Math.Floor((float)characterBounds.Top / tileHeight);
int bottomTile = (int)Math.Ceiling(((float)characterBounds.Bottom / tileHeight)) - 1;

for (int y = topTile; y <= bottomTile; ++y)
{
    for (int x = leftTile; x <= rightTile; ++x)
    {
        // Handle collisions with the tile level[x,y] just like you were doing!
    }
}

Проверьте образец, если у вас все еще есть проблемы.

Дэвид Гувея
источник
Это очень хороший маленький алгоритм, я даже не слышал об образце Platformer (я должен был, но я утверждаю, невежество). Спасибо!
Росс
@ Росс Действительно? Вы будете удивлены, насколько ваше решение похоже на образец. :-) За исключением части списка, все остальное в значительной степени идентично (пересекаются ограничивающие рамки, получают глубину пересечения, разрешаются по наименьшей оси).
Дэвид Гувея
1
О человек, я только что посмотрел на это. >. <Жаль, что я знал это 2 дня назад !! Ну, я новичок в XNA, но я вникал в 2D-графику (просто OpenGL, не очень много игрового программирования). Я думаю, что я должен проверить больше ресурсов в первую очередь, прежде чем я начну в коде.
Росс
1

Я думаю, мой ответ будет вашим ответом! ;-)

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

Может быть, проверить учебник о столкновениях на riemers.net, если вы еще этого не сделали.

PrinceCharles
источник
Я слышал о Римере, но не удосужился посмотреть, спасибо!
Росс
1

При работе с большим количеством коллизий вы обычно хотите использовать более продвинутую структуру , такую ​​как Quadtree или Hashmap, для проверки этих коллизий.

Поскольку плитки статичны, я бы предложил использовать Quadtree. Четырехъядерное дерево состоит из четырехугольников. Каждый четырехугольник состоит из четырех прямоугольников, и каждый из этих прямоугольников является четырехугольником. Это продолжается рекурсивно до указанного размера. Каждый квад может содержать список тайлов, которые обитают в этой области экрана. Таким образом, когда вы проверяете наличие столкновений, вы можете

  1. Ограничьте проверки теми, кто находится в непосредственной близости
  2. Ограничить проверки только движущимися объектами

Теперь, если вы не хотите даже смотреть на плитки вне экрана, вы можете сделать что-то вроде

public bool CheckCollision(myPosition) {
    if(quadNodes.Count > 0) {
        // This is not a leaf, keep checking
        foreach(Quad node in quadNodes) {
            if(node.Position is insideViewport && nearPlayer)
                // Continue recursion
            }
        }
    }
    else {
        // This is a leaf, do checks
        foreach(Tile tile in tileList) {
            if(collision)
                return true;
        }
        return false;
    }
}
Майк Клак
источник
Хм, я слышал о Octrees в 3D-обнаружении столкновений, но никогда не видел продвинутую структуру данных, используемую для 2D-обнаружения столкновений. Большое спасибо!
Росс
1
Поскольку его игра (в предположении Terraria) состоит из равномерно расположенных тайлов, использование сетки будет намного проще и быстрее, чем квадри. Квадродерево работает лучше для более сложных миров, где сетка будет трудно уместить, и все будет иметь произвольный размер.
Дэвид Гувея
1
Вы правы, если это чисто сеточная игра, вплоть до размеров персонажей. Я знаю, что в Террарии у них также есть монстры, которые не вписываются в формат сетки. Я работал в предположении, что основной мир состоит из плиток, но другие объекты будут другими, и они могут хранить их в похожей структуре, чтобы избежать создания другой. Я предполагаю, что они могли бы использовать сетку для плиток, а не другую структуру (если необходимо) для других произвольных объектов.
Майк Клак
1
Это то, что я собирался предложить :) Сетка должна использоваться для обработки столкновений с рельефом местности, в то время как квадродерево может использоваться для обработки столкновений между объектами.
Дэвид Гувейя
Правда. Прямо сейчас каждый ограничивающий прямоугольник имеет 2 степени мощности. Это значительно облегчает обнаружение столкновений. Сетка будет соответствовать моим потребностям на данный момент.
Росс