Jak zarządzać zależnościami między mapą kafelków a jednostkami

11

W pracach mam strategię opartą na kafelkach 2D. Wędruję, jak poradzić sobie z relacją między mapą a jednostkami na mapie.

Biorąc pod uwagę współrzędne kafelków, będę musiał móc postawić na nim jednostkę, jeśli taka istnieje. W tym samym czasie, jeśli otrzymam jednostkę, będę chciał uzyskać współrzędną jednostki.

Widziałem dwa rozwiązania tego. Pierwszym rozwiązaniem byłoby, aby jednostki zapisywały współrzędne, a odniesienia do jednostek mapy zapisywały na swoich kafelkach. Stwarza to cykliczną zależność między mapą a jednostkami. Muszę się upewnić, że mapa dowolnej jednostki będzie zsynchronizowana, jeśli jednostka się poruszy.

Drugim rozwiązaniem byłoby śledzenie współrzędnych tylko przez jednostki. Aby stwierdzić, czy kafelek zawiera jednostkę i uzyskać tę jednostkę, przejrzałbym cały zestaw jednostek, które znajduję, z pasującymi współrzędnymi. Otrzymują one cykliczną zależność, ale tracą właściwość O (1), jaką miało pierwsze rozwiązanie do wyszukiwania jednostek z mapy. Może się to sumować, ponieważ chcę móc regularnie skanować mapę w poszukiwaniu takich rzeczy, jak znalezienie ścieżki, określenie zasięgu ruchu i znalezienie prawidłowych celów dla danej jednostki.

Nie mogę też po prostu przechowywać jednostek na mapie (czy mogę?). Jednostki są powiązane z „armiami”, zarówno graczami, jak i AI. Armia powinna mieć łatwy dostęp i iterację wszystkich swoich jednostek.

Ponieważ wydaje się, że jest to częsty problem w grach strategicznych, czy istnieją jakieś inne wzorce oprócz dwóch opisanych przeze mnie do zarządzania relacjami między jednostkami a mapami?

tiles maps character AJM
źródło

Odpowiedzi:

3

To nie jest popularny wzorzec, ale świat relacyjnych baz danych oferuje trzeci sposób: użyj struktury danych, która ma wiele kluczy. W formie tabelarycznej może to wyglądać następująco:

Unit id    Location
-------------------
  1309     13,15
  2357      7,93
  8552      7,93

Chcesz zapytać: „gdzie jest jednostka 2357?” i wróć 7,93. Chcesz także móc zapytać: „co jest w lokalizacji 7,93?” i odzyskaj 2357 i 8552. Istnieją struktury danych, które umożliwiają wiele kluczy do wyszukiwania rzeczy. Możesz przechowywać to poza jednostkami i poza mapą, jeśli chcesz usunąć zależności.

Jednak w praktyce bardziej powszechne jest zapisywanie lokalizacji w każdej jednostce, a następnie użycie struktury danych partycjonowania przestrzennego, która informuje, jakie jednostki są w danym regionie. Ponieważ jest to osobna struktura, regiony nie muszą być przestrzenią siatki; mogą to być większe obszary.

Zalecam robienie tego, co najłatwiejsze (twoje drugie rozwiązanie), a następnie, jeśli jest to problem z wydajnością, możesz dodać partycję przestrzenną, aby przyspieszyć wyszukiwanie.

amitp
źródło
Tak więc wspomniana struktura danych podziału przestrzennego może być po prostu mapą (która w moim przypadku jest pozornie siatką 2D płytek). Zakładam, że kiedy jednostka się porusza (jest dodawana lub usuwana), muszę zaktualizować zarówno jednostkę, jak i strukturę podziału przestrzennego, aby zachować synchronizację. Może to jedna z tych rzeczy, z którymi będę musiał żyć?
AJM
1
Tak, mapa jest najbardziej szczegółową partycją przestrzenną, jakiej można użyć. Globalna lista wszystkich jednostek jest najbardziej gruboziarnistą partycją. ;) Musisz tylko zaktualizować partycję przed jej użyciem. Jeśli używasz go przez cały czas, prawdopodobnie chcesz go aktualizować za każdym razem, gdy urządzenie jest przenoszone. Jeśli jednak używasz go tylko w niektórych fazach logiki aktualizacji, możesz przejrzeć listę jednostek w jednym przebiegu i obliczyć strukturę danych partycji, a następnie odrzucić ją, gdy skończysz. W ten sposób nie musisz cały czas ich synchronizować.
amitp
5

Cóż, chyba że masz kilka tysięcy jednostek na gracza, nie martwię się o użycie pamięci i skorzystam z pierwszego rozwiązania. Wydaje się, że pamięć jest tańsza niż procesor.

W rzeczywistości, nawet jeśli masz 4000 jednostek na gracza, używając dwóch liczb całkowitych do przechowywania tam lokalizacji, i 8 graczy, co zajmuje tylko 2 MB, ale przy pierwszym rozwiązaniu możesz użyć koordynatora O (1) zamiast O (n) (przy założeniu nieposortowane), co przy dużej liczbie jednostek może być powolne.

Większość gier wydaje się być oparta na pikselach, a nie na kafelkach, teraz już kilka dni, więc muszą tylko zdobyć jednostkę do przechowywania ko-zamówień.

Ray Britton
źródło
Nie martwię się o użycie pamięci, bardziej interesuje mnie zarządzanie zależnościami (w sensie projektowania obiektowego). Martwi mnie to nie dodatkowa pamięć, którą wiązałoby się z pierwszym rozwiązaniem, ale zależność cykliczna, o której się nie mylę, tak jak lubię moduł koordynujący O (1). Wiem też, że wiele gier jest teraz opartych na pikselach, ale lubię kafelki, więc tego właśnie używam. : P
AJM
@AJM, to samo, płatne aplikacje, które będę wypuszczać na Androida, będą używać kafelków.
Ray Britton