[Tutorial] Variables, Arrays, Hash Tables - An Overview

I hope this overview helps starters understanding some of the logic behind all those terms.

I. Bits, bytes and memory

What is this:

0

1

2

3

4

A bunch of numbers, you say? Well, yes, but the computer doesn't care about the type of data, internally everything (a number, a letter, a sound, a color, ...) is represented by switches that have the state 'on' or 'off', and all those switches together are called RAM (Random Access Memory). Such a switch is called a 'bit', and the states are referred to as the bit being set or not set. One bit represents 2 states, which is rather limiting. We could say, that the bit not set stands for the number 0 and the bit set for the number 1. But how would we then represent the number 2 or 3 or 4, etc?

The answer is: by combining several bits. This grouping of bits is so essential, that there are names for all kinds of grouped bits. For example, the combination of 8 bits is called 'byte', the first 4 bits of such a byte are called 'low nibble', the other 4 are called 'high nibble'. To differentiate between those 8 bits of a byte, every bit is given a "weight", a unique valence based on the position of a bit within a byte. The power of two valency fits prefectly, because every bit represents two states.

8 7 6 5 4 3 2 1 position of the bit
7 6 5 4 3 2 1 0 the power of two represented by the bit if set[/code:1e7v91ps]

To represent 0, we just don't set any bit:
00000000
To represent 1, we set the first bit, because 2^0 = 1:
0000000X
To represent 2, well, you guess:
000000X0
3 is represented by setting bit 1 and bit 2, that's 2^0 + 2^1 = 3:
000000XX

Now that we grouped bits to represent numbers, how do we tell the processor, what number we want to access? By giving every byte an address, the place (or position), where in our RAM the byte is stored. But it would be very annoying to keep all those addresses in mind. We replace those addresses with something that we can use more naturally.

[b]II. Constants and variables[/b]

When we type '1 + 2', then we are typing two numbers, right? No, we type two addresses. Fortunately they lead the processor to the place in memory, where the numbers 1 and 2 are stored. Isn't that clever? So, the address '1' always leads to the same place in memory, where the number 1 is stored, this will never change. [i]An address that is used this way is called a 'constant'.[/i]

myNumber = 1
myNumber = 2
What is happening here? We reserved a place in memory for our own use and gave the address a name we can remember: 'myNumber'. Then we ordered to copy the content of the constant '1' to our address. But in the next line we copy the content of the constant '2' to our address. The content of 'myNumber' changes. [i]An address that is used that way is called a 'variable'.[/i]

Constants and variables are the base of programming. The number of hearts collected in a game changes as we play, so we use a variable. The speed of a car changes as we play: variable. But what, if we need to keep track of the speeds of 100 cars? We could create 100 variables and give them names like 'car1', 'car2', etc. But that is a very tedious task. Luckily, there's a shortcut.

[b]III. Arrays[/b]

We need 100 variables, but they all refer to the same aspect in our game, in this case the speed of the cars. Wouldn't it be much easier to enumerate the cars while accessing all of the variables with the same name? We would know, that speed(1) refers to the speed of the first car, while speed(2) refers to the second car, etc. That's the purpose of an array. It is grouping a greater number of variables and knows their addresses, and the array itself also has an address. When we access the address of the array, 'speed', together with an index, '(1)', the array looks for the variable at the address that is stored at the index.

[i]You should use an array, whenever you need to manage a lot of variables for the same purpose.[/i] You make an oldschool adventure with a parser understanding hundreds of words? Use an array to store those words! You have a map editor to place different objects on fixed positions? Use an array!

As good as arrays are, there is a disadvantage. Imagine another task filling our array with data. Worst of all, it fills the array differently everytime. For example, the cars only add their speeds to the array, if a certain value is reached. Now car 5 may be the first one to store its speed, car 9 the second one, etc. If we then access speed(1), we simply don't know to what car this speed variable belongs to. Don't worry, a solution to our problem is already existent.

[b]IV. Hash tables[/b]

To know exactly what variable refers to the car's speed we are interested in, we need something unique to identify it. We could use simple variables again, but that would make our project very complex. Also we have still a group of variables representing the same aspect, the speeds of the cars. Something like "speed('car1')" instead of "speed(1)" would help a lot here.

But what is speed('car1')? Nothing more than an address to an address to a variable. With this indirect addressing it isn't important anymore, at what exact positions the speeds are stored. The address of the speed of the first car may be stored at index 1 or at index 5, we access it by a name and the functionality behind it finds the right index to our name. That's what a hash table does. [i]Think of a hash table as an array with a clever index aliasing on top.[/i]

The name we use is called a 'key'. This key will always lead us to the correct variable, no matter where exactly it is stored in the array.

You should use a hash table whenever you have to manage a lot of variables representing the same aspect of something with changing count or content and still need to access them quickly.

I would love to see some comments here, although it might seem like something not worth answering.

I often try to help and invest some time in it. Writing in english makes it even more time consuming. So feedback, if something like that is helpful or not needed, would point me to the right direction.

nice tutorial, I didn't have much time so I just read the Hash Tables part. It would be very helpful if you could show the usage of Hash tables using some construct examples, if you plan to continue this tutorial.

Thanks

Thank you for the tut, I didn't have time on the weekend to comment it so I'm doing it now.

Part 1 to 3 - it's good you're also writing about basics. I've already known the stuff, but I like to refresh my memory and it's good for begginers. There is only one thing, you're using advanced terms in the text. Parsing is one I remember.

Part 4 - I think I understand it, but not completly. Probably cap would help. Why should I use hash over normal array. In your example I would give every car a private variable and use normal array and than compare it's variable with array's position. I think with hash array I wouldn't need to use that private variable. That would make it easier, but I would like to see it how to it's set up and used.

nice tutorial, I didn't have much time so I just read the Hash Tables part. It would be very helpful if you could show the usage of Hash tables using some construct examples, if you plan to continue this tutorial.

Thanks

Thank you for the tut, I didn't have time on the weekend to comment it so I'm doing it now.

Part 1 to 3 - it's good you're also writing about basics. I've already known the stuff, but I like to refresh my memory and it's good for begginers. There is only one thing, you're using advanced terms in the text. Parsing is one I remember.

Part 4 - I think I understand it, but not completly. Probably cap would help. Why should I use hash over normal array. In your example I would give every car a private variable and use normal array and than compare it's variable with array's position. I think with hash array I wouldn't need to use that private variable. That would make it easier, but I would like to see it how to it's set up and used.

Thank you both for commenting. I will try to avoid advanced terms unless I explained them. And I will do an example, comparing arrays to hash tables to show when one or the other makes more sense.

Here we go again. This time I have made a rather simple example cap, showing one scope of application for both, arrays and hash tables, and setting them side by side, to compare them and see, where they are of advantage.

NEW VERSION (19.02.2011):

Array_Hash.cap

You may want to first download the cap and then switch back and forth between Construct and this post.

I. Array

I.1 Demands

The base for the example is a map editor. Imagine you want to create one for your game. It is tile-based, so you know the exact dimensions of the map and you know the tile dimensions. In this example the map has 256x256px, and the tiles have 64x64px. That's a map size of 4x4 in tiles.

You might want to have a little variation for the tiles as well. In this example, every tile has 4 animation frames, which can be freely selected.

Now we need to manage and save the informations. The easiest way is to save the frame number of a tile to its position expressed in tiles. That does give the advantage that we could later change the size of the tiles without affecting the map layout. This is a perfect job for an array.

I.2 Effect

Run the cap now and click on 'Array'. You will see a red-colored area. Use the mouse wheel to change the animation frame of the tiles. When satisfied, click on 'menu' and then on 'Save array'. Click 'menu' again and select 'Main menu' this time. Click 'Array' again. You will notice that your map is automatically loaded. Change some frames and select 'Load array'. It is reverted to its last saved state.

I.3 Cause

Have a look at the event sheet of the layout 'Array'. Open the group 'Array'.

Event 21 and its subevents are initializing the array. First it is set to 4 in x-dimension and 4 in y-dimension. Then every "cell" of the array (16 in total) is set to the value 1. This is needed, because the first animation frame is 1, but the array is initialized to 0. The next event loads a saved array file, if there is one. This is just a convenience. The last subevent loops through the map and creates the 4x4 tiles.

Event 26 and its subevents changes the frames of the tiles and updates the array with the new frame numbers.

Open the group 'Menu'. Events 16 and 19 take care of loading and saving the array. When loading, it is needed to loop through all tiles and set the frame number to the one stored in the array.

For all accessing of array "cells", some simple math is used to get the tile position. The map starts at (0, 32), a tile has a size of 64x64 and its hotspot is centered. Therefore the tile at array value {1, 1} is located at (32, 64) in pixel values. With (mapobject.X - 32) / 64 + 1 we get (0) / 64 + 1 = 1, and with (mapobject.Y - 64) / 64 + 1 its 1 again, as expected. The tile at array value {3, 4} is located at (160, 256). Just try the math above with that pixel values, you will get the correct tile position. You just need to substract all offsets from the origin, then divide by the tile's size and add 1, to shift the range from [0, 3] to [1, 4].

II. Hash Table

II.1 Demands

Again the base for this example is a map editor. But in difference to the first example it now is object-based. A map object can be placed anywhere on the map, not just on a grid, and it can be deleted or moved. The map size still is 256x256px, and the map objects have a size of 64x64px. And all objects also have the same variations as in the first example.

To manage and save the informations, we need something to store the coordinates of an object and its animation frame, and those informations may change at any time, or the object may even be deleted. Using an array as we did in the first example is not very effective. First, we would need to make it have 256x256 cells, even if we only place one object in the map. Second, everytime an object is moved we sould need to clear one cell and set another. Third, if two objects are placed at the same coordinates we couldn't store the informations for the second one, the cell is already used for the first one.

It is much better to have an object-oriented approach. This is a good (but not perfect) job for a hash table.

II.2 Effect

Run the cap now and click on 'Hash Table'. You will see the empty map area and some text in the upper left. This text will keep you informed over your objects. Left-click anywhere on the map to create an object. Hold the shift-key and click and hold the left mouse button over an object to change its position. Right-click over an object to delete it. Use the mouse wheel when over an object to change its animation frame. When satisfied, click on 'menu' and then on 'Save hash table'. Click on 'menu' again and select 'Main menu'. Click 'Hash Table' again. Click on 'menu' and select 'Load hash table'. Your last saved map is restored.

II.3 Cause

Have a look at the event sheet of the layout 'Hash Table'. Open the group 'Hash Table'.

Event 23 initializes the hash table by inserting the key 'pid' with the value 0. Event 32 creates a new map object, sets the object's pid to the value of the hash table's 'pid', raises the hash table's 'pid' by 1 and inserts a new key into the hash table. This key represents the new object and it has the following structure:

key = object's pid, value = a string in the form objectXxobjectY;animationframe (e.g. "128x64;3")

Event 28 moves an object to a new position. The value of the key that corresponds to the object's pid is set to the new position, by just creating a string from the coordinates and the frame number again.

Event 29 deletes an object and the key that corresponds to the object's pid.

Events 30 and 31 change the animation frame of an object and sets the value of the corresponding key to a string created from the coordinates and the frame number again.

Open the group 'Menu'. Event 16 and its subevents take care of loading and creating the map from a file. If there is no file, the content of the hash table keeps its current state, else it is replaced by the data from the file. Either way, all objects on the map are deleted. We then loop through every key that is not named "pid" and create an object based on the string value of the key. The coordinates and the frame number are retrieved using GetToken, which returns a substring of a string by interpreting a given letter as a delimiter. For the coordinates the delimiter is "x" and for the frame number the delimiter is ";". See the comment in event 20 for more information.

I'm working on other examples for hash table use, so check this thread from time to time.

I'll download it and read it later, but I thought I'd thank you in advance. It looks very detailed.

I added this thread to my favorites,

I have no programming experience, so I found these tutorials very helpful.

Thank you for taking the time to do this.

Thank you for the comments, really appreciate it

Unfortunately, I uploaded the wrong version, which was calculating the positions wrong in the array example. I updated the link, to the (hopefully) correct version. I'm terribly sorry

I just finished your tutorial. Finally, I can say I understand a hash array . I've never knew why should I use hash over normal array, but here it's nice and clear example.

I have one little thing, could you comment(explain) conditional action for mouse wheel up event? I've never used it and wiki expressions example makes me more confused.

EDIT:nevermind - found a good explanation here

last post on the first page

As promised, here is another example using hash tables. This time I present one possible way of supporting multi-language-games. The languages are stored in hash tables sharing the same keys. Furthermore, the use of a hash table to randomly select items, while every item is only selected once, is shown here.

Most of the time people will use a system similar to this:

1) Generate a random number

2) Compare it with the previously generated random number

3) If they match, repeat from step 1

4) Finally after millions of repetitions, the numbers don't match and stuff can be done

The hash table approach doesn't need that, as every key that was used is deleted from the hash table, and the random number is always generated based on the number of keys left.

The .rar file contains a cap and three language files (aka saved hash tables) and the events of the cap are extensively commented.

Download:

LanguageExample.rar

I hope it is a useful example

Thank you, it's well commented. I'll read it when I get home.