Эффективное отбраковка объектов вне экрана на 2D-карте сверху вниз

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

Для 2D-игры TopDown: (просто визуализируйте текстуры / плитки мира, ничего больше)

Скажем, у вас есть карта 1000x1000 (плитки или что-то еще). Если плитка не в поле зрения камеры, она не должна отображаться - это так просто. Не нужно рендерить плитку, которая не будет видна. Но поскольку у вас на карте есть 1000x1000 объектов или, возможно, меньше, вы, вероятно, не захотите перебирать все 1000 * 1000 плиток, просто чтобы посмотреть, будут ли они отображаться или нет.

Вопрос: Как лучше всего реализовать эту эффективность? Чтобы он «быстрее / быстрее» мог определить, какие плитки предполагается отображать?

Кроме того, я не строю свою игру вокруг плиток, визуализированных с помощью SpriteBatch, поэтому здесь нет прямоугольников, фигуры могут быть разных размеров и иметь несколько точек, например изогнутый объект из 10 точек и текстуру внутри этой формы;

Вопрос: Как вы определяете, находится ли этот вид объектов «внутри» вида камеры?

Это легко с прямоугольником 48x48, просто посмотрите, виден ли он X + Width или Y + Height в поле зрения камеры. Отличается несколькими точками.

Проще говоря, как эффективно управлять кодом и данными, чтобы не обходить / перебирать миллионы объектов одновременно.

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

Что касается эффективной обработки больших карт, вы должны подразделить карту в большем масштабе, скажем, 10х10. Затем вы проверяете пересечение окна просмотра. В худшем случае он попадет в 4 «региона», что приведет к (100x100) * 4 = 40K объектам. Это упрощенный пример. Для реального использования вы должны рассмотреть структуру Quadtree, которая особенно эффективна для таких подразделений и обнаружения столкновений (проверка видимости в области просмотра - это, в основном, проверка столкновения между областью просмотра и спрайтом).

Когда у вас много мобильных объектов, вы должны хранить их по их координатам в многомерной древовидной структуре. Таким образом, вы можете эффективно получить список всех объектов, которые находятся внутри данного прямоугольника. Вы даже можете упорядочить их по их x- или y-координатам, что важно для порядка отрисовки, когда спрайты объекта перекрываются.

Это также очень пригодится для обнаружения столкновений.

Подробности смотрите в статье в Википедии о деревьях kd .

Когда двумерные деревья слишком сложны для вас, есть и более простая, но не менее эффективная альтернатива: храните объекты как дочерние элементы плиток. Когда вы перемещаете объект, вы удаляете его из списка объектов его старой плитки и помещаете его в список объектов новой. Когда вы рисуете объекты, вы снова перебираете плитки в области просмотра и извлекаете их объекты. Затем вы сортируете их по y-координатам и рисуете.

Не знаю, лучший ли это способ, но вот как я научусь это делать:

у вас есть двумерный массив «плиток»

public Tile tilemap[][];

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

Теперь вам нужно получить смещения, если вы хотите, чтобы ваша камера находилась в центре сцены:

offsetX = (graphics().width() / 2 - Math.round(cam.Position().X));
offsetX = Math.min(offsetX, 0);
offsetX = Math.max(offsetX, graphics().width() / 2 - mapWidth);
offsetY = (graphics().height()) / 2 - Math.round(cam.getPosition().Y);
offsetY = Math.min(offsetY, 0);
offsetY = Math.max((graphics().height() / 2 - mapHeight), offsetY);

Теперь, в какой части массива видимые плитки начинаются и заканчиваются?

firstTileX = pixelsToTiles(-offsetX);

lastTileX = firstTileX + pixelsToTiles(graphics().width());

firstTileY = pixelsToTiles(-offsetY);

lastTileY = firstTileY + pixelsToTiles(graphics().height());

int pixelsToTiles(int pixels) {
    return (int) Math.floor((float) pixels / Tile.getHeight());
}

и в вашем методе рисования вы просто просматриваете видимую часть массива:

   for (int x = firstTileX; x < lastTileX; x++) {
        for (int y = firstTileY; y < lastTileY; y++) {
              Vector2 position = new Vector2(tilesToPixelsX(x) + offsetX,
                        tilesToPixelsY(y) + offsetY);
              tilemap[x][y].Draw(surf, position);
        }
    }

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