Sunday, November 27, 2011

GameMaker - multi-dimensional arrays

As you may know, GameMaker natively supports only 2-dimensional arrays with size up to 32000x32000.
However, in some cases, you may want to use arrays with 3 (or more) dimensions.
Small comparison table with descriptions below:

Stat\Method array:offset array:instance ds_grid's ds_map
Init (fill-up) Slow Slow Fast Slowest
Access (i/o) Fast Fast Average Average
Size limit ~109 cells 32k/dimension Resizable No
Index Integer Integer Integer String
Existance check No No Not needed Yes
Region operations No No Yes Only clearing
References No Partial (layer) Yes Yes

Methods:

array:offset

Often used in languages that only support one-dimensional arrays, is based on storing several dimensions in a single one.
cell = array[z * y_size + y][x]
So, the primary restrictions that you are going to have with this method are fixed size for all but two dimensions, and lack of error handling. One could note that there is a limit on max cell count, however it is not significant - 109 cells are already 2Gb of data (assuming that they are stored next to each-other in double precision floating point format) - if you have a feeling that you may exceed that limit, think again.

array:instance

This method is a 'call' to very relative object oriented programming that exists in GameMaker. Concept is simple - you cannot store array in a array, but you can perfectly store instance in a array. So why not just make ones that would serve a single purpose of storing sub-arrays?
// Initialization
for (k = 0; k < zsize; k += 1) {
    layer = instance_create(0, 0, obj_array)
    array[k] = layer
    // Sub-init for layer itself:
    for (i = 0; i < xsize; i += 1)
    for (j = 0; j < ysize; j += 1)
    layer.array[i, j] = 0
}
Advantages of this method are less strict array limits (32000 per dimension) and ability to pass reference to specific array 'layer'. Disavantage is in having additional dummy instances.

ds_grid's / ds_list's

Setting up multi-dimensional array with this method is relatively easy - you create a ds_grid (or ds_list), and store it in other one of these.
// read
value = ds_grid_get(ds_list_find_value(array, z), x, y)
// write
ds_grid_set(ds_list_find_value(array, z), x, y, value)
As advantage, list and grid functions become available, which allow faster manipulations over array contents. Primary disadvantage is need for a complex array disposal function.

ds_map

String-based key gives ds_map slight advantage over other methods in methods of storing data - you can have a cell at (0, 0, 0) and few thousands points away without filling everything between. As well it grants ability to store negative indexes, which is hard to manage with other data structures. Access to values is done via composed index (normally coordinates with delimeters between them).
// read
value = ds_map_find_value(map, string(x) + ';' + string(y) + ';' + string(z))
// write
adress = string(x) + ';' + string(y) + ';' + string(z)
if (ds_map_exists(map, adress))
then ds_map_replace(map, adress, value)
else ds_map_add(map, adress, value)
Advantage of this method is practially no limitation in array size or coordinate spread. Dis-advantages are problematic enumeration (to get all items on specific depth, program must cycle through all items), and slightly slower access speed.

If I am mistaken somewhere, feel free to leave a comment.

No comments:

Post a Comment