O dwóch funkcjach do ścieżek

Kolejnymi kawałkami kodu z poprzedniej wersji mojej biblioteki uniwersalnej, którym postanowiłem się przyjrzeć, były różnego rodzaju funkcje "systemowe". Nazwa jest może trochę na wyrost, jako że dotyczyły one głównie pewnych operacji na plikach i ich nazwach. Wśród z nich znalazły więc procedury do pobierania nazw plików, ich rozszerzeń, sprawdzania istnienia plików, tworzenia całych ścieżek katalogów i tym podobne.

Ostały się też dwie najciekawsze funkcje o bardzo podobnych do siebie sygnaturach:

Wykonują one interesującą pracę: konwertują ścieżki względne na bezwzględne i odwrotnie. Jak wiadomo, ścieżka bezwzględna określa położenie w systemie plików w sposób jednoznaczny, np.:

• C:\Program Files\Taphoo

oznacza podkatalog Taphoo w katalogu Program Files na dysku C - niezależnie od tego, gdzie się teraz znajdujemy. Natomiast ścieżka względna - taka jak ta:

• ../images/logo.gif

mówi jedynie, że w celu dostania się do pliku logo.gif należy wyjść do nadrzędnego katalogu (..), a stamtąd przejść do katalogu images.

Do czego może przydać się konwersja między oboma typami ścieżek? Dobrym przykładem jest dyrektywa #include w C(++), która akceptuje ścieżki względne:

Preprocesor musi jest rozwinąć, aby móc wstawić zawartość dołączanego pliku. Z użyciem wymienionej wyżej funkcji RelativeToAbsolutePath można łatwo dodać podobną dyrektywę do języka opisu lub skryptowego.

Czcionki i tekst(ury)

Żadna porządna biblioteka do grafiki 2D nie może obyć się bez narzędzi służących do wypisywania tekstu. Kiedy jednak mamy na uwadze głównie programowanie gier (lub pokrewnych aplikacji), sprawa wygląda nieco inaczej niż w bardziej "ogólnych" zastosowaniach. Nie trzeba na przykład rozkładać tekstu na czynniki pierwsze:

Pozwalałoby to oczywiście w razie potrzeby dodać kursywę, pod-, nad- i przekreślenie. Zazwyczaj jednak nie jest to potrzebne.

Tak więc chociaż wygląda to na krok wstecz, stosuje się najczęściej czcionki bitmapowe. Pomysł polega na tym, że cały używany zestaw znaków danego kroju i danej wielkości jest rysowany na jednej teksturze w taki sposób, by łatwo można było obliczyć pozycję każdego znaku:

Wyświetlanie napisu polega wtedy na renderowaniu oteksturowanych prostokątów - po jednym dla każdego znaku. Jest to bardzo wydajne, bo chociaż trójkątów może być bardzo dużo, to ich tekstura jest zawsze taka sama. Można zatem wyrzucić całe połacie tekstu na ekran tylko jednym wywołaniem Draw[Indexed]Primitive.

Tylko skąd wziąć taką sprytną teksturę? Można rzecz jasna generować ją samemu przy pomocy funkcji GDI; choć jest to wolne, byłoby wykonywane tylko raz, więc nie stanowiłoby problemu. Lepszym rozwiązaniem jest użycie odpowiednich programów, z których najlepszym jest chyba Bitmap Font Generator. Potrafi on w sprytny sposób upakować w jednym obrazku sporą ilość znaków, zaś ich parametry opisuje w łatwym do odczytania formacie tekstowym przypominającym szczątkowy INI.

Obecnie używam więc właśnie jego i dzięki temu mogłem w końcu dodać do swojego silnika podstawowy i zupełnie niezbędny element: licznik FPSów :)

Trzy rozwiązania dla relacji zawierania

Chcę dzisiaj zająć się pewną sprawą natury projektowej. Mam tu mianowicie na myśli sytuację, gdy mamy do czynienia ze zbiorem różnych elementów, wywodzących się z tej samej klasy bazowej. Najlepiej widać to będzie na odpowiednim diagramie:

Jest tu klasa kontenera (Container), która posiada m.in. zestaw różnych Elementów. Ich dokładne typy nie są i nie muszą być znane - ważne, że wywodzą się od klasy bazowej Element. W szczególności klasy Container i Element mogą być jednym i tym samym - wtedy będziemy mieli do czynienia ze strukturą hierarchiczną, reprezentującą np. drzewo węzłów dokumentu XML czy kontrolki systemu GUI. Zauważmy jeszcze, że każdy element wie o swoim właścicielu (pole Owner), czyli o pojemniku, który go zawiera (albo o elemencie nadrzędnym w przypadku drzewa).
Z obsługą już dodanych elementów nie ma zbytniego problemu, jako że wyjątkowo naturalne jest tu wykorzystanie metod wirtualnych i polimorfizmu. Kłopot polega właśnie na tworzeniu i dodawaniu nowych elementów - a ściślej na interfejsie (funkcjach i parametrach), które mają do tego służyć. I tutaj właśnie pojawiają się te trzy rozwiązania.

Rozwiązanie pierwsze polega na wyposażeniu klasy Container w garnitur metod zajmujących się tworzeniem każdego typu elementów i dodawaniem ich do zbioru. W naszym przypadku byłyby to więc funkcje AddElementA, AddElementB i AddElementC:

Jak widać w tym przypadku dobrze jest wyposażyć konstruktory klasy Element i pochodnych w parametr, przez który będziemy podawali wskaźnik do nadrzędnego kontenera lub elementu.

Drugie rozwiązanie zakłada, że pojemnik dysponuje tylko jedną ogólną metodą AddElement. Przekazujemy jej już utworzone obiekty, a jej zadaniem jest tylko dodać je do już posiadanych:

Zauważmy, że tutaj konstruktory elementów już nie przyjmują wskaźników na swoich właścicieli. Dzięki temu możemy uchronić się przed omyłkowym dodaniem elementu do innego pojemnika niż ten, który podaliśmy podczas jego tworzenia.
Skąd jednak element wie, do kogo należy?... Za to odpowiada już metoda dodająca, która modyfikuje pole określające właściciela:

Oczywiście w tym celu klasa Container musi być zaprzyjaźniona z klasą bazową Element, co na szczęście w C++ nie stanowi problemu :) (W innych językach, jak np. C# czy Java, można osiągnąć bardzo podobny efekt przy pomocy pakietów.)

W końcu trzecie wyjście przenosi cały ciężar pracy na same elementy. W tej koncepcji to elementy same się dodają do podanego pojemnika:

Żeby miało to sens, muszą być one aczkolwiek tworzone dynamicznie poprzez operator new.

Czas na nieodparcie nasuwające się pytanie, czyli... które rozwiązanie jest najlepsze? No cóż, sprawa nie jest taka prosta (inaczej bym o niej nie pisał ;D), więc może przyjrzyjmy się kilku argumentom:

• Rozwiązanie nr 1 jest dość powszechnie stosowane zwłaszcza tam, gdy elementy mają ustalone i raczej niezmienne typy. Przykładem jest wspomniane drzewko węzłów XML: tam wachlarz typów ogranicza się do tekstu, elementów XML, atrybutów, sekcji CDATA, instrukcji przetwarzania i jeszcze paru innych. Napisanie dla każdego z nich odpowiedniej metody Add* nie jest specjalnie czasochłonne.
• Trzecie rozwiązanie jest najwygodniejsze i daje najmniejsze pole manewru, jeżeli chodzi o popełnienie błędów - np. stworzenie obiektu i niedodanie go do pojemnika. Z drugiej strony może ono produkować nieintuicyjny kod. Jeżeli bowiem chcemy tylko dodać jakiś element i nie jest on nam za chwilę potrzebny, to użyjemy poniższego kodu:
  new ElementA(pContainer, parametry);

  Jest więc new, którego rezultat ignorujemy i tylko po dłuższym przyjrzeniu się można zauważyć, że to jednak nie jest wyciek pamięci.

• Zarówno trzecie, jak i (zwłaszcza) drugie rozwiązanie dopuszcza tworzenie elementów "wolnych", nieprzypisanych do żadnego pojemnika. Wbrew temu co napisałem przed chwilą, taka czynność nie musi być wcale błędem. W takim przypadku odwołanie do właściciela w elemencie ustawiamy po prostu na NULL.

Cóż więc wybrać? Ostatnio skłaniam się ku drugiemu rozwiązaniu. Według mnie jest ono z tych trzech najbardziej przejrzyste - tworzenie obiektu to jedno (operator new), a jego dodawanie drugie (metoda Add). Ponadto dzieli ono pracę w miarę równo między element, jak i pojemnik - w przeciwieństwie do pozostałych modeli. I w końcu, nic w tym rozwiązaniu nie jest robione za plecami programisty, co oczywiście może być zaletą, ale i wadą oznaczającą, że przecież wszystko musimy zrobić samemu.

A zatem... kwadratura koła? W takich sytuacjach warto chyba iść na kompromis, czyli poprzeć prostokąt z zaokrąglonymi rogami ;)

Obiekty są pamiętliwe

Czasami mylne wyobrażenie o pewnych elementach języka programowania potrafi ściągnąć na nas nie lada kłopoty. Właśnie ostatnio mogłem o się o tym przekonać, a sprawa dotyczy niezbyt często wykorzystywanego elementu C++, a mianowicie placement new.

Cóż to takiego? Jest to sposób na podanie operatorowi new adresu miejsca w pamięci, który ma wykorzystać. Może to brzmieć niedorzecznie, bo przecież new ma za zadanie właśnie alokację pamięci. To jednak tylko część prawdy, bowiem ten operator wywołuje też konstruktor tworzonego obiektu. W przypadku wersji placement będzie to więc jedyna czynność, jaką wykona.
Składnia placement new wygląda mniej więcej tak:

Na czym jednak polega problem? Otóż tego specjalnego wariantu operatora new nie można wywoływać bezkarnie. W szczególności nie jest to sposób na "przezroczyste" wywołanie konstruktora dla jakiegoś obiektu.

Pytanie oczywiście brzmi: do czego było mi potrzebne użycie tego rzadkiego mechanizmu języka? No cóż, teraz już wiem, że do niczego, jednak wcześniej myślałem, że będzie to niezły sposób na wczytywanie zasobów.
W skrócie: w mojej bibliotece zasoby takie jak np. tekstury czy bufory tworzą dość prostą hierarchię dziedziczenia. Parametry niektórych z nich - jak np. tekstur - można wczytywać z pliku tekstowego - w tym przypadku chodzi chociażby o nazwę pliku graficznego z obrazkiem tekstury.
Sęk w tym, że zasób tekstury (reprezentowany przez klasę CTexture) jest też zasobem DirectX (dziedziczy po IDxResource). A z tym związane są kolejne parametry, jak np. pula pamięci czy sposób użycia zasobu (to akurat nie jest mój wymysł, tylko DirectXa ;P). One również mogą być zapisane w pliku i trzeba je uwzględnić przy wczytywaniu tekstury.

W moim "genialnym" rozwiązaniu wymyśliłem więc, że podczas tworzenia obiektu CTexture zostanie najpierw stworzony obiekt IDxResource (dzięki czemu zostanie załatwiona kwestia "DX-owych" parametrów). Następnie w tym samym miejscu pamięci - placement new! -skonstruujemy obiekt CTexture, który zajmie się załadowaniem pozostałych danych.
I to rzeczywiście działało, dopóki się nie zorientowałem, że zapomniałem dopisać do menedżera zasobów kodu, który zwalniałby wszystko przy kończeniu programu. Wtedy to w ruch poszły destruktory, a wtedy pojawiły się... przerwania systemowe informujące o uszkodzeniu sterty.

Powodem jest fakt, że obiekty (a ściślej mechanizm ich alokacji) pamiętają sposób, w jaki zostały stworzone. Jeżeli było to zwykłe new, to zniszczenie obiektu pociąga za sobą zwolnienie pamięci. Lecz jeżeli było to placement new, to operator delete zakłada, że nic nie wie o obszarze pamięci, w którym obiekt rezyduje - więc go nie zwalnia. W istocie FAQ C++ wyraźnie pisze, by przy używaniu placement new samemu wywoływać destruktor, a potem samodzielnie zwalniać pamięć.
placement new nie jest po prostu sposobem na wywołanie konstruktora - z jego użyciem wiążą się określone konsekwencje. Jak widać czasami można przekonać się o nich w mało przyjemny sposób :)

Walidacja wszerz

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 ;)

Tam, gdzie kończy się C++

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:

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

Gorące testy

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