¿Detección de colisión eficiente basada en mosaicos para muchos cuadrados?

Actualmente estoy trabajando en mi propia versión de un juego basado en mosaicos (piense en Terraria, pero menos fantástico (creo que es una palabra? Lo siento si no lo es)).

De todos modos, actualmente tengo detección de colisión funcionando (¡incluso para casos de esquina!), Lo cual fue un gran paso para mí. Hay algo extremadamente gratificante en ver que un sprite no corre por un bloque. Pero luego tuve la idea de comparar. Mala idea.

1,000 cuadrados, no hay problema. 10,000 casillas, para 3 personajes, fue un poco lento. 100,000 cuadrados (mapa realmente enorme), para 3 personajes no se podía jugar.

Tengo el problema de que ni siquiera quiero considerar los bloques que están demasiado lejos del jugador, los personajes, los elementos, etc., pero no quiero cargarlos constantemente de memoria.

Aquí está mi algoritmo hasta ahora, no dude en criticar.

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

Como notará, cuando el tamaño del nivel aumenta, el orden de este algoritmo crece en N bloques. Me gustaría ni siquiera considerar bloques que ni siquiera están cerca del jugador.

Estoy pensando que tal vez use un (0,0) para (mapWidth, mapHeight) doble matriz de bloques en lugar de una lista, calculando una zona de peligro dependiendo de la posición de la persona, por ejemplo, si la posición del jugador está en (10, 20) se verá de (0, 10) a (20, 30), etc.

Cualquier pensamiento y consideraciones son increíbles, gracias.

Sí, estás pensando correctamente. Debería estar utilizando una matriz 2D de mosaicos ya que eso le permite indexar mosaicos por posición.

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

Y dado que el jugador solo puede colisionar con sus fichas circundantes, la cantidad de controles de colisión que necesita hacer es muy pequeña. Esto, por supuesto, depende del tamaño del jugador. La muestra de Platformer lo hace así:

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

Verifique la muestra si aún tiene algún problema.

¡Supongo que mi respuesta sería tu respuesta! ;-)

Si tiene la posición del jugador (y el tamaño), puede calcular los índices de las fichas circundantes (que son los únicos que se verifican en detalle). De esta manera, debería ser irrelevante qué tan grande es su mapa, solo depende del tamaño real de su jugador, lo que da como resultado más fichas potenciales para verificar.

Tal vez revise el tutorial sobre colisiones en riemers.net si aún no lo ha hecho.

Cuando se trata de una gran cantidad de colisiones, generalmente desea adoptar una estructura más avanzada , como un Quadtree o Hashmap para verificar esas colisiones.

Dado que los mosaicos son estáticos, sugeriría usar un Quadtree. Un árbol cuádruple está formado por quads. Cada quad está formado por cuatro rectángulos y cada uno de esos rectángulos son quads. Esto continúa recursivamente hasta un tamaño especificado. Cada quad puede contener una lista de mosaicos que habitan esa área de la pantalla. De esa manera, cuando esté buscando colisiones, puede

1. Restrinja los cheques a quienes se encuentren en las inmediaciones
2. Restrinja las comprobaciones solo a los objetos que se mueven

Ahora, si ni siquiera quieres mirar los mosaicos fuera de la pantalla, entonces podrías hacer algo como

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