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

Drzewo czwórkowe-kolizje

VPS Starter Arubacloud
+2 głosów
747 wizyt
pytanie zadane 19 marca 2017 w C i C++ przez Nekronomik Użytkownik (600 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

+1 głos
odpowiedź 19 marca 2017 przez mokrowski Mędrzec (155,460 p.)
edycja 19 marca 2017 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 2017 przez Nekronomik Użytkownik (600 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 2017 przez mokrowski Mędrzec (155,460 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 2017 przez Nekronomik Użytkownik (600 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 2017 przez Nekronomik Użytkownik (600 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 2017 przez mokrowski Mędrzec (155,460 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 2017 przez Nekronomik Użytkownik (600 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 2017 przez mokrowski Mędrzec (155,460 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ź 550 wizyt
pytanie zadane 11 stycznia 2017 w C i C++ przez devi Początkujący (320 p.)
0 głosów
1 odpowiedź 663 wizyt
pytanie zadane 31 października 2016 w C i C++ przez NieznanyV2 Nowicjusz (160 p.)
0 głosów
3 odpowiedzi 828 wizyt
pytanie zadane 8 czerwca 2016 w C i C++ przez Kyoya Początkujący (260 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...