Contents of this blog

Contents

---

Below you'll find a list of all the tutorials with a list of part and a short description of each part.

Game programming in SDL2

---

A tutorial about making games. Focuses a lot on SDL 2, but also other topics related to game programming. Some parts are pretty extensive so that you'll get a deeper understanding about what's going on.

Part 1 - Setting up SDL 2

---

This part gives you a quick introduction to SDL 2. It'll help you set up SDL2 including header files, linking and everything you need to get SDL 2 up and running. It also contains a bare-boned SDL2 program.

Part 2 - Your first SDL 2 application

---

Here we take a look at the two basic structs of SDL 2, SDL_Window and SDL_Renderer. It'll help you understand what these do and how to initialize them and the basics of SDL2 correctly. We also take a look at how to set the render color ( which also works as background color )

Part 3 - Drawing rectangles

---

Here we take a look at SDL_Rect and how to render it with SDL_RenderDrawRect and SDL_RenderFillRect.

Part 4 - Making things happen

---

About events in SDL 2. How to get the events, how the event structure, SDL_Event laid out, and how we do we handle the event.

Part 5 - Collision detection and our first game!

---

We learn how to check for collisions and make a simple game out of it.

Part 6 - Let's load some textures!

---

In this part we take a look at SDL_Textures and how to create them from image files ( bmp. ) We also look at how to render SDL_Textures.

Part 7 - Using PNG files

---

We look at, and set up, SDL_Image library. This is used to load png files which then can be rendered with the transparency layer.

Part 8 - It's TIME for another update!

---

Here we look at a new rendering function, SDL_RenderCopyEx. The function lets us render textures rotated. We use it to make a simple analog clock.

Part 9 - No more delays!

---

Up until now we've used SDL_Delay to limit framerate to ~16 FPS. We look at how to render using a delta time.

Part 10 - Text Rendering

---

Text rendering in games can be tricky. Luckily, SDL2_TTF does this for us. This part talks about SDL2_TTF, how to set it up and how to use it.

C++11 Features

---

A series about the new features of C++11. I will try to explain everything thoroughly and extensively. The goal is to learn about C++11, how the various parts of it works and why you should use them.

I will cover both minor features like enum classes and larger ones like chrono

Part 1 - Enum classes

---

This is a very short part about the new version of enums, enum classes. It covers what they are and why you should use them as much as possible

Part 2 - Timing with chrono

---

This part is very extensive and covers the new timing features of C++11, chrono. It will help you when you're dealing with timing in games and other applications.

My SDL2 Tutorial part 9 ( No more delays! ) also deals with chron but this part covers it more extensively.

Part 3 - Smart pointers in C++11

---

About smart pointers in C++11 ( unique_ptr, shared_ptr and weak_ptr ) what they are, how they work and how to use them. You should always use smart pointers unless you have a really good to.

[ Data structures - Part 2 ] Stack

Stacks

---

Last time, we learnt about vectors. This time we're gonna learn about stacks. Stacks are extremely important in understanding how your code runs. hIt's used both for storing y our local variables and for making sure your functions run in the right order. Recursive method heavily rely on stacks.

The stack ADT

---

Stacks asr ad ADTs this basically says it's a data type with certain operations you can perform on it. But ADTs does not have any specific implementation, you can implement it any way you like.

Supported operations

---

The following operations are typical for stacks

• Push
• Pushes and element on the top of a stack
• Pop
• Removes the top element of the stack
• Note that this doesn't return the top element.
• Top
• Returns the top element of the stack.

An example

---

Imagine you have a stack of plates. The plates are all of the same plates, but some have different motives. It is your jobs to sort them into new stacks where depending on the motives of the plates. So you look at the top plate ( top() ) and decide which of the sorted stacks it belongs onto. When you have decided it belongs in stack 1 ( as an example ), you remove it from the stack ( pop() ) and put it onto stack 1 ( push() ). You look at the next one ( top() ) it belongs in stack 2 so you remove it ( pop() ) from the unsorted stack and place it on stack 2 ( push() ).

This goes on and on. Always looking ( top() ) and remove ( pop() ) the top element and placing it ( push() ) on the top of the correct stack. You can't look at or remove any of the elements below the top one, so you're always working with the top one. This is how a stack works. Always insert and remove at the top. The elements below the top are irrelevant until they are the top elements themselves.

Usage

---

Stacks have a lot of usage in the world of computers. Every time you write a function, you are dealing with stack. Every time you do an if or loop ( for, while ) you are dealing with a stack. So let's take a look at how that works.


void Function()
{
    int value = 5;
    int someValue = 19375;


    if ( value == 5 )
    {
        int otherValue = 3;]
    }

    while ( value !=10 )
    {
        int someValue = value;

        int something1 = 0;
        int something2 = 0;

       value = someValue + 1;
    }
}


Here's what happen when you enter Function().

Step 1:

---

The variable value and someValue will be added to the stack.

The stack is now

• someValue
• value

Step 2:

---

We enter a new block { so we add a mark to show this

The stack is now

• {
• someValue
• value

Step 3:

---

We find a new variable, otherValue, and add it t the stack

The stack is now

• otherValue
• { 
• someValue
• value

Step 4:

---

So now we are leaving the current block. The current block was the one that started in step 2.
So now we need to delete the variables we added in the current block ( they are now out of scope )

We do this by doing the following look at the top element :

• The element is not a {
• Pop it and go check all the next element.
• If the element is a {
• We have deleted ( popped ) all elements that belonged to this scope so we pop the { and return. Now we have deleted all the elements and can continue.

 So let's do this step by step

• } - The end of the scope, pop it and continue
  
• otherValue1 - A variable in the scope. Pop it and continue
  
• { - The { signaling the beginning of the scope. Pop it and return
  
• someValue
• value

 In the end, our stack looks like this :

• someValue
• value

Step 5:

---

Now we have come to the loop in our function. Here we declare the variable someValue. Wait? Isn't that what the other variable is called? Yes, it is. But it's in a different scope so the compiler knows that when you someValue within this scope, you are referring to the variable declared in this scope. Let's add the { and someValue to the stack.

This is what we end up with :

• }
• something2 
• something1
• someValue - The one in the loop, value is same as value
• {
• someValue - The original one, declared at the top. Its value is 19375
• value

Step 6:

---

The loop goes out of scope, and someValue is deleted. Only to be recreated as we re-enter the loop. This time value is one more than last time.

The order in which the items will be deleted is the opposite of the order they were inserted. So : something2, then something1 and finally someValue.

Next we go to 5, value will be one more, but otherwise exactly the same will happen all the way until value is 10, in which case we continue to the last step.

Step 7:

---

Now the entire function is done. All that is left of the stack is

• someValue
• value

So we pop of the top variable, someValue. Now we're left with the first variable we created, value. We pop that of too. Now the entire stack is empty and we return from the function.

Conclusion

---

Stacks are limited in what they can do. But they are also very easy to implement and understand. They are also extremely useful in some cases ( as we have just seen. )

I hope to update this post soon with more information about the implementation of the object in STL, std::stack.

---

Feel free to comment if you have anything to say or ask questions if anything is unclear. I always appreciate getting comments.

For a full list of my tutorials / posts, click here.

[Data structures - Part 1] Vector

Introduction

---

In this series I will be talking about the major data structures, what operations they support and how to implement it. It is intended mainly as a way for me to learn these things better, but I also hope it will be of use to someone.

At the same time I will try to describe the functionality of the various classes in the STL.

Let's start with one of the most basic one, vector.

ADTs

---

Vectors are ADTs ( Abstract Data Type ) This means it's not a concrete data type like ints, pointers, arrays, etc... An ADT is just a data structure with no specific implementation. It could be implemented as an array, but it could also be implemented as a linked list ( I'll write a post on this later. In simplicity, it's just a container where each element has a pointer to the next one. )

An ADT has a specific set of operations that can be performed on it. On a vector, you can add an item to the back( push ), remove the element in the back ( pop ) or read a random element. In most implementations, vectors are implemented as an array because it's way simpler and more efficient. But you could implement it as a linked list if you wanted to.

The Vector ADT

---

Vectors are one of the most important structures. According to Bjarne Stroustrup

If you know vector and int, you know C++

While this is not entirely true, vectors are very useful, and very fast.
Vector is an array-like container. It's very useful for storing data, and it's particularly focused on adding/removing elements from the back.

Vectors are focused around adding and removing elements to the end of the vector. But it also supports random access, so it will work as a regular array in many cases.

Vector is a good choice if you need to store a list of object and you intend to add items as you go along. As long as you add/delete at the end, vectors are very fast. Adding and removing at the end is O( 1 )

Supported operations

---

The following functions are typical to a vector:

• Push Back
• Insert at the end
• Pop
• Remove last element
• Back
• Access last element
• operator[ ]
• Access a specified element

Implementation

---

The random access functionality of a vector is why it's usually implemented using an array. And when using an array, the items are laid out consecutively in memory. This means that, if element 0 is at pos x, then element 1 is at position x + size, where size is the size of one element. And the CPU works VERY efficiently when the memory is laid out like this. And that is one of the major reasons it's so widely used.

And this is one of vectors shortcomings. Because when extending a vector, you usually need to move all elements to a different place in memory. And since your vector can potentially hold millions of elements, this might take some time.

Luckily though, this is one of the areas the CPU excels. It's incredible effective when it comes to working on consecutive blocks of memory. So in a lot of cases, the overhead of increasing the capacity of a vector is not so bad.

Data members

---

The following are the data members a standard vector needs to have. Note: these are intended to show the basic member of a vector. The members below are not the same as the ones in std::vector, they're just intended used as an example.

Type[] data

---

The array that holds all the data. It contains all elements in the vector. The memory for the object is dynamically allocated with new, since a vector needs to be able to grow.

unsigned int size

---

The number of elements in the vector. Note: this is not the same as capacity of the vector. The size of a vector is just how many elements are in the vector right now. It is equivalent to the length of a string.

unsigned int capacity

---

How many items the vector can currently store. This number will always be as large, or larger, than the size of a vector.

Size vs capacity

---

Every time you insert an item, the vector needs to check whether it is equal to the capacity of the vector. If it is, the vector is full and the capacity needs to be increased. This also means new space have to be allocated and the elements has to be moved. See reserve further down for details.

Inserting

---

When it comes to insertions, there are a few cases to consider

Inserting at the end ( index = size of vector )

---

Say you have a vector of 11 elements. The first element is at index 0, the las one at index 10. Inserting an element to the back ( index 11 ) means you have to do the following:

1. Insert the item at the next empty position ( 11 )
2. Increase the size by 1

Done!

Inserting in a differend position

---

Now let's assume you have the same vector as before ( 11 elements ) and you want to add an element at index 5 :

1. Take all elements from index 5 to 10 ( the last element ) and move them back one position ( increasing index by 1 ). The last item will now be at index 11 and the position 5 will be empty
2. Now you can insert the item into position 5
3. Increase the size  by one

The function might have to move a lot of elements. But this isn't a huge worry since CPU's work very efficiently on consecutive blocks of memory like arrays and vectors.

Functions in std::vector

---

These are all the supported functions of std::vector you find in the C++ STL ( Standard Template Library. ) This section does not contain the algorithms like std::find(), I will cover these later.

Push Back

---

The basic insertion algorithm, it adds an element to the end of the vector. It will also increment the size by one. If the current capacity of the vector is too small to fit this element, the capacity will be extended. See the point Reserve( int ) for more info.

Reserve

---

This function increases the capacity of the vector. The function will do the following :

1. Allocate a new, larger, chunk of memory.
2. Copy all elements to this chunk of memory
3. Deallocate the old chunk of memory

If you try to reserve more than the theoretical limit of the vector ( see Max Size ), and exception of the type std::length_error will be thrown.

A few notes :

• The function might have to move a lot of elements.
• In most cases this isn't a huge concert since CPU's are very efficient at this.
• If you are constantly inserting a lot of elements, this function might get called automatically a lot. 
• To prevent this, you can call Reserve() with a large value so that the size never grows beyond the capacity so that the capacity won't have to be extended.
• You can't use this function to shrink the capacity.
• If you call this function with a value smaller than the current capacity nothing will happen.
• You can use ShrinkToFit() to decrease the capacity ( see below. )

Shrink To Fit

---

Will reduce memory usage by freeing unused memory. Since it deallocates all unused memory ( all elements after size - 1 ), capacity will be set to the same as size. If you try to PushBack or Insert an item after calling this method, Reserve() will be called.

Back

---

Simply returns the last element.

Front

---

Simply returns the first element.

operator [int]

---

Returns the element specified the brackets[]. Does NOT perform any bounds checking. If you specify a number below 0, or equal to or more than size. The function returns a reference, so this function can be used to change the element in the vector.

At( int )

---

Just like the [], this returns the elements specified in the function argument. But unlike the [] operator this function performs bounds checking. If you specify an index out of bonds, an exception of the type std::out_of_range is thrown.Just like [], function returns a reference, so this function can be used to change the element in the vector.

So why use the brackets[]?

---

While at() is technically safer, there is also a little overhead in performing the bounds checking. [] can potentially be run in just in one clock cycle.

My general rule of thumb is to use [] in your code. If you check and test your code properly, stepping out of bounds should not be a risk.

Empty

---

Returns true if the vector is empty, otherwise false.

Size

---

Returns the number of elements currently in the vector.

Capacity

---

The number of items the vector has allocated space for. If this is equal to the sixe, the vector needs to be expanded ( see Reserve() above. )

Data

---

Returns the underlying data of the vector.

Max Size

---

Returns the the maximum theoretical capacity of the vector, meaning the maximum number of elements the vector can hold using all avaialbe memory.Note : this is not the capacity of the vector.

When size reaches capacity

---

So when the size reaches the same value as capacity, the capacity of the vector needs to be extended. Usually this is checked whenever an element is inserted and the function Reserve( int ) will be called.

Illustration

---

Here is a simple illustration of a vector.

It demonstrates insert ( both at the back and any other position, ) and remove. It also shows back element ( last element in the vector, ) size ( how many items that are in the vector ) and capacity ( how many items is there room for. )

This code is meant as a base for later parts where I will show various sorting algorithms. You can find the code here.


=========================

A container we'll look at later, linked list solves the problem of capacity limitations.

---

Feel free to comment if you have anything to say or ask questions if anything is unclear. I always appreciate getting comments.

For a full list of my tutorials / posts, click here.