Dwukierunkowa struktura danych dla tej sytuacji

Question

Uczę się małej części mojego silnika gry i zastanawiam się, jak zoptymalizować niektóre części.

Sytuacja jest dość prosta i jest on następujący:

• Mam mapę Tile S (przechowywany w bi-wymiarowej tablicy) (~ płytek 260K, ale zakładamy, wiele więcej)
• mam listę Item s, które zawsze są w co najmniej i co najwyżej dachówki
• Tile można logicznie zawierać nieskończoną ilość Item s
• Podczas wykonywania gra wiele Item s są ciągłe ly tworzone i zaczną z własnej Tile
• Każdy Item nieustannie zmienia swój Tile do jednego z sąsiadów (góra, prawo, dół, lewo)

Do tej pory każdy Item ma odniesienie do jego rzeczywisty Tile i po prostu przechowuję listę przedmiotów. Za każdym razem, gdy Item przesuwa się na sąsiedni kafelek, aktualizuję tylko item->tile = .. i nic mi nie jest. Działa to dobrze, ale jest jednokierunkowy.

Podczas rozbudowy silnika zdałem sobie sprawę, że muszę znaleźć wszystkie elementy zawarte w kafelku wiele razy, co skutecznie obniża wydajność (szczególnie w niektórych sytuacjach, w których muszę znaleźć wszystkie przedmioty dla zakresu płytek, jeden po drugim).

Oznacza to chciałbym znaleźć struktury danych odpowiedniego znaleźć wszystkie elementy określonego Tile lepsze niż w O (n), ale chciałbym uniknąć dużo napowietrznych w „przejście od jednej płytki do kolejna "faza (teraz to jest właśnie przypisywanie wskaźnika, chciałbym uniknąć wykonywania wielu operacji tam, ponieważ jest to dość częste).

Zastanawiam się nad niestandardową strukturą danych, aby wykorzystać fakt, że przedmioty zawsze przesuwają się do sąsiedniej komórki, ale w tej chwili szukam po omacku! Każda rada byłaby doceniona, nawet podchwytliwe lub zagadkowe. Niestety nie mogę po prostu marnować pamięci, więc potrzebny jest dobry kompromis.

Rozwijam go w C++ z STL, ale bez zwiększenia. (Tak, wiem o multimap, to mnie nie satysfakcjonuje, ale spróbuję, jeśli nie znajdę nic lepszego)

Answer 1

struct Coordinate { int x, y; }; 
map<Coordinate, set<Item*>> tile_items; 

To mapuje współrzędne na mapie kafelków do zestawów wskaźników Przedmiotów wskazujących, które elementy znajdują się na tym kafelku. Nie potrzebujesz wpisu dla każdej współrzędnej, tylko te, które faktycznie mają na nich przedmioty. Teraz wiem, że to powiedział:

ale chciałbym uniknąć dużo napowietrznych w „przejście od jednej płytki do innej” fazie

a ta metoda wiązałoby dodając więcej napowietrznych, że faza. Ale czy próbowałeś już czegoś takiego i ustaliłeś, że to problem?

Answer 2

Dla mnie chciałbym owinąć std::vector w typ matrycy (IE narzucić dostęp 2d na tablicy 1d) daje to szybki losowy dostęp do dowolnych twoich płytek (implementacja macierzy jest banalna).

użycie

vector_index=y_pos*y_size+x_pos; 

do indeksu wektorem wielkości

vector_size=y_size*x_size; 

Następnie każdy element może mieć std :: vector przedmiotów (jeśli kwota pozycji płytka ma bardzo dynamiczny może Deque) znowu są to losowe dostęp zawiera bardzo minimalny narzut.

Chciałbym trzymać się z daleka od pośrednich pojemników na wypadek użycia.

PS: jeśli chcesz, możesz mieć mój szablon matrycy.

Answer 3

Jeśli naprawdę myślisz, że posiadanie każdego magazynu płytek będzie kosztowało Cię zbyt dużo miejsca, rozważ użycie quadtree do przechowywania przedmiotów. Pozwala to skutecznie uzyskać wszystkie elementy na kafelku, ale pozostawia ruszt na miejscu w celu przesunięcia przedmiotu.