• 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
137 wizyt
pytanie zadane 19 marca w C i C++ przez Nekronomik Początkujący (420 p.)
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ź 19 marca przez mokrowski Nałogowiec (34,140 p.)
edycja 19 marca przez 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ź 19 marca przez Nekronomik Początkujący (420 p.)
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 19 marca przez mokrowski Nałogowiec (34,140 p.)
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 19 marca przez Nekronomik Początkujący (420 p.)

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ź 20 marca przez Nekronomik Początkujący (420 p.)
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 20 marca przez mokrowski Nałogowiec (34,140 p.)
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 21 marca przez Nekronomik Początkujący (420 p.)
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 21 marca przez mokrowski Nałogowiec (34,140 p.)
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ź 162 wizyt
pytanie zadane 11 stycznia w C i C++ przez devi Początkujący (320 p.)
0 głosów
1 odpowiedź 114 wizyt
pytanie zadane 31 października 2016 w C i C++ przez NieznanyV2 Nowicjusz (160 p.)
0 głosów
1 odpowiedź 229 wizyt
pytanie zadane 8 czerwca 2016 w C i C++ przez Kyoya Początkujący (260 p.)

39,763 zapytań

78,219 odpowiedzi

153,731 komentarzy

18,810 pasjonatów

Przeglądających: 203
Pasjonatów: 15 Gości: 188

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...