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

43

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 )

data-structures game-development Rachel
źródło
Nie sądzę, aby jakikolwiek układ działałby, ponieważ pokoje rosłyby w dowolnym kierunku ... Więc jeśli zaczniesz od [0,0] i skręcisz w lewo? spróbuje [-1, 0].
Paweł
@Paul Dołącz wiersz / kolumnę, przesuń wszystkie dane tablicy, a następnie przesuń wszystkie pozycje gracza, aby dopasować nową tablicę map. Powolny i może być trudny w zależności od tego, ile trzeba przesunąć, ale jest to możliwe. Mimo to odpowiedź Bubblewrap jest znacznie lepsza.
Izkata
Prawdopodobnie się mylę, ale czy nie byłoby lepiej na GameDev.SE?
Dynamiczny
1
@Dynamic To pytanie dotyczące struktury danych, więc dobrze tu pasuje.
Izkata

Odpowiedzi:

44

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)

Folia bąbelkowa
źródło
2
Spraw, aby każdy obiekt Pokoju zawierał informacje z północnego wschodu na południowy zachód do innych obiektów Pokoju, abyś mógł używać zarówno słownika / mapy skrótów, jak i głównych kierunków Pokoju, aby poruszać się po labiryncie (czasami będziesz chciał znaleźć z absolutnymi współrzędnymi i czasami będziesz chciał wiedzieć, co jest na północ od obiektu Room X).
Neil
2
@Paul Myślę, że pomysł polega na utworzeniu słownika pokoi, a podczas budowy nowego Room, poszukaj pokojów w słowniku i dodaj ich linki do Roomobiektu, zanim dodasz nowe pokoje do pozostałych stron. Tak więc wyszukiwanie słownika może nastąpić tylko podczas tworzenia nowego Roomobiektu, a nie podczas podróży międzyRooms
Rachel
7
W ogóle nie ma powodu, aby przechowywać linki do innych pomieszczeń wewnątrz Roomobiektu. Jeśli jesteś w pokoju (x,y)i chcesz podróżować na północ, poszukaj pokoju (x,y+1)w słowniku, tworząc go, jeśli nie istnieje. Słownik wyszukiwań są bardzo szybko O(1).
Karl Bielefeldt
3
@KarlBielefeldt: Pokój @ (x,y+1)może istnieć, ale nie jest możliwy do nawigacji od drogi na (x,y)północ. To znaczy, że krawędź nie może przejść bezpośrednio od (x,y)do (x,y+1).
Steven Evers
2
To komplikujecie. Zasadniczo jest to to samo, co tablica ... z tym wyjątkiem, że przeglądasz ją w słowniku zamiast w tablicy dwuwymiarowej. Będą tam również wszelkie problemy, które napotkasz z tablicą ... ale i tak zamierzał użyć tablicy.
user606723
15

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 .

Steven Evers
źródło
1
Nie jestem pewien, czy wykres jest wystarczający, aby to opisać, ponieważ N / E / S / W tak naprawdę nie są częścią koncepcji wykresu; jest tylko podłączony i możliwe wejście / wyjście.
Edward Strange
3
@CrazyEddie: Należy pamiętać, że struktura danych / a nie ma na celu bezpośredniego mapowania do żadnej konkretnej domeny (w rzeczywistości jest to ich korzyść). W tym konkretnym przykładzie wykres byłby kierunkowy, a krawędzie można w trywialny sposób opatrywać znakiem wyliczeniowym.
Steven Evers
Adnotacja może w prosty sposób egzekwować relacje wschód-zachód, północ-południe. Wyeliminowałoby to problemy z przejściem na zachód z pokoju A do pokoju B, a następnie przejściem na wschód z pokoju B do pokoju C (zamiast pokoju A) z powodu złego połączenia.
Peter Smith
3
Powiedzmy, że chcieliśmy zaimplementować pokój wypełniony przez czarodzieja, który chroni się, teleportując gracza o dziesięć pól w losowym kierunku. Znalezienie tego punktu w strukturze danych opartej na wykresie byłoby bardzo kosztowne, szczególnie jeśli ten pokój nie istniałby i trzeba było wygenerować wszystkie pokoje łączące ten pokój z innym pokojem na wykresie (ponieważ struktura nie pozwalałaby na wiele, wzajemnie rozłączone sekcje lochów).
Mark Booth,
2
@MarkBooth, ale potem zmieniliśmy wymagania, nie?
Joshua Drake
9

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.

Społeczność
źródło
1
Dobra odpowiedź, jak sugeruje Bubblewrap , słownik z krotką pozycji jako kluczem jest rozsądną strukturą do zastosowania w celu zaimplementowania rzadkiej macierzy.
Mark Booth,
2

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.

Paweł
źródło
1

To, co projektujesz, przypomina bardzo wykres.

Wykres labiryntu

Są one często przedstawiane jako zbiór stanów Q , stan początkowy q 0 ∈ 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 0 : 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.

kba
źródło
0

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ć.

Edward Strange
źródło
1
Czy mógłbyś rozwinąć pojęcie „listy połączonej w 4 kierunkach”? Jedyne, co mogłem znaleźć, to artykuł CodeProject, który sprowadza się do bycia listą przyległości.
Steven Evers
0

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ć.

laaph
źródło
0

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ą.

juliański
źródło