Game Maker Games, Articles, Tutorials & More

Print

Implementing 3D Arrays

By Daniel · January 5, 2009

>> Download Example <<

Although GM doesn't provide native support for 3D arrays, there are numerous ways of simulating them. The standard technique is to "flatten" the three dimensions by converting three indices into one:

array[ a, b, c ] => array[ a*bLimit*cLimit + b*cLimit + c ]

The multipliers in the code ensure that each (a, b, c) combination gets a unique one-dimensional index. This method is suitable for some purposes, but the strict size limitations are often confining. GM places a limit of 32,000 on each array index, so aLimit*bLimit*cLimit cannot exceed 32,000. If the three limits are equal (which is typically the case), this means that each index has a limit of |_32,000^1/3_| = 31. Hence you can simulate a 31x31x31 array using this approach.

For more space, you can store data in 2D arrays instead of 1D arrays. Remember that GM places a limit of 32,000 on each index, so a 2D array can potentially hold 32,000² = 1,024,000,000 values. The simple, standard approach looks like this:

array[ a, b, c ] => array[ a, b*cLimit + c ]

This is sometimes adequate, but the capacity of each dimension is imbalanced. The A dimension has a limit of 32,000, while B and C have a limit of |_32,000^1/2_| = 178, which is too low for most purposes.

So how can we convert three indices into two in a way that preserves this balance between dimensions (or allows us to choose the limits with more flexibility)? Well, we can expand one index into two using the following technique, which is essentially the reverse of flattening:

array[ i ] => array[ i div dimL, i mod dimL ]

Here dimL is the limit on each dimension; in our case we use 32,000. So to convert three indices into two, we can simply combine the 3-to-1 technique with the 1-to-2 technique:

array[ a, b, c ] => array[ (a*bLimit*cLimit + b*cLimit + c) div 32000, (a*bLimit*cLimit + b*cLimit + c) mod 32000 ]

Now if we make the three limits equal, the limit on each dimension will be |_32,000^2/3_| = 1,007. Hence we can simulate 1,007x1,007x1,007 arrays, which can be quite useful. We can also choose other limits on each dimension, as long as aLimit*bLimit*cLimit does not exceed 32,000² -- so you could simulate a 2,000x1,000x512 array, for example. You can also use this technique to simulate n-dimensional arrays -- just add additional terms following the same pattern.

The code used to reduce three indices to two is admittedly somewhat sophisticated, so I'd recommend making two scripts for the two resulting indices. In the example, I named them "idx1" and "idx2". Once you have this, the conversion can be simplified to this:

array[ a, b, c ] => array[ idx1(a, b, c), idx2(a, b, c) ]

So you can read and write to 3D arrays like this:

array[ idx1(a, b, c), idx2(a, b, c) ] = <value>;

Included is a simple example showing how these ideas can be implemented. For simplicity, I gave each dimension a limit of 1,000 (even though only the maximum is 1,007, and only 4 is needed).

Happy flattening,
~ Daniel

Categories: Data processing

Comments

There are no comments to display.

Post a Comment

You must be signed in to post comments.

Advertisement