Kolizja oparta na drzewach / siatce - realizacja logiki


13

Po pierwsze, piszę własną logikę gry tylko przez krótki czas, więc przepraszam, jeśli wydaje się to proste.

Dużo czytałem o drzewach quadów i wykrywaniu kolizji na podstawie siatki. Rozumiem logikę - w zasadzie nie sprawdzaj kolizji, chyba że obiekty są w pobliżu. Ale nigdy nie wspomniano, jak to faktycznie wykonać.

Mam w głowie kilka możliwych metod, ale nie jestem pewien, która z nich jest najlepsza

Ogólny test zderzeniowy - bez optymalizacji

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

przechowuj sąsiadów (metoda 1) Ale co, jeśli chcemy zoptymalizować kolizje, aby sprawdzić tylko obiekty znajdujące się w pobliżu. Czy nadal przebiegamy przez wszystkie obiekty, czy też tworzymy tablicę z obiektami blisko do sprawdzenia?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else
    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }
    }

zapętl wszystkie obiekty, ale sprawdzaj tylko sąsiadów pod kątem kolizji (metoda 3) . Inną możliwością jest to, że wciąż zapętlamy wszystko, ale sprawdzamy, czy obiekty są w pobliżu przed przetestowaniem kolizji.

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }

    }

Przechowuj obiekty w danych kafelków (metoda 3) Używając systemu opartego na kafelkach, dopuszczaj inną opcję; Przechowuj obiekty znajdujące się na określonym kafelku w samych danych kafelka. Sprawdź, na którym kafelku obiekt jest otaczającym kafelkiem, zawierający obiekty, z którymi mógłby się zderzyć:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!
    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

Zawsze staram się patrzeć na rzeczywisty świat jako przykład. Gdybym chciał porównać elementy tego samego koloru, nielogiczne byłoby sprawdzanie wszystkich elementów, nawet jeśli nie pasują one do koloru (Metoda 2, sprawdzanie każdego elementu). Prawdopodobnie zebrałbym przedmioty tego samego koloru (obiekty, które są blisko siebie) i sprawdziłbym je (metoda 1), zamiast sprawdzania wszystkiego.

To nie jest właściwe porównanie, ponieważ elementy podczas sprawdzania kolizji ciągle się przesuwają, więc zamówienie się pomieszało. To mnie dezorientuje.

Czy bardziej efektywnie byłoby sprawdzić każdy element, usuwając w ten sposób wysiłek generowania szeregu sąsiadów.

Czy może bardziej efektywne jest znajdowanie sąsiadów, dzięki czemu nie trzeba zapętlać tak wielu obiektów w celu sprawdzenia kolizji?

Ciągłe zmienianie danych na każdym kafelku wydaje się również bardzo intensywne, więc nie jestem pewien, czy to dobry pomysł ...

Myślałem o grze w obronę wieży, w której wieża musi wykrywać obiekty, jeśli znajdują się w zasięgu, zanim do nich strzelą. I głupio wydaje się sprawdzanie wszystkich przedmiotów, a czasami w pobliżu nie będzie żadnych przedmiotów.

Przepraszam za długi post, zawsze mając problem z wyjaśnieniem siebie!


jaki to język? JavaScript?
Kyle C

2
ActionScript 3, ale język jest dość nieistotny. Chcę tylko dowiedzieć się, jaki jest najlepszy sposób obsługi i struktury tego :)
omgnoseat

Odpowiedzi:


8

Musisz zmniejszyć liczbę faktycznych kontroli kolizji. Jasne, że wiem. Rozwińmy więc to:

Twój pierwszy algorytm sprawdzania kolizji bez jakiejkolwiek optymalizacji: ile kontroli wykona za jednym razem? Jeśli n jest liczbą obiektów, będzie to około n * (n-1) kontroli. W przypadku wielu obiektów (> 100) będzie to strasznie wolne.

Twoja metoda sprawdzania sąsiada nie będzie dużo szybsza. Jeśli twoje obiekty nie są statyczne i często się poruszają, będziesz musiał zbudować listę sąsiadów dla każdego obiektu za każdym razem w swojej pętli gry. Jest to w rzeczywistości gorsze niż pierwszy algorytm, ponieważ wykonujesz n * (n-1), aby zbudować listę sąsiadów, a następnie sprawdzić każdy obiekt, jeśli koliduje on z jednym z jego sąsiadów.

Musisz podzielić przestrzeń gry. Powiedzmy, że Twoje miejsce do gry ma szerokość 400 x 400 pikseli. Możesz podzielić to na 4 podprzestrzenie o wymiarach 200 x 200 i sprawdzić każdy obiekt, do którego należy do podprzestrzeni (jeden obiekt może znajdować się w więcej niż jednej podprzestrzeni). Następnie musisz tylko sprawdzić, czy obiekty w każdej podprzestrzeni kolidują z innym obiektem w tej samej podprzestrzeni.

Tak więc koszt czasu wykonania wyniesie: n dla budowy listy 4 podprzestrzeni + (n / 4) * ((n-1) / 4), co jest znacznie lepsze niż poprzednie koszty czasu wykonania. Można to dodatkowo zmniejszyć, zmniejszając podobszary (np. 50 x 50).

Nasz algorytm wygląda teraz mniej więcej tak:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

Jest to nieco podobne do pomysłu na dane kafelkowe. Ale podprzestrzenie nie muszą być tego samego rozmiaru co kafelki.

Możemy zrobić ostatni krok, aby zoptymalizować to dalej za pomocą czterokąta. Niech k będzie liczbą podprzestrzeni. Aby zbudować listy obiektów spacji, przeprowadzamy kontrole k * n, co prowadzi do wielu kontroli, jeśli twój świat gry staje się duży.

Aby obniżyć ten koszt, używamy czterokąta. Quadtree to kolejny sposób na podzielenie naszej przestrzeni gry. Zamiast dzielić naszą przestrzeń 400 x 400 na 64 podprzestrzenie 50 x 50 i sprawdzać każdy obiekt, w którym z obecnych 64 podprzestrzeni znajduje się, przestrzeń gry dzieli się na 4 podprzestrzenie o połowę mniejszej niż przestrzeń gry (200 x 200), które z kolei dzielą się na mniejsze podprzestrzenie (100 x 100), które z kolei są ponownie dzielone na podprzestrzenie 50 x 50. To jest nasze quadtree.

Teraz, jeśli chcemy wiedzieć, do której podprzestrzeni 50x50 należy obiekt, sprawdzamy, do której podprzestrzeni 200x200 należy. Następnie idziemy o jeden poziom głębiej w naszym quadtree i porównujemy z 4 podprzestrzeniami 100 x 100, które znajdują się w właśnie znalezionej podprzestrzeni 200 x 200. Jest to powtarzane, dopóki nie dowiemy się, do której podprzestrzeni 50x50 należy obiekt. Więc ile czeków było teraz niezbędnych? 4 na każdy poziom kwadratu (pamiętaj, że obiekt może znajdować się na krawędzi dwóch podprzestrzeni). Potrzebujemy więc czeków 4 * 3, aby przypisać obiekt do poprawnej podprzestrzeni 50x50. O wiele lepiej niż 64 czeki.

Dlatego nasz algorytm quadtree wymaga 4 * 3 * n kontroli, aby zbudować listy podprzestrzeni, a następnie czegoś w rodzaju kontroli k * (n / k), aby sprawdzić kolizje każdego obiektu.


To bardzo przejrzysty i zrozumiały awnser, bardzo dziękuję! Jak obsługiwane jest to, w której podprzestrzeni znajduje się obiekt? Czy podprzestrzeń jest przedmiotem handlu jako obiekt, w którym obiekty na niej są zapisywane jako tablice i sprawdzane względem siebie? Czy po prostu sprawdzasz, która to podprzestrzeń, sprawdzając X i Y w głównej pętli? Wydaje się, że budowanie i zmienianie tablic cały czas jest dość nieefektywne. Chcę więc mieć pewność, że użyję odpowiedniej metody :) Widzę także problem występujący, gdy obiekty różnią się wielkością. Wydaje mi się, że najmniejsza podprzestrzeń powinna być tak duża jak największy obiekt?
omgnoseat

Cieszę się, że mogę pomóc :) Podprzestrzeń byłaby obiektem, który utrzymuje 4 zawarte w niej podprzestrzenie. Najmniejsza podprzestrzeń jest inna, ponieważ nie zawiera już podprzestrzeni, ale listę twoich obiektów. Biorąc pod uwagę koszt aktualizacji: drzewo podprzestrzeni jest budowane raz na początku gry. W każdej pętli głównej pętli listy obiektów w najmniejszych podprzestrzeniach są czyszczone i ponownie wypełniane. Konieczne jest więc tylko dodawanie / usuwanie listy. Nie trzeba zmieniać tablic. Najmniejsza podprzestrzeń powinna być wystarczająco duża, aby pomieścić kilka obiektów gry. Jak duży zależy od twojej gry i można go później ulepszyć.
Stephen

Dzięki, zapomniałem, że będziemy również sprawdzać kolizje między rzeczywistymi obiektami w najmniejszej podprzestrzeni, ma sens, że powinno być teraz w stanie pomieścić wiele obiektów. Zacząłem od testu i ładnie mi idzie. Największym problemem jest wykrycie, do której podprzestrzeni należą obiekty. Wciąż zapętlam wartości podrzędne X i Y podprzestrzeni, czy jest to właściwa metoda?
omgnoseat

Jak obchodzić się z obiektami, które rozciągają się na więcej niż jedną podprzestrzeń (tj. Których lokalizacja znajduje się na granicy lub w jej pobliżu)?
mghicks

Proste: nie. Obiekty mogą być częścią wielu podprzestrzeni, jeśli znajdują się na granicy każdej podprzestrzeni. Jeden obiekt może być częścią maksymalnie 4 podprzestrzeni. Ale to mniejszość.
Stephen
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.