Hi again!

In this (technical) devlog I will discuss the switch of rendering and logic, as requested by one comment :D in the 100k perf test post.

Series: Previous | First

As mentioned in devlog #0, we use godot-rust. However, the described mechanics should also apply to C#, for example. I'm not sure how well GDScript would perform since I haven't checked its inner workings, but I fear it might be slower in terms of execution.

Voronoi rendering

This caused the highest performance hit, so I started here.

In the first version, we used custom draw functions and used calls like draw_colored_polygon, draw_multiline/draw_dashed_line and draw_circle in order to draw each cell in the Voronoi map.

It was a complete mess, and even small changes required redrawing everything (queue_redraw). This was not scalable, meaning that as the map size increased, the frame rate decreased, reaching around 20 FPS for 5k cells. As I understand it, this was caused by draw calls to the GPU. Each draw_* function call caused GPU draw calls (in our case multiple thousands), which you can check in the Godot Editor Debugger tab:

https://preview.redd.it/jowb6i00iiig1.png?width=1154&format=png&auto=webp&s=7e99f72ff23ccf3a7a6210deedfb8f823353d5d1

Since we don't want any restrictions during development, such as a limit on the maximum map size, we redid the map rendering.

We switched to MeshInstance2D and ArrayMesh for the mesh and constructed each cell as triangles. However, that was not the whole story. We also needed to be able to customize the color of each cell and switch colors (e.g., fog of war vs. cells under vision) at runtime.

We achieved this with a combination of a texture and a simple shader. We further improved the shader execution by restricting the texture to powers of two (saving us some modulus operations).

const int STRIDE = 512;
const int MASK = STRIDE-1;
const int SHIFT = 9;  // 2^9 = 512

varying flat float v_cell_id;

void vertex() {
    v_cell_id = CUSTOM0.x;
}

void fragment() {
    int id = int(v_cell_id+ 0.5);

    int x = id & MASK;
    int y = id >> SHIFT;

    COLOR = texelFetch(cell_data_buffer, ivec2(x, y), 0);
}

Each cell has only one color at a time. We use CUSTOM0 to tell the shader the index of the one-pixel texture and access its color. Color changes are made by adjusting the appropriate pixel in the texture and updating it to the GPU.

The next challenge was line rendering because each cell has a border. Initially, we considered creating more triangles, but we abandoned that idea. Since we only need one line color, we came up with this idea:

We shrink each cell (so we get a line-width-wide gap) and set the clear color to match the desired line color. This gives us the lines for free.

Units

Now, let's talk about the units, which we handle quite efficiently, I think. The first important point is GPU draw calls and reducing scene tree nodes. One might initially think that each unit is its own node in Godot, but that would create unnecessary overhead.

We simply use an ECS (CPU) and MultimeshInstance2D (GPU).

MultimeshInstance2D allows us to render many identical objects with just one draw call (and one node in the scene tree), which saves CPU and GPU resources. You could even have millions of instances here without the GPU caring much about it (just a guess).

The ECS is the important piece on the CPU side. It allows for cache-optimized data representation. The CPU prefers predictable data processing. It needs to load data from RAM (e.g., the position of a unit, its velocity, its target, etc.). If that data is stored in an array-like fashion in the RAM, the CPU smokes through the calculations without waiting for long RAM transfers.

You should also aim for a small amount of data. I think 64 bytes is a good upper bound for what you need for one unit's calculations. We use steering behaviors for the movement of the units. Furthermore, we choose a blend of weights that will be determined at runtime. What I mean is that a unit can have multiple active behaviors at a time (e.g., path following, obstacle avoidance, etc.). We use one 16-bit mask for the active behaviors and one 32-bit mask for blending the weights of the behaviors. You might wonder how that works. We use only two bits of the weights for one behavior, resulting in four plus one possible values (e.g., the weights will be 0 (0 = if the behavior is not switched on), 0.25, 0.5, 0.75, or 1.0). This allows for a rough mixture of behaviors, which seems sufficient to us.

I hope there is something useful in there for someone, thanks and cu!

Discord | Youtube | X | Itch