Posts from 2009

Repozytorium dla każdego

2009-04-15 17:26

Były takie prognozy, że w Internecie wkrótce nie będzie już prawie niczego za darmo, a za większość usług czy nawet informacji trzeba będzie płacić. W rzeczywistości można obecnie znaleźć w sieci coraz bardziej wyrafinowane i wyspecjalizowane usługi często całkowicie (lub niemal całkowicie) darmowe. Nie chodzi tu już tylko o webhosting czy konto e-mail. Przeciwnie, nietrudno natrafić na oferty skierowane bezpośrednio do… programistów – zawodowców i amatorów.

Istnieją bowiem serwisy, które nieodpłatnie udostępniają swoim użytkownikom repozytoria, na których mogą oni umieszczać swoje projekty. Tak tak, chodzi tutaj o hostowanie systemów kontroli wersji, w szczególności najpopularniejszego: Subversion (SVN). Wystarczy zarejestrować się w jednym z takich serwisów, a otrzymujemy możliwość założenia swojego własnego repozytorium i nadania praw dostępu do niego innym użytkownikom. Obowiązują oczywiście pewne ograniczenia, dotyczące najczęściej ilości miejsca na naszą twórczość lub liczby osób, które możemy zaprosić do współpracy. Na potrzeby własne, szkolne i uczelniane często są one jednak możliwe do zaakceptowania. A jak nie, to pozostają jeszcze wersje płatne – bo nie ma co ukrywać, że to o przyciągnięcie do oferty komercyjnej w całym tym ambarasie chodzi :)

Darowanemu koniowi nie ma co jednak zaglądać za bardzo w zęby. Jeśli bowiem potrzebujemy narzędzia do zorganizowania pracy grupowej (albo nawet swojej własnej) nad niewielkim projektem, to serwisy w rodzaju Beanstalk, XP-Dev czy Assembla mogą być bardzo dobrym rozwiązaniem.

Tags:
Author: Xion, posted under Internet, Programming » 9 comments

Zmienne globalne w C++

2009-04-14 11:37

Niejeden początkujący programista C++ natknął się pewnie na prosty problem: jak zdefiniować zmienną, która będzie dostępna w całym programie? Sprawa nie jest oczywista z tego względu, że w języku tym nie występuje w ogóle pojęcie ‘projektu’; każdy moduł .cpp jest kompilowany osobno i dopiero linker składa je wszystkie w jeden plik wykonywalny. O tym jednak łatwo zapomnieć, jeśli używamy współczesnych środowisk programistycznych.

Warto więc wiedzieć, że w C++ tak naprawdę nie ma zmiennych globalnych. Symulują je zmienne łączone zewnętrznie – takie, które definiujemy w jednym module .cpp, a odwołujemy się do nich z innych modułów przy pomocy deklaracji zapowiadających extern. Te muszą być oczywiście umieszczone we wspólnych plikach nagłówkowych.
Powyższy sposób jest jedynym na uzyskanie zmiennych dostępnych z wielu plików .cpp. Jeśli coś w nim pokręcimy, możemy otrzymać albo kod niekompilujący się (jeżeli nie dołączymy deklaracji extern), ale – co gorsza – uruchamiający się, ale działający zupełnie inaczej (jeśli w headerze damy normalną definicje zmiennej, każdy dołączający go moduł otrzyma jej własną niezależną kopię).

Tags:
Author: Xion, posted under Programming » Comments Off on Zmienne globalne w C++

Dwa paradoksy prawdopodobieństwa

2009-04-05 18:34

Na dzisiaj przewidziałem ciekawostki z nieco innej niż zwykle beczki :) Chciałem mianowicie pokazać dwa przykłady na to, jak intuicyjnie całkiem proste pojęcie matematyczne w rzeczywistości jest bardzo podatne na niewłaściwe zrozumienie. Chodzi tutaj o zwykłe prawdopodobieństwo – czyli szansę na zajście jakiegoś zdarzenia.

Pierwszy przykład jest z gatunku rozrywkowo-medialnych i związany jest z pewnym teleturniejem, który zresztą był kiedyś emitowany także w Polsce. Oto w pewnym jego etapie uczestnik jest konfrontowany z trzema zasłoniętymi bramkami, z których jedna zawiera nagrodę, a dwie pozostałe są puste. Spośród tej trójki gracz wybiera jedną bramkę, by stać się właścicielem jej ewentualnej zawartości. Trik polega na tym, że gospodarz programu – już po wyborze gracza – odsłania jedną z pozostałych bramek, która okazuje się być pusta. Zgodnie z regułami teleturnieju gracz może w tym momencie zmienić swój wybór i wskazać trzecią bramkę zamiast tej wybranej pierwotnie. Pytanie brzmi: czy taka zamiana mu się opłaca?
Część ludzi stwierdziłaby zapewne, że nie ma to znaczenia, bo szansa wygranej przecież i tak wynosi 1 do 3, bo tylko za jedną bramką jest nagroda. Inni mogliby uznać, że po odsłonięciu jednej bramki wybieramy już spośród dwóch, więc nasze szansę rosną do 50% – też niezależnie od tego, czy zmienimy swój pierwotny wybór czy nie… A jak jest naprawdę?
Może się to wydawać niedorzeczne, jednak będąc na miejscu gracza, powinniśmy zawsze zmienić swój wybór. Mało tego, w ten sposób nasze szanse na wygraną rosną dokładnie dwukrotnie! Jak to możliwe?… Otóż kluczowe w wyjaśnieniu tego zjawiska jest zauważenie, że gospodarz programu zawsze odsłoni bramkę pustą i niewybraną przez gracza (w innym przypadku gra skończyłaby się od razu i w ogóle nie byłoby możliwości zmiany). Dlatego też opłaca się dokonać zmiany, bo w ten sposób w istocie odwracamy prawdopodobieństwo wygranej i przegranej. Możliwe są bowiem dwie sytuacje:

  • gracz początkowo wybiera bramkę z nagrodą – po zmianie kończy więc z bramką pustą
  • gracz najpierw wskazuje bramkę pustą; wówczas gospodarz odsłoni drugą pustą bramkę, więc zmiana skończy się wyborem bramki z nagrodą

Jak wiadomo prawdopodobieństwo dobrego wyboru spośród trzech bramek wynosi 1/3, a złego – 2/3. Takie są też odpowiednie prawdopodobieństwa dwóch powyższych scenariuszy; innymi słowy, zmiana bramki powoduje, że prawdopodobieństwo wygranej rośnie z początkowego 1/3 do 2/3.
Jeśli ktoś ma nadal wątpliwości, to nie ma czym się martwić – podobno wielu matematyków też ma kłopoty z ogarnięciem tego paradoksu :) Wydaje mi się, że rzecz w tkwi w błędnym określeniu, co tak naprawdę jest tutaj zdarzeniem losowym. Jeśli za takie będziemy uważali zarówno początkowy wybór, jak i zmianę, to rzeczywiście mogą być kłopoty z dojściem do poprawnych wniosków. Zamiast tego całą grę powinno się traktować jako jedno doświadczenie losowe, ze z góry ustalonym scenariuszem.

A co z drugim przykładem? Jest na szczęście nieco prostszy i dotyczy koncepcji zdarzeń (nie)zależnych. Oto kilka pytań dotykających tej kwestii, dla których odpowiedzi “intuicyjne” są zwykle błędne:

  • Jeśli zakręcimy kołem ruletki 57 razy i za każdym razem kulka wpadnie w czarne pole, to jaka jest szansa na to, że będzie tak również przy następnym obrocie?
  • Jeśli liczba 42 ostatni raz wystąpiła w Dużym Lotku pół roku temu, to jaka jest szansa, iż wypadnie w dzisiejszym losowaniu?
  • Jeśli w grze X potwór Y wyrzuca przedmiot Z z prawdopodobieństwem 1/n, to jak dużo potworów Y powinienem zabić, aby być prawie pewien, że wypadnie mi z nich przedmiot Z?

Nie, prawdopodobieństwo wpadnięcia kulki w czarne pole to cały czas 1/2. Nie, liczba 42 może wypaść z takim samym prawdopodobieństwem dzisiaj, jak i w każdym innym losowaniu. Nie, zabicie n potworów Y wcale nie da nam prawie-pewności dostania Z – o ile mówimy o zwyczajowym użyciu słowa ‘prawie’ ;)
Wszędzie tutaj mamy bowiem do czynienia z sekwencją zdarzeń całkowicie niezależnych, których wyniki nie wpływają na siebie. Zatem nie ma znaczenia to, ile razy wcześniej kręciliśmy ruletką, ile wysłaliśmy już w życiu kuponów Lotto i ile wrażych monstrów zdołaliśmy zaszlachtować – prawdopodobieństwo zajścia interesującego nas zdarzenia w kolejnej próbie jest zawsze identyczne. Możemy aczkolwiek spróbować policzyć, na ile jest to prawdopodobne dla ciągu k kolejnych prób. Otóż ze schematu Bernoulliego wynika, że szansa na sukces wynosi wtedy

1 – (1 – p)k

jeśli dla pojedynczej próby prawdopodobieństwo wynosi p. Stąd dla p = 1/n i k = n otrzymujemy (po kilku, jak to by powiedzieli matematycy, “trywialnych przekształceniach ;D) wynik: (e – 1)/e; nieco ponad 63%. To trochę mało jak na prawie-pewność, czyż nie? ;]

Jak więc widać na przykładach, szansa na to, że opacznie zrozumiemy sytuację, w której zastosowania mają pojęcia ‘szansy’ czy ‘prawdopodobieństwa’ (używane tutaj jako synonimy) jest – nomen omen dosyć duża. Może dlatego w szkole niespecjalnie przepadałem za tym działem matematyki :)

Tags:
Author: Xion, posted under Math » 19 comments

Kopiuj-i-wklej kod

2009-03-28 11:29

Gdy znajdziemy w sieci kawałek kodu, który chcemy przeanalizować, to nie zawsze jest on ładnie sformatowany czy pokolorowany. Wtedy możemy sobie pomóc, wklejając rzeczony kod do naszego środowiska programistycznego; w większości znajdzie się opcja pozwalająca np. wyrównać wcięcia (w Visual Studio jest to Edit | Advanced | Format Selection), że o kolorowaniu nie wspomnę ;]

O powyższym wiedzą pewnie wszyscy. Jednak czasami kopiujemy też kod w drugą stronę, z IDE. Jeśli korzystamy z Visual Studio, to możemy wykorzystać przy okazji fakt, że jest on kopiowany jako… tekst formatowany typu RTF.
Na pierwszy rzut oka może to wydawać się co najmniej dziwne. Przecież kod z założenia jest zwykłym tekstem, więc po co dodatkowe informacje o czcionkach czy wyglądzie znaków?… Otóż odpowiedź jest bardzo prosta: w ten sposób zachowana jest bowiem informacja o kolorowaniu składni. Jeśli teraz wkleimy nasz kod do dowolnego edytora tekstu formatowanego (czyli od WordPada wzwyż), to zobaczymy z słowami kluczowymi i innymi elementami zakolorowanych dokładnie w ten sam sposób, jak w środowisku programistycznym.

Do szczęścia brakowało by pewnie jest możliwości szybkiej konwersji takiego kodu do formatu HTML… ale cóż, nie można mieć wszystkiego ;-)

Tags:
Author: Xion, posted under Applications, Programming » 8 comments

Nie tylko alpha blending

2009-03-18 10:31

Uaktywnienie łączenia alfa w DirectX na pierwszy rzut oka wydaje się dość skomplikowana. Niby występuje tam oczywiste ustawienie stanu renderowania D3DRS_ALPHABLENDENABLE na true, jednak to nie wszystko. Potem zwykle od razu występują przynajmniej dwa inne stany: D3DRS_SRCBLEND i D3DRS_DESTBLEND, ustawiane na równie tajemnicze wartości. Wyjaśnimy sobie dzisiaj, co one oznaczają i jak można je wykorzystać.

Należy zacząć od tego, że ten zagadkowy alpha blending to nic innego, jak zwykła suma ważona:

SourceBlend * SourceColor + DestBlend * DestColor

(z dokładnością do tego, że dodawanie można zastąpić innym działaniem przy pomocy D3DRS_BLENDOP, ale tę możliwość zostawimy w spokoju ;]). To, co jest tutaj sumowane, to dwa kolory: źródłowy – pochodzący od właśnie mającego się narysować piksela, oraz docelowy – będący już w danym miejscu bufora ramki (ekranu). Normalnie ten pierwszy zwyczajnie zastąpiłby ten drugi, ale dzięki łączeniu alfa można zamiast tego uzyskać jakąś kombinację ich obu – czyli na przykład symulację półprzezroczystości. Wagami dla sumy są SourceBlend i DestBlend, i to właśnie je ustawiamy przy pomocy stanów renderowania.

Możliwych wartości jest kilka i obejmują one zarówno tak proste jak zero czy jeden aż po same kolory: źródłowe i docelowe (podobnie jak one, współczynniki te są 4-elementowymi wektorami), wartości ich kanału alfa, specjalny globalny współczynnik blend factor – jak również negacje tych wszystkich wartości. Sporo tego, prawda? :) Zobaczmy więc kilka typowych kombinacji:

  • SourceBlend = SourceAlpha; DestBlend = InvSourceAlpha

    To najbardziej typowy sposób osiągania przezroczystości. Używamy tutaj źródłowej wartości alfa, by określić, jak bardzo kolor źródłowy ma wpływać na wynikowy oraz jak bardzo ma być pominięty wpływ koloru docelowego – że tak spróbuje się “intuicyjnie” wyrazić :) Ostatecznie mamy wtedy równanie typu:

    SourceAlpha * SourceColor + (1 – SourceAlpha) * DestColor

    czyli tzw. kombinację liniową obu kolorów, która w wyniku daje wrażenie półprzezroczystości.

  • SourceBlend = One; DestBlend = One

    Ustawienie obu wag na 1 sprawia, że nasza suma ważona stają się zwykłą sumą, więc kolory są po prostu dodawane. Taka konfiguracja jest stosowana na przykład do łączenia ze sobą efektów oświetlania sceny kilkoma różnymi światłami i nazywa się blendingiem addytywnym.

  • SourceBlend = DestColor; DestBlend = Zero

    Takie dziwne ustawienie wag sprawia z kolei, że zamiast dodawania otrzymujemy w istocie mnożenie przez siebie kolorów – czyli blending multiplikatywny. Istnieje oczywiście jeszcze jedna konfiguracja współczynników dająca ten sam efekt, która jest symetryczna do powyższej.

Powyższe warianty nie są naturalnie wszystkimi możliwymi ani nawet wszystkimi praktycznie wykorzystywanymi. Widać z nich jednak, że tak zwany alpha blending nie służy tylko do przezroczystości i nierzadko wykorzystujemy go również wtedy, gdy wszystkie obiekty naszej sceny nie są ani trochę prześwitujące.

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

Kwantowanie kierunku

2009-03-13 17:20

Wszyscy wiedzą jak, mając dane dwa punkty, wyznaczyć wektor kierunkowy od pierwszego punktu do drugiego. Niekiedy jednak nie chcemy, aby możliwe było uzyskanie dowolnego kierunku. Może tak być np. przy poruszaniu jednostkami na mapie, gdy z jakiegoś powodu chcemy dopuścić, powiedzmy, tylko 8 czy 16 podstawowych kierunków. W jaki sposób należy wtedy “zaokrąglić” nasz dowolny wektor, uzyskany jako różnica aktualnej pozycji jednostki i np. miejsca kliknięcia myszką przez gracza?

Pierwszym możliwym sposobem jest zamiana jego reprezentacji ze współrzędnych prostokątnych (x, y) na biegunowe (r – długość, theta – kąt między dodatnią półosią X a wektorem). Jest to możliwe przy pomocy obecnej w wielu językach funkcji atan2(y, x). Wystarczy potem sprawdzić, któremu wzorcowemu wektorowi jest najbliższy otrzymany kąt.

Swego czasu znalazłem jednak nieco inny sposób, który daje się zastosować bez zmiany reprezentacji wektora. Oryginalnie służył on do wyboru jednego z ośmiu podstawowych kierunków, ale nietrudno było zauważyć, że da się go trochę uogólnić:

  1. VEC2 Quantize(const VEC2 v, int k)
  2. {
  3.     v.Normalize();
  4.     v *= k;
  5.     return VEC2((int)Round(v.x), (int)Round(v.y));
  6. }

Użyta tutaj funkcja Round(t) oznacza zaokrąglenie w stronę najbliższej liczby całkowitej, czyli floor(t + 0.5). Współczynnik k kontroluje natomiast, ile wektorów wzorcowych znajduje się w naszej “róży wiatrów”. Powyższa funkcja dzieli bowiem kąt pełny na dokładnie 2k+2 wycinków, dając tyle też możliwych wektorów wynikowych. Osiem kierunków otrzymamy więc dla k = 1, szesnaście dla k = 2, itd. Teoretycznie możliwe są też ułamkowe wartości współczynnika, co najprawdopodobniej pozwałoby kontrolować “czułość dopasowania” wektora do wzorca. Nie podjąłem się jednak opracowania jakiejś ścisłej zależności :) Jedyne co udało mi się zaobserwować to to, że dla k = 2/3 otrzymujemy dopasowanie do czterech podstawowych kierunków (N, S, W, E).
Ogólnie więc nie jest to może epokowe odkrycie w dziedzinie wektorologii stosowanej, ale istnieje szansa, że komuś do czegoś się przyda ;]

Tags: , ,
Author: Xion, posted under Programming » Comments Off on Kwantowanie kierunku

Koniec pory karmienia

2009-03-06 10:06
Nowy \"nagrobek\" postów
“Nagrobek” postów
po zmianach

Niecały rok temu napisałem tutaj co nieco o tym, dlaczego nie podobają mi się różnego rodzaju “wynalazki statystyczne”, obecnie na forum Warsztatu. Wtedy pomysł usunięcia karmy i licznika postów nie spotkał się z jakimś szerokim poparciem. Pewnie było jeszcze na to za wcześnie. Musiało minąć te kilkanaście miesięcy, żeby pozostali moderatorzy zauważyli w końcu to, że obecność tych śmiesznych cyferek nie powoduje wcale podniesienia jakości forum – wręcz przeciwnie :)

No, ale lepiej późno niż wcale ;> Wczoraj – jako skutek głosowania w gronie moderatorów – zarówno karma, jak i licznik postów zostały usunięte z widoku. Ta pierwsza zniknęła całkowicie, zaś liczbę postów można wciąż obejrzeć w profilu użytkownika. Całkiem rozsądne wyjście, moim skromnym zdaniem.

Tags: ,
Author: Xion, posted under Internet » 5 comments
 


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