Introduction to C++ with Game Development: Part 13, Data Structures

Introduction

If you got here in good shape, you learned a lot: you went though the basics of C programming, and got a taste of object-oriented programming as well. In the meantime, you experimented with quite a few game-related concepts. In the second half of the tutorial series you will further expand your knowledge, with more info on bit magic, file I/O, graphics programming and game development in general. But first we will conclude this half. Let's get acquainted with the wonderful world of data structures.

The problem with arrays

Article 10 introduced you to arrays. These allow you to store a list of values:

int x[10], y[10];
float speed[10];

Obviously, you can conquer the world with arrays alone. However, sometimes they are not the most efficient solution to a problem. To illustrate this, let's start with a small game of snake.

int x[8] = { 5, 6, 7, 8, 9, 10, 11, 12 };
int y[8] = { 8, 8, 8, 8, 8, 8, 8, 8 };
int heading = 0;
void Game::Tick( float a_DT )
{
	m_Screen->Clear( 0 );
	for ( int i = 0; i < 7; i++ )
	{
		x[i] = x[i + 1];
		y[i] = y[i + 1];
		m_Screen->Box( x[i] * 8, y[i] * 8, x[i] * 8 + 6, y[i] * 8 + 6, 0xffffff );
	}
	if (heading == 0) x[7]++;
	if (heading == 1) y[7]++;
	if (heading == 2) x[7]--;
	if (heading == 3) y[7]--;
	if (GetAsyncKeyState( VK_LEFT )) heading = (heading + 3) % 4;
	if (GetAsyncKeyState( VK_RIGHT )) heading = (heading + 1) % 4;
	Sleep( 100 );
}

That's pretty short, isn't it? I do think it requires some explanation though. The snake is represented by 8 squares, stored in arrays. Element 0 is the tail; 7 is the head of the snake. To move the snake forward, a heading is used: 0 is east, 1 is south, 2 is west and 3 is north. The snake thus starts by moving east. To do so, we first move up the snake one position: every square of the snake moves to the position of the square that is one part closer to the head. And finally the head is placed on a new position, based on the current heading. The heading is controlled by the player, using to GetAsyncKeyState commands.

This code is using arrays to store the snake. At first this appears to be a logical choice, until you start thinking big: what happens when the snake is hundreds of blocks long? Are you really going to copy every element to the next? That appears to be inefficient, because most of the snake is stationary: Only the head and the tail moves. The rest of the sliding snake body is merely suggested.

So what if...

Imagine this: rather than starting our array at 0 (tail) and ending it at 7 (head), we start at a random position. When the tail is at 0, the head is at 7. But when the tail is at 1, the head is at 0. And when the tail is at 2, the head is at 1. So, to get to the tail, you take the head, and proceed one element. If that takes you beyond the length of the array, you wrap around to 0.

Now why would you want to do that? Well... It saves you work! Or rather, it saves your computer work. Because, if your snake's tail was located at 0, and the head at 7, you could move the whole thing by making it start at 1. Like this:

All you need to do after this is setting he head at the correct new location, because this is now the only element with a wrong position: it's located where the tail was in the previous situation.

The code, with the modification:

int x[8] = { 5, 6, 7, 8, 9, 10, 11, 12 };
int y[8] = { 8, 8, 8, 8, 8, 8, 8, 8 };
int heading = 0, head = 7, tail = 0;
void Game::Tick( float a_DT )
{
	m_Screen->Clear( 0 );
	for ( int i = 0; i < 8; i++ )
	{
		m_Screen->Box( x[i]*8, y[i]*8, x[i]*8 + 6, y[i]*8 + 6, 0xffffff );
	}
	int headx = x[head];
	int heady = y[head];
	if (heading == 0) headx++;
	if (heading == 1) heady++;
	if (heading == 2) headx--;
	if (heading == 3) heady--;
	tail = (tail + 1) % 8;
	head = (head + 1) % 8;
	x[head] = headx;
	y[head] = heady;
	if (GetAsyncKeyState( VK_LEFT )) heading = (heading + 3) % 4;
	if (GetAsyncKeyState( VK_RIGHT )) heading = (heading + 1) % 4;
	Sleep( 100 );
}

So is this better? The code grew a few lines, is incomprehensible, and not noticeably faster. Well, the answer is: yes. Instead of copying all the elements of the array to the next element, we do nothing. The only reason that for loop is still there is the fact that we still need to draw the snake. Or...do we?

Data structures

This was a small example of a smart trick to reduce the amount of work that your computer has to do. There are data structures for many things: for huge arrays that have just a few useful values, for searching though endless piles of values, for stacking values so that you can retrieve them in the opposite order, and so on. Often, a data structure is the key to game performance. You've just added the first of many to your arsenal.

Assignment

  1. Get rid of the for loop altogether. Just paint the tail in black, and the head at the new position. Note: you will not want to clear the screen for every frame.
  2. Add food (blue square) at position 20, 15. When the snake 'eats' it, let the snake grow, and put new food at position 4, 4.

Comments

Commenting will be coming soon. In the meantime, feel free to create a discussion topic on the forums.