Autor Wątek: Generowanie zamkniętych przestrzeni do map  (Przeczytany 7274 razy)

Offline matheavyk

  • Użytkownik

# Marzec 12, 2015, 03:27:54
Chcę stworzyć generator map 2D, ale z zaznaczeniem, że nie mają to być mapy otwartych terenów (czyli nie mapy np. europy albo takie jak choćby w znanej na warsztacie grze Gizarma). Bliżej temu będzie do generowania podziemi, ale chciałbym zawrzeć w nim wszystkie takie ogólne, podstawowe podejścia do tematu. Chodzi mi o same idee algorytmów.

Chciałbym mieć zbiór algorytmów, który pokryłby wszystkie "typy" zamkniętych przestrzeni. Z moich poszukiwań wyłania się taki obraz:

1. labirynty

Tutaj opis zdaje się zbędny - chodzi o takie klasyczne labirynty.

Wygląd: http://upload.wikimedia.org/wikipedia/commons/9/9d/MAZE_40x20_DFS_no_deadends.png

Algorytmy: jest dużo różnych, np. modyfikacja Prime'a (odnośnik do wiki: http://en.wikipedia.org/wiki/Maze_generation_algorithm)

2. Wnętrza budynków

Coś co przypomina zbiór pokojów w budynku.

Wygląd: http://www.boymeetsdinosaur.com/wp-content/uploads/2014/10/struggle_screenshot_012.png

Algorytmy: Binary Space Partitioning

3. Jaskinie

Na takie jaskinie można patrzeć jak na rzut od góry, ale też, a może przede wszystkim, jako rzut z boku.

Wygląd: https://jeremykun.files.wordpress.com/2012/07/cave-generation-ex-with-resolution.png

Algorytmy: Szum perlina, automat komórkowy

4. Komnaty połączone korytarzami (można rozumieć jako wyspy połączone mostami)

Wygląd: http://www.pygame.org/shots/2007.png

Algorytmy: Nie wiem jaka jest jego nazwa, ale działa tak, że rozmieszcza prostokąty (lub inne figury) na płaszczyźnie, a później tworzy połączenia (korytarze).


Po co to wypisałem i czego od Was w ogóle chcę :P :
a) Czy znacie "typy" przestrzeni zamkniętych, których nie uwzględniłem?
b) Czy znacie inne algorytmy generujące coś na kształt przestrzeni, które już wymieniłem?
c) Czym mógłbym się zainteresować chcąc ulepszyć te podstawowe algorytmy? (Wiem, że na pewno przyda mi się jakieś dzielenie płaszczyzny np. Diagram Woronoja. Mógłbym też spróbować wykorzystać gramatyki grafów (graph rewriting), ale widziałem że chyba nie daje to jakichś efektów bardzo różniących się od kombinacji wypisanych przeze mnie metod.)
« Ostatnia zmiana: Marzec 12, 2015, 03:33:10 wysłana przez matheavyk »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline maro

  • Użytkownik

  • +2
# Marzec 12, 2015, 10:44:51
Może nie do końca związane z tematem, ale znasz to?
http://ondras.github.io/rot.js/hp/

m.in. http://ondras.github.io/rot.js/manual/#map/dungeon
« Ostatnia zmiana: Marzec 12, 2015, 10:49:07 wysłana przez maro »

Offline matheavyk

  • Użytkownik

# Marzec 12, 2015, 11:02:19
Dzięki. Drugi link można powiedzieć, że bardzo związany z tematem :). Wprawdzie te algorytmy już widziałem, ale oczywiście im więcej materiałów tym lepiej dla mnie.

Czekam na więcej :D
« Ostatnia zmiana: Marzec 13, 2015, 05:42:11 wysłana przez matheavyk »

Offline matheavyk

  • Użytkownik

# Marzec 28, 2015, 09:05:05
Zacząłem pisać mój generator i są pierwsze efekty - labirynty:
http://scratchgames.ja24.net/generatormap/
To co widać na screenach z tego linku to mapy wygenerowane metodą Drunkard's Walk z narzuconymi pewnymi regułami (może więc bardziej poprawnie będzie powiedzieć Random Walk + reguły). Każdy screen to render z Unitego, a obok mapa w formacie, w jakim ją przechowuję, czyli zera i jedynki w pliku tekstowym.

Pytania, które zadałem w pierwszym poście są dalej aktualne, więc możecie śmiało dalej odpowiadać :)

Offline głos

  • Użytkownik

# Marzec 28, 2015, 11:26:18
Zobacz portale np. tutaj http://kb.komires.net/article.php?id=21
Możesz użyć je do generacji zamkniętych przestrzeni lub do wspomagania algorytmu generującego korytarze (wejścia i wyjścia z komnat to portale)

Offline matheavyk

  • Użytkownik

# Kwiecień 09, 2015, 23:45:49
Do programu doszła druga metoda generowania - automat komórkowy. Przy odpowiednio ustalonych regułach automatu komórkowego tworzą się jaskinio-podobne mapy.
Zaktualizowałem stronę, więc jak ktoś chce zobaczyć efekty zapraszam tutaj:
http://scratchgames.ja24.net/generatormap/
(przepraszam za brzydki wygląd strony (i screenów?); mam nadzieję że treść załagodzi ból, który odczuje prawdopodobnie każdy, kto posiada zmysł estetyki ;p)

Moja implementacja powstała na podstawie tego opisu:
http://www.roguebasin.com/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels.

P.S. Mam nadzieję, że nie łamię regulaminu nie umieszczając tego tematu w dziale z rozpoczętymi projektami. Tutaj chyba też na razie pasuje, bo dalej liczę na pomysły dotyczące generowania map 2D.
« Ostatnia zmiana: Kwiecień 09, 2015, 23:48:52 wysłana przez matheavyk »

Offline Xender

  • Użytkownik

# Kwiecień 10, 2015, 11:18:33
Jaka treść?
Ja tam widzę parę screenów wygenerowanych map.

Gdzie źródła generatora?

Offline matheavyk

  • Użytkownik

# Kwiecień 11, 2015, 03:36:39
Źle się wyraziłem. Pisząc "treść" miałem na myśli właśnie te screeny.

Kodu generatora nie chcę na razie udostępniać z następujących powodów:
1. Nie jest piękny.
2. Nie jest odkrywczy.
3. Chyba byłoby to nawet nielegalne, bo zdaje się, że pisząc pracę na studia uczelnia ma pierwszeństwo w publikowaniu.

Co nie znaczy, że w przyszłości nie podzielę się program i kodem też, jeśli będą chętni. Ale jeszcze nie teraz :)

Offline Xender

  • Użytkownik

# Kwiecień 11, 2015, 12:14:53
@matheavyk - Co do uczelni - te generalnie zastrzegają sobie pierwszeństwo w publikowaniu pracy, natomiast nie wiem, czy nie można napisać pracy o programie Open Source, który akurat "przypadkiem" w tym samym czasie się pisało w swoim czasie wolnym. ;)

Drugą efektywną techniką, gdyby komuś z uczelni wpadło do głowy, żeby w regulaminie/kontrakcie zastrzec przeniesienie praw majątkowych (a nie tylko pierwszeństwo w publikacji), jest użycie fragmentu kodu na GPL (nie LGPL!), ot np. zalinkowanie GNU Readline.

Oczywiście ma to wadę - musisz używać Readline, które ma "piękny" interfejs w C.
Ale to już bardzo subiektywna kwestia gustu.


Kod może nie jest odkrywczy, ale gdyby udało Ci się go zrobić na czysto jako bibliotekę + standalone interfejs, mógłby być całkiem przydatny.


Zamień te 0 i 1 na jakieś wizualnie sensowniejsze symbole. Może ' ' albo '.' i 'X'?


Popracuj nad wyglądem strony, bo jeszcze ktoś pomyśli, że jesteś jakimś doktorem albo profesorem...
Oni przeważnie takie brzydkie strony mają.

Żeby zrobić jakąś sensownie wyglądającą stronę, wcale nie trzeba się narzeźbić w HTML i CSS.
Na Twoim miejscu raczej spróbowałbym jednego z dostępnych rendererów Markdown lub ReStructures Text do HTML, z gotowymi wymienialnymi stylami.
Jednym z nich jest Pelican, ale jest tego teraz cała masa.

//EDIT: typo.
« Ostatnia zmiana: Kwiecień 12, 2015, 15:14:02 wysłana przez Xender »

Offline matheavyk

  • Użytkownik

# Kwiecień 11, 2015, 19:32:56
Myślę dokładnie to samo co Ty, we wszystkich kwestiach, które poruszyłeś ;)

Cytuj
Kod może nie jest odkrywczy, ale gdyby udało Ci się go zrobić na czysto jako bibliotekę + standalone interfejs, mógłby być całkiem przydatny.
Postaram się tak zrobić. Przepraszam, że wrzucam na razie same wynikowe screeny programu, ale u mnie jest tak, że robię kilka projektów jednocześnie i po prostu każdy kawałek dodatkowej pracy to kawałek mniej w innymi miejscu. Dlatego rozwój programu jest bardzo powolny i jedyne, co mogę zagwarantować, to że do końca wakacji będzie kod udostępniony.

Cytuj
Zamień te 0 i 1 na jakieścwizualnie sensowniejsze symbole. Może ' ' albo '.' i 'X'?
Ok, popróbuję różnych znaczków.

Cytuj
Popracuj nad wyglądem strony, bo jeszcze ktoś pomyśli, że jesteś jakimś doktorem albo profesorem...
Oni przeważnie takie brzydkie strony mają.
Dokładnie to samo pomyślałem, kiedy zobaczyłem co mi tam wyszło :D. Tyle, że ja się trochę ucieszyłem, bo doktorsko-profesorska brzydota strony koresponduje z tym, że jest to uczelniany projekt ;p. Zrobiłem tak jak było najszybciej dla mnie - kilka linii w php, kilka w css i już. Zdaję sobie sprawę, że to trzeba zmienić, ale też na razie traktuję upublicznianie screenów jako zachętę do dalszej dyskusji, a nie prezentację programu.

Offline Xender

  • Użytkownik

# Kwiecień 12, 2015, 15:25:36
No dobra, to trzymam kciuki za program i za pracę.

Algorytmy są parametryzowane?
Bo jak ja się kiedyś bawiłem "marszem pijaka", to efekt końcowy przypominał bardziej jaskinię (coś jak Twój automat komórkowy, ale też nie do końca), niż labirynt.

Ogólnie też, wszędzie, gdzie jest losowość, można się bawić w jakieś modyfikowanie rozkładu.
Np. w "marszu pijaka" w różnym stopniu faworyzować różne kierunki (może relatywnie do kierunku poprzedniego ruchu, żeby nie łamać symetrii - to powinno dać dłuższe korytarze, a może właśnie absolutnie do układu współrzędnych mapy - to chyba zmieni głównie proporcje wygenerowanej mapy).

Offline matheavyk

  • Użytkownik

# Kwiecień 13, 2015, 05:01:23
Są parametryzowane.
Mój "marsz pijaka" ma parę warunków, które powodują utworzenie labiryntu:
- sprawdza przed każdym krokiem, czy zachowany zostanie odstęp jednego pola od innego korytarza,
- ma określoną pożądaną długość korytarza, czyli minimalną liczbę kroków jakie zrobi w jednym kierunku, zanim zmieni kierunek na inny,
- po wykonaniu kroku, nie mozemy miec po "skosie w kierunku chodzenia" żadnego pola innego korytarza,
- jeśli nowy korytarz ma mieć długość tylko jednego pola, to go w ogóle nie tworzymy.

Kod jest napisany na zasadzie strażników, których dowolną konfigurację podaję do metody sprawdzającej kolejne kroki:
        // kazdy straznik okresla regule jaka musi spelnic kazdy krok pijanego marszu
        public interface IStraznik
        {
            bool Testuj(int staryX, int staryY, int nowyX, int nowyY, int[][] mapa);
        }
       
        // przykladowy straznik bedzie wygladal tak:
        // (po wykonaniu kroku, nie chcemy miec po skosie w kierunku chodzenia ustawionych pol)
        private class StraznikPolaSkosPrzod : IStraznik
        {
            public bool Testuj(int staryX, int staryY, int nowyX, int nowyY, int[][] mapa)
            {
                if (...) return false;

                return true;
            }
        }


       // potem w funkcji generującej mam takie sprawdzenie przed kazdym krokiem:
       CzyMoznaPojsc(x, y, nowyX, nowyY, mapa,
                                                new StraznikMur(),
                                                new StraznikSasiadujacePola(),
                                                new StraznikPolaSkosPrzod()
                                                )

        // kazdy straznik musi zwrocic true, zeby funkcja CzyMoznaPojsc tez zwrocila true

Także łatwo rozszerzać o kolejne reguły dodając nowych strażników.

Przy generowaniu jaskiń też można się bawić, a ja mam parametry takie:
        public bool WymagajSpojnosci = true;                        // czyli, czy bedzie jedna "wyspa", czy wiecej
        public int ProcentPoczatkowegoWypelnieniaScianami = 37;     // czyli jaki jest stan wyjsciowy automatu komorkowego
        public float MinimalnePokrycieMapy = 0.4f;                  // minimalne dopuszczalne pokrycie polami, po których można chodzić (od 0.0 do 1.0)
        public float MaksymalnePokrycieMapy = 0.57f;                // analogicznie

A później można jeszcze manipulować liczbą kroków automatu komórkowego i znowu regułami-strażnikami. U mnie wygląda to mniej więcej tak:
mapa = WykonajKroki(4, mapa, stopPoKroku, new RegulaSasiedziPola(5), new RegulaSasiedziSciany(4), new RegulaWypelnijPustePrzestrzenie());
mapa = WykonajKroki(3, mapa, stopPoKroku, new RegulaSasiedziPola(5), new RegulaSasiedziSciany(4));
Co oznacza, że automat komórkowy wykona 4 kroki z jednym zestawem reguł, a potem wykona jeszcze 3 kroki z innym zestawem reguł. Tak jak przy strażnikach - łatwo rozszerzać o nowe reguły i bawić się w różne rzeczy :)
« Ostatnia zmiana: Kwiecień 13, 2015, 05:07:57 wysłana przez matheavyk »

Offline Xender

  • Użytkownik

  • +1
# Kwiecień 13, 2015, 11:04:18
Hmm, jakoś słowo "predykat" pasuje mi tu bardziej, niż "strażnik".
"Strażnik" kojarzy mi się raczej z tym: https://en.wikipedia.org/wiki/Sentinel_value

Architektura wydaje mi się sensowna.
Tylko oddaliłbym dobór predykatów aż do kodu klienckiego biblioteki, dając jakieś funkcje pomocnicze z sensownymi wartościami domyślnymi jako opcję dla leniwych.

Miałem już pisać, że zamiast interfejsów można by tu użyć zwykłego std::function, albo nawet lepiej, variadic template...
A potem dotarło do mnie, że to nie C++, tylko Java...
No to mocno ogranicza użyteczność tego jako biblioteki do gry. Welp.

A co do samych predykatów, to ja bym chyba połączył RegulaSasiedziPola i RegulaSasiedziSciany w jedno.

Dlaczego piszesz kod po polsku? (To jest poważny zarzut! :P)
« Ostatnia zmiana: Kwiecień 13, 2015, 11:06:48 wysłana przez Xender »

Online koirat

  • Użytkownik

# Kwiecień 13, 2015, 11:08:15
Dlaczego piszesz kod po polsku? (To jest poważny zarzut! :P)
+

Offline matheavyk

  • Użytkownik

# Kwiecień 13, 2015, 21:16:46
Ja słowo strażnik wyniosłem z tego http://en.wikipedia.org/wiki/Guard_%28computer_science%29. Ale chyba faktycznie predykat bardziej pasuje.

oddaliłbym dobór predykatów aż do kodu klienckiego bibliotekiTeż bym tak zrobił. Aż dopadło mnie uczucie, że więcej czasu spędzam na forum niż pisząc kod ^^.

To akurat nie jest Java, ale C#. Jeśli ktoś używa np. Unity (to jest coraz większa grupa), to będzie mógł użyć jako biblioteki. Poza tym zostaje jeszcze możliwość odpalania .exe z argumentami i przechwytywania wyniku - teraz tak tego używam w grze do testów. A tak w ogóle to kod jest prosty, więc może na koniec pomyślę o przepisaniu do C++ (chociaż jakość tego będzie raczej mizerna, bo na co dzień nie piszę w C++). Będzie okazja do przetestowania np. https://cscpp.codeplex.com/ :D


Na koniec odniosę się do najpoważniejszego zarzutu, czyli pisania po polsku. Wiem, że każdy szanujący się programista pisze po angielsku :P. Ja czasami też, na przykład programiki na zajęcia z list zadań. Ale dwie rzeczy ciągle trzymają mnie przy języku polskim w moich domowych projektach:
1. Lubię to, że od razu widzę, które funkcje/klasy/itd. są moje, a które nie.
2. Lekka nutka patriotyzmu... mój program i tak nie będzie na tyle przydatny, żeby używał go cały świat, więc niech Polacy czują, że mają coś "od swojego". Chociaż z drugiej strony może sam dołki kopię pod swoimi skoro, jak widać, wolicie angielskie nazwy ;)