Skuteczne wykrywanie kolizji na podstawie płytek dla wielu kwadratów?

obecnie pracuję nad własną wersją gry opartej na kafelkach (pomyśl Terraria, ale mniej fantastycznie (myślę, że to słowo? Przepraszam, jeśli nie jest)).

Tak czy inaczej, obecnie działam wykrywanie kolizji (nawet w przypadkach narożnych!), Co było dla mnie dużym krokiem. Jest coś niezwykle satysfakcjonującego w widzeniu, że duszek nie biegnie przez blok. Ale potem wpadłem na pomysł, aby przeprowadzić testy porównawcze. Kiepski pomysł.

1000 kwadratów, nie ma problemu. 10 000 kwadratów, dla 3 postaci było trochę opóźnione. 100 000 kwadratów (naprawdę ogromna mapa), na 3 postacie nie można było grać.

Mam problem polegający na tym, że nie chcę nawet brać pod uwagę bloków, które znajdują się zbyt daleko od gracza, postaci, przedmiotów itp., Ale nie chcę ciągle ładować tych brakujących pamięci.

Oto mój algorytm do tej pory, nie krępuj się krytykować.

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

Jak zauważysz, gdy rozmiar poziomu staje się większy, kolejność tego algorytmu rośnie o N bloków. Chciałbym nawet nie brać pod uwagę bloków, które nawet nie są blisko gracza.

Myślę, że może użyj (0,0) do (mapWidth, mapHeight) podwójnej tablicy bloków zamiast listy, obliczając strefę zagrożenia w zależności od pozycji osoby, np. Jeśli pozycja gracza wynosi (10, 20) będzie wyglądać od (0, 10) do (20, 30) itd.

Wszelkie przemyślenia i uwagi są niesamowite, dziękuję.

Tak, myślisz poprawnie. Powinieneś używać tablicy 2D, ponieważ pozwala to na indeksowanie płytek według pozycji.

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

A ponieważ gracz może zderzać się tylko z otaczającymi go płytkami, liczba kontroli kolizji, które należy wykonać, jest bardzo mała. To oczywiście zależy od wielkości gracza. Próbka platformówka robi to tak:

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

Sprawdź próbkę, jeśli nadal masz jakieś problemy.

Myślę, że moja odpowiedź byłaby twoją odpowiedzią! ;-)

Jeśli masz pozycję gracza (i rozmiar), możesz obliczyć wskaźniki otaczających kafelków (które są jedynymi, które należy szczegółowo sprawdzić). W ten sposób nie powinno mieć znaczenia, jak duża jest twoja mapa, zależy to tylko od rzeczywistej wielkości gracza, co daje więcej potencjalnych płytek do sprawdzenia.

Być może sprawdź samouczek na temat kolizji na stronie riemers.net, jeśli jeszcze tego nie zrobiłeś.

W przypadku dużej liczby kolizji zwykle chcesz zastosować bardziej zaawansowaną strukturę , taką jak Quadtree lub Hashmap, aby sprawdzić te kolizje.

Ponieważ płytki są statyczne, sugerowałbym użycie Quadtree. Drzewo quad składa się z quadów. Każdy kwadrat składa się z czterech prostokątów, a każdy z nich jest kwadratem. Trwa to rekurencyjnie do określonego rozmiaru. Każdy quad może zawierać listę płytek, które zamieszkują ten obszar ekranu. W ten sposób, sprawdzając kolizje, możesz

1. Ogranicz kontrole do osób w bezpośrednim sąsiedztwie
2. Ogranicz kontrole tylko do poruszających się obiektów

Teraz, jeśli nie chcesz nawet patrzeć na kafelki poza ekranem, możesz zrobić coś takiego

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