Od jakiegoś czasu chciałem napisać plugin do minecraft w języku Java, który pozwoli graczom tworzyć własne działki na mapie. Działki mieściłyby się na mapie o rozmiarze - 10000x10000 w przestrzeni dwuwymiarowej. Gracze mogliby tworzyć działki w losowych lokalizacjach na tej mapie. Działki miałyby zawsze ten sam rozmiar, na przykład 50 kratek. I teraz mam kilka problemów, po pierwsze podczas tworzenia działek chciałbym sprawdzić, czy działka, którą gracz chce stworzyć, nie nachodzi na inną działkę. Drugim problemem jest to, że gdy gracz wejdzie na teren jakiejś działki, chciałbym, aby zobaczył komunikat z informacją o działce, np. do kogo ona należy, a żeby uzyskać taki efekt musiałbym użyć PlayerMoveEvent, który jak wiadomo przy nawet niewielkim ruchu gracza jest wywoływany wiele razy, więc potrzebowałbym bardzo szybkiego systemu do sprawdzania czy w danym miejscu na mapie jest jakaś działka. Udało mi się napisać dwie struktury danych: KDTree(do szukania działki w danym punkcie) i QuadTree(do sprawdzania czy się nie pokrywają), ale nadal nie wiem czy jest to najlepsze rozwiązanie. Używam JPA + Spring w swoich pluginach. Czy ktoś wie jakie inne szybsze struktury danych można wykorzystać, lub mógłby mnie jakoś nakierować jak to napisać dobrze i co najważniejsze ta żeby działo maksymalnie szybko jak to możliwe?
Ja bym zrobił tak:
-działki przechowywane jako jeden punkt narożny, tzn. przechowujemy punkt [x,y], co oznacza że działka (o stałym rozmiarze 50) jest ograniczona punktami [x,y], [x+50,y], [x,y+50],[x,y].
-przechowywane w liście posortowane po x
-dzięki temu nie trzeba iterować po wszystkich by sprawdzić czy działki nie nachodzą, bierzesz sobie działki spełniające noweX - 50 < x < noweX+50, z tych które spełniają warunek sprawdzasz y (często się może zdażyć że y już nie będzie trzeba sprawdzać bo nie ma takich działek). Szukanie takich działek będzie mieć złożoność
-w sprawdzaniu czy się weszło na inną działkę analogicznie
Z tym że nie mam pojęcia jak napisałeś KDTree i QuadTree, więc nie wiem czy mój pomysł jest dobry, czy zły. Jeszcze bym rozważył trzymanie tego w hashmapie (ze względu na szybki odczyt) lub treemapie (ze względu na sortowanie kluczy), ale nie mam czasu ani głowy na wymyślanie jak dokładnie to zrobić
geospatial
Baza danych Postgreql takie rzeczy ma, więc powędrowałem przypomnieć sobie, jakie to słowo (nie że namawiam do użycia bazy gdy jej nie potrzebujesz)
Wrzuciłem w goola geospatial algorithm wiec wystawia pewną ilosć fachowych artykułow.
Nie, nie miałem praktycznych doświadczeń z tą częścią posgresa, ani zagadnieniami
Nie wiem jakie to bedą w praktyce dane i ilu ma być potencjalnych właścicieli i jakie wymiary czy kształty działek ani jak info o właścicielu jest zaimplementowane. Ale 50 kratek tworzących kształt prostokata to spokojnie idzie dość szybko sprawdzić w większości przypadków jeśli mapa jest po prostu zwykłą tablicą 2D. Taką przykładowo której pojedyncze pole ma powiedzmy 1 bajt rozmiaru gdzie wartość 0 to brak właściciela pola a reszta to 255 identyfikatorów różnych właścicieli.
Zanim zaczniesz kombinować z jakimiś strukturami danych sprawdż zawsze czy najprymitywniejsza implementacja nie będzie wystarczająca. 100000000 bajtów to nie jest w dzisiejszych czasach ilość zawrotna dla hardware, a tablice mają to do siebie, że mogą się lubić z cache. K-D Tree czy Quad Tree wykorzystuje się jeśli coś w problemie krzyczy "nietrywialne właściwości" - np. zawiła geometria wchodzi w interakcję z inną geometrią czy istotne dane są "zatopione" w przesztrzeni której analizowanie cię nie ineresuje i której przechowywanie możesz sobie darować jeśli w ogóle chcesz zmieścić istotne dane w pamięci operacyjnej lub chce się ograniczyć ilość porównań wielu obiektów "każdy z każdym" z danego zbioru bo nie zachodzi przez większość czasu między nimi interakcja więc byłaby to aktywność jałowa.
W tablicy 2D od razu będziesz miał identyfikator właściciela pola zakładając ze każde pole może mieć maksymalnie jednego właściciela. Trudno pobić O(1) takiego rozwiązania, zwlaszcza jeśli wspomagać cię będzie cache. Z opisu jaki przedstawiłeś nie wynika być potrzebował czegoś ponad to.
HubiRto12 napisał(a):
Używam JPA + Spring w swoich pluginach.
Na kiego grzyba JPA (a zasadzie SQL) w tym wszystkim? Do czegoś Ci się przydaje?
Pół biedy jeśli baza jest tam tylko do zapisania/wczytania raz na jakiś czas. Jeśli podejrzewasz go o wysyłanie zapytań SQL co klatkę renderingu to istotnie jakby tak robił to by było strzelanie w plecy wydajności. Pytanie o struktury danych wydaje się jednak przeczyć takiemu scenariuszowi. Nie siedzę w temacie Minecrafta, ale w modach serwerów różnych gier wpychanie różnych SQL do trzymania danych nieulotnych to dość nagminna praktyka sięgająca jeszcze czasów kiedy Quake 3 był w miarę jeśli nie świeżym, to przynajmniej jeszcze ciepłym tytułem. Obecnie przy bogactwie wszelkiej maści bibliotek do zapisywania danych w sposób różny i podłużny można oczywiście często wskazać rozwiązania bliższego do faktycznych potrzeb kalibru. SQL w modach to często strzelanie z ICBM do komara.