Home > SoulHow > SoulHow to use data structures

SoulHow to use data structures

September 13, 2008

NOTE: Comments are locked. I no longer answer questions about the Game Maker tutorials on this blog; I suggest you take any questions to the Game Maker Community. For more info, view the FAQ page.

Skill Level: Experienced User (6)

I told you it was coming. The data structure soulhow article. We’re up over 8000 hits, thanks to you, so I figured it was a great time to write another article.

So what are data structures? Well first, before I go any further, I’d like to redirect you to the arrays soulhow article if you haven’t read it yet and don’t already know what an array is. The reason is that data structures are just special types of arrays.

Sadly, this is a pro-only feature. So if you have lite, GO GET PRO and come back.

Back yet? Great. Let’s go.

First of all, let’s look at the types of data structures. We have stacks, queues, lists, maps, grids, and priorities. They all sound different, strange, and foreign, like they would growl and claw at you if you ever got locked in a cage with one of them. But in reality, they are nothing more than arrays which function in “different” ways, and have more controls and power. I will say that they won’t always be the best option; but in most cases where you have a lot of data to store in a specific way under a single name, data structures are the way to go.

To get a data structure, you must first choose which type you want and then call the appropriate ds_*_create() function. Note that “ds” stands for “data structure” (if you didn’t already pick up that one), and the * should be replaced with whatever type of structure you want. When you use this function, it returns an integer which is the id of the data structure that is used to mess with it later on. You MUST catch this return value in a variable, or else you won’t be able to use it later. For example:

mylist=ds_list_create();

Okay, I think we skipped something. We know how to create a data structure, but I haven’t covered how to choose which one to use. Here’s a list of the data structures and their attributes:

Stacks:
Stacks are a data structure considered FILO – that’s First In Last Out. So whatever you have most recently put into it, will be spit out when you retrieve from it. Imagine a deck of cards; whatever you put on the top of the deck, is what will come off when you draw from the deck. If you put the numbers 2, 5, and 6 on the stack (called “pushing”), then when you get the numbers back from the stack (called “popping”; this will return the top value in the stack AND remove it completely), they will be returned in the order 6, 5, 2. (the functions ds_stack_push() and ds_stack_pop() are used to push and pop values on and off ds_stack’s; there will be an actual example further down)

Queues:
Queues can be considered somewhat of an inverse of stacks. They are of the type FIFO. That, as you might have guessed through wizardry, is First In First Out, which means whatever you put in first will come out first when you draw from the queue. Imagine a line of people outside the movie theatre box office. The first one in the line is the first one to get tickets and then leave the line. So 2, 5, and 6 put in the queue (called enqueueing) will come out (called dequeueing; again, this will both return AND remove the item longest in the queue/person who’s at the front of the movie theatre line) in just that order – 2, 5, then 6. (amazeringly, ds_queue_enqueue() and ds_queue_dequeue() are used to enqueue and dequeue items from a ds_queue)

Lists:
Lists can be thought of as stacks and queues put together, sprinkled with a little magic pixie dust. Items added into a list, remain in that order, but a programmer can draw out any value at any point in the list, without having to go FILO or FIFO. There is a whole horde of functions built in to GM that deal with messing around with these special lists, including ds_list_add() and ds_list_delete(), which do the obvious. Check up on the GM manual for the rest and their exact uses. There is even a ds_list_shuffle() function, which completely randomizes the order of the items in the ds_list. Great for card games!

Maps:
Maps are different from stacks, queues, and lists, in one important way: their format. Whereas the former three are only a number of values arranged in some way, etc., maps actually store what are called key-value pairs. This means everything is stored in the format “key=value”; thus the map data structure is organized according to keys, and not FIFO, FILO, etc. Here’s a representation of a ds_map:

“MyHealth”=100
“EnemyHealth”=59
“MP”=30
“NumOfMonsters”=32
“PlayerName”=”Martin”
“OMG”=”LOL”
“1234”=1234
1234=9820

All of the above key-value pairs are valid. Keys and values both can be either numbers or strings. Use ds_map_add() to put a key-value pair in the ds_map, and use the many other functions to mess around with it.

Grids:
Whereas the other data structures were more or less dynamic forms of one-dimensional arrays, the grid is simply a supercool form of a two-dimensional array. In case you don’t know what a two-dimensional array is, imagine a chess board. The squares are all separate indexes of one array. When using a two-dimensional array in code, it looks like this:

myarray[7,7]=0;

The first number is the size of a column, and the second number is the size of a row. A chess board is 8 squares by 8 squares, and that’s why we used an array size of 7,7 (remember, array indexes start at 0). So assuming we’re playing as white in the game of chess, the black queen would be at array index [0,3], the black queen’s rook would be at [0,0], and the black king’s knight would be at [0,6]. The black pawns would be at each index in the row of [1,0] (e.g. [1,0], [1,1], [1,2], etc.).

So grids are just a two-dimensional array, once again with some special functions to help you work more easily.

There are a few things to note here, however. First, when using a ds_grid, as opposed to a two-dimensional array, you will have to use ds_grid_create(). In this function, you specify the width and height of the grid; however, these should be actual width and height values. So to get a ds_grid to represent a chessboard, we would write, “ds_grid_create(8,8);” not 7,7. The indexes still begin at 0, however, so when retrieving i.e. the top left cell of the grid would still be retrieved by calling “ds_grid_get(0,0)”.

Next, to set the value of an index in a grid, you must use ds_grid_set(), not ds_grid_add(). The latter will actually add whatever value you give to whatever is already in the particular cell, rather than exchanging it.

Priorities:
ds_priorities are essentially ds_maps but with a set value type – an integer which represents an item’s priority. Imagine a doctor’s office; there may be many patients, but the ones with worse illnesses must be accepted before those there only for a mere checkup. The more sick any particular patient is, the higher priority is given to them. Then the doctor’s office arranges them according to this priority and chooses the one that is highest.

ds_priorities are the same. I have never personally used a ds_priority, but there are many ways to use it. Maybe you’re making a strategy game and you need to rank the possible moves the A.I. can make before it chooses the best (or knocks off the best to decrease the difficulty – see here for a good example). You can use various ds_priority functions to get the values with the highest and lowest priorities, values with a specific priority, etc.

*exhales* Whew, that was kind of a lot. About 1250 words up to this point.

Okay, now that you know about the kinds of data structures and the functions that do stuff with them, there is one more thing to cover. That is how to use the functions; meaning, programmatically. There is generally always an argument in all data structure functions named “id”. This is the id that you caught in the variable when calling ds_*_create(). For example:

mylist=ds_list_create();
ds_list_add(mylist,3);

ds_list_add()’s format is ds_list_add(id,value). There’s that id argument; we plug in mylist, which gets the id of our newly created list when ds_list_create() is called, and then GM knows that we’re working with that particular list, not one that you may have i.e. created earlier.

Well that’s it. I hope you learned something useful, and remember feedback is always welcome. Good luck guys.

If you enjoyed this article, please consider checking out the rest of the blog.

If you have a technical question, such as “How do I do this” or “this is not working right” (relative to something with your Game Maker game after reading this tutorial), please head over to the Game Maker Community and ask there.  I can’t answer any such questions in this blog and the members at the GMC will be more than capable to help you.  For more info, go to this blog’s FAQ page.

Advertisements
%d bloggers like this: