Archiwa kategorii: biblioteka

NoSQL w grach

Referat na temat baz NoSQL w grach, który wygłosiłem na konferencji Inżynierii Gier Komputerowych. Tutaj można zobaczyć prezentacje. Poniżej zamieszczam abstrakt artykułu. Całość można ściągnąć tutaj.

Abstrakt:

Artykuł dotyczy zastosowania baz danych noSQL, jako alternatywy wobec baz relacyjnych w grach online. Omówiono właściwości baz najczęściej używanych przez twórców gier. Na przykładzie Redis, MongoDB oraz CouchDB, przedstawiono ich wady i zalety, oraz podano rozwiązania stosowane w istniejących produkcjach. Ponadto przeprowadzono analizę wymagań gier komputerowych wobec oprogramowania, na tej podstawie przedstawiono powody, dla których warto stosować nowe technologie bazodanowe.

 

SQL vs noSQL

W ostatnim czasie zastanawiałem się nad zmianą bazy danych serwera Giazrmy. Obecnie stan gry przechowywany jest w bazie danych Mysql oraz pliku binarnym. Mógłbym jednak używać bazy tupu noSQL, ponieważ nie używam skomplikowanych zapytań łączących wiele tabel (nie korzystam z relacyjności bazy). Żeby sprawdzić, czy w ogóle mi się taka zmiana opłaca przeprowadziłem następujący test dla trzech typów źródeł danych: bazy Mysql, bazy MongoDB oraz pliku binarnego.

Test sprawdza szybkość odczytu / zapisu bloków danych (update i select).

  1. Tworzę testowy zbiór danych składający się z dużej liczby binarnych bloków danych o stałej długości

  2. Sekwencja testowa (powtarzana wielokrotnie):

    • Odczytaj wszystkie bloki danych

    • Zapisz wszystkie bloki danych

Parametry maszyny:

Intel Core 2 Duo 2.2GHz, 3GB ram

Parametry testów:

liczba powtórzeń odczytu / zapisu: 100
rozmiar bloku: 10000B
liczba bloków: 300

Implementacja:

kod testujący napisany został w PHP. Tutaj można pobrać kod źródłowy

Średni czas dla wykonania sekwencji testowej:

Mysql: 140ms
MongoDB: 80ms
Plik: 8ms

Oczywiście należy traktować te wyniki orientacyjnie, bo czasy zależą od chwilowego obciążenia systemu, sposobu instalacji serwerów baz (np. czy są na tej samej czy innej maszynie) i innych czynników.

Troll

kompresja bitmap

W tym artykule chciałem opisać sposób w jaki kompresuje grafikę (czyli głównie bitmapy) w moim projekcie. Pomysł polega na odpowiednim wykorzystaniu formatów png i jpg.

1. Stosowane Formaty:

  • JPG – stratna kompresja bez przeźroczystości.
  • PNG (RGBA) – format z kompresją bezstratną i kanałem alfa
  • PNG (z paletą kolorów)  – format z tablicą kolorów (do 256 kolorów w tym kolor przeźroczysty)

2. poprawa kompresji dla PNG (RGBA)

Najprostszym sposobem na poprawienie kompresji np. serii ikon jest wrzucenie ich do jednego obrazka w formacie PNG i zapamiętanie pozycji zajmowanych przez ikony. Ponieważ format PNG stosuje kompresje wierszową najlepiej rozkładać je horyzontalnie.

Przykładowo w Gizarmie są 22 ikonki zasobów. Każda ikona zapisana jest w PNG-24, posiada przezroczystość.

gizarma-024

Ikonki bez kompresji zajmują 34 556 bajtów, po zastosowaniu metody plik obrazu i plik z koordynatami zajmują 25 987 bajtów. Kompresja poprawiła się o około 25%.

3. Kompresja stratna z kanałem alfa

Czasami może się zdarzyć, że nie zależy nam na bezstratności kompresji obrazu, ale z drugiej strony potrzeba obsługi przeźroczystości. W tym wypadku dobrze sprawdza się zapisanie obrazu w JPG i dodatkowo maski przeźroczystości w oddzielnym obrazie PNG z paletą barw (zazwyczaj nie trzeba pamiętać 256 poziomów przeźroczystości, z moich doświadczeń wynika, że już 32 poziomy dają dobre rezultaty). Maskę zapisujemy w PNG ponieważ często ma ona gwałtowne przejścia od pełnej przeźroczystości do jej braku. Format JPG mógłby sprawić, że na takich ostrych granicach pojawiły by się artefakty.

gizarma-025
przykład artefaktów na krawędzi maski przy zastosowaniu formatu JPG

Ponieważ obraz początkowo z kanałem alfa jest zapisywany do JPG, trzeba pozbyć się przeźroczystości.

  • Dla każdego punktu gdzie alfa!=1 alfa=0, żeby nie mieszać koloru tła z naszym obrazem.
  • Po drugie dobrze jest rozmyć nasz obraz na jego zewnętrznych krawędziach. Należy to zrobić ponieważ JPG miesza kolory jeżeli zmieniają się one gwałtownie, nasz obraz mógłby być zanieczyszczony tłem na krawędziach.

Przykład na podstawie obrazu domku

Na przykładzie 34 grafik domków wstępnie skompresowanych metodą z punktu 2. pokaże efektywność metody. Obraz w PNG zajmuje 328 887 bajtów, po kompresji obraz i maska zajmują 101 258 bajtów. Poziom kompresji obrazu jpg wynosi 0.5, maska posiada 32 kolory. Objętość grafiki zmniejszyła się ponad 3 krotnie przy niewielkiej stracie jakości.

Troll

podział na regiony

Podczas tworzenia Gizarmy musiałem wymyślić metodę na znalezienie podziału mapy na regiony. Nie mogła to być regularna siatka, więc zadanie nie było trywialne. Udało mi się wymyślić algorytm który taki podział wyznacza i chciałem go tutaj opisać

Założenia:

  • Regiony powinny mieć nieregularny kształt.
  • Regiony powinny być podobnej wielkości
  • Rozkład regionów powinien uwzględniać lądy i morza, to znaczy nie może istnieć region wodno-lądowy.
  • Regiony nie mogą znajdować się poza dopuszczonym obszarem

Poniżej mapa określająca warunki dla regionów oraz efekt działania algorytmu

Moja metoda jest inspirowana bakteriami (jakimiś amebami). Ameby żyją na planszy i żywią się cukrem. Cukier ma pewien losowy rozkład na całej planszy. Ameby mogą zajmować nowe terytoria (rozrastać się) i zżerać się nawzajem.

Plansza symbolizuje ląd który dzielimy na obszary, a kiedy ameby zajmą cały obszar planszy, kształt ich ciał utożsamiamy z obszarami których szukamy.

Koniec bajeczki, algorytm:

Na początku zdefiniuje funkcje oceny opłacalności rozrostu ameby N na jakiś punkt k. Punkt k nie należy do N, ale sąsiaduje z N

ocena =
wsp1*[liczba punktów zajmowanych przez amebę N w okolicy punktu k] +
wsp2*[liczba punktów zajmowanych przez inne ameby w okolicy punktu k] +
wsp3*[odległość k od punktu początkowego ameby N] +
wsp4*[natężenie cukru w punkcie k] +

(jeżeli punk k jest pusty + BONUS_PUSTOSCI)

 

  1. Rozrzucam punkty początkowe ameb na całej planszy w sposób losowy, ale tak aby odległość dwóch dowolnych punktów <Rmin
  2. Wstawiam ameby które początkowo mają kształt okręgów o r<Rmin
  3. Znajduje i zapamiętuje wszystkie punkty sąsiadujące z amebą

while (true) {
    Dla wszystkich ameb {

  1. Spośród wszystkich punktów brzegowych ameby N znajduje ten o najwyższej ocenie (nazywam go k)
  2. Jeżeli k jest pusty zajmij, continue
  3. Jeżeli k zajęty przez amebe N\’ oblicz ocena(N\’,k)
  4. Jeżeli ocena(N\’,k)<ocena(N,k) * wsp_drapieżności odgryź amebie N\’ punkt k

}

co n kroków sprawdź czy ameby mają spójny kształt, jeżeli jakaś nie ma usuń części nie mające połączenia ze swoimi punktami początkowymi

}

W mojej symulacji do osiągnięcia zadowalającego efektu wystarczało 5000 – 10000 iteracji tego algorytmu.

Złomowisko

W tym dziale będę zamieszczał grafikę (ikony, sprajty, …), które miały być użyte w Gizarmie, ale z różnych powodów nie zostaną. Może komuś się przydadzą.

Grafiki z wersji 0.4

link: gizarma04.zip

Grafiki z wersji 0.4
Grafiki z wersji 0.4

4 pory roku

Grafiki które wykorzystałem przy pisaniu pewnej gry. Są to głównie sprajty drzew i krzewów w 4 odmianach (po jednej na pore roku). Część jest wyciągnięta z Heroes II.

Link: pory roku.zip

Grafiki z gry:

Troll