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!
źródło
Odpowiedzi:
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:
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.
źródło