Jak zbudować strukturę danych dla dynamicznego „labiryntu” o nieograniczonej wielkości?

Nie jestem pewien, czy „labirynt” jest właściwym terminem. Zasadniczo użytkownicy zaczynają od jednego, Roomktóry ma 4 drzwi (N, S, E i W). Mogą iść w dowolnym kierunku, a każdy kolejny pokój zawiera inny pokój z dowolnym miejscem od 1 do 4 drzwi prowadzących do innych pokoi.

„Labirynt” ma być nieograniczony i powiększać się w miarę przemieszczania się po pokojach. Dostępna jest ograniczona liczba Rooms, jednak dostępna liczba jest dynamiczna i może ulec zmianie.

Mój problem polega na tym, że nie jestem pewien najlepszej struktury danych dla tego typu wzorca

Najpierw pomyślałem o użyciu tablicy Roomobiektów [X] [X] , ale naprawdę wolałbym tego unikać, ponieważ rzecz ma rosnąć w dowolnym kierunku i należy budować tylko pokoje, które są „odwiedzane”.

Inną myślą było, aby każda Roomklasa zawierała 4 połączone Roomwłaściwości dla N, S, E i W, i po prostu łączyła się z poprzednią Room, ale problem z tym, że nie wiem, jak rozpoznać, czy użytkownik wejdzie do pokoju, w którym ma sąsiadujący pokój już „zbudowany”

Na przykład,

--- --- ----------
| | | |
   Rozpocznij 5 4
| | | |
--- --- --- ---
--- --- ---------- --- ---
| | | | | |
| 1 2 3
| | | | | |
--- --- --- --- ----------

Jeśli użytkownik przejdzie z pozycji Start> 1> 2> 3> 4> 5, wówczas Roomnr 5 musi wiedzieć, że W zawiera pokój początkowy, S oznacza pokój nr 2 iw tym przypadku nie powinien być dostępny, a N może być albo nowy Roomlub ściana (nic).

Być może potrzebuję połączenia tablicy i połączonych pokoi, a może po prostu patrzę na to w niewłaściwy sposób.

Czy istnieje lepszy sposób budowania struktury danych dla tego typu „labiryntu”? Czy też jestem na dobrej drodze z obecnym procesem myślowym i brakuje mi tylko kilku informacji?

(Jeśli jesteś zainteresowany, projekt jest grą bardzo podobną do Munchkin Quest )

Podaj współrzędne każdego pokoju (początek wynosiłby (0,0)) i zapisz każdy wygenerowany pokój w słowniku / haszapie według współrzędnych.

Ustalenie sąsiednich współrzędnych dla każdego Pokoju jest banalne, dzięki czemu można sprawdzić, czy Pokój już istnieje. Możesz wstawić wartości null, aby reprezentować lokalizacje, w których już ustalono, że nie ma pokoju. (lub jeśli nie jest to możliwe, nie jestem pewien atm, osobny słownik / mapa dla współrzędnych, które nie zawierają pokoju)

W większości przypadków to, co opisujesz, brzmi jak wykres. Biorąc pod uwagę niektóre z twoich wymagań (aspekt rosnący) prawdopodobnie wybrałbym listę implementacji jako implementację (inną powszechną opcją byłaby macierz zgodności ).

Nie jestem pewien, co język używasz, ale dobry poradnik / wyjaśnienie ze szczegółami realizacji na wykresie realizowanego z listy przylegania w .NET jest tutaj .

Kilka przemyśleń na temat implementacji (pomyślałem o Carcassonne, która ma wiele innych trudnych aspektów budowania matrycy - było to nawet pytanie do wywiadu, które kiedyś zadano mi).

Istnieje kilka pytań dotyczących tej struktury:

1. czy jest pokój w X, Y?
2. czy jest pokój [N / S / E / W] pustej lokalizacji X, Y?

Problem z prostymi listami i wykresami

Trudność z prostymi listami polega na tym, że trzeba chodzić po strukturze, aby sprawdzić, czy coś można umieścić w danym miejscu. System potrzebuje sposobu dostępu do dowolnej lokalizacji O (1).

Rozważać:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

Aby znaleźć informacje o możliwej lokalizacji „?”, Gdy w wieku 3 lat trzeba przejść całą drogę, aby dostać się do 4. Odpowiedź łącza z dodatkowymi informacjami o tym, ile węzłów przeskakuje (tak, aby 3 było połączone z 4 z dodatkowymi informacjami „skoku 1”) nadal wymaga spacerów, gdy znajduje się sąsiedztwo „*” od 6 lub A.

Proste, duże tablice

Dostępna jest ograniczona liczba pokoi

Jeśli nie jest to duża liczba, po prostu utwórz tablicę 2N x 2N i pozostaw ją tam. Tablica 100 x 100 to „tylko” 10 000 wskaźników i 50 obiektów. Indeksuj bezpośrednio do tablicy.

Można to zredukować do NxN, jeśli działania poza granicami przesunęły tablicę tak, aby zawsze mieściły się w ograniczeniach. Na przykład, jeśli ma zostać dodane pomieszczenie, które będzie niedopełniać macierzy, siatka przesunie każdy element o jedną pozycję, aby nie było już niedomiaru. W tym momencie świat na 50 pokoi wynosiłby 2500 wskaźników i 50 obiektów.

Rzadkie tablice i macierze

Aby bardziej optymalnie to stworzyć, zajrzyj do rzadkiej tablicy, w której większość elementów ma wartość 0 lub zero. W przypadku dwóch wymiarów jest to znane jako rzadka matryca . Wiele języków programowania ma różne biblioteki do pracy z tą strukturą. Jeśli biblioteka ogranicza się do liczb całkowitych, można użyć tej liczby całkowitej jako indeksu w ustalonej tablicy pokoi.

Moim preferowanym podejściem byłoby mieć pokoje jako strukturę (wskaźniki do sąsiednich pokoi i współrzędne) i mieć pokój również wskaźnikiem z tabeli mieszającej, która jest mieszana na współrzędnych. W tej sytuacji, aby zapytać, który pokój jest [N / S / E / W] z pokoju zerowego, należy zapytać o tablicę skrótów. Nawiasem mówiąc, jest to format „DOK” do przechowywania rzadkiej matrycy.

Co powiesz na to..

Daj każdej komórce link do każdego z jej sąsiadów. Nadaj każdej komórce jakąś nazwę (np. „0/0”, „-10/0” (Załóżmy, że zaczynasz od 0,0)). Dodaj zestaw Hash ze wszystkimi nazwami. Podczas próby przejścia do innej komórki po prostu sprawdź, czy sąsiad nie istnieje jeszcze w zestawie HashSet.

Ponadto, jeśli utworzysz wejście do innego pokoju, czy to oznacza, że ​​pokoje istnieją? Tak więc utworzysz link do pustego pokoju bez żadnych linków do żadnych pokoi. Prawdopodobnie zechcesz także sprawdzić sąsiadów nowych pokoi. Jeśli taki istnieje i otworzyłby się w twoim nowym pokoju, dodaj drzwi do tego pokoju.

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | -1, 1 | -1 ....} 1,0: W = 0,0 / drzwi; 1,0: N = 1,1 / Pusty; E = 2,0 / drzwi; S = 1, -1 / ściana

Musisz także zadbać o to, aby każdemu nowemu pokojowi dać przynajmniej jedne drzwi nieprzylegające (do innego pokoju), aby labirynt mógł rosnąć w tym kierunku.

To, co projektujesz, przypomina bardzo wykres.

Są one często przedstawiane jako zbiór stanów Q , stan początkowy q ₀ ∈ Q i niektóre przejścia Δ . Sugeruję więc przechowywanie go w ten sposób.

• Zestaw Q : {s, 1, 2, 3, 5, 6}
• Stan początkowy q ₀ : s
• Mapa relacji przejściowych Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

Najbardziej rozsądne języki mają zarówno mapy, jak i zestawy.

Możesz rozważyć listę połączoną w 4 kierunkach ...

Najpierw pomyślałem o użyciu tablicy obiektów X [X] [X], ale naprawdę wolałbym tego unikać, ponieważ ta rzecz ma rosnąć w dowolnym kierunku i należy budować tylko pokoje, które są „odwiedzane”.

Nadal możesz do tego użyć [] []. Dynamiczny wzrost może być powolny, szczególnie przy dodawaniu na początku, ale może nie aż tak źle. Powinieneś profilować, aby to sprawdzić. Próba manipulowania połączoną listą lub mapą może być w rzeczywistości gorsza i raczej na stałym poziomie niż sporadycznie.

Możesz budować tylko odwiedzane pokoje, wdrażając leniwe oceny. Obiekt może znajdować się w miejscu, które zawiera pokój i nie buduje tego pokoju, dopóki nie room()zostanie do niego wywołany. Potem za każdym razem zwraca to samo. Nietrudno to zrobić.

Nauczyłem się tego robić dzięki książce „Tworzenie gier przygodowych na komputerze”. Jeśli chcesz przekopać się przez kod BASIC (ta książka jest tak stara), przeczytaj tutaj:

http://www.atariarchives.org/adventure/chapter1.php

Skrót polega na tym, że mają tablicę pokoi, a element w każdej tablicy jest wskaźnikiem do innego pokoju, do którego możesz przejść, z 0 (użyłbym teraz -1), aby wskazać, że nie możesz idź tą drogą. Na przykład zrobiłbyś strukturę pokoju (lub klasę lub co-masz-ciebie)

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Wtedy możesz mieć strukturę tablic lub połączonych list, lub w inny sposób chcesz zarządzać swoimi pokojami. Dla wektorów w stylu tablicowym (lub wektorów C ++) użyłbym tego kodu, a kierunki zawierałyby indeks pokoju, do którego prowadzą; w przypadku listy połączonej można użyć wskaźników do następnego pokoju.

Jak powiedzieli inni, jeśli chcesz dynamicznie generować nowe pokoje, gdy ludzie do nich wchodzą, możesz to zrobić.

Nie próbuj rozwiązywać wszystkich problemów za pomocą jednej struktury.

Zdefiniuj obiekt pokoju, aby przechowywać rzeczy o pokoju, a nie jego relacje z innymi pokojami. Następnie tablica 1D, lista itp. Mogą rosnąć, jak chcesz.

Oddzielna struktura może zawierać „osiągalność” - które pokoje są dostępne z pokoju, w którym się znajduję. Następnie zdecyduj, czy przechodnia osiągalność musi być szybkim obliczeniem, czy nie. Możesz chcieć obliczenia brutalnej siły i pamięci podręcznej.

Unikaj wczesnej optymalizacji. Używaj naprawdę prostych struktur i głupich, łatwych do zrozumienia algorytmów, a następnie optymalizuj te, które się przyzwyczają.