• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Drzewo czwórkowe-kolizje

+2 głosów
98 wizyt
pytanie zadane 4 dni temu w C i C++ przez użytkownika Nekronomik Początkujący (420 punkty)
Witam, od zawsze korzystałem z kolizji AABB wszystko było dobrze puki nie pojawiło się 500 obiektów. Fpsy spadły do 50 gdzie cała grafika była wyświetlana na prymitywach. Czytałem na temat drzewka czwórkowego , widziałem jak działa, jak dzieli przestrzeń. Ale nie wiem jak go połączyć z listą obiektów i jak sprawdzić czy obiekt znajduje się w danym miejscu podzielonego obszaru lub nawet i pare obiektów. Czy był by ktoś w stanie mnie naprowadzić  aby jakoś zacząć ?

3 odpowiedzi

+2 głosów
odpowiedź 4 dni temu przez użytkownika mokrowski Stary wyjadacz (10,320 punkty)
edycja 4 dni temu przez użytkownika mokrowski
Jak zacząć? Zrób mapę: { zakres_współrzędnych_2d -> kontener_obiektów_w_tym_zakresie }. Przy zmianie współrzędnej obiektu sprawdź czy nie należy go przepisać do innego slotu/klucza mapy (czyli usunąć z kontenera i dodać do innego). Sprawdzenie kolizji będzie ograniczało się do sprawdzenia obecnych w kontenerze (i ew. w przypadkach położenia na krawędzi slotu, sąsiednich slotów/kluczy mapy - tego oczywiście da się także uniknąć).

Na początek może wystarczyć. Zależy jak podzielisz tę mapę, na ile slotów i jakiej wydajności będziesz oczekiwał :-)

A tu masz implementację (na dole) w pseudokodzie: https://en.wikipedia.org/wiki/Quadtree
0 głosów
odpowiedź 4 dni temu przez użytkownika Nekronomik Początkujący (420 punkty)
Kontener obiektów jeden już mam (lista dwukierunkowa), jeśli chodzi o drzewo czwórkowe to zauważyłem że on działa na konkretnej przestrzeni którą dzieli dynamicznie i nie wiem w jaki sposób to robi gdzie jeszcze przy tym sprawdza obiekty.
komentarz 4 dni temu przez użytkownika mokrowski Stary wyjadacz (10,320 punkty)
No i dlatego zaproponowałem Ci w ramach "zrób co możesz", podział na wstępie na strukturę statyczną gdzie zakresy są bezpośrednim odzwierciedleniem całości przestrzeni gdzie są obiekty. Koszt implementacji niewielki i łatwy do zrozumienia algorytm który może wystarczyć. Jeśli nie wystarczy to będziesz zagłębiał się w dynamiczne drzewa czwórkowe.

Lista dwukierunkowa? Hmm.. ta struktura nie jest zbyt przyjazna pamięci cache. Rzeczywiście tak często wykonujesz insert że opłaca Ci się lista?
komentarz 4 dni temu przez użytkownika Nekronomik Początkujący (420 punkty)

Chciał bym zrobić już to porządnie nawet na dynamicznym drzewie czwórkowym w którym będą sprawdzane kolizje między obiektami okrągłymi różnej wielkości tylko że nie wiem jak się za to zabrać.
Liste napisałem sam, samo jej używanie jest bardzo wygodne, mam bardzo szybki dostęp do obiektów jak i odnajdywanie obiektów przez inne obiekty jest też bardzo szybkie.
Obiekty są cały czas w ruchu, cały czas powstają nowe i są tez usuwane tak jak na tym filmiku
https://www.youtube.com/watch?v=tyTdPYmoDNU

0 głosów
odpowiedź 3 dni temu przez użytkownika Nekronomik Początkujący (420 punkty)
Wiem już jak napisać drzewo czwórkowe dynamicznie, tylko mam jeszcze pytanie:
Zauważyłem że drzewo czwórkowe działa jak kontener, czy dobrze by było w nim tworzyć obiekty i zrezygnować z listy dwukierunkowej ?
komentarz 3 dni temu przez użytkownika mokrowski Stary wyjadacz (10,320 punkty)
Czy zrezygnować? To zależy. Jeśli masz częste poszukiwanie w stylu "następny w stosunku do obecnego obiekt" to lista może być wydajniejsza. Będzie zawsze szybsze np. uaktualnienie pozycji obiektów poprzez iterowanie po liście a nie przechodzenie po drzewie.

Jeśli jednak powodem istnienia listy było jedynie dostarczenie kontenera zbierającego obiekty do przeglądania ew. kolizji, to z niej zrezygnuj.
komentarz 3 dni temu przez użytkownika Nekronomik Początkujący (420 punkty)
Tak, lista była głównie do sprawdzania kolizji AABB. No ale też mogłem szybko wykonywać jakieś operacje na obiektach typu "ruch", "atak" jak i szybkie dodawanie i usuwanie obiektów itp.
A widzę że w drzewku czwórkowym też powinienem mógł to wszystko wykonywać.
Myślałem też nad "fuzją" aby połączyć klasę drzewka czwórkowego z klasą lista.
komentarz 2 dni temu przez użytkownika mokrowski Stary wyjadacz (10,320 punkty)
W takim razie odwlecz decyzję o usunięciu listy do czasu implementacji drzewa i sprawdzenia wydajności aplikacji. Raczej nie łącz listy z drzewem. Nie wiadomo jak taka "fuzja" miała by teraz wyglądać a listę ew. usuniesz jak już będziesz miał działającą implementację.

Podobne pytania

0 głosów
1 odpowiedź 118 wizyt
pytanie zadane 11 stycznia w C i C++ przez użytkownika devi Początkujący (320 punkty)
0 głosów
1 odpowiedź 70 wizyt
pytanie zadane 31 października 2016 w C i C++ przez użytkownika NieznanyV2 Nowicjusz (160 punkty)
0 głosów
1 odpowiedź 183 wizyt
pytanie zadane 8 czerwca 2016 w C i C++ przez użytkownika Kyoya Początkujący (260 punkty)
...