Autor Wątek: Generowanie odtwartych przestrzeni 2D  (Przeczytany 1835 razy)

Offline Adam B

  • Użytkownik

# Kwiecień 19, 2009, 20:15:51
Witam.

Ostatnio miałem problem z generowaniem podziemi - wydaje mi się, że z tym się już uporałem, chociaż algorytm nie jest jeszcze gotowy w 100%, ale ze względu na lekką zmianę fabuły mojego projektu - duża część gry ma też się odbywać na lądzie (tak ustaliłem z kolegą, który jest mhh.. jak by to nazwać... "SCENARZYST¡"). Przygotowałem częściowy projekt generowania świata.

Założenia, które ma spełniać:
 1. Mały plik z zawartością mapy,
 2. Mała zajętość mapy w pamięci,
 3. świat ma być możliwie duży

Pierwsze dwa podpunkty determinują , że mapa musi być maksymalnie prosta i w sensownym formacie oraz musi być dogrywana w czasie rzeczywistym, z tego wynika też możliwość uzyskania tego co jest w podpunkcie 3 :)

ad. 1 i 2
Wymyśliłem, że mapa będzie składać się z kafli 1600px na 1600px. na których będą zapamiętywane informacje o ich type:



1, 2, 3, 4, 5, 6, 7, 8 - to punkty od których może zaczynać i na których może się kończyć droga oraz rzeka.  (do zakodowanie tego potrzebuje 12bitów (początek i koniec drogi, początek i koniec rzeki)).
Z racji tego, że duża część świata to mogą być pola, morza, lasy, pustynie - to zostawiam 2bity na zakodowanie tej informacji (daje to 4 możliwości, jak na jakimś polu znajduje się tylko morze lub pole to nie trzeba już mieć na nim informacji o np. drodze - oszczędność całkiem spora). Dodatkowo 1bit na flagę o nazwie inne, która determinuje czy na danym polu jest droga, rzeka itp. I 1bit na flagę specjalne - dla miejsc specjalnych zaprojektowanych dokładnie przez człowieka:)

No to mam na razie 2bity na podłoże, 1bit informacja czy na kaflu znajdują się inne rzeczy oraz  12bitów na informacje o początku i końcu drogi i rzeki + 1 bit na specjalne = 16bitów = 2Bajty - na informacje o kaflu wielkości 1600px na 1600px

PYTANIE NR 1:
Szukam pomysłu jak w optymalny sposób zapisać  informacje o drzewach, kamieniach itp znajdujących się na mapie - maszerowanie przez pustkowia polną drogą jest raczej nudnawe ;)  mogę tu oddać całe 2 bajty ;) ee co ja mówię nawet 4B!! :)
Więc najbardziej wypasiony Kafel zajmie 6B!

Jeżeli chodzi o małą zajętość pamięci to mapa będzie dogrywana w sposób następujący:


Kiedy zawodnik będzie na kaflu to wczytują się do pamięci kafle sąsiadujące z "kaflem aktywnym" (czyli tym na którym jest player). Kiedy player przejdzie na inny kafel to ponownie są dogrywane potrzebne kafle, a te które już nie są potrzebne usuwane są w zapomnienie. Czyli potrzebuje tablice 9 (odkodowanych) elementów z obiektem KAFEL.

PYTANIE NR 2:
Zastanawiam się jak zachować orientację między kaflami - w sensie, żeby dobrze się dogrywały itp.

Wymyśliłem, że kafle dostana atrybut (typ enum) góra, dół, lewo, prawo oraz góra_lewo itp. Kiedy wejdziemy np. na KAFEL z atrybutem LEWY dostaje on atrybut AKTYWNY gorny_lewy jest teraz góra itd. natomiast kafel który wcześniej był prawy nie jest usuwany ale podmienia mu się atrybut na prawy i zaczyna być generowany na podstawie informacji zawartych w pliku z mapą.  Jednak nie jestem jakoś do końca pewien swojego rozwiązania.


Podliczając polowa świata to woda więc 50% kafli zajmie tylko 2bity("Z racji tego, że duża część świata to mogą być pola, morza, lasy, pustynie - to zostawiam 2bity na zakodowanie tej informacji.")
Na lądzie myślę, że pustynie, pola i lasy zajmują znakomitą większość czyli mhh.. 80% no ale zakładam, że na potrzeby gry wolnego terenu (las, pole, pustynia) będzie około 60%. Czyli z tego wynika, że tylko 20% świata będzie składać się z Kafli po 6Bajtów. (zakładam, że na 4 Bajtach uda mi się zakodować informacje o drzewkach i kamyczkach). Średni rozmiar kafla będzie wynosił około 12bitów. Na 2Bajtach (troszkę zawyżona średnia) średnio zapisywany jest teren o wielkości 1600px na 1600px. Wiec na 20KB powinno się dać zapisać mapę o rozmiarach 160 000px na 160 000px. Player będzie miał rozmiar 20px czyli można założyć, że 1metr to 10px i mapa będzie miała 16KM na 16KM - Bardzo bym chciał zmierzać do takiego wyniku !!!! :)

Pozdrawiam i dziękuje tym, którzy przeczytali, a jeszcze bardziej tym, którzy podpowiedzą jakieś rozwiązanie - sorry, za przynudzanie ;0

Offline Mr. Spam

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

Offline sobol

  • Użytkownik

# Kwiecień 19, 2009, 20:33:48
Co do pytania 1 - jak tak strasznie chcesz iść w oszczędności to przechowuj w tych 4 bajtach seed dla randa i skorzystaj z tego, że dla danego seeda rand zwróci tą samą sekwencję. Polecam rozdział 2.0 z pierwszych perełek. Jednym słowem - po prostu rozlosuj drzewa / kamienie po mapie, zawsze tak samo  dla danego kafla. Zamiast randa na pałę możesz zrobić sobie jakąś metodę do losowania tych danych na podstawie jakiś parametrów.

Cytuj
Wymyśliłem, że kafle dostana atrybut (typ enum) góra, dół, lewo, prawo oraz góra_lewo itp. Kiedy wejdziemy np. na KAFEL z atrybutem LEWY dostaje on atrybut AKTYWNY gorny_lewy jest teraz góra itd. natomiast kafel który wcześniej był prawy nie jest usuwany ale podmienia mu się atrybut na prawy i zaczyna być generowany na podstawie informacji zawartych w pliku z mapą.  Jednak nie jestem jakoś do końca pewien swojego rozwiązania.
Troszkę się zamotałeś w tym opisie, ale z grubsza o to właśnie chodzi. Musisz dążyć do tego, żeby przy zmianie aktywnego kafla było jak najmniej przeładowań. Czyli dla kafli sąsiadujących zmieniasz tylko flagi, w najgorszym przypadku, gdy przechodzisz idealnie po skosie, np. na kafel góra-prawo musisz załadować aż 5 nowych kafli, ale to przypadek mega pesymistyczny. Pamiętaj, żeby nie zrobić przeładowania za każdym razem, gdy tylko przejdziesz przez granicę kafli. Bo jak gracz będzie szedł równo po granicy to będziesz miał ładny spadek na FPSie :) Dlatego powinieneś zrobić coś w deseń histerezy jak w LODach się robi - unikasz przeskoków. Nowe dane dla kafla załadowujesz jak na niego wchodzisz, ale stare niepotrzebne dane wyładowujesz dopiero jak odejdziesz na pewną odległość od starego kafla. Czyli w pamięci nie przechowujesz zawsze 9 kafli, tylko minimum 9. Dodatkowo możesz łatwo sprawdzać które dane trzeba wczytać wcześniej, bo potencjalnie do pewnych kafli gracz może dojść wcześniej, a chcesz unikać loadscreenów.



Offline maciek_slon

  • Użytkownik

# Kwiecień 19, 2009, 21:13:32
To ja jeszcze co do tej losowości coś dodam - http://libnoise.sourceforge.net/ - biblioteka z kilkoma fajnymi randami :P I ogólnie całkiem przydatna podczas generowania terenu.

Offline Adam B

  • Użytkownik

# Kwiecień 19, 2009, 21:30:19
ad1.

Będę musiał popróbować z randem tylko jest z trochę problemów:
 1. Pisze to na komórki - dlatego tak ważna jest dla mnie zajętość pamięci i rozmiar. Na różnych telefonach - mają przecież różne procesory nie wiem czy to będzie działać tak samo. Trzeba będzie zakodzić odpalić na kilku komórach i zobaczyć - innej motody nie ma :) Zawsze mogę sam napisać funkcję jak podpowiadałeś
 2. O ile obliczenie ścieżki od jednego punktu do drugiego lub obliczenie na podobnej zasadzie przepływu wody da się wyliczyć błyskawicznie, to wyliczenie kilkuset parametrów dla drzewek, kamieni itp już troszkę zajmie (spadek FPS) ale i tak generowanie KAFLI chciałem rozbijać na kilka etapów.

ad2.

Nie będzie problemów z FPS na pewno - bo już wcześniej zakładałem, że w każdym obrocie pętli będą obliczane pojedyncze informacje dla poszczególnych KAFLI. Obawiam się tylko, że może zajść sytuacja gdy player zobaczy jeszcze nie do końca załadowaną mapę - ale to już bardziej kwestia dopasowania maksymalnej prędkości - żeby za szybko nie doszedł na pole, które się właśnie ładuje :)

// EDIT: rzeczywiście się zakręciłem przy tym nadawaniu nowych parametrów dla pól ;) Gdy przechodzimy na lewy kafel to środkowy staje się prawym, a prawy zmieniamy na lewy i generujemy od początku :)
« Ostatnia zmiana: Kwiecień 19, 2009, 21:33:21 wysłana przez Adam B »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Kwiecień 19, 2009, 21:52:45
Cytuj
Wiec na 20KB powinno się dać zapisać mapę o rozmiarach 160 000px na 160 000px.
Po co aż takie kombinacje? :)

Offline Adam B

  • Użytkownik

# Kwiecień 19, 2009, 22:01:29
Cytuj
Wiec na 20KB powinno się dać zapisać mapę o rozmiarach 160 000px na 160 000px.
Po co aż takie kombinacje? :)

Jak chce się zrobić jakiegoś RPG albo "Przygodówkę" to to mapa powinna dawać możliwość, że się idzie kilka min w jedna stronę i w drugą ;) A co proponujesz ?

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Kwiecień 19, 2009, 23:38:55
Cytuj
Jak chce się zrobić jakiegoś RPG albo "Przygodówkę" to to mapa powinna dawać możliwość, że się idzie kilka min w jedna stronę i w drugą ;) A co proponujesz ?
Proponuję zmienić jednostkę przy tej dwudziestce. 20MB na tak dużą mapę jest rozmiarem jak najbardziej akceptowalnym, a masz 1000x więcej możliwości zrobienia tego porządnie. :)

Offline Adam B

  • Użytkownik

# Kwiecień 19, 2009, 23:58:02
Cytuj
Jak chce się zrobić jakiegoś RPG albo "Przygodówkę" to to mapa powinna dawać możliwość, że się idzie kilka min w jedna stronę i w drugą ;) A co proponujesz ?
Proponuję zmienić jednostkę przy tej dwudziestce. 20MB na tak dużą mapę jest rozmiarem jak najbardziej akceptowalnym, a masz 1000x więcej możliwości zrobienia tego porządnie. :)

Cytuj
Pisze to na komórki - dlatego tak ważna jest dla mnie zajętość pamięci i rozmiar

Jak bym to na PC robił to bym się nie przejmował takimi pierdołami - najprawdopodobniej bym nie robił żadnej kompresji tylko mapa by była ładowana do pamięci w formacie gotowym do odczytu ;)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Kwiecień 20, 2009, 00:03:10
Cytuj
Pisze to na komórki - dlatego tak ważna jest dla mnie zajętość pamięci i rozmiar
OK, nie doczytałem się. :) W takim razie polecam generowanie proceduralne. :)

Offline Adam B

  • Użytkownik

# Kwiecień 20, 2009, 20:30:05
Zaznajomiłem się z drugim rozdziałem w 1 tomie perełek - całkiem fajnie tam to jest wyjaśnione ;)..

Dziękuję za pomoc i pozdrawiam...