Détection de collision efficace basée sur des tuiles pour beaucoup de carrés?

actuellement je travaille sur ma propre version d'un jeu à base de tuiles (pensez Terraria, mais moins fantastique (je pense que c'est un mot? Désolé si ce n'est pas le cas)).

Quoi qu'il en soit, la détection des collisions fonctionne actuellement (même dans les cas d'angle!), Ce qui a été une grande étape pour moi. Il y a quelque chose d'extrêmement gratifiant à voir un sprite ne pas traverser un bloc. Mais j'ai eu l'idée de faire un benchmark. Mauvaise idée.

1000 carrés, pas de problème. 10000 carrés, pour 3 personnages était un peu décalé. 100 000 carrés (carte vraiment énorme), pour 3 personnages était injouable.

J'ai un problème où je ne veux même pas considérer les blocs trop éloignés du joueur, des personnages, des objets, etc., mais je ne veux pas charger ceux qui sont en mémoire en permanence.

Voici mon algorithme jusqu'à présent, n'hésitez pas à critiquer.

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

Comme vous le remarquerez, lorsque la taille du niveau augmente, l'ordre de cet algorithme croît de N blocs. Je ne voudrais même pas considérer les blocs qui ne sont même pas à proximité du joueur.

Je pense peut-être utiliser un (0,0) à (mapWidth, mapHeight) double tableau de blocs au lieu d'une liste, calculant une zone de danger en fonction de la position de la personne, par exemple, si la position du joueur est à (10, 20) il apparaîtra de (0, 10) à (20, 30), ou ainsi de suite.

Toutes les pensées et considérations sont géniales, merci.

Oui, tu penses correctement. Vous devez utiliser un tableau 2D de tuiles car cela vous permet d'indexer les tuiles par position.

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

Et comme le joueur ne peut entrer en collision qu'avec les tuiles environnantes, le nombre de vérifications de collision que vous devez effectuer est très faible. Cela dépend bien sûr de la taille du joueur. L' exemple Platformer le fait comme ceci:

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!
    }
}

Vérifiez l'échantillon si vous avez toujours des problèmes.

Je suppose que ma réponse serait votre réponse! ;-)

Si vous avez la position (et la taille) du joueur, vous pouvez calculer les indices des tuiles environnantes (qui sont les seules à être vérifiées en détail). De cette façon, la taille de votre carte ne devrait pas être importante, cela dépend simplement de la taille réelle de votre joueur, ce qui entraîne davantage de tuiles potentielles à vérifier.

Peut-être consultez le tutoriel sur les collisions sur riemers.net si vous ne l'avez pas déjà fait.

Lorsque vous traitez un grand nombre de collisions, vous souhaitez généralement adopter une structure plus avancée , comme un Quadtree ou un Hashmap pour vérifier ces collisions.

Étant donné que les tuiles sont statiques, je suggère d'utiliser un Quadtree. Un arbre quad est composé de quads. Chaque quad est composé de quatre rectangles et chacun de ces rectangles sont des quads. Cela continue récursivement jusqu'à une taille spécifiée. Chaque quad peut contenir une liste de tuiles qui habitent cette zone de l'écran. De cette façon, lorsque vous vérifiez les collisions, vous pouvez

1. Restreindre les contrôles à ceux dans le voisinage immédiat
2. Limiter les contrôles aux seuls objets en mouvement

Maintenant, si vous ne voulez même pas regarder les tuiles hors écran, vous pouvez faire quelque chose comme

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