C++ Game Engine Development – Part 14 – Drawing Sort Order

This is part of an ongoing series where we write a complete 2D game engine in C++ and SFML. A new tutorial is released every Monday. You can find the complete list of tutorials here and download the source code from the projects GitHub page.
In this tutorial, we will create a drawing system and start preparing for our collision system. To do this we need to make a few changes to our tilemap parser. We will be creating an additional layer within Tiled that will include only the tiles that we want our player to collide with. Currently we have rudimentary support for multiple layers, however, we only support the one tileset (the image containing our tiles). We’ll want to change this as we will be using different tile sets for different layers. For more information on what Tiled is and how we are using it in our game, you can read the previous tutorial. Also, we currently have no way of specifying the order that sprites are drawn to the screen, so even when we add another tile layer it will not appear in the correct order. At the moment they are drawn in the order we add them to the ObjectCollection, which is not ideal; so we’ll add support for setting a sort order for our drawable components. We’ll then use this to draw our collision layer on top of our platform layer.
There’s a lot to get done this week so let’s start by opening Tiled and creating a new layer called Collisions. I’ve Imported a new tileset which is just a red square. You can use any tiles you want for this layer as eventually we will not be drawing them. I’ve chosen red sprite as it provides a contrast with our current map so it is obvious which tiles are collision tiles and which are not. Place the collision tiles on a new layer called ‘Collisions’ and wherever you want the player to collide with the environment. The name of the layer is important as you’ll see shortly.
Collision layer in red.
Once done you can save and close Tiled. I’ve updated the map in the folder for this tutorial so you can use that if you would like.
As the layer uses a new tileset, before we can import this layer in our game, we need to add support for multiple tilesets. This will involve making a few changes to our TileMapParser class. We’ll start by creating a new TileSheets alias.
TileMapParser.hpp
using TileSheets = std::map<int, std::shared_ptr<TileSheetData>>;
TileSheets is a map of integers and a shared pointer to TileSheetData. The integer represents the starting id of the images in the tileset, I’ll explain this in more detail shortly when we get to implementation.
We’ll also need to update our BuildSheetData and BuildLayer function declarations so that they return and receive our new TileSheets.
TileMapParser.hpp
…
	std::shared_ptr<TileSheets> BuildTileSheetData(xml_node<>* rootNode);

	std::pair<std::string, std::shared_ptr<Layer>> 
	BuildLayer(xml_node<>* layerNode, std::shared_ptr<TileSheets> tileSheets);
…
BuildSheetData now returns a pointer to our newly created TileSheets rather than a singular TileSheetData and BuildLayer accepts TileSheets as a parameter instead of a singular tileset, as each layer may have tiles from multiple tile sheets.
With the declarations modified its time to update the function bodies. BuildSheetData requires the biggest change as it is responsible for building the data structures for our tilesets.
TileMapParser.cpp
std::shared_ptr<TileSheets> 
TileMapParser::BuildTileSheetData(xml_node<> *rootNode)
{
    TileSheets tileSheets;
    
    for (xml_node<> * tilesheetNode 
		 = rootNode->first_node("tileset"); 
		 tilesheetNode; 
		 tilesheetNode = tilesheetNode->next_sibling("tileset"))
    {
        TileSheetData tileSheetData;
        
        int firstid 
			= std::atoi(tilesheetNode->first_attribute("firstgid")->value());
        
		tileSheetData.tileSize.x 
			= std::atoi(tilesheetNode->first_attribute("tilewidth")->value());
        
		tileSheetData.tileSize.y 
			= std::atoi(tilesheetNode->first_attribute("tileheight")->value());
        
		int tileCount 
			= std::atoi(tilesheetNode->first_attribute("tilecount")->value());
        
		tileSheetData.
			columns = std::atoi(
				tilesheetNode->first_attribute("columns")->value()
			);
        
		tileSheetData.rows = tileCount / tileSheetData.columns;
        
        xml_node<>* imageNode = tilesheetNode->first_node("image");
        tileSheetData.textureId 
			= textureAllocator.Add(
				std::string(imageNode->first_attribute("source")->value()));
        
        tileSheetData.imageSize.x
			= std::atoi(imageNode->first_attribute("width")->value());
        tileSheetData.imageSize.y 
			= std::atoi(imageNode->first_attribute("height")->value());
        
		// We store the tile sheets firstid.
        tileSheets.insert(
			std::make_pair(
			firstid, std::make_shared<TileSheetData>(tileSheetData))
		); 
        
    }
    
    return std::make_shared<TileSheets>(tileSheets);
}
We now loop through nodes with the name ‘tileset’ and then do the usual process of building the TileSheetData for that node. This is then added to our new map of tilesets. We use the id of the first tile in the tileset as the key. For example, if the first tileset we add has 4 tiles, its id will be 0 (we start the index at 0) and when we add the next tile set, its first id will be 4.
Tile maps with ids.
Tile maps with ids.

With that done your IDE of choice (if you use one that is) should be having an issue with the BuildMapTiles function because we have not yet updated the return parameter when we call our newly updated BuildSheetData function. We’ll fix that now.

TileMapParser.cpp
std::shared_ptr<MapTiles> TileMapParser::BuildMapTiles(xml_node<>* rootNode)
{
	// We change the return type for our BuildSheetData function.
    std::shared_ptr<TileSheets> tileSheetData = BuildTileSheetData(rootNode);
…
}
The last change we need to make in our parser is in the BuildLayer function. Now that it accepts multiple tilesets, we first need to find which tileset it belongs to before we can set a tiles texture information.
TileMapParser.cpp
std::pair<std::string, std::shared_ptr<Layer>> 
TileMapParser::BuildLayer(xml_node<>* layerNode, 
						  std::shared_ptr<TileSheets> tileSheets)
{
…
        
	int tileId = std::stoi(substr);
        
	if (tileId != 0)
	{
		auto itr = tileSet.find(tileId); 
		if (itr == tileSet.end())
		{
			std::shared_ptr<TileSheetData> tileSheet;
                
			for (auto iter = tileSheets->rbegin(); 
				 iter != tileSheets->rend(); ++iter) // 1
			{
				if(tileId >= iter->first) // 2
				{
					// We know the tile belongs to this tileset.
					tileSheet = iter->second;
					break;
				}
			}
                
			if(!tileSheet) // 3
			{
				//TODO: output error message.
				continue;
			}
			
			...
		}
		...
	}
   …
}
  1. We loop through the tilesets in reverse order as the tilesets are added with the tile ids in ascending order.
  2. If the tile id is greater than or equal to the key we know that the tile belongs to this tileset as we are iterating over the tileset in reverse order.
  3. If no tileset is found we skip this tile. This should not happen and we will want to add additional logging here.
Once we have the tileset we can create the tile data the same way we did before.

And that’s it for our parser! We can now use multiple tilesets however if you run the game you will probably not see the new layer. This is because we have not created a method of drawing sprites in a certain order as currently they are drawn in the order we add them to the object collection.

You can set a sort order for sprite renderers in Unity.
You can set a sort order for sprite renderers in Unity.

To accomplish this we’ll need to create a drawable component and a drawable system. As you’ll remember from previous tutorials, a component is what we use to extend objects functionality and a system will control the components. This is the beginning of a conversion to a true Entity Component System model that we discussed here. Although we’re not converting completely (yet) as components in an ECS are purely data objects and our components will still do some processing i.e. drawing the sprites.

We’ll start with creating the component, C_Drawable.
C_Drawable.hpp
#ifndef C_Drawable_hpp
#define C_Drawable_hpp

#include <SFML/Graphics.hpp>

#include "Window.hpp"

class C_Drawable
{
public:
    C_Drawable();
    virtual ~C_Drawable();
    
    virtual void Draw(Window& window) = 0;
    
    void SetSortOrder(int order);
    int GetSortOrder() const;
    
private:
    int sortOrder;
};

#endif /* C_Drawable_hpp */
C_Drawable.cpp
#include "C_Drawable.hpp"

C_Drawable::C_Drawable() : sortOrder(0){}

C_Drawable::~C_Drawable(){}

void C_Drawable::SetSortOrder(int order)
{
    sortOrder = order;
}

int C_Drawable::GetSortOrder() const
{
    return sortOrder;
}
This allows us to set and retrieve an integer that we use to sort our sprites before drawing. Draw is a pure virtual function, as this will be the parent class of any component that requires drawing and should not be instantiated. All components that will draw to the window will inherit from this class. This includes our sprite component, so let’s change that now.
C_Sprite.hpp
#include "C_Drawable.hpp"

// We now inherit from C_Drawable.
class C_Sprite : public Component, public C_Drawable
…
The sprite component is the only component we currently have that draws to the window so it is the only one we need to change.
As we will soon have a separate system for drawing we can remove the Draw function from our Component class. So the new Component class looks like this:
Component.hpp
#ifndef Component_hpp
#define Component_hpp

#include "Window.hpp"

class Object;

class Component
{
public:
    Component(Object* owner) : owner(owner){}
    
    virtual void Awake() {};
    virtual void Start() {};
    
    virtual void Update(float deltaTime) {};
    virtual void LateUpdate(float deltaTime) {};
    // Deleted draw method

    Object* owner;
};

#endif /* Component_hpp */
To draw objects we will need to modify our Object class. First, we add a pointer to a drawable component as a member variable and then we modify our AddComponent function so that we check if the new component inherits from C_Drawable, if it does then we set our drawable member variable to point to this component.
Object.hpp
class Object
{
public:
…
    
    template <typename T> std::shared_ptr<T> AddComponent()
    {
        static_assert(
			std::is_base_of<Component, T>::value, "T must derive from Component"
		);
        
        //TODO: allow us to add more than one component, implement getcomponents
        // Check that we don't already have a component of this type.
        for (auto& exisitingComponent : components)
        {
            if (std::dynamic_pointer_cast<T>(exisitingComponent))
            {
                return std::dynamic_pointer_cast<T>(exisitingComponent);
            }
        }
        
        std::shared_ptr<T> newComponent = std::make_shared<T>(this);
        
        components.push_back(newComponent);
        
		// We now check if the component is a drawable.
        if (std::dynamic_pointer_cast<C_Drawable>(newComponent))
        {
            drawable = std::dynamic_pointer_cast<C_Drawable>(newComponent);
        }
        
        return newComponent;
    };
     
    std::shared_ptr<C_Drawable> GetDrawable();
    
…
    
private:
…
    std::shared_ptr<C_Drawable> drawable;
};
I’ve also added a GetDrawable method that returns a reference to our drawable component.
Object.cpp
std::shared_ptr<C_Drawable> Object::GetDrawable()
{
    return drawable;
}
The last change we’ll make in the Object class is to have our draw method call our drawable component rather than looping through every attached component. We could check to see if the drawable component is not a nulptr before calling its draw function but this will be handled when we create our drawing system.
Object.cpp
void Object::Draw(Window& window)
{
    drawable->Draw(window);
}
We are currently limited to one drawable per object at the moment as it simplifies our drawing system but we’ll be expanding this in future.
Now with our drawable component complete, we’ll create the drawable system which I’ve called S_Drawable. I prepend S_ to the class name to show that it is a system, feel free to disregard this naming convention and name the class whatever you want.
S_Drawable.hpp
#ifndef S_Drawable_hpp
#define S_Drawable_hpp

#include <map>

#include "C_Drawable.hpp"
#include "Object.hpp"

class S_Drawable
{
public:
    void Add(std::vector<std::shared_ptr<Object>>& object);
    
    void ProcessRemovals();
    
    void Draw(Window& window);
    
private:
    void Add(std::shared_ptr<Object> object);
    void Sort();
    
    std::vector<std::shared_ptr<Object>> drawables;
    
};

#endif /* S_Drawable_hpp */
ObjectCollection and our drawing system manage separate collections that contain similar objects (with S_Drawable containing a subset of all objects as it only stores objects with a drawable component). Doing this allows us to store, and sort the data in different ways depending on the needs of each system. For example, if we only maintained the one collection and sorted it by draw order, then when it came to implementing our collision system having the objects sorted by draw order is of little use. Using a separate collection for collisions allows us to store the objects into different zones to minimise the number of collision checks we perform (more on that in a when we start our collision system). However, there are a number of disadvantages: firstly we have to manage these collections separately, when we remove an object from the ObjectCollection we expect it to be removed from the game so we’ll have to check all other systems and ensure it is removed from their collections too. Also, it uses additional memory for each collection, however as they are all pointers to objects we’ve minimised this disadvantage.
We’ll start the implementation with the Add function. Its role is to check to see if the object has a drawable component and if it does it is added to this systems collection. Once the vector of new objects has been processed we sort the collection based on the sort order of its drawable component with lower sort orders appearing at the beginning of the collection and higher sort orders at the end of the collection.
S_Drawable.cpp
#include "S_Drawable.hpp"

void S_Drawable::Add(std::vector<std::shared_ptr<Object>>& objects)
{
    for (auto o : objects)
    {
        Add(o);
    }
    
    Sort();
}

void S_Drawable::Add(std::shared_ptr<Object> object)
{
    std::shared_ptr<C_Drawable> draw = object->GetDrawable();
    
    if (draw)
    {
        drawables.emplace_back(object);
    }
}

void S_Drawable::Sort()
{
    std::sort(
		drawables.begin(), drawables.end(), 
		[](std::shared_ptr<Object> a, std::shared_ptr<Object> b) -> bool
		{
			return a->GetDrawable()->GetSortOrder() 
					< b->GetDrawable()->GetSortOrder();
		}
	);
}
By sorting the objects in this way, when it comes to drawing them, we can simply loop through the collection from beginning to end, call the objects draw method and they are drawn in the correct order.
S_Drawable.cpp
void S_Drawable::Draw(Window& window)
{
    for (auto& d : drawables)
    {
        d->Draw(window);
    }
}
As I mentioned earlier when we remove objects from the main ObjectCollection we also want to remove objects from this system so we have to have a ProcessRemovals function.
S_Drawable.cpp
void S_Drawable::ProcessRemovals()
{
    auto objIterator = drawables.begin();
    while (objIterator != drawables.end())
    {
        auto obj = *objIterator;
        
        if (obj->IsQueuedForRemoval())
        {
            objIterator = drawables.erase(objIterator);
        }
        else
        {
            ++objIterator;
        }
    }
}
This works in the exact same way as it does in ObjectCollection. Talking of ObjectCollection, we need to make a few changes there to use our new drawable system. First, we create a drawable member variable.
ObjectCollection.hpp
#include "S_Drawable.hpp"

class ObjectCollection
{
…
    
private:
…
    S_Drawable drawables;
};
ObjectCollection.cpp
void ObjectCollection::ProcessNewObjects()
{
    if (newObjects.size() > 0)
    {
        for (const auto& o : newObjects)
        {
            o->Awake();
        }
        
        for (const auto& o : newObjects)
        {
            o->Start();
        }
       
        objects.insert(objects.end(), newObjects.begin(), newObjects.end());
        
        drawables.Add(newObjects); // New Line.

        newObjects.clear();
    }
}
We also have to call the ProcessRemovals function on our new system.
ObjectCollection.cpp
void ObjectCollection::ProcessRemovals()
{
    auto objIterator = objects.begin();
    while (objIterator != objects.end())
    {
        auto obj = *objIterator;
        
        if (obj->IsQueuedForRemoval())
        {
            objIterator = objects.erase(objIterator);
        }
        else
        {
            ++objIterator;
        }
    }
    
    drawables.ProcessRemovals(); // New Line.
}
And lastly, rather than loop through every object in the Draw function, we now just call our drawing systems which draws the objects in the correct order.
ObjectCollection.cpp
void ObjectCollection::Draw(Window& window)
{
    drawables.Draw(window);
}
This is everything we need to do for the moment to be able to set the sort order of sprites. To test it we can set a tiles sort order in our TileMapParser based on the layer they are on. We’ll do this in the Parse method.
TileMapParser.cpp
std::vector<std::shared_ptr<Object>> 
TileMapParser::Parse(const std::string& file, sf::Vector2i offset)
{
   …
    // Add new layer count variable. Set it to the maximum number of layers.
    int layerCount = tiles->size() - 1;
    
    for (const auto& layer : *tiles)
    {
        for (const auto& tile : *layer.second)
        {
       …
            auto sprite = tileObject->AddComponent<C_Sprite>();
 			…
			// We set the sort order for the tile based on its layer.
            sprite->SetSortOrder(layerCount);
        		…
        }
        // Decrement layer count.
        layerCount--;
    }
    
    return tileObjects;
}
We set the sprite sort order in reverse because that is how it is drawn in Tiled. The layers first in the list are drawn on top of subsequent layers.
Now when you run the game you’ll see that our new collision layer is drawn on top of our platform layer. Great!
Our collision layer is now drawn.
That’s all for this week. As a final note there are a few things to have in mind about the current limitations of our drawing system:
  • We currently do not support layers. It would be good if we could set a group of sprites as a background layer for example and have them always drawn before subsequent layers.
  • We are drawing everything regardless of whether it is onscreen to not. We should add Occlusion Culling.
  • We have a limit of one drawable per object. In future, we will want to add more.
  • If we add a new drawable component to an object the drawable system will not sort its collection to accommodate the new object, consequently, it is likely that the object will be drawn out of order.
This is not everything we’ll change before we’re done with our drawing system. It is just a few ideas that I had as I was writing this tutorial.
As always, if you have any suggestions for what you would like covered or are having any trouble implementing a feature, then let me know in the comments and I’ll get back to you as soon as I can. Thank you for reading 🙂