Tag: algorithms

Entries for tag "algorithms", ordered from most recent. Entry count: 68.

Uwaga! Informacje na tej stronie mają ponad 6 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

Pages: 1 ... 6 7 8 9

# Architektura całej gry

Fri
27
Jul 2007

Architektura całej gry, choć nie o nią mi w obecnej chwili chodzi, przewija się w literaturze którą obecnie analizują i też mnie interesuje. Szczególnie, że ilekroć staję przed tym zadaniem, zawsze mój kod zamienia się w jedną wielką kulę błota, w której wszystko korzysta ze wszystkiego beztrosko rzutując klasy w dół hierarchii dziedziczenia. Ciekawy wątek forum na ten temat jest TUTAJ.

Wyczytałem właśnie, że architekturę gry można podzielić na:

Wielowarstwowa, w której kod podzielony jest na warstwy, a każda z nich korzysta tylko z warstw niższych i oferuje pewne usługi dla warstw wyższych, o których nic nie wie.
Z centralną bazą danych (repozytorium), która przechowuje wszystkie dane gry i do której odwołują się niezależne od siebie podsystemy np. grafiki, dźwięku czy fizyki.
Z niezależnymi komponentami, które komunikują się między sobą wyłącznie za pomocą przesyłania jakiś określonych komunikatów.

Wprowadzanie takich podziałów wydaje się trochę na siłę, szczególnie że można tu wymyślić jeszcze dużo innych opcji. Gdzieś kiedyś na forum pisali nawet o takiej, w której każdy obiekt gry posiadać ma swoje pod-obiekty odpowiedzialne za grafikę, dźwięk, fizykę itd. Tylko czy coraz większe komplikowanie rozwiązuje ten i tak skomplikowany problem? :)

Comments | #algorithms Share

# XNL2 do kosza

Thu
12
Jul 2007

Wymyśliłem kiedyś język opisu XNL2 i wiem, że kilku osobom nawet się spodobał. Teraz doszedłem do wniosku, że był oparty na błędnych założeniach i w związku z tym ogłaszam koniec "dorabiania ideologii do tokenizera", jak to jeden mój kolega kiedyś trafnie skwitował.

Zachęcam, by zamiast używać XNL2 czy innych takich wynalazków albo pisać coś w tym rodzaju samemu, skorzystać z modułu Tokenizer z mojej biblioteki CommonLib 6.1 (zobacz też online nagłówek i dokumentację). Jest dużo lepiej przemyślany, prostszy w użyciu, a co najważniejsze - parsuje język przypominający tokeny C/C++, a więc z takimi komentarzami i łańcuchami znaków, do jakich jesteśmy przyzwyczajeni. Taki tokenizer może być dobrą bazą do szybkiego zaprojektowania i zaimplementowania własnego języka opisu.

Comments | #libraries #productions #algorithms Share

# Nigdy nie ufaj optymalizacji kompilatora

Sat
30
Jun 2007

Xion widząc kod mojej biblioteki CommonLib zarzucił mi dzisiaj, że niepotrzebnie przesyłam wszelkie zwracane przez funkcje obiekty większe niż pojedyncza liczba (jak wektor, macierz czy string) przez parametr wskaźnikowy nie ufając optymalizacji kompilatora (nazwał to RVO - Return Value Optimization). Zrobiłem więc na szybko prosty test na przykładzie stringów i wyniki potwierdziły mój pogląd, żeby nigdy nie ufać optymalizacjom kompilatora. Zobacz kod i wyniki: TestNieoptymalizacjiKompilatora.cpp.

Może dożyję czasów, kiedy kompilatory C++ (albo lepiej - jakiegoś nowocześniejszego języka) pozwolą napisać po prostu return wektor * macierz1 * macierz2 albo return string1 + string2, a to zostanie zamienione na taki kod maszynowy, jaki napisałby dobry programista posługujący się bezpośrednio liczbami float albo łańcuchami char*. Przykład kompilatorów HLSL i Cg pokazuje, że da się...

Comments | #c++ #algorithms Share

# Napisałem FreeList

Thu
31
May 2007

Napisałem na podstawie artykułów z "Game Programming Gems" (oraz swoich pomysłów) własne alokatory pamięci do obiektów konkretnego typu, czyli tzw. FreeList. Powinny działać szybciej niż standardowe, podobno wolne operatory new i delete. Znajdą się oczywiście w nowej wersji mojej biblioteki CommonLib. Testy (przeprowadzone dla 10240 operacji alokacji lub zwalniania) są bardzo optymistyczne:

DEBUG:
Element typu int:
  FreeList : 68.0636 ms
  DynamicFreeList : 184.441 ms
  new i delete : 78.8142 ms
Element typu zajmujacego 1024 bajty:
  FreeList : 69.3896 ms
  DynamicFreeList : 203.506 ms
  new i delete : 93.2942 ms
RELEASE:
Element typu int:
  FreeList : 7.87224 ms
  DynamicFreeList : 11.4786 ms
  new i delete : 17.0348 ms
Element typu zajmujacego 1024 bajty:
  FreeList : 9.18059 ms
  DynamicFreeList : 18.0729 ms
  new i delete : 24.0537 ms

Comments | #c++ #algorithms Share

# Policy-Based Design

Wed
30
May 2007

class DeletePolicy {
public:
  template <typename T>
  static void Destroy(T *p) { delete p; }
};
class ReleasePolicy {
public:
  template <typename T>
  static void Destroy(T *p) { if (p) p->Release(); }
};

class scoped_ptr<typename T, typename PolicyT = DeletePolicy>
{
public:
  explicit scoped_ptr(T *p = NULL) : m_Ptr(p) { }
  ~scoped_ptr() { PolicyT::template Destroy<T>(m_Ptr); }
  // ...
};

scoped_ptr<int, DeletePolicy> p1;
scoped_ptr<IDirect3DTexture9, ReleasePolicy> t1;

To przykład techniki zwanej Policy-Based Design, którą wynalazł Andrei Alexandrescu. Wszystkich zainteresowanych zabawami z językiem C++ zachęcam do zgłębiania tematu. Szablony to nie jest lekarstwo na wszystkie (jakże liczne) problemy rodzące się podczas programowania w tym języku, ale to jedna z potężnych i zaawansowanych technik. Znałem ją już wcześniej, ale teraz doceniłem i użyłem. Jak to się mówi w komentarzach na Allegro: Polecam! :)

Comments | #c++ #algorithms Share

# Pytanie o inteligentne wskaźniki

Mon
28
May 2007

Chcę sobie napisać tzw. inteligentne wskaźniki (po to żeby, przyznaję, uwolnić się od biblioteki Boost :) W związku z tym będę wdzięczny każdemu kto potrafi i znajdzie chwilę żeby odpowiedzieć na moje pytanie z tym związane w odpowiednim wątku forum.

Comments | #c++ #algorithms Share

# IntToStr, StrToInt

Fri
25
May 2007

Na dobry koniec dnia wyniki pomiaru wydajności moich nowych funkcji do konwersji między liczbą a łańcuchem - porównane z funkcjami systemowymi (plus konwersje do std::string, bo takich łańcuchów wszędzie używam i takich używają te moje funkcje). Wyniki w mikrosekundach na pojedyncze wywołanie, już podzielone przez liczbę wykonanych iteracji.

- DEBUG
  - int > string
    itoa : 0.244895 us
    IntToStr (stary) : 3.20974 us
    IntToStr (nowy) : 0.659205 us
  - string > int
    atoi : 0.270027 us
    StrToInt : 0.391424 us
- RELEASE
  - int > string
    itoa : 0.137373 us
    IntToStr (stary) : 0.225465 us
    IntToStr (nowy) : 0.134297 us
  - string > int
    atoi : 0.0785857 us
    StrToInt : 0.0589072 us

Comments | #c++ #algorithms Share

# Signed czy unsigned

Fri
25
May 2007

Czy do zapisywania rozmiaru danych, liczby bajtów, liczby elementów albo indeksu lepiej stosować liczbę całkowitą ze znakiem, czy bez znaku? Liczby ze znakiem są standardem w Delphi i mają wielu zwolenników dzięki swoim zaletom: Indeksy ujemne, jako niepoprawne, można stosować do oznaczenia wartości specjalnej (np. -1). Nie ma też obawy o "przekręcenie" przy zliczaniu w dół.

Ja jestem jednak zwolennikiem podejścia obowiązującego w C++, czyli stosowania typu bez znaku tam gdzie to możliwe (np. pod nazwą: unsigned, size_t, DWORD czy mój własny uint4). Zaleta tego podejścia to m.in. dwa razy większy dostępny zakres. Nie trzeba też sprawdzać poprawności liczby od dołu - wystarczy od góry. Jako wartości specjalnej można używać 0xFFFFFFFF (taką wartość ma na przykład stała std::string::npos zwracana przez std::string::find kiedy nic nie znaleziono).

Co wtedy z przechodzeniem tablicy w dół? Sposobem na to jest tzw. Pętla Tarlandila (tak sobie ją nazywam, bo nauczył mnie jej Tarlandil):

for (size_t i = RozmiarTablicy; i--; )
{
  Tablica[i] = 0;
}

Jak chcesz to przeanalizuj dokładnie jak działa ta sprytna pętla, a jeśli nie, to uwierz na słowo że ona naprawdę przechodzi tablicę w dół od elementu ostatniego do pierwszego i nie straszne jej przekręcenie się liczby bez znaku poniżej zera :)

Comments | #c++ #philosophy #algorithms Share

Pages: 1 ... 6 7 8 9