sobota, 25 kwietnia 2009

Wielki Mistrz – Brengir demo

screen1sdr Mimo natłoku zajęć, rozmaitych obowiązków oraz przeróżnych zadań, udało się ukończyć aplikację, którą można spokojnie przedstawić jako trzecie demo gry Wielki Mistrz, a zostało ono opatrzone nazwą kodową Brengir. Dlaczego właśnie tak, a nie inaczej – można się domyślać. Pierwszy test nosił nazwę Gargulec, bo motywem przewodnim było uwolnienie Gargulca. Drugi – Tofik, gdyż była to najbardziej charakterystyczna postać z tej wersji. A Brengir… Ale tego sami się już dowiecie. Na początek tradycyjnie linki (tam-taratam-tam-tam):

Cóż, jest to już większe demo niż dwa poprzednie. Dużo większe. screen2sdr No dobrze, może średnio-dużo większe. Tak czy inaczej, nie ma już tutaj czterech NPC-ów. Nie, dwóch też nie… Jest ich przynajmniej piętnastu i chociaż modele są praktycznie te same (to naprawdę ogromna robota z ludzkimi modelami, przynajmniej przy amatorskim projekcie robionym w czasie wolnym), to mam nadzieję, że dialogi oraz zadania to Wam wynagrodzą. W ogóle – stały punkt programu, czyli “co nowego”:

  • Zupełnie nowa oś fabularna i postacie NPC
  • Znacznie większy teren gry, struktura podziemnego miasta
  • Całość jest dużo bliższa cRPG-owi
  • Duuuuuuuużo NPC-ów (jak na taką grę – Baldur to jeszcze nie jest) i ich avatary
  • Dodane efekty cząsteczkowe
  • Możliwość zapisu i odczytu gry
  • Dodane nowe tekstury
  • Odświeżona skórka dialogów oraz kompas
  • Możliwość wyboru cechy specjalnej oraz wpisania swojego imienia
  • W końcu dowiadujemy się, po co nas zesłano do ciemnych i śmierdzących lochów
  • I dlaczego przy okazji nie dano antyperspirantu
  • To by tłumaczyło, dlaczego w lochach śmierdzi
  • Zwiększona interakcja między postaciami
  • Poprawione niektóre drobne elementy

To chyba te najważniejsze “ficzerki” nowego wydania. Pomijając antyperspirant.

screenshot_04252009_204540335 Ogólnie rzecz biorąc, w Brengir demie mamy do czynienia z nową fabułą i to rzeczywiście z fabułą – postać trafia do miasta Myrvandel z wyraźnie określonym pierwszym celem i ma do wykonania Pewne Ważne Zadanie, Które Tym Razem Nie Polega Na Ratowaniu Świata, Czyli Nie Jesteśmy Sztampowi. Czuć ten klimat. Zresztą samemu się można o tym przekonać, ściągając demo oraz w nie grając (tak mi się przynajmniej wydaje). Jeśli chce się porządnie zaznajomić z produkcją, nie da się tego zrobić tak szybko jak w poprzednich wersjach – w tym celu też błogosławieństwem okazuje się możliwość “sejwowania” i “lołdowania” stanu gry. Pomocny okaże się także kompas oraz pewien przedmiot, który możemy dostać już na samym początku – z racji skomplikowania terenu rozgrywki, postanowiliśmy nieco ułatwić życie graczom, a także mnie samemu, bo nie dość, że mam kiepską orientację w terenie w rzeczywistości, to jeszcze gubiłem się do pewnego momentu w lochach Myrvandel – tak to jest, jak się pracuje “z doskoku”.

Właśnie sobie uświadomiłem, że buduję bardzo długie zdania. Ale to jest takie fajne – zupełnie jak 10000-linijkowy program w jednym pliku.

Również przy wstępie do rozgrywki, mamy możliwość wybrania tzw. cechy, która determinuje możliwość pewnych zachowań naszej postaci przy dialogach lub podczas samej eksploracji lochów. Wiąże się z tym też możliwość wybrania imienia dla naszej postaci – taki miły dodatek.

Poprawie uległa także część określana głównie jako “oprawa graficzna”, “żuchwa w dół” czy też “dlaczego to nie jest takie jak w screenshot_04252009_204815127 Crisisie?”. Przede wszystkim, pojawiły się efekty cząsteczkowe, który budują klimat lochów, gdzie przecież standardowo powinny się palić pochodnie, a ludzie gonią potwory z widłami. I pochodniami. Pojawiło się też parę nowych tekstur, ale rzeczywiście, tutaj odbyło się bez szaleństw. Powstał też nowy, całkiem przyjemny model, którego dwie kopie widać w grze jak w brzydkie-określenie-na-twarz strzelił. Powstał także inny model, ale jest ciekawie ukryty. Uklimatyczniono również tło przy przeprowadzaniu dialogów oraz zapewniono solidne wsparcie dla avatarów, którymi obdarzeni są bohaterowie niezależni.

Dla twórców nowe demo to również pole doświadczalne dla nowych narzędzi – wspominałem o programie UMLet, który jest wykorzystywany do tworzenia dialogów (których mechanika także uległa ogromnym przeobrażeniom, dzięki czemu rozmowy być one jeszcze bardziej zawiłe). Na repozytorium rozwiązała się sprawa ze stosowanymi przez zespół IDE – niektórzy używają Visual Studio 2005, inni 2008, a jeszcze inni Eclipse. Poprzednio był mały problem jeśli chodzi o konwersje pomiędzy plikami projektu, ale obecnie chodzi to bardzo ładnie, szybko, efektywnie i nie wiem jeszcze jak.

Pozostała jeszcze jedna informacja do przekazania – wszystkie kotki ćwierkają (a przynajmniej te, których nie udało mi się zestrzelić), iż prawdopodobnie za kilkanaście dni wyjdzie aktualizacja do Brengir dema. Nie jest to jeszcze jednak sprawa przesądzona, zatem powstrzymam się od dalszego komentarza, zanim chlapnę językiem o kapkę za dużo.

A cóż innego mogę zrobić – zachęcam wszystkich do ściągnięcia dema, potestowania, pogrania, pobawienia się i wypisania swoich uwag w komentarzach pod tą notką. Każda uwaga jest cenna i chociaż nie wszystkie są poprawiane od razu, jest to dla nas informacja, że podoba się to, co robimy i że mamy to robić dalej. No i lista na Bugzilli jest dłuższa.

Cóż, czy mi się wydaje, czy to znowu jest notka po długiej nieobecności? Cóż, nie wydaje mi się. Jednakże, z tego co wnioskuję, tak już pozostanie do końca semestru – dopiero wtedy będę miał prawdopodobnie czas na regularne pisanie na blogu i oczekiwany powrót do tworzenia Yesty (tak, nie zapomniałem o niej). Do tego czasu, wpisy będą pojawiały się sporadycznie (innymi słowy – tak, jak dzieje się to teraz). Prze-pra-szam…

…i pozdrawiam, a także dziękuję i jeszcze raz gorąco zachęcam do zapoznania się z demem – SceNtriC.

poniedziałek, 13 kwietnia 2009

Cięcia czerwonego kabelka ciąg dalszy

scr001 Niestety. Prawdę mówiąc, zbyt ufnie i optymistycznie (tak, zdarza mi się) podszedłem do zadania napisania programu na zaliczenie z języka C i wybrania sapera jako ten cudotwórczy program. Myślałem, że to po paru dniach, gra będzie skończona, inne projekty i sprawozdania skończę wcześniej i będę mógł się w końcu zabrać za to, co lubię najbardziej – lenistwo i narzekanie, że nic mi się nie chce. Niestety, rzeczywistość bywa okrutna – szczególnie, jak projekt nie jest robiony hobbystycznie, tylko ktoś nade mną stoi i mówi, kiedy mija tzw. “deadline”.

Od ostatniego czasu pojawiło się jednak sporo nowości. Wśród nowinek mam na myśli również nowe błędy. Skoro można korzystać z bibliotek napisanych w języku C, doszło do zaprzęgnięcia OpenGL i GLUT. Trzeba przyznać, że wersja graficzna wygląda dużo lepiej niż konsolowa. Co za tym idzie, można dodać obsługę myszki i klawiatury, co generuje nowe nieprzewidziane własności programu – niepodświetlanie tych pól, co trzeba, złe liczenie współrzędnych, wysypywanie się aplikacji. W końcu jednak udało mi się to doprowadzić do minimalnego porządku i zająć się innym rzeczami.

Warto również zaznaczyć jedną rzecz – program co prawda umożliwia wybranie planszy, w której wysokość i szerokość nie są sobie równe, ale nijak się ma to do poprawności działania. Algorytm generowania planszy działa prawidłowo wyłącznie (acz nie zawsze – trzeba będzie chyba postawić “zasłony” przy generacji) dla macierzy kwadratowych. Z tego też względu rozważam dopuszczenie jedynie takich plansz do egzystencji, ponieważ – prawdę mówiąc – nie mam już zielonego pojęcia, gdzie tkwi błąd.

Kod zaczyna przypominać spaghetti – pociągniesz za jeden koniec, to okaże się, że drugi przechodzi przez procesy wybitnie destrukcyjne. Próbowałem w ten sposób dodać system cząsteczkowy, który generowałby ładne świecidełka przy klikaniu na pole. Niestety, to jest C i kompilator MinGW dla ustawień niskopoziomowych, zatem pewne kruczki tu nie przejdą, a co dopiero skopiowanie gotowego kodu z frameworka. A z racji dosyć “interesujących” założeń wyświetlania w projekcie, wszystko zaczęło się sypać – jakby te ładne świecidełka wypaliły kratki na planszy, a monitor zasłonił twarz rękoma. Zatem zrezygnowałem z tego pomysłu chwilowo. Musiałem to też uczynić z shaderami (w końcu Cg jest napisany w C), gdyż ustawienia kompilatora nie umiał wprawdzie dokładnie wytłumaczyć o co mu chodzi, ale wiedział za to, że to się nie kwalifikuje do stworzenia pliku wykonywalnego. Pewnie do tych rzeczy wrócę, jak będę miał już sapera napisanego na tyle, że wszystko będzie ładnie działało, a do zaliczenia zostanie troszkę czasu.

To oczywiście nie oznacza, że zamierzam odpuścić sobie ujawnienie sapera szerszemu gronu. Wręcz przeciwnie – zawsze lubiłem pokazywać coś, co napisałem, gdyż być może ktoś na tym skorzysta (inna motywacja to “a może ktoś się zachwyci”, ale tutaj raczej ona odpada). Problem w tym, że jeśli początkujący zobaczy kod, to będzie się zastanawiał, dlaczego Microsoft nie jest potentatem na rynku rozrywki komputerowej, skoro dla każdego Windowsa pisze takie trudne gry. A tak naprawdę, idea “majnsłipera” jest dosyć prosta – należy jednak nie zniechęcać się niepowodzeniami, a nie zostawiać kod i ruszać na bloga wyżalać się Bogu ducha winnym ludziom.

Z innych ciekawych rzeczy – postanowiłem zaprzyjaźnić się z LaTeXem, a konkretnie z Beamerem służacym do tworzenia prezentacji. Inspiracją była smutna konieczność przygotowania materiałów na zajęcia z angielskiego o wybranym przez siebie temacie (ale nie do końca dowolnym). Mnie jakoś przypadła inżynieria oprogramowania, co zmusiło mnie do zasięgnięcia porady angielskiej Wikipedii i skopiowania paru(dziesięciu) mądrze brzmiących definicji, w których następnie muszę zrozumieć o co tak właściwie chodzi. Zostawiając warstwę merytoryczną na boku, muszę przyznać, że język ten nie jest jednak tak kosmiczny jakby się wydawało. Oczywiście, pewne rzeczy są z początku mało intuicyjne, ale można sobie z tym dać radę i tworzyć naprawdę profesjonalne dokumenty.

Cóż, popisałem, ponarzekałem – ale tego czasami też trzeba. Miejmy nadzieję, że następne notki przyniosą same dobre wieści.

Pozdrawiam i dziękuję – SceNtriC.

piątek, 10 kwietnia 2009

Grafy, a raczej próby wykazania się w czymś, w czym nie warto się wykazywać

Bez tytułu Znowu notka po dwóch tygodniach i dodatkowo spowodowana tymi samymi czynnikami. Dzisiaj jednak będzie bez przepraszających wstępnych, gdyż prawdopodobnie po pierwsze są już one nudne dla Was, a po drugie – patrz punkt piewszy (nie, to nie pętla).

Chciałem jednak nieco rozpisać się o strukturach, które musieliśmy przebadać na przedmiot Algorytmy i Struktury Danych, a mianowicie o grafach. W tym miejscu chciałem zadeklarować, iż nie chcę umieszczać tutaj wszystkich definicji i tym podobnych rzeczy – na to przyjdzie czas, jak zdecyduję się na ukazanie ocenionych już wtedy (mam nadzieję) raportów algorytmicznych, które będzie można spacyfikować i krytykować. Wypada jednak jakąś cząstkę teorii zawrzeć ku temu, o czym chcę napisać. Polecam zatem ten oto link, w którym dobrze są rozpisane reprezentacje grafu w komputerze i podstawowe informacje. Jedynymi zmianami oznaczeń jakiej dokonałem w swoich rozważaniach są:

  • Ilość wierzchołków to nie V tylko n
  • Ilość krawędzi to nie E tylko m
  • Lista sąsiedztwa nazywa się listą incydencji
  • Będą używane następujące skróty – macierz sąsiedztwa to MS, lista krawędzi to LK, macierz incydencji to MI, a lista incydencji to LI. Ułatwi to późniejszą prezentację wyników

Zagadnienie, na którym chciałbym się skupić, można by było zacząć od zdania, które napisał NOWIESZ (pozdrawiam i przepraszam jeśli naruszyłem jakiekolwiek prawa autorskie):

Liczbę wierzchołków będę oznaczać przez V (i numerować 1..V), a liczbę krawędzi przez E. Oczywiście V2>=E. Grafy, w których E=V2 nazywamy pełnymi, E jest trochę mniejsze od V2 - gęstymi, a dużo mniejsze - rzadkimi.

Można jednak wprowadzić dodatkową wielkość, a mianowicie współczynnik nasycenia. Jest to wartość z przedziału [0, 1], która określa jaki procent wszystkich możliwych krawędzi znajduje się w grafie o n wierzchołkach. Im graf bardziej gęsty, tym współczynnik ten jest większy, a zatem istnieje więcej połączeń pomiędzy wierzchołkami. Można zatem ten podział wykazać tak:

  • Grafy pełne – współczynnik nasycenia jest równy 1.
  • Grafy gęste – współczynnik nasycenia mieści się w przedziale [0,5; 1).
  • Grafy rzadkie – współczynnik nasycenia jest mniejszy niż 0,5.

Generalnie, interesuje nas złożoność pamięciowa (w skrócie ZP) oraz dwa rodzaje operacji – sprawdzenie, czy pomiędzy danymi dwoma wierzchołkami istnieje krawędź (innymi słowy, czy są one do siebie incydentne) (w skrócie S,CPDDWIK(IS,CSODSI)) oraz wyszukanie wszystkich incydentnych wierzchołków do danego (w skrócie WWIWDD). Te trzy zagadnienia oraz ich teoretyczną, asymptotyczną szybkość działania dla poszczególnych reprezentacji można przedstawić następująco:


ZP

S,CPDDWIK(IS,CSODSI)

WWIWDD

MS O(n2) O(1) O(n)
LK O(m) O(m) O(m)
MI O(nm) O(m) O(m)
LI O(n+m) O(n) O(1)


Warto by było jednak w jakiś sposób porównać te wartości. Dlatego, dla przedstawionych wcześniej rodzajów grafów (pełny, gęsty i rzadki), po uwzględnieniu faktu, iż maksymalnie m może wynosić n2, a współczynnik nasycenia od 0 do 1, można zastosować następujące przeliczniki:

Rodzaj grafu Minimalna wartość m Maksymalna wartość m
Pełny n2 n2
Gęsty 0,5n2 0,(9)n2
Rzadki 0 0,(5)n2


Zatem, dla poszczególnych typów grafów i reprezentacji, można wysnuć następujące wnioski co do złożoności obliczeniowej.

Graf pełny

Złożoność pamięciowa

Sprawdzenie, czy dwa wierzchołki są incydentne

Wyszukanie wszystkich wierzchołków incydentnych do danego

Macierz sąsiedztwa

O(n2)

O(1)

O(n)

Lista krawędzi

O(n2)

O(n2)

O(n2)

Macierz incydencji

O(n3)

O(n2)

O(n2)

Lista incydencji

O(n2+n)

O(n)

O(1)


Graf gęsty

Złożoność pamięciowa

Sprawdzenie, czy dwa wierzchołki są incydentne

Wyszukanie wszystkich wierzchołków incydentnych do danego

Macierz sąsiedztwa

O(n2)

O(1)

O(n)

Lista krawędzi

[O(0,5n2), O(n2))

[O(0,5n2), O(n2))

[O(0,5n2), O(n2))

Macierz incydencji

[O(0,5n3), O(n3))

[O(0,5n2), O(n2))

[O(0,5n2), O(n2))

Lista incydencji

[O(0,5n2+n), O(n2+n))

O(n)

O(1)


Graf rzadki

Złożoność pamięciowa

Sprawdzenie, czy dwa wierzchołki są incydentne

Wyszukanie wszystkich wierzchołków incydentnych do danego

Macierz sąsiedztwa

O(n2)

O(1)

O(n)

Lista krawędzi

[O(1), O(0,5n2))

[O(1), O(0,5n2))

[O(1), O(0,5n2))

Macierz incydencji

[O(n), O(0,5n3))

[O(1), O(0,5n2))

[O(1), O(0,5n2))

Lista incydencji

[O(n), O(0,5n2+n))

O(n)

O(1)

Cóż, nie wygląda to zbyt interesująco – zwłaszcza dla tych, którzy jeszcze nie muszą (lub już nie muszą) się tym zajmować. Można jednak wysnuć z tych tabelek parę wniosków, które mogą się przydać w przyszłości:

  • Dla grafów gęstych i pełnych świetnym wyborem jest macierz sąsiedztwa.
  • Im mniej krawędzi ma graf (lub jeśli chcemy posortować go topologicznie), tym lepszą reprezentacją będzie lista incydencji.
  • Jedynymi zaletą listy krawędzi okazuje się miejscami mała zajętość pamięci oraz dosyć prosta budowa. Jest jednak zbyt wolna w porównaniu do dwóch powyższych struktur.
  • Macierz incydencji jest wolna, zajmuje dużo pamięci i generalnie nie jest to produkt polecany przez Instytut Matki i Dziecka.

Zdaję sobie sprawę, że te wynurzenia nie są jakoś specjalne wyrafinowane. Lubię jednak dużo dziwnych wyprowadzać, a nie lubię się tym nie chwalić. A poza tym – być może ktoś skorzysta lub nawet mnie poprawi, co będzie dla mnie bardzo miłą oznaką.

A co do obrazka przy tytule notki – nie, to nie dotyczy grafów. To po prostu “easter egg” z Wielkiego Mistrza umieszczony przez jednego z twórców. Przy okazji – przepraszam całą ekipę za to, iż nie mam ostatnio czasu na tworzenie gry ze względu na studia.

A skoro mowa o easter eggach – Wesołych Świąt!

Pozdrawiam i dziękuję – SceNtriC.