Selección eficiente de objetos fuera de la pantalla en un mapa 2D de arriba hacia abajo

Sé que la eficiencia es clave en la programación de juegos y he tenido algunas experiencias con la representación de un "mapa" anteriormente, pero probablemente no de la mejor manera.

Para un juego 2D TopDown: (simplemente renderiza las texturas / mosaicos del mundo, nada más)

Digamos que tienes un mapa de 1000x1000 (mosaicos o lo que sea). Si el mosaico no está a la vista de la cámara, no se debe renderizar, es así de simple. No es necesario renderizar un mosaico que no se verá. Pero dado que tiene 1000x1000 objetos en su mapa, o tal vez menos, probablemente no desee recorrer todos los mosaicos de 1000 * 1000 solo para ver si se supone que deben representarse o no.

Pregunta: ¿Cuál es la mejor manera de implementar esta eficiencia? ¿De modo que "más rápido / más rápido" puede determinar qué mosaicos se supone que se renderizarán?

Además, no estoy construyendo mi juego alrededor de fichas renderizadas con un SpriteBatch, por lo que no hay rectángulos, las formas pueden ser de diferentes tamaños y tener múltiples puntos, digamos un objeto curvo de 10 puntos y una textura dentro de esa forma;

Pregunta: ¿Cómo se determina si este tipo de objetos está "dentro" de la Vista de la cámara?

Es fácil con un rectángulo de 48x48, solo vea si X + Ancho o Y + Altura está en la vista de la cámara. Diferente con múltiples puntos.

En pocas palabras, cómo administrar el código y los datos de manera eficiente para no tener que ejecutar / recorrer un millón de objetos al mismo tiempo.

En cuanto a los objetos complejos , creo que la mejor manera es reducirlos a los rectángulos circundantes y verificar si ese rectángulo está dentro de la ventana gráfica. Incluso si renderiza una textura que no es realmente visible (debido a su forma), probablemente será más rápida que si utiliza un algoritmo de detección más complejo.

En cuanto al manejo eficiente de mapas grandes, debe subdividir su mapa a mayor escala, digamos 10x10. Luego verifica la intersección de su ventana gráfica. En el peor de los casos, llega a 4 estas 'regiones' que darán como resultado (100x100) * 4 = 40K objetos. Este es un ejemplo simplificado. Para un uso real, debe considerar la estructura Quadtree, que es especialmente eficiente para tales subdivisiones y detección de colisión (la verificación de la visibilidad de la ventana gráfica es básicamente una verificación de colisión entre la ventana gráfica y el sprite).

Cuando tenga muchos objetos móviles, debe almacenarlos por sus coordenadas en una estructura de árbol multidimensional. De esa manera, puede obtener de manera eficiente una lista de todos los objetos que están dentro de un rectángulo dado. Incluso puede ordenarlos por sus coordenadas x o y, lo cual es importante para el orden de dibujo cuando los sprites de objeto se superponen.

Esto también será muy útil para la detección de colisiones.

Vea el artículo de Wikipedia sobre los árboles kd para más detalles.

Cuando los árboles 2d son demasiado complicados para usted, también hay una alternativa más fácil pero no menos efectiva: almacenar los objetos como hijos de los mosaicos. Cuando mueve un objeto, lo elimina de la lista de objetos de su mosaico antiguo y lo coloca en la lista de objetos del nuevo. Cuando dibujas los objetos, vuelves a recorrer los mosaicos de la ventana gráfica y recuperas sus objetos. Luego los clasifica todos por coordenadas y y los dibuja.

No sé si es la mejor manera, pero así es como aprendo a hacerlo:

tiene una matriz bidimensional de "mosaicos"

public Tile tilemap[][];

y usted decide la posición de la "cámara" con un Vector2, solo renderizará lo que está dentro de la escena, el gran rectángulo es lo que puede ver en la pantalla, es inútil dibujar el resto de la escena.

Ahora necesita obtener las compensaciones, suponiendo que desea que su cámara esté en el centro de la escena:

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

ahora, ¿en qué parte de la matriz comienzan y terminan los mosaicos visibles?

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

y en su método de dibujo, simplemente recorre la parte visible de la matriz:

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

Puede tener un mapa de bits que es toda la escena pero no se muestra. Y luego, un mapa de bits de capa de cámara del tamaño de una pantalla que solo se basa en toda la escena, pero solo en la parte que debe mostrarse.