Losowy labirynt z klocków

[Barsztik]

Cześć.

 

Przymierzam się do stworzenia labiryntu trochę na zasadzie rogouelike, ale maksymalnie uproszczonego.

 

Wymyśliłem sobie, że świat składałby się z kwadratowych komnat w rzucie top-down, z których każda mogła by mieć 1-4 wyjść w różnych kombinacjach (część z nich widoczna na obrazku ? po zielonym można chodzić, szare symbolizuje ściany) - teoretycznie mogła by nie mieć wyjść wcale, ale to by było bez sensu ;-) . Komnaty byłyby zapisane w systemie 0,1,0,0 (gdzie 1 to ściana, 0 to przejście) - 0,1,0,0 to zapis pomieszczenia widocznego w prawym dolnym narożniku obrazka. Taki system łatwo rozszerzyć o inne struktury np.: 1 ? ściana z kamienia, 2 ? ?ściana? z lasu, 3 ? rzeka.Na raz widoczna jest tylko ta komnata, w której znajduje się gracz.

 

Obrazek 1

 

 

Można też komnaty w całkowicie swobodny sposób narysować w programie graficznym i przechowywać w png, a w systemie 0,1,0,0 przechowywać jedynie zapisane przejścia jak na drugim obrazku.

 

Obrazek 2

 

 

Problemu nie ma (jakiegoś super dużego) jeśli zapiszę cały labirynt. Robiłem podobnie w basicu na 8-bitowcu, zapisując wszystkie komnaty w systemie 9 liczb: 13, 0,1,1,0, 0,8,12,0 gdzie pierwsza to numer komnaty, następne cztery to zapisane ściany i przejścia, a ostatnie cztery zawierały numery komnat, do których prowadziły przejścia. Jednak teraz chciałbym by świat tworzył się losowo, ale tak by przejścia zawsze pasowały. Na obrazku komnata 1 to komnata startowa, te oznaczone zielonym ptaszkiem pasują, ta czerwonym x nie pasuje. Te z szarymi pytajnikami w zasadzie też nie bo pozwalają wyjść poza świat.

 

Co sądzicie o takim pomyśle, czy prosty wydaje się tylko mojej głowie, ale w implementacji do gml byłby bardzo skomplikowany? Czy lepiej losować komnaty w locie (przy przejściu z jednej do drugiej), czy przy uruchomieniu gry.

 

 

Czy takie rozwiązanie ma sens?

[I am vader]

Tak.

 

Zwazajac na tresc Twojego pytania, zakladam, ze wolisz wskazowki anizeli gotowce(co przyznam, jest dobrym posunieciem, dobrze ze wiesz co robisz).

Skoro roomy sa tych samych wielkosci to mieszcza sie w siatce, wiec mozesz trzymac dane w jakies strukturze oraz wymusic konkretne wartosci, np. zeby sciany przylegajace do wszystkich wygenerwoanych juz wejsc, mialy wejscia.

To co mam na mysli przez powyzsze zdanie, to ze mozesz miec w generatorze 3 podstawowe wartosci dla kazdego niewygenerowanego roomu: Wymus sciane, Wymus wejscie, Losowe.

Sciane wymusza poboczny room jezeli on tez tam ma sciane.(Jezeli Room A ma sciane z prawej, to w roomie z prawej wymusza sciane z lewej).

Przejscie wymusza poboczny room jezeli on tez tam ma wejscie.(Jezeli Room A ma przejscie na dole, to w roomie na dole wymusza wejscie u gory).

Losowe to cokolwiek czego nie wymusily inne roomy.

 

Jezeli ma byc okreslona ilosc pomieszczen max, wystarczy ze po przekroczeniu ilosci roomow, wszystkie pozostale maja sciany tam gdzie nie wymusilo sie przejscia.

Oczywiscie w wyniku niefortunnych wynikow losowosci moze byc ekstremalnie maly dungeon wygenerowany. Wtedy wystarczy, ze okreslisz, ze dopoki nie ma conajmiej X roomow na mapie, conajmniej 1 losowa(niewymuszona) sciana musi miec przejscie.

 

Jezeli chodzi o samo wziecie sie za generowanie, polecam uzyc struktury ds_list do zapisania par wspolrzednych roomow ktore sa przeznaczone do stworzenia.

Najprosciej ujmujac, jezeli masz swoj room poczatkowy [0,0] i z prawej wygeneruje przejscie, dodajesz do listy [1,0](JEZELI JEJ JUZ NIE MA NA LISCIE)(oraz pamietasz o wymuszeniu na pozycji 1,0 przejscia w lewej scianie).

 

 

[Barsztik]

Tak, wolę wskazówki :) A to dlatego, że bardziej zależy mi na stworzeniu możliwie najprostszego algorytmu prowadzącego do mojego celu(nawet poza gml), niż samej gry.

 

Wymuszanie ścian/drzwi jest bardzo ciekawym pomysłem. Bardzo mi się podoba.

 

Jeśli dobrze Cię zrozumiałem to nie losuję komnat z zapisanych możliwości, tylko same drzwi. Część już stworzoną przechowuję w siatce.

(Legenda: 1 ? ściana, 0 ? przejście, ? ? nie interesuje mnie w danej chwili, A ? w danej chwili jest określana)

 

1. tworzę komnatę o współrzędnych x,y i zapisie 1,1,1,1 ( przyjmijmy, że drzwi są oznaczone począwszy od godziny 12-ej zgodnie z ruchem wskazówek zegara ? góra, prawo, dół, lewo)

 

2. przechodzę do skryptu losującego drzwi:

 

- sprawdzam, czy komnata x,y-1 istnieje? Jeśli nie losuję drzwi A,?,?,?. Jeśli istnieje to: jeśli ma kształt ?,?,0,? to w tworzonej komnacie wymusza 0,?,?,? Jeżeli ma kształt ?,?,1,? to w tworzonej komnacie wymusza 1,?,?,?

 

- następnie sprawdzam czy komnata x-1,y istnieje i postępuję analogicznie dla tych i kolejnych drzwi.

 

3. W zależności od wybranej metody:

 

- czekam aż gracz gdzieś przejdzie i wtedy ponownie odpalam skrypt tworząc komnatę powiedzmy x,y+1 (poszedł w dół) ? jeżeli zdecydowałem się tworzyć labirynt w locie - jednorazowo tylko jedna komnata = szybkość:)

 

 

- przechodzę do tworzenia kolejnej komnaty (x+1,y etc?) ? jeżeli zdecydowałem się losować cały labirynt przy uruchomieniu gry. Wolniej, ale łatwiej będzie porozrzucać w sensowny sposób znajdźki. Np: skrzynia musi być oddalona co najmiej o 5 komnat od klucza itp...

 

 

 

 

Czy to miej więcej miałeś na myśli?

 

 

[edit] początkowo założyłem, że będę używał ds_grid, ale chyba faktycznie ds_list będzie tu zwyczjanie prostszy [/edit]

[I am vader]

Apropo kroku 2, nie o to chodzi.

Chodzi raczej o budowanie wokol punktu startowego.

Zamiast leciec po kolei kazda wspolrzedna tworzysz pierwszy room na teoretycznej pozycji [x,y] a nastepnie dopisujesz do listy pozycje do ktorych wygenerowano wyjscia. Przykladowo romo startowy [x,y] Wylosowal wartosci 1,1,0,0, wiec do listy dopisujesz [x,y-1] oraz [x+1,y], nastepnie przechodzisz do generowania tych dwoch pozycji z listy, z kazda dopisujaca wiecej pozycji.

 

 

DS_GRID sie tu nie nada bo moga byc pozycje o ujemnych wartosciach

 

Edit: Huder w temacie, czuje sciane kodu. W sumie to nawet dobrze. Jezeli ktos tu wie jak porzadnie generowac te rzeczy(Ja glownie tutaj improwizuje idac droga logiki, nie ma powodu aby to nie zadzialalo, ale pewnie sa wydajniejsze sposoby) to HuderLord i Threef

 

Edit 2: Pozwolilem sobie zrobic malego gifa. Zielone to koordynaty dodane do listy, numer to kolejnosc, a rozowe to wymuszona sciana / wymuszone przejscie.

 

[I am Lord]

Gdybym miał coś takiego robić to najpierw bym wziął jakiś algorytm generowania labiryntu https://en.wikipedia.org/wiki/Maze_generation_algorithm

i wygenerował bym go w postaci ds_grida. I przyjąłbym że każda zapełniona kratka grida to pomieszczenie. Po wygenerowaniu całego grida przelatujesz go jeszcze raz i przypisujesz każdej komórce ds_listę ( Threef zaraz mi wyjedzie że by zrobił ds_map :D ), którą wypełniasz swoimi właściwościami pomieszczenia. Najbardziej podstawowa lista by miała 4 wartości, które oznaczają 4 rodzaje ścian, łatwo to dalej rozwinąć np dodając kolejne 4 wartości określające typy drzwi itd.

[Threef]

Cześć!

Widzę że zostałem przywołany, ale widzę też że I am vader już dobrze wytłumaczył i nie mam tu za dużo do roboty. ;)

 

Ogółem już sam zauważyłeś że możesz generować labirynt na 2 sposoby: jednorazowo przy starcie, albo na bieżąco przy zmianie pomieszczenia. Oba rozwiązania będą miały swoje plusy i minusy dlatego zaproponuję abyś zrobił sobie prototypy oboma sposobami i wybrał ten który wyda się ciekawszy.

 

Wszystko i tak sprowadzi się do przechowywania danych. HuderLord śmiał się że przyjdę i będę proponował ds_map i też się zaśmiałem bo nie widziałem sensu, ale to też jest możliwość. Na pewno odradzę ds_grid i tablice 2 wymiarowe. Chyba że mapa miałaby ustalony maksymalny rozmiar, wtedy to nawet zalecam ds_grid.

 

Sposób jaki zaproponuję do przechowywania danych to flagi bitowe które ostatnio pokochałem. Nie chce mi się opisywać dokładnie tego jak maja działać więc zapraszam do internetu gdzie zrobiło za mnie to już dużo ludzi. Link.

 

Implementacja w GM jest banalna. Najwygodniej można to zrobić przy pomocy stałych albo enum. Ale skoro masz tylko 4 flagi to możesz olać to i zapamiętać wartości. Tylko po co? Skoro enum jest taki fajny?

GML

enum paths {

N = 1,

E = 2,

S = 4,

W = 8

}

Dzięki temu zapisanie czy pokój ma przejścia wygląda tak:

GML

mapa[#xx, yy] = paths.N + paths.E + paths.W

A efektem jest to że zapisana wartość to po prostu 11. Zamiast jakiś tablic, albo stringów. Problemem może się teraz wydawać sprawdzenie ścian, ale robi się to poprzez bitowy AND tak:

GML

if(mapa[#xx, yy] & paths.N) {

// północna ściana

}

 

if(mapa[#xx, yy] & paths.E) {

// wschodnia ściana

}

 

(...)

 

Powodzenia ;)

[I am Lord]

Też myślałem nad zaproponowaniem flag ale nic mu nie daje zwykła informacja czy drzwi są czy nie. On potrzebuje określić więcej danych, które przypadają na ścianę. Stąd wzięła się moja lista bo tam sobie może władować co tylko zechce.

[Barsztik]

Odpowiedź tak na szybko, bo nie mam chwilowo czasu by to dobrze rozkminić, a Wasz odzew jest na tyle duży i rzeczowy, że niemógłbym go zignorować.

 

Im A Vader: Dzięki za gifa, teraz już rozumiem

 

Im A Lord: ten artykuł z wiki znam, ale nie chcę korzystać z tych gotowych algorytmów. Nie żebym uważał mój pomysł za lepszy, bo na dzień dobry widać, że jest słabszy, ale jest mój i czerpię frajdę z zabawy z nim. Chociaż żywię również przekonanie, że nie ja jeden na takie rozwiązanie wpadłem ;-).

 

Threef: flag bitowych używałem niewiedząc nawet, że tak się nazywają. :-) Dzięki. Z Amstradadowego basica pamiętam jeszcze, że w ten sposób definiowało się czcionki. Miały rozmiar 8x8 i uzywało się komnedy Symbol 65,255,255,255,255,255,255,255,255. Pierwsza liczba to kod ascii, a kolejne to dziesiętny zapis wierszy 11111111, czyli jak to mądrze nazwałeś flagi bitowe.

 

A może połączyć oba Wasze rozwiązania? Zamiast zapisywać drzwi w czterech wartościach 1,1,1,1, zapisać z wykorzystaniem tych magicznych flag bitowych jako 15. Oszczędzam w ten sposób 3 wartości, w których mogę zapisywać różne inne pierdółki, np. "biom" - który mógłbym sprawdzać w sąsiednich komnatach analogicznie do przejść/ścian. Chociaż nie sądzę bym zużył wszystkie wartości w ds_list.

 

Dobra. Dziękuję za rady, w wolniejszym czasie muszę to wprowadzić w życie.

Dam oczywiście znać co się wykluło. :-)