xion.log » 2007 » July

Monthly archive for July, 2007

Ewolucja serwisu

2007-07-23 20:27

Zdaje się, że ostatnio polubiłem webmajstrowanie. Podejrzewam jednak, że to stan wysoce przejściowy i dlatego lepiej by było jak najwięcej zrobić przy tej stronce, zanim przejdzie mi na to ochota ;P

Tak więc dzisiaj dodałem mnóstwo różnych gadżetów, które sprawiają, że blog coraz bardziej przypomina normalną stronę domową. Wśród nich jest chociażby to menu na górze, dające dostęp do najważniejszych działów.
Jednym z ciekawszych jest Galeria, gdzie docelowo znajdzie się miejsce na różne ładne obrazki, które jako programista gier powinienem przecież masowo produkować ;) Póki co znalazło się tam miejsce za niewielkiej kolekcji wykonanych przeze mnie screenów z gry World of Warcraft. Nie jest ich zbyt wiele, jako że generalnie jestem dość oszczędny w korzystaniu z klawisza Print Screen :) Z tych, które znalazły swoje miejsce w Galerii, chyba najbardziej reprezentatywne są te trzy:

WoWScrnShot_071006_202715.jpg WoWScrnShot_052007_202451.jpg WoWScrnShot_073006_214508.jpg

czyli: coś śmiesznego, ładny widoczek i równie uroczy trup pewnego bossa ;]

Oprócz galerii mamy też dość standardowe działy Download i Linki. W sumie jest już chyba wszystko co na prawdziwą stronę domową przystało…


Author: Xion, posted under Website » 4 comments

Walidacja wszerz

2007-07-22 18:42

Dzisiaj będzie trochę algorytmicznie :) Zajmowanie się programowaniem grafiki i konstruowaniem silnika jest oczywiście satysfakcjonujące, ale programowanie to przecież nie tylko tworzenie, lecz także rozwiązywanie problemów. Dlatego czasami dobrze jest sobie jakiś problem wynaleźć i go rozwiązać :D

Dzisiejszy wprawdzie nie wziął się znikąd, jako że wynalazłem go już jakiś czas temu przeglądając część mojej biblioteki zajmującą się operacjami na łańcuchach. Zagadnienie dotyczy zaś sprawy dość przydatnej i nie tak znowu trywialnej.
Chodzi tu tzw. filtry wildcards. Jest to bardzo znany (zwłaszcza w Windows) sposób zapisywania szablonów nazw plików, przydatny zwłaszcza przy wyszukiwaniu. Jego reguły są bardzo proste: w filtrze mogą występować w dowolnej ilości dwa znaki specjalne:

  • gwiazdka (*), która symbolizuje dowolny ciąg znaków (także pusty)
  • znak zapytania (?), który symbolizuje dokładnie jeden dowolny znak

Oprócz tego szablon może też zawierać dowolne inne znaki, które muszą być dopasowane dosłownie. Typowe “plikowe” przykłady takich szablonów to:

  • *.exe – pasuje do wszystkich nazw plików wykonywalnych (z rozszerzeniem EXE)
  • file????.tmp – pasuje do file0000.tmp, file0001.tmp, ale też fileqwer.tmp, itd.
  • *.? – pasuje do wszystkich nazw plików z jednoliterowym rozszerzeniem

Wildcards (swoją drogą, ciekawa nazwa – ktoś zna jej pochodzenie?) stały się na tyle popularne, że rozpoznaje je także większość wyszukiwarek internetowych. Są bowiem całkiem elastyczne, a o wiele prostsze od wyrażeń regularnych.

Jaki więc problem jest z nimi związany? Chodzi po prostu o sprawdzenie, czy podany ciąg znaków pasuje do podanego wzorca wildcards. Na pierwszy rzut oka może wydawać się to proste – niby wystarczy szukać kolejnych “części stałych” i sprawdzać, czy odstępy między nimi są odpowiednio duże. Ten algorytm jest jednak niepoprawny, bowiem czasami znaki sprawdzanego tekstu musimy traktować na różne sposoby. Przykładowo dla szablonu “a*ba” ciąg “ababa” będzie uznany za niepoprawny, gdyż algorytm dopasuje pierwsze “ba” z tekstu do “ba” zapisanego na sztywno we wzorcu zamiast potraktować je jako dowolny ciąg pasujący do gwiazdki.
Poprawne rozwiązanie musi sprawdzać wszystkie możliwe dopasowania – w tym przypadku oba wystąpienia ciągów “ba”. W swoim algorytmie dla poprawienia efektywności zastosowałem jeszcze wstępne przetwarzanie, dzielące wzorzec na fragmenty – czyli części stałe – oraz zakresy – sekwencje znaków * i ?. Samo sprawdzanie polega natomiast na znajdowaniu wszystkich wystąpień fragmentów, które są w odpowiedniej odległości od siebie (wyznaczanej przez zakresy) i dodawaniu ich do kolejki. Potem są one pobieranie i używane do znalezienia dopasowań następnego fragmentu.
Zasadniczo jest to bardzo podobne do przeszukiwania wszerz wyimaginowanego “grafu dopasowań”. Swoją drogą to ciekawe, że szkielet tego algorytmu grafowego może być użyty do tak wielu rzeczy (jak np. wyszukiwanie najkrótszej drogi między dwoma miastami (algorytm Djikstry) czy szukanie węzłów XML pasujących do wyrażenia XPath). Tak jest oczywiście dlatego, że w tych problemach zawsze wchodzi w grę jakiś mniej lub bardziej intuicyjny graf, tyle że w większości wypadków zastanawianie się nad tym, jak on wygląda, nie ma zbytniego sensu. A tak przy okazji, to w moim algorytmie wildcards można by zmienić kolejkę na stos i wszystko byłoby OK – wtedy mielibyśmy po prostu coś w stylu przeszukiwania wgłąb.

Hmm… wyszedł z tego trochę przydługi miniwykładzik ;) Pozwolę sobie jednak nie kończyć go nieodzowną kwestią “Czy są jakieś pytania” – załóżmy po prostu optymistycznie, że pytań nie stwierdzono ;)

Tags: ,
Author: Xion, posted under Programming » Comments Off on Walidacja wszerz

Pora migracji

2007-07-21 20:43

Rozpoczynając prowadzenie tego bloga w serwisie Blogger, stwierdziłem, że jest on bardzo dobrym rozwiązaniem ze względu na swoją prostotę. Ważne było to, że wszystko można tam zrobić bez grzebania w HTMLu czy jeszcze mniej przyjemnej mieszance HTML i PHP.

W końcu jednak potrzebuje się czegoś więcej. Braki Bloggera odczułem pierwszy raz wtedy, gdy zachciało mi się dołączyć do bloga krótkie opisy niektórych spośród moich produkcji. Niestety, serwis nie oferuje póki co możliwości tworzenia dodatkowych podstron, niebędących notkami.
Dlatego też (między innymi) mamy tę “drobną” rewolucję :) Obecnie blog oparty jest na WordPress – znanym i bardzo rozbudowanym mini-CMSie przeznaczonym właśnie dla tego rodzaju stron. Wygoda korzystania z niego jest właściwie taka sama jak z Bloggera – włączając to rzecz jasna niezbędny edytor działający w trybie WYSIWYG :)

Przesiadka wymagała oczywiście nieco pracy, łącznie ze sporą ilością dłubaniny w jakże ‘pięknym’ kodzie PHP+HTML. Na szczęście w ogromnej większości mam już ją za sobą, zatem teraz czeka nas już tylko świetlana przyszłość ;)


Author: Xion, posted under Website » 2 comments

Tam, gdzie kończy się C++

2007-07-20 19:26

Pod jednym z ostatnich postów, dotyczącym kwestii rysowania dwuwymiarowych sprite’ów, rozpętała się całkiem ciekawa dyskusja. Jej głównym tematem było to, czy i jak implementowany system 2D będzie przydatny w renderowaniu elementu niezbędnego każdej grze – choćby była do bólu trójwymiarowa. Chodzi naturalnie o graficzny interfejs użytkownika, czyli GUI.

Wyświetlanie elementów takiego interfejsu (na który składać się będą różnego rodzaju kontrolki, jak przyciski, pola tekstowe czy listy rozwijalne) to dość złożone zagadnienie. Można je rozwiązać łatwo acz nieefektywnie lub trochę trudniej, ale prawie optymalnie :) Oprócz tego GUI prezentuje sobą też bardzo poważne wyzwanie projektowe, które wymaga dokładnego zaplanowania występujących w nim klas i ich składowych.
Niestety w C++ dochodzi do tego jeszcze jeden problem, który w dodatku jest nieco krępujący. Nie lubimy się nim chwalić w towarzystwie i w sumie chcielibyśmy o nim zapomnieć, zakopać jak najgłębiej, by tylko usunąć go z pola widzenia. Ale rzeczywistość skreczy i uciekanie od kłopotu go nie rozwiąże… Trzeba wypowiedzieć go na głos. Otóż – w C++ nie ma delegatów i w związku z tym obsługa zdarzeń generowanych przez kontrolki GUI zaczyna być problemem.

‘Delegat’ to taka trochę myląca dla prostego i wręcz niezbędnego w obiektowym języku programowania mechanizmu. Delegatem nazywamy bowiem pewien rodzaj wskaźnika, który pokazuje na konkretną metodę w konkretnym obiekcie. Taki wskaźnik jest konieczny do wygodnego realizowania mechanizmu callback, czyli powiadamiania (poprzez wywołanie owej metody), że coś się zdarzyło.
W programowaniu strukturalnym nie ma z tym problemu, jako że istnieją wskaźniki na zwykłe funkcje. Najbardziej znanym jest chyba wskaźnik na procedurę zdarzeniową okna w Windows API:

  1. typedef LRESULT (CALLBACK *WNDPROC)(HWND, UINT, WPARAM, LPARAM);

Mimo pokrętnej składni, wskaźniki do funkcji dobrze spełniają swoje zadanie. Problem polega na tym, że w programowaniu obiektowym nie życzymy sobie obecności “luźnych” funkcji, skoro wszystko zamykamy w klasy. Ten rodzaj wskaźników jest więc kompletnie nieprzydatny.

C++ ma też inny rodzaj wskaźników na kod. Są to w gruncie rzeczy bardzo dziwne twory, dla których samodzielnego zastosowania póki co nie udało mi się znaleźć (co oczywiście nie znaczy, że ono nie istnieje). Te wskaźniki służą do pokazywania na metodę o danej sygnaturze, lecz nie w obiekcie, tylko w klasie. Jak już mówiłem, są to bardzo wyjątkowo nietypowe twory (C++ jest chyba jedynym językiem posiadającym coś podobnego), a towarzysząca im składnia jest zdecydowanie odpychająca.
Ten egzotyczny mechanizm można jednak użyć do implementacji własnego systemu delegatów w C++. Kiedyś nawet popełniłem artykuł wyjaśniający, jak można to zrobić. Przedstawiony tam sposób jest jednak mało elegancki i dlatego jest raczej wątpliwe, bym bo użył.

Skłaniam się raczej do zastosowania zewnętrznej biblioteki, co jest według mnie dość przykrą koniecznością. Ciężko bowiem pogodzić się z tym, że używany język programowania zmusza do uciekania się do zewnętrznych i nieustandaryzowanych rozwiązań tylko po to, by w jakiś w miarę sensowny sposób symulować to, czego mu ewidentnie brakuje. W dodatku kłóci się to z moją filozofią konstrukcji kodu “bibliotecznego” (do którego należy silnik graficzny lub silnik gry), która każe eliminować zewnętrzne powiązania. Czasem jednak stajemy pod ścianą.
Opcje są właściwie dwie. Pierwsza to użycie bibliotek Function i Bind wchodzących w skład Boosta. Mimo że Boost jest rzecz jasna świetnie opracowanym zestawem bibliotek rozszerzających C++, chciałbym jednak jej uniknąć ze względów wydajnościowych. Dokładniej chodzi o obciążenie kompilatora (z którego właściwie każda część Boosta wyciska ostatnie soki) oraz na znacznie ważniejszą kwestię wywołań delegatów w czasie wykonania programu. Dlatego skłaniam się raczej ku innej bibliotece o nazwie FastDelegate, która pod tym względem nie ma sobie równych. Być może kiedyś uda mi się napisać coś równie dobrego i będę mógł z niej zrezygnować, ale chyba bardziej prawdopodobne jest, że do tego czasu C++ będzie miał już wbudowany mechanizm delegatów :)

Mógłbym jeszcze wspomnieć o innym rozwiązaniu polegającym na użyciu polimorfizmu i funkcji wirtualnych i o tym, dlaczego w C++ – ze względu na brak niestatycznych klas wewnętrznych – byłoby ono skrajnie niewygodne. Myślę jednak, że na dzisiaj moglibyśmy już sobie tego oszczędzić :D

Tags: ,
Author: Xion, posted under Programming » 2 comments

Gorące testy

2007-07-18 18:38

W takich dniach jak dzisiejszy, gdy słupek rtęci w termometrze oscyluje w zdecydowanie zbyt wyżynnych okolicach, można żałować, że procesor w stojącym na biurku pececie pracuje dokładnie tak, jak mu fabryka nakazała i ani megaherca więcej. Dlaczego? Bo może wtedy nie obyło by się bez chłodzenia wodnego, co odjęłoby robiący w tych dniach krecią robotę radiator :)

W takich dniach kodowanie też jakoś za bardzo nie idzie, ale oczywiście jest to marnym usprawiedliwieniem nierobienia niczego pożytecznego. Skoro więc produkowanie nowego kodu nie przebiega tak płynnie jak zwykle, może warto zająć się kodem już istniejącym?… Ano warto – zwłaszcza jeśli pilnie wymaga on np. tak elementarnej czynności jak testowanie.
Przy tej okazji oczywiście nie raz i nie dwa pada najważniejsze pytanie, zadawane jak świat długi i szeroki przez wszystkich programistów, jacy kiedykolwiek chodzili po tej ziemi. Tak, chodzi naturalnie o gromkie:

Dlaczego to nie działa?!

To jest jednak tylko pytanie podstawowe, które można modyfikować w zależności od swojej programistycznej specjalności. I tak koderzy zajmujący się grafiką w ogóle, a programowanie w DirectX w szczególności mogą zmodyfikować je do równie dramatycznego:

Dlaczego nic nie widać?

Ten problem jest już na szczęście bardziej konkretny i stąd jego rozwiązanie powinno być łatwiejsze. Istotnie, na warsztatowym Wiki leży sobie nawet odpowiedni artykuł w formie listy kontrolnej, która wylicza sporo możliwości, mogących stać za problemami. Pocieszać można się jeszcze tym, że w 99% przypadków możemy przynajmniej zobaczyć coś innego niż nieprzeniknioną czerń – ja np. gustuję w czyszczeniu bufora tylnego na jaskrawozielony, opierając się wszechobecnej dyktaturze koloru niebieskiego ;P

Skoro tyle piszę o testowaniu, debugowaniu czy jak to ktoś “ładnie” spolszczył – odpluskiwaniu – to powinienem jeszcze wspomnieć, jakiż to kod poddaję tym mało wyszukanym operacjom. Jest to oczywiście pewien kawałek modułu grafiki 2D, który niedawno opisywałem.
Tak więc zgodnie ze starą prawdą, pisanie programu to rozkosz; uruchamianie programu to koszmar :) I chociaż może (oby!) nie zawsze jest tak w rzeczywistości, to jednak programiści są istotami wybitnie omylnymi i przez tę drugą, mniej przyjemną fazę tworzenia też trzeba przejść. I prawdę mówiąc, raczej nie ma co się nad nią dłużej rozwodzić :P

Tags: ,
Author: Xion, posted under Programming » Comments Off on Gorące testy

Jedno D mniej

2007-07-16 16:20

Zaprogramowanie w miarę porządnego, elastycznego i wydajnego silnika grafiki 3D jest oczywiście dość trudne. W końcu trzeba zadbać o właściwą organizację sceny, wczytywanie modeli, system materiałów, oświetlenie, cienie i pewnie jeszcze mnóstwo innych rzeczy. Trzeci wymiar nie ułatwia nam wcale życia.

Wydawałoby się więc, że gdy go usuniemy, sprawy nabiorą znacznie przyjemniejszego (i prostszego) kształtu. No cóż, kiedyś życie było łatwiejsze – ale głównie dlatego, że mieliśmy mniejsze wymagania. Mieliśmy na przykład całkiem znośną bibliotekę 2D zaimplementowaną jako część DirectXa – czyli DirectDraw. Chociaż obcowanie z nią na początku mogło być dość odstręczające (zwłaszcza jeśli wcześniej korzystało np. tylko z windowsowego GDI czy arcyprostego SDL), to jednak i tak stworzenie powierzchni do rysowania z podwójnych buforowaniem jest w DD znacznie prostsze niż chociażby poprawne zainicjowanie urządzenia Direct3D…
Fakty są jednak takie, że 3D ma się dobrze i coraz lepiej, a grafika dwuwymiarowa jest najczęściej tylko dodatkiem (prawda, że niezbędnym) do renderowanej sceny. Dlatego też najlepiej używać do niej tego samego DirectXa, z którego korzystamy w trakcie wyświetlania scen.

I chociaż jest to generalnie trudniejsze, daje o wiele większe możliwości i lepszą wydajność. Można oczywiście korzystać z należącego do D3DX interfejsu ID3DXSprite, lecz jego możliwości są raczej ograniczone i do wygodnego stosowania należałoby zapakować go w bardziej gustowne klasy.
Stąd też lepiej, w moim odczuciu samemu zatroszczyć się o odpowiednie funkcje i klasy do obsługi rysowania 2D. Muszę przy tym przyznać, że jestem trochę może za bardzo przyzwyczajony do eleganckich interfejsów bibliotek w rodzaju GDI+, VCL czy Graphics32. Chodzi tu przede wszystkim o dosyć intuicyjną koncepcję “płótna” (canvas), czyli obiektu kontrolującego całe rysowanie (w zwykłym GDI nazywa się to kontekstem urządzenia). Płótno, jak sama nazwa wskazuje, jest to taki obiekt, na którym rysujemy inne obiekty – jak na przykład obrazy czy tekst. Jest to nieco inne rozwiązanie projektowe niż chociażby te stosowane w D3DX, w którym to same obiekty (sprite’y, czcionki, itp.) wiedzą, jak się narysować.

Jak zapewne nietrudno się domyślić, piszę o tym dlatego, iż obecnie zajmuję się właśnie implementacją modułu grafiki 2D opartego z grubsza o podane wyżej założenia. Naturalnie, zakodowanie wszystkich funkcji dostępnych w GDI(+) itp. byłoby strasznie pracochłonne i w większości przypadków zupełnie niepotrzebne. Dlatego ograniczam się przede wszystkim do wyświetlania prostokątnych obrazków, a później także do wypisywania tekstu.
Zadanie to może wydawać się proste, ale w gruncie rzeczy wcale takie nie jest. Weźmy chociażby pod uwagę to, że dla efektywności należy podczas rysowania obrazków (będących oczywiście oteksturowanymi prostokątami) unikać częstego przełączania tekstur. A z tego wynika, że pojedynczy “obrazek” to tak naprawdę określony fragment pewnej tekstury, dla którego trzeba chociażby wygenerować określone współrzędne. A to już wymaga odpowiedniego opisu takich obrazków (konsekwentnie unikam słowa sprite, które uważam za sztuczne ;P) – na przykład w zewnętrznym pliku tekstowym. Dla wygody czy chociażby dla celów animacji obrazki wypadałoby ponadto układać w kolekcje. W sumie wychodzi więc całkiem sporo pracy, nieprawdaż? :)
Zresztą samo rysowanie też nie należy do najłatwiejszych. Jedną z pojawiających się tu kwestii jest na przykład przycinanie (clipping), czyli ograniczenie rysowania do wybranego obszaru – w najprostszej wersji prostokąta. Direct3D od wersji 9 posiada wprawdzie narzędzie nazywane scissor test (“test nożyczkowy”), które to właśnie robi, jednak jego użycie praktycznie wykluczałoby możliwość buforowania rysowanych kształtów. Znaczy to, że każda zmiana obszaru przycinania wymuszałaby renderowanie zebranych trójkątów – co w dość skuteczny sposób obniżyłoby ogólną wydajność. Tak więc przycinanie trzeba robić – tadam! – ręcznie :P Na szczęście nie jest to bardzo trudne, jeżeli dotyczy wyłącznie prostokątów wyrównanych do osi układu współrzędnych (czyli wtedy, gdy wykluczamy obroty).

Tak mniej więcej przedstawia się początek tematu pt. grafika dwuwymiarowa. Czy ktoś nadal uważa, że jest to rzecz znacznie prostsza niż 3D? :)

Tags: , ,
Author: Xion, posted under Programming » 13 comments

Wykopaliska

2007-07-14 11:12

Na swoich stronach domowych zamieszczałem zwykle różnego rodzaju produkcje programistyczne własnego autorstwa. Przez sześć lat nazbierało się tego całkiem sporo, z czego oczywiście nie wszystkie nadają się ponownego pokazania :)
Z czeluści twardego dysku wybrałem jednak kilka, które, jak sądzę, mogą być jeszcze interesujące. Linki prowadzące do ich ściągnięcia można zobaczyć po prawej stronie, ale wypadałoby powiedzieć pokrótce, co (nie)ciekawego można tam znaleźć:

  • Megatutorial “Od zera do gier kodera” to rzecz jasna znany już kurs programowania w C++ i Windows API z kilkoma mniej lub bardziej związanymi z tym dodatkami. Ku mojemu zaskoczeniu okazał się on niezwykle popularny, co ma swoje dobre i złe strony :)
    Link prowadzi do strony Warsztatu, gdzie kurs jest dostępny w całości.
  • Taphoo to moja najnowsza produkcja, chociaż ma już kilka miesięcy. Jest to dość oryginalna gra logiczna, w której celem jest przejście wyznaczonej ścieżki na planszy i zniszczenie po drodze wszystkiego, co da się zniszczyć :)

    Taphoo (screen)

  • PenSoccer to z kolei nic innego jak popularne piłkarzyki – zwykle rozgrywane na kartce papieru w kratkę. Mimo że planowałem opracowanie jakiegoś AI dla tej gry, to póki co można grac jedynie lokalnie dwoma graczami. Ale za to grafika jest ładna ;P
  • CoordCAD to taki niecodzienny programik, którego przeznaczeniem jest rysowanie różnych figur w prostokątnym układzie współrzędnych. Można więc kreślić wykresy funkcji, linie proste, krzywe Beziera, itp.
  • ColorShop to bodaj najprostszy i jednocześnie najbardziej przydatny program z nich wszystkich :) Mieści się on w małym okienku, przy pomocy którego można pobrać kolor dowolnego piksela na ekranie. Mimo że generalnie trzymam się od grafiki jak najdalej, muszę stwierdzić, że przydaje się to w wielu najmniej oczekiwanych sytuacjach ;)
  • AlteString to z kolei wynik zabawy nowopoznanym językiem programowania C#. Teoretycznie program potrafi dokonywać różnego rodzaju ‘transformacji’ na tekście, a praktyce jest chyba jedną z najbardziej bezużytecznych aplikacji, jakie widział świat ;] Wymaga .NET Framework 2.0.
  • Zegarek jest, jak sama nazwa wskazuje, zegarkiem :) A jak przystało na porządny zegarek, potrafi on pokazywać aktualny czas oraz działać jak stoper. Posiada też funkcję synchronizacji czasu ze zdalnym serwerem, która niestety od czasu pojawienia się Windows XP nie jest już tak przydatna.

Jak widać nie ma tu żadnych zapierających dech w piersiach dzieł, ale istnieje przecież niezerowe prawdopodobieństwo, że coś może tu komuś wpaść w oko. Przy okazji muszę zaznaczyć, że kolejność ułożenia pozycji jest nieprzypadkowa i te z górnej części listy są generalnie ciekawsze niż te z dolnej :)


Author: Xion, posted under Games, Website » 2 comments
 


© 2018 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.