Mon
01
Dec 2008

Ucząc się programowania gier każdy w pewnym momencie trafia na techniki podziału przestrzeni. Najczęściej opisywane są drzewa BSP, Octree itp. Tymczasem świat struktur danych - bardziej lub mniej związanych z programowaniem gier - jest bardzo bogaty, różnorodny i ciekawy.

Ot choćby Bloom filter - struktura, która wbrew nazwie nie ma nic wspólnego z popularnym efektem graficznym Bloom, ale służy do przechowywania zbioru elementów i testowania przynależności do zbioru (np. w słownikach sprawdzania pisowni). Ostatnio dowiedziałem się też o istnieniu drzew R-tree (pozdro Robert!), które opisują hierarchię boksów otaczających i działają podobnie do drzew B-tree (stosowanych np. w systemach plików i bazach danych).

Zaimplementować samemu taką strukturę danych na pewno nie jest łatwo, ale warto chociaż poczytać o nich na Wikipedii :)

Comments | #algorithms Share

Comments