Sorting sprite's layers in isometric view

Question

I'm making a strategy game with isometric view and I'm having some problems with deciding which sprite should be drawn first (I'm using SFML 2.2 as graphic library). I'm using std::sort to sort sprites in array by their Y position in a window (Floor and walls aren't sorted, they are stored in different arrays). This code works well in an RPG game where there aren't more than 100 sprites on the map at the same time, but this is going to be a strategy game and when there are 13000 or more sprites on the map, FPS is dropping below 30 and game is becoming unplayable. So, is there any faster way to sort these sprites?

Answer 1

Sorting
Use a quad- or oct-tree. Basically, the single bucket (vector/array) you are using now represents the outer-most tree-node; it contains everything. In addition to containing all game objects, it will contain 4/8 child nodes (sub-buckets) that are exactly 1/4(quad) or 1/8(oct) the size of the orginal and fit entirely inside it with no "empty space" between any of them. Each of those also contains another 4/8 sub-buckets. The subdivision continues until the number of objects in a single node is manageable.

If you sort the nodes first, you have already sorted your objects. Draw the nodes in front-to-back (near-to-far) order.

As an example, visualize standing at the exact center point of a node. You can see that 2/4 of the 4/8 child nodes are behind you and there is no need to draw them or whatever is inside them.

Depth/distance sorting is certainly a popular use for trees, but they are not limited to only drawing. The nodes can represent any logical division that you want. Consider an InterfaceComponent that is also a container of InterfaceComponents. If you make an InterfaceComponent non-visible, there is no need to draw/check any of its' children or it's children's children. You cull the entire rest of the branch as soon as you reach Visible=False. That also represenets a tree structure (with variable dimensions).

Drawing
You are not specific about how you are drawing these, but it sounds like you may be rendering them individually, i.e. foreach(object->Render()). Please look into using instanced draw calls, if you are not already.

It implies taking the data needed for rendering out of your InterfaceComponent and storing it in a tightly packed buffer, ready to go to the GPU. When you move the InterfaceComponent around, you modify the vertex in the buffer and not the "object". In essence, InterfaceComponent has been abstracted to just the data in the buffer and, separately, the class implementation that uniquely manipulates it. To draw a quad, I need a position, size, and color; even with a complicated class inheritance structure, that's all an InterfaceComponent will ever be.

Combining
The leaf-nodes do not have to directly contain objects. You can subdivide each node into buckets for reusable geometry. i.e. a "trees bucket", "buildings bucket", etc. When you add a building instance to the tree, the usual node finding occurs, but the node adds the building to the building bucket instead of just one big master bucket for everything in the node. When you query the tree for buildings, the usual node finding occurs, but the node can easily return a list of just buildings; this is in addition to being already spatially sorted near-to-far.

This simplifies:
[state change]
Draw a TreeVariant1
[state change]
Draw a TreeVariant1
[state change]
Draw a TreeVariant2
[state change]
Draw a TreeVariant1
etc. etc. etc.

Down to:
[state change]
Draw terrain
[state change]
Draw all TreeVariant1's near-to-far
[state change]
Draw all TreeVariant2's near-to-far
[state change]
Draw all buildings near-to-far

Neat:
Using the new-ish geometry shader stage, you can render all of your sprites as individual vertices. Each sprite's position, size, UV/texture-atlas, time-factor, etc. are all crammed into a single vertex for each. The geometry shader spits out a properly-sized (and billboarded?) quad for each point it receives, calculating and filling in anything the pixel shader will need to color it.

This allows instancing, without instancing; each vertex is an instance.

Iso:
Since you are isometric, you have an advantage over normal 3D games in that you have 4 well-defined angles to work with. The difference in the near-to-far sorting algorithm between the SW and SE views will be something like checking node[2] first, rather than [3].

LOD:
Check the leaf-nodes' distances first and set the LOD for each node appropriately. Assign the highest leaf-LOD to each parent. Continue until you reach the top-level-node. With the LOD factor baked into the vertex, there are no additional states to set. The LOD factor would get consumed by the shaders to implement dynamic LOD; the LOD factor can be used to select a specific mip-level for pixel shader sampling and/or be the tessellation factor for the hull shader. The LOD factor can also, also, also be used CPU-side to determine update priorities; distant animations do not need to be updated as often as the nearer ones.