Élimination efficace des objets hors écran sur une carte 2D descendante

Je sais que l'efficacité est la clé de la programmation de jeux et j'ai déjà eu quelques expériences avec le rendu d'une "carte" mais probablement pas de la meilleure des manières.

Pour un jeu 2D TopDown: (restituez simplement les textures / tuiles du monde, rien d'autre)

Disons que vous avez une carte de 1000x1000 (tuiles ou autre). Si la tuile n'est pas dans la vue de la caméra, elle ne devrait pas être rendue - c'est aussi simple que cela. Pas besoin de rendre une tuile qui ne sera pas vue. Mais puisque vous avez 1000x1000 objets dans votre carte, ou peut-être moins, vous ne voudrez probablement pas parcourir toutes les 1000 * 1000 tuiles juste pour voir si elles sont supposées être rendues ou non.

Question: Quelle est la meilleure façon de mettre en œuvre cette efficacité? Pour qu'il "rapidement / plus rapidement" puisse déterminer quelles tuiles sont supposées être rendues?

De plus, je ne construis pas mon jeu autour de tuiles rendues avec un SpriteBatch donc il n'y a pas de rectangles, les formes peuvent être de tailles différentes et avoir plusieurs points, disons un objet courbe de 10 points et une texture à l'intérieur de cette forme;

Question: Comment déterminez-vous si ce type d'objets est "à l'intérieur" de la vue de la caméra?

C'est facile avec un rectangle 48x48, il suffit de voir si la largeur X + ou la hauteur Y + est dans la vue de la caméra. Différent avec plusieurs points.

Autrement dit, comment gérer efficacement le code et les données pour ne pas avoir à parcourir / boucler un million d'objets en même temps.

En ce qui concerne les objets complexes , je pense que la meilleure façon est simplement de les réduire aux rectangles environnants et de vérifier si ce rectangle est à l'intérieur de la fenêtre. Même si vous restituez une texture qui n'est pas réellement visible (en raison de sa forme), elle sera probablement plus rapide que de faire un algorithme de détection plus complexe.

Quant à la gestion efficace de grandes cartes, vous devez subdiviser votre carte à plus grande échelle, par exemple 10x10. Ensuite, vous vérifiez l'intersection de votre fenêtre. Dans le pire des cas, il frappe 4 ces «régions», ce qui donnera (100x100) * 4 = 40K objets. Ceci est un exemple simplifié. Pour une utilisation réelle, vous devriez considérer la structure Quadtree qui est particulièrement efficace pour de telles subdivisions et la détection de collision (le contrôle de la visibilité de la fenêtre est essentiellement un contrôle de la collision entre la fenêtre et le sprite).

Lorsque vous avez de nombreux objets mobiles, vous devez les stocker par leurs coordonnées dans une structure arborescente multidimensionnelle. De cette façon, vous pouvez obtenir efficacement une liste de tous les objets qui se trouvent à l'intérieur d'un rectangle donné. Vous pouvez même les classer par leurs coordonnées x ou y, ce qui est important pour l'ordre de dessin lorsque les images-objets se chevauchent.

Cela sera également très utile pour la détection des collisions.

Voir l'article de wikipedia sur les arbres kd pour plus de détails.

Lorsque les arbres 2D sont trop compliqués pour vous, il existe également une alternative plus simple mais pas beaucoup moins efficace: stocker les objets en tant qu'enfants des tuiles. Lorsque vous déplacez un objet, vous le supprimez de la liste d'objets de son ancienne tuile et le placez dans la liste d'objets de la nouvelle. Lorsque vous dessinez les objets, vous parcourez à nouveau les tuiles de la fenêtre et récupérez leurs objets. Ensuite, vous les triez tous par des coordonnées y et les dessinez.

Je ne sais pas si c'est la meilleure façon, mais voici comment j'apprends à le faire:

vous avez un tableau bidimensionnel de "tuiles"

public Tile tilemap[][];

et vous décidez de la position de la "caméra" avec un Vector2, vous ne rendrez que ce qui est à l'intérieur de la scène, le grand rectangle est ce que vous pouvez voir à l'écran, inutile de dessiner le reste de la scène.

Maintenant, vous devez obtenir les décalages, en supposant que vous souhaitez que votre caméra soit au centre de la scène:

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

maintenant, dans quelle partie du tableau les tuiles visibles commencent et finissent?

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

et dans votre méthode de dessin, il vous suffit de parcourir la partie visible du tableau:

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

Vous pouvez avoir un Bitmap qui est la scène entière mais non affiché. Et puis un bitmap de couche d'appareil photo de la taille d'un écran qui ne fait que dessiner à partir de la scène entière mais seulement de la partie qui doit être affichée.