Autor Wątek: Quadtree implementacja  (Przeczytany 1263 razy)

Offline daniel1302

  • Użytkownik

# Listopad 30, 2012, 22:15:34
Witam, mam problem z implementacją drzewa czwórkowego.
Jak ona powinna wyglądać?

Myślałem tak:
Przestrzeń 2d dzielimy na kwadraty o najmniejszym kwadracie 10x10px;
I tutaj nie wiem jak to zaimplementować. Myślałem aby w drzewie trzymać AABB danego obszaru.

I wyglądało by to tak
Mamy mapę 100px*100px
                              [(0;0)(100;100)]
   [(0;0)(50;50)]                               [(51;0)(100;50)]                   [(0;51)(50;100)]       [(51;51)(100;100)]
[(0;0)(25;0)] [(26;0)(50;0)]..........


Co myślicie na ten temat?
Nie lepiej jest wykorzystać drzewko binarne dzielące mapę w poziomie?


Jak wg was najlepiej opisywać części mapy?
Jak w tych częściach przechowywać obiekty?


Z góry dziękuje za odpowiedź

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Cerberus

  • Użytkownik
    • Moja strona

# Listopad 30, 2012, 22:30:29
Nie odpowiem Ci, jak powinno to wyglądać, tylko jak ja to zaimplementowałem.

Tak jak drzewko binarne jest po jednym kluczu, tak drzewko czwórkowe jest po dwóch kluczach. Wrzucasz do drzewa element, porównujesz z jednym i drugim kluczem, wybierasz jeden z czterech podrzędnych węzłów, schodzisz piętro niżej.

Drzewko buduje zdaje się tak, jak Ty piszesz: Załóżmy, że ja chce, żeby moje regiony (obszary po podzieleniu powierzchni przez drzewo) nie były większe niż 10 jednostek. Plansza ma 100 x 100 jednostek. Root drzewa ma więc parametry [50][50], cztery niższe węzły to [25][25], [75][25], [25][75], [75][75] etc.

Kiedy drzewo ma już odpowiednią głębokość, pod liście podpinam kontenery na obiekty, do których wrzucane są obiekty z odpowiednimi współrzędnymi, działa to bardzo fajnie jeśli mapa jest duża, jest dużo obiektów statycznych i chcemy wrzucać na GPU tylko to, co potrzebne.

Offline daniel1302

  • Użytkownik

# Grudzień 01, 2012, 09:08:38
Dziękuje, tak to zaimplementuję.

Mapa jest raczej średnia przynajmniej w aktualnym przypadku.

Piszę silnik graficzny(pod gry w Canvas) uniwersalny dla gier platformowych i strategicznych czy izometrycznych lecz z wymiennymi modułami. Cały kod jest obecnie pisany w JavaScripcie.

Nigdy się czymś takim nie zajmowałem, dużo gier pisałem tekstowych Viawww na zamówienie(ala TheCrims, Vallheru itp.) oraz jedną grę typu Margonem(ale to w DOM Obiekt czyli zwykły HTML i obrazki są przesuwane), gdzie pierwszy raz spotkałem się z elementami grafiki