10
\$\begingroup\$

I'm curious about the data structures used when programming older games like Super Mario Brothers for NES and Super Mario World for SNES. My understanding is that games of this period were written in assembly. Did the programmers define/use any data structures?

For example: when a group of coins appears on the screen how are they stored? Did the programmers just use arrays? Or perhaps they had linked-lists?

Cheers!

Edit: I'm interested in various approaches... not necessarily a universal approach.

Edit 2: In a few of my games I use a (potentially bad) approach towards collections and I want to know if any of the older games used a similar approach. I like to do the following:

// 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
    }
 }
Improve this question
\$\endgroup\$
7
  • 2
    \$\begingroup\$ There is no universal answer; it comes down to how a given programmer implemented the solution for a given problem. \$\endgroup\$
    – Ed S.
    Aug 19, 2011 at 22:00
  • 1
    \$\begingroup\$ While I do not think all of those games were written in assembly, I will say it was fairly common for assembly programmers to collect their small components for copy/paste reuse from program to program. How many times would you want to write the printf() function afterall? :) \$\endgroup\$
    – James
    Aug 20, 2011 at 0:10
  • \$\begingroup\$ Good point. I'm really curious about dynamically allocated collections vs statically allocated collections \$\endgroup\$
    – MrDatabase
    Aug 20, 2011 at 0:12
  • 1
    \$\begingroup\$ What specific problem do you have? Why do you care what old games do? \$\endgroup\$
    – Tetrad
    Aug 20, 2011 at 0:43
  • 2
    \$\begingroup\$ What you've got in your second edit is an example of a "structure of arrays" layout, which remains common even in modern games as it has benefits for parallelism and SIMD operation. Sony did a presentation a couple of years ago on how the traditional C++ way of structuring data can have serious hidden perf costs: research.scee.net/files/presentations/gcapaustralia09/… \$\endgroup\$
    – Crashworks
    Aug 20, 2011 at 3:07

2 Answers 2

Reset to default
13
\$\begingroup\$

Even in the 16-bit days, game consoles were basically just small, embedded computers running realtime software, and the data structures we used are the same ones you'd find anywhere in computer science: arrays, matrices, heaps, trees. Not many linked lists because they're so slow (indirect lookups have a long latency).

The difference is that before the STL, and with performance so critical, we usually had to write the structures and algorithms ourselves!

David Braben did a fun lecture at the 2011 GDC where he talked about all the crazy tricks he used to fit Elite onto a BBC Micro in 1984. You can watch it for free at the GDC Vault.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Cool. Did you use dynamically allocated arrays? Or did most have a static size? I'm curious about situations where, say, five coins would appear on-screen and remain on-screen until the player collected them (or they scrolled off-screen). \$\endgroup\$
    – MrDatabase
    Aug 20, 2011 at 0:02
  • 2
    \$\begingroup\$ @MrDatabase - Static allocations wherever possible. For cases like you describe, we'd often just have a statically allocated array of eg 32 possible coins that could exist. When coins came into the world, we'd fill a spot in the array. When they left, we'd blank out it. Dynamic allocation wasn't unavailable, we just avoided using it because when you've only got 2MB of RAM you really need to guarantee your program runs in constant memory! \$\endgroup\$
    – Crashworks
    Aug 20, 2011 at 0:16
  • \$\begingroup\$ Cool. I do something similar (see edit #2 to the question). In my update function I check the "coinsActive" bitset if(coinsActive) before I loop over maxNumCoins and update. This way I completely avoid the loop if zero coins are active. \$\endgroup\$
    – MrDatabase
    Aug 20, 2011 at 0:54
  • \$\begingroup\$ +1 because of the GDC Vault link. The postmortem Popolous talk by Peter Molyneux must be the most hilarious talk I've ever seen. \$\endgroup\$
    – TravisG
    Aug 20, 2011 at 1:29
  • \$\begingroup\$ MeDataBase - you copy the last active object to the slot that was occupied by a coin that became inactive (ie, if you have 10 coins, coin 5 becomes inactive, copy coin 10 to slot 5 and decrease numactive coins) you can just iterate up to numCoins and update all those elements. You wouldn't need the 'if'. Of course this only works if inactive coins don't need to maintain state and if order of update is not important (the state could be maintained if the array stores pointers to coins and not actual coins, but then you get scattered cache behaviour which is likely worse than the 'if') \$\endgroup\$
    – Kaj
    Aug 20, 2011 at 23:04
5
\$\begingroup\$

Here is an interesting discussion on GameDev.net for the Super Mario Bros source code: Super Mario source code

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .