Struktury danych w starszych grach

10

Jestem ciekawy struktur danych używanych podczas programowania starszych gier, takich jak Super Mario Brothers dla NES i Super Mario World dla SNES. Rozumiem, że gry z tego okresu zostały napisane w asemblerze. Czy programiści zdefiniowali / wykorzystali jakieś struktury danych?

Na przykład: kiedy na ekranie pojawia się grupa monet, w jaki sposób są one przechowywane? Czy programiści używali tylko tablic? A może mieli połączone listy?

Twoje zdrowie!

Edycja : Interesują mnie różne podejścia ... niekoniecznie uniwersalne.

Edycja 2 : W kilku moich grach stosuję (potencjalnie złe) podejście do kolekcji i chcę wiedzieć, czy którakolwiek ze starszych gier zastosowała podobne podejście. Lubię wykonywać następujące czynności:

// statically allocated arrays (max number of coins is 4)
int coinsXs[4] = {0, 0, 0, 0};
int coinsYs[4] = {0, 0, 0, 0};

// bitset that keeps track of which coins are active
int coinsActive = 0;

// ...

// update the active coins in an update function
for(int i = 0; i < 4; i++){
    if(coinsActive & (1 << i)){
        // update ith coin
    }
 }
data-structure MrDatabase
źródło
2
Nie ma uniwersalnej odpowiedzi; sprowadza się to do tego, jak dany programista zaimplementował rozwiązanie danego problemu.
Ed S.
1
Chociaż nie sądzę, że wszystkie te gry zostały napisane w asemblerze, powiem, że programiści asemblera dość często gromadzili swoje małe komponenty w celu ponownego użycia / skopiowania / wklejenia z programu do programu. Ile razy chciałbyś mimo wszystko napisać funkcję printf ()? :)
James
Słuszna uwaga. Naprawdę ciekawi mnie dynamicznie przydzielane kolekcje kontra kolekcje statycznie przydzielane
MrDatabase
1
Co konkretnego problemu czy ty masz? Dlaczego obchodzi Cię, co robią stare gry?
Tetrad
2
To, co masz w swojej drugiej edycji, to przykład układu „struktury tablic”, który jest powszechny nawet w nowoczesnych grach, ponieważ ma zalety dla równoległości i obsługi SIMD. Kilka lat temu Sony przeprowadziło prezentację na temat tego, w jaki sposób tradycyjny sposób strukturyzacji danych w C ++ może mieć poważne ukryte koszty perf: research.scee.net/files/presentations/gcapaustralia09/…
Crashworks

Odpowiedzi:

13

Nawet w 16-bitowych dniach konsole do gier były po prostu małymi, wbudowanymi komputerami z oprogramowaniem działającym w czasie rzeczywistym, a stosowane przez nas struktury danych są takie same, jakie można znaleźć w informatyce: tablice, macierze, stosy, drzewa. Niewiele list połączonych, ponieważ są one tak wolne (wyszukiwania pośrednie mają długi czas oczekiwania).

Różnica polega na tym, że przed STL i przy tak krytycznej wydajności, zwykle musieliśmy pisać struktury i algorytmy!

David Braben wygłosił fajny wykład na GDC w 2011 r., Gdzie opowiadał o wszystkich szalonych sztuczkach, których używał, aby dopasować Elite do BBC Micro w 1984 r. Możesz go obejrzeć za darmo w GDC Vault .

Crashworks
źródło
Fajne. Czy korzystałeś z tablic alokowanych dynamicznie? A może większość miała rozmiar statyczny? Jestem ciekawy sytuacji, w których, powiedzmy, pięć monet pojawi się na ekranie i pozostanie na ekranie, dopóki gracz ich nie zbierze (lub przewinie poza ekran).
MrDatabase
2
@MrDatabase - Przydziały statyczne tam, gdzie to możliwe. W przypadkach, które opisujesz, często mamy po prostu statycznie przydzielony zestaw np. 32 możliwych monet, które mogłyby istnieć. Gdy na świat przyszły monety, wypełnilibyśmy miejsce w tablicy. Kiedy wyszli, to wymazaliśmy. Alokacja dynamiczna nie była niedostępna, po prostu jej unikaliśmy, ponieważ gdy masz tylko 2 MB pamięci RAM, naprawdę musisz zagwarantować, że Twój program działa w stałej pamięci!
Crashworks,
Fajne. Robię coś podobnego (patrz edycja nr 2 do pytania). W mojej funkcji aktualizacji sprawdzam zestaw bitów „coinsActive”, if(coinsActive)zanim przejdę przez maxNumCoins i zaktualizuję. W ten sposób całkowicie unikam pętli, jeśli zero monet jest aktywnych.
MrDatabase
+1 z powodu linku do GDC Vault. Popolowa rozmowa Petera Molyneux po śmierci musi być najbardziej zabawną, jaką kiedykolwiek widziałem.
TravisG,
MeDataBase - kopiujesz ostatni aktywny obiekt do szczeliny zajmowanej przez monetę, która stała się nieaktywna (tj. Jeśli masz 10 monet, moneta 5 staje się nieaktywna, kopiujesz monetę 10 do szczeliny 5 i zmniejsza liczbę monet) możesz po prostu iterować do numCoins i zaktualizuj wszystkie te elementy. Nie potrzebujesz „jeśli”. Oczywiście działa to tylko wtedy, gdy nieaktywne monety nie muszą utrzymywać stanu i jeśli kolejność aktualizacji nie jest ważna (stan może być utrzymany, jeśli tablica przechowuje wskaźniki do monet, a nie rzeczywistych monet, ale wtedy zachowuje się rozproszone buforowanie, które jest prawdopodobnie gorsze niż „jeśli”)
Kaj
5

Oto interesująca dyskusja na GameDev.net dotycząca kodu źródłowego Super Mario Bros: kod źródłowy Super Mario

pek
źródło