Algorytm tworzenia lochów

[Sutikku]

Witam. Chciałem się w końcu nauczyć robić losowy generator mapy. Padło na dungeony. Chodzi mi o takie jakie są na przykład w The Binding of Isaac, czy nowej grze zwanej Enter the Gungeon. No i teoretycznie wypisałem sobie punkty jak to w teorii ma wyglądać. Myślałem żeby robić to tak

1. W centrum ustawiam pokój.

2. W każdej ze ścian daje jakąś szansę, że zrobi się przejście.

3. Jeśli zrobiło się przejście to ustawia się pokój.

4. Powtarza punkt 2 i 3, aż zabraknie możliwości, czy dojdzie do jakiegoś tam ustalonego limitu.

Wszystko wygląda pięknie, w czym więc problem? Ano jak takowy pokój postawić.

A jakby ktoś miał jakiś inny pomysł, jak tworzyć dungeony fajniejsze, łatwiejsze, cud miód orzeszki, to z chęcią wysłucham.

[PsichiX]

jest parę algorytmów generujących korytarze - podpytaj Threefa, bo on w tym więcej siedział :3

[I am Lord]

Właśnie coś takiego próbuje zrobić na marketplace bo idealnie pasuje do mojego poprzedniego skryptu z labiryntem :D

Jak wpadnę na coś fajnego, łatwego w użyciu to coś o tym napiszę. Głównie chodzi mi oto by obejść się bez tworzenia jakiegoś edytora i kombinowania z plikami.

[Threef]

*wynurza się z czeluści piekielnych po usłyszeniu słów inkantacji*

 

Widzę że ogarnąłeś całkowite podstawy więc teraz już będzie z górki.

Ogółem wszystko co będziesz robić będzie bazowało na tablicach (albo ds_grid). Każda komórka będzie zawierała id (twoje wymyślone, nie id obiektu). Na początek uznajmy że id=0 to powietrze a id=1 to ściana no i róbmy to na ds_grid (muszę porobić testy czy wciąż jest szybszy od tablic, ale użyjemy go z innego powodu). Jeszcze przypomnę o różnicy pomiędzy random() a irandom(), bo możesz mieć przez to czasami problemy. ;)

 

Wypełnij całą mapę (tak teraz będę nazywał nasz ds_grid) wartością 0 używając ds_grid_clear(), a połowę ustaw na 1 przez ds_grid_set_grid_region(). Robimy to tylko dla testów więc teraz zrób ds_grid_shuffle() i mamy testowe dane.

Teraz zabierz się za wyświetlanie tego wszystkiego w room. Najprościej jest przelecieć całą mapę przez podwójny for:

GML

for(var _y=0;_y<ds_grid_height();_y++)

for(var _x=0;_x<ds_grid_width();_x++)

{}

Na podstawie wyciągniętych danych z mapy wstawiaj odpowiedni instance w room na odpowiedniej pozycji. Nie masz pojęcia jak? _x*szerokość ściany etc. Jeżeli dobrze wszystko ustawisz to nie będziesz musiał się nawet bawić w depth ze ścianami w izometrii. ;)

Jak wszystko jest ok to możesz zabierać się za generator. (uwierz że wcześniej nie ma sensu bo nie będziesz widzieć efektów, co prawda ja kiedyś się bawiłem w rysowanie tego co mi wyszło przez draw_point() ale po co?)

 

 

 

Więc twój pierwszy punkt jest jak najbardziej poprawny i jest całkowitą podstawą. Pierw ds_grid_clear(,1) a potem ds_grid_set_region() z 0 na środek. I mamy nasz pierwszy pokoik.

 

Teraz twój drugi punkt wymagałby podania większej ilości informacji. Co rozumiesz przez "przejście"? Zwykłe drzwi czy korytarz? Zrobienie drzwi nie jest proste bo muszą łączyć 2 sąsiadujące pokoje, za to korytarze można stawiać na setki sposobów. Olejemy drzwi bo nie mam zamiaru rozpisywać się. Opiszę za to 3 bardzo proste sposoby.

 

1. Korytarz łączy dwa pokoje.

1. Losujemy wartości naszego pokoju: wysokość, szerokość, pozycję x i y. Pamiętając aby nie próbować stawiać pokoi poza rozmiarem mapy!
2. Przed postawieniem pokoju sprawdzamy czy nie ma tam już innego pokoju. Jak? Dzięki ds_grid_get_min()! Funkcja ta zwraca najmniejszą wartość wewnątrz prostokąta, to oznacza że jak wewnątrz naszej pozycji dla nowego pokoju będzie jakiś kawałek innego pokoju (wartość 0 czyli brak ściany) to będziemy o tym wiedzieć.

   Nasz punkt 1 jest pętlą do, a punkt 2 warunkiem w until()

3. Gdy mamy pozycję na pokój stawiamy go przy pomocy ds_grid_set_region()

   Teraz zaczyna się magia:

4. x i y naszego pokoju dodajemy do dwóch ds_list. Nazwijmy je list_rooms_x i list_rooms_y. (Muszą tam też być x i y pierwszego pokoju! lol)
5. Punkty 1-4 wykonujemy aż zabraknie możliwości albo nastąpi inny warunek kończący.

   Korytarze:

6. Dopóki wewnątrz list_rooms_x jest więcej niż 1 dana ( while(ds_list_size(list_rooms_x)>=2){} ) wykonuj punkty 7-8
7. Wstaw korytarz. Tu możesz puścić wodze fantazji. Musisz po prostu wyryć drogę pomiędzy x i y jednego pokoju a x i y drugiego. Możesz spróbować narysować pogrubioną linę pomiędzy punktami, ale jest to trudniejsze niż się wydaje. :P Najprostsze rozwiązanie to... narysowanie obwodu prostokąta. Nie ma do tego funkcji w GM więc musisz napisać sobie coś takiego ds_grid_set_region(mapa,x1,y1,x2,y1,0)
8. Usuń jedną parę punktów z naszych ds_list. Przy rysowaniu polecam losować tylko x (y będzie na tym samym index) a do pary brać parę o następnym index.

Jeżeli czegoś nie pomyliłem to wyszedł algorytm z bardzo długimi korytarzami. Możesz teraz zacząć się bawić w jego customizację. Robić grubsze korytarze, albo losować aby wejście do korytarza nie było zawsze na środku pokoju. Moje ulubione może być sprawienie aby pozycja pokoju usuwała się z lista tylko czasami, dzięki temu jeden pokój będzie połączony z kilkoma.

Efektem może być coś takiego:

Sorry że gif, ale innego nie miałem.

(gif w ogóle przedstawia skrypt dungeon crawlera. Postać sama chodzi po labiryntach aż nie spotka czegoś interesującego jak przeciwnik, albo nie zwiedzi całego labiryntu)

 

2. Najprostszy algorytm ever.

Są to punkty 1-3 z poprzedniego algorytmu... z tym że warunek jest odwrócony i stawiamy pokój tylko gdy będzie miał wspólną część z innym pokojem. Ta! da! Banalny i piękny. Żadnych korytarzy! To już działa! Możesz się teraz pobawić z jego customizacją i olać wszystkie inne algorytmy bo ten wystarczy Ci do końca życia. Spróbuj wymusić aby pokoje nigdy nie były kwadratami a zawsze były płaskie albo długie, a algorytm zacznie rzeczy niesamowite!

Jego wadą niestety jest jego prostota, bo przez to jest bardzo nieprzewidywalny.

 

3. Kopanie

Algorytm działający właśnie tak jak opisałeś.

1. Od pierwszego pokoju wybieramy kierunek i losujemy długość korytarza.
2. Stawiamy korytarz w wybranym przez nas kierunku i długości. Miejsce w którym zakończyliśmy będzie teraz miejscem nowego pokoju.
3. Stawiamy pokój i wykonujemy te 3 punkty jak długo potrzebujemy.

Tak napisany algorytm będzie działać od razu (i jest dość prosty) ale wymaga godzin customizacji. Być może chcesz aby korytarz nie tworzył się już w kierunku z którego przyszedłeś, ale dzięki temu będą powstawać ślepe zaułki. Może chcesz aby korytarze były dłuższe, a może krótsze? Może żeby się nie przecinały?

 

Algorytm z Nuclear Throne też jest dość fajny.

 

 

OK. To pora na jeszcze trochę lektury.

Jest jedna poważna wada każdego z tych sposobów. Wszystko poza wnętrzem pokoi jest obiektem ścianą. Wszędzie gdzie gracz nie może wejść jest masa nie potrzebnych obiektów. Trzeba bawić się w optymalizację tego, bo nie można tego tak zostawić.

Stawianie przeciwników odbywa się bardzo prosto. Losujesz pozycję startową tak długo aż nie będzie kolizji.

Automaty komórkowe! - Yep! Tym razem nie zapomniałem. W przypadku tych akurat algorytmów mogą się nie przydać ale warto o nich pamiętać. Wszystko polega na budowaniu zasad które wykonywane są po skończonym generowaniu. Np.: "jeżeli ściana jest jakimś cudem sierotą i nie ma żadnych sąsiadów to ją usuń", albo "usuń ścianę jeżeli w okręgu 4 jest mniej niż 60% ścian". No i jak na razie nie udało mi się znaleźć jakiegoś ultra szybkiego sposobu na zrobienie tego. :/ I ja porównuję zwyczajnie sąsiadujące komórki.

Zawsze zostawiaj przynajmniej po jednej zapełnionej komórce przy krawędziach mapy. Przez pomyłkę gracz może tak wyjść za mapę! Leniwy sposób to po skończonym generowaniu zarysowanie okręgu.

Przy używaniu ds_grid uważaj na różnice pomiędzy add a set. Czasami możesz mieć głupi błąd przez swoje nie dopatrzenie.

Funkcje do sprawdzania wartości wewnątrz prostokąta są bardzo przydatne. Możesz poznać najmniejszą, największą, sumę albo średnią z komórek. I tak, możesz tego użyć przy prostych automatach komórkowych o ile operujesz tylko na wartościach 0 i 1.

GML

if(ds_grid_get_sum(map,x-2,y-2,x+2,y+2)>13){jest ponad 50% ścian}

 

A ja ostatnio pisałem kumpeli program na studia i wyszedł tak wyrąbisty i prosty algorytm że będę się przy nim masturbował jeszcze przez kilka lat.

[Sutikku]

No więc. Napisałeś mi wszystko krok po kroku, dodając minusy i plusy danych sposobów, podałeś jakich funkcji użyć i najgorsze jest to, że chyba nie mogę zrobić więcej jak powiedzieć, a właściwie napisać dziękuje. Także, dziękuje.

[Threef]

Już się bałem że mi napiszesz "Ale mi potrzebne było tylko ds_grid_set_region()". :lol:

[gnysek]

A ja ostatnio pisałem kumpeli program na studia i wyszedł tak wyrąbisty i prosty algorytm że będę się przy nim masturbował jeszcze przez kilka lat.

 

Po screenie widzę, że robi dokładnie to, czego można by oczekiwać. Wart nie jednej masturbacji :lubieto:

[Sutikku]

To się dzieje na moich oczach. Mały krok dla Threefa, wielki dla mnie. Zrobiłem na razie grid 32x32 i użyłem drugiego sposobu na połączenia (jest prostszy i bardziej mi się podoba). Ale co zrobić by pokoje nie były tak wielkie? Bo im więcej pokoi tym szybciej robią się wielkie przestrzenie. W pewnym momencie zaczynać w innym miejscu ?

[Threef]

Ostatnia rzecz o jakiej napisałem przy ds_grid_get_sum(). ;)

Zrób warunek żeby nowy pokój stawiany był tylko gdy będzie częścią starego pokoju, ale nie zajmował zbyt wielu % starego pokoju. Próbuj. Zmieniaj wartości aż w końcu coś Ci się spodoba.