Category: programming

Democracy 4 has one aspect of its GUI that still screams IMPERFECT at me, and needs fixing, but its at least 10x harder than it sounds. Its the sizing, and positioning of the icons on the main UI:

This looks like just a bunch of different sized circles on a screen. How is that tricky? Let me count the ways:

• The icons have to be in specific zones, which are not rectangles, but could be any polygon. These change size and shape over time
• There has to be consistency of size. A radius 10px icon in zone A has to represent the same value as a radius 10 icon in zone D
• We could have ANY screen resolution or aspect ratio.
• There could be ANY number of icons.
• There is finite time, on perhaps a CPU-limited laptop to do all the calculations.
• The icons cannot touch the center icon, or each other, or the zone boundaries.

Now it turns out…coding that is a real pain in the neck. The system that you *think* will solve it all, is to have each zone boundary and icon project a sort of repulsive force on to all the others, then step through an iterative system of applying forces and moving stuff around until an equilibrium is reached. Well kinda… but no. Look again:

Those icons with black arrows are the pain. They are kind of stuck next to corners and other icons. its the shortest distance between two icons ANYWHERE on the screen that limits the size of all of the others.

My initial solution to fix this, DID make it better, but its not good enough. What was it? Basically I do the physics-repulsing-forces thing as usual, then I ‘jiggle’ each icon in turn, randomly kicking it a few pixels in different directions, then checking to see if the overall separation of the icons got better or worse with each jiggle. I keep the jiggles that improved the situation.

Actually I improved that algorithm by first finding the icon that was the closest to the others and giving that 32 initial jiggles. This is the result, (less force is better, it means the separation is better)

Pre Jiggle. Total force:[0.39] Strongest: [0.14]
Post Jiggle. Total force:[0.03] Strongest: [0.03]
Pre Jiggle. Total force:[1.31] Strongest: [0.45]
Post Jiggle. Total force:[0.23] Strongest: [0.23]
Pre Jiggle. Total force:[1.67] Strongest: [0.32]
Post Jiggle. Total force:[0.19] Strongest: [0.19]
Pre Jiggle. Total force:[1.23] Strongest: [1.19]
Post Jiggle. Total force:[0.06] Strongest: [0.06]
Pre Jiggle. Total force:[1.14] Strongest: [0.13]
Post Jiggle. Total force:[0.17] Strongest: [0.17]
Pre Jiggle. Total force:[2.17] Strongest: [0.68]
Post Jiggle. Total force:[0.31] Strongest: [0.31]
Pre Jiggle. Total force:[0.53] Strongest: [0.40]
Post Jiggle. Total force:[0.26] Strongest: [0.26]

Which is what brings me to the current state of affairs. However, this is just one of those tasks’ that humans excel at and machines suck at. I bet you can see locations where the icons should be shuffled really easily.

Something I intend to experiment with is a more focused approach to the jiggling! I can tell now which icons (in this case two of them) seem ‘trapped’ and are causing the biggest problems, so rather than just going through all of the point containers and jiggling everything, I should now focus my attention just on the containers with the problem

Maybe I can even focus my attention just on the half-dozen icons per container that are closest to the problematic ones, but that may not actually be the solution. Check out this section in more detail:

This row of icons has basically got trapped. Moving any of them upwards and to the right is going to be tricky, unless the icons *above* them can get out of the way. The trouble is, we need some super-clever algorithm that could move an icon above them higher (thus making *that* icon worse off… so that later we can jiggle these others… and everyone will be better off.

It might be that the initial force algortihmn is too linear. A linear force would not concentrate midns enough of the dire plight of the icon in the bottom left. If the squeeze here was not seen as just *slightly* worse than the squeeze on others, but exponentailly worse… that might fix it.

…and also this icon is receiving some strong forces from its location in the corner., Unlike other icons, boundaries cannot move, so maybe we should prioritize their plight more? Surely no coincidence that both worst-case icons are in corners?

This all strikes me as something that would be easy if I’d learned more physics and maths, but hey… working it out alone from basic principles is kinda fun. I have plenty of ideas to tweak my algorithm.

Democracy 4, (my latest game) is quite evidently a 2D game. There is an assumption by players and developers alike that 2D games always run fine, that even the oldest, crappest PC will run them, and that you only need to worry about optimisation when you do some hardcore 3D game with a lot of shaders and so forth.

Nothing could be further from the truth! There are a TON on 2D games that run like ass on any laptop not designed for gaming. I think there are a bunch of factors contributing to this phenomena:

• The growth in sandbox building/strategy games with huge sprawl and map sizes that can result in a lot of objects onscreen
• An emphasis on mobile-first computing has resulted in a lot of low-power low-spec but affordable CPUs/GPUs in laptops
• An emphasis on ‘retina’ display aspiration ahs meant high screen resolutions being paired with low-spec GPUs
• A lot of game developers starting with unity, and never being exposed to decent profilers, or ground-up programming, without understanding how video cards work

So my contention is that there is a bunch of people out there with mom or dads hand-me-down laptop that was bought for surfing the internet and using word, and is now being pressed into service reluctantly as a games machine. These laptops aren’t about to run Battlefield V any time soon, but they can run an optimized 2D game very well indeed… IF the developer pays attention.

Its also worth noting that markets like Africa/India/China er definitely good targets for future market growth, and a lot of these new gamers are not necessarily going to be rocking up to your game with a 2070 RTX video card…

I recently did a lot of optimizations on Democracy 4 and I’d like to talk through the basic principles and the difference it can make. Specifically how to double the frame rate (from 19 fps to 109fps) on a single screen. The laptop spec in question: Intel core i7 6500U @ 2.50GHZ CPU Intel HD Graphics 520 GPU, screen res 1920×1080. Here is the screen in question:

This is the ‘new policy’ screen in Democracy 4. TBH this screen looks a lot more complex to render than it actually is, because of some trickery I’d already done to get that lofty 19 fps. That background image that is all washed out and greyscaled is not actually rendered as a bunch of tiny icons and text. its drawn once, just as we transition to this screen, and saved in an offscreen buffer, so it can be blapped in one go as the non-interactive background to this screen. I use a shader to greyscale and lighten the original image so this is all done in a single call.

So here we are at 19 fps, but why! To answer that I needed to use the excellent (and free) intel GPA performance tools for intel GPUs. Its easy to use and install, and capture a trace of a specific frame. With the settings i chose, I end up with a screen like this:

The top strip shows time in this frame, and how long each draw call took (X axis) and how many pixels were affected (y axis). A total of 158 draw calls happened in this frame, and thats why this puny GPU could only manage things at 19 fps.

Its worth setting up the frame analyzer so that you have GPU elapsed time on the X axis, otherwise all draw calls look as bad as each other, whereas in fact you can see that the first bunch of them took AGES. These are the ones where I draw that big full-screen background image, and where I fill the current dialog with the big white and blue background regions. It seems like even fill-rate can be limiting on this card.

By stepping through each draw call I can see the real problem. I am making a lot of really tiny changes in tiny draw calls rendering hardly anything. Here is draw call 77:

This draw call is basically just the text in that strip in the middle of the screen (highlighted in purple). Now this is not as inefficient as a lot of early-years gamdev methods, because the text has actually been pre-rendered and cached, so that entire string is rendered in a single strip, not character-by-character, but even so its a single draw call, as is each icon, each little circular indicator, and each horizontal line under each strip.

So one of these strips is actually requiring 4 draw calls. And we have 18 of them on the screen. So 72 draw calls. Can we fix this?

Actually yes, very easily. I actually do have code in the game that should handle this automatically, by batching various calls, but it can become problematic as limits in buffers can be reached, and textures can be swapped, requiring an early ‘flush’ of such batches, which if they happen in the wrong order, can mean missing text or icons. As such, the simplest and easiest approach is to change the code that roughly goes like this:

for each strip
  Draw horzizontal line
  Draw Icon
  Draw little circle icon
  Draw Text

…to something more like this…

for each strip
  Batch horizontal line
Draw all lines
for each strip
 Batch Icon
 Batch little circle icon
Draw all Icons
for each strip
 Batch text
Draw All Text

Which on the face of it looks like more hassle. isn’t it bad to iterate through the list of strips 3 times instead of 1? Well kinda…but I’m GPU limited here. the CPU has time to do that stuff, and actually there is likely NO TIME LOST at all, because of CPU/GPU concurrency. Something people forget is you are coding 2 chips at once, the CPU and the GPU. Its very common for one to just be waiting for the other. While the GPU is doing ‘Draw All Lines’ my CPU can keep busy by building up the next batched draw call. Concurrency is great!

I guess we nee to take a moment here to ask WHY does this work? Basically video cards are designed to do things in parallel, and at scale. A GPU has a LOT of settings for each time it does anything, different render states different blend modes, all the various fancy shader stuff, culling, z-buffer and render target settings etc. Think of it as a MASSIVE checklist of settings that the GPU has to consider before it does ANYTHING.

When the GPU has finished its checklist, it can then pump a bunch of data through its system. Ideally everything has been set up with huge great buckets of vertices and texels, and they can all blast through the GPU like a firehose of rendered pixels. GPUs are happiest when they are rendering a huge ton of things, all with the same settings. The last thing it wants is to have to turn off the firehose, and go through the darned checklist again…

But with a new draw call, thats pretty much what you do. Unless you are doing fancy multi-texturing, every time you switch from rendering from texture A to texture B, or change the render states in some other way, then you are ‘stalling’ the video card and asking it to reset. Now a GPU is super-quick, but if you do this 150 times per frame… you need to have a GPU that can handle this 900 times a second to get the coveted 60fps. Thats without the actual rendering, flipping or anything else…

So the less resetting and stalling of the card the better, which means BATCH BABY BATCH!

Now with the re-jig and those strips being done with the new algorithm (plus a few other tweaks), the GPA analysis looks like this:

Let me here you shout ‘109 FPS with only 52 draw calls!‘. Its also worth noting that this means less processing in general, and thus less power-draw, so that laptop battery life will last longer for games that have fewer draw calls per frame. Its a missive win.

There is actually a lot more I can do here. Frankly until I get to that tooltip right at the end, ALL of the text on this screen can be done in a single drawn call near the end. The same is true of a bunch of other icons. Essentially all I have done here is optimize the left hand side of the screen, and there is scope to go further (and when I have time I will).

I thoroughly recommend you keep (or get) an old laptop with a low spec video card, and slap the intel GPA tools on there. Other such suites of profilers exist for GPUs, the AMD one is pretty good, and nvidia have nsight as well. It all depends on your GPU make obviously.

I do wish more people were aware of the basics of stuff like this. Its hugely rewarding in terms of making your game more playable. BTW these tools work on the final .exe, you don’t need a debug build, and the engine is irrelevant, so yes, you can use them on your unity games no problem.

Hope this was interesting :D

I just added pak file support to Democracy 4. Its something I already had coded for an earlier game, but I had to do a bit of fussing to get it to work properly with democracy 4.

Pak files are basically big phat files that contain other files inside them. If you are a new developer, you probably have no idea they exist, because you probably use unity and AFAIK they handle it for you. Pak files are pretty old school, as I recall Doom and Quake used them (maybe called wad files), anyway the principle is pretty simple:

A pak file contains two sections, an index that tells you where all the other files are inside the main section, and a big phat list of data that is the contents of those files. All of this gets stuck in a single flat blob of binary data. A class exists that lets you grab the memory address of the file you want if you pass in the name of the file, so hopefully to anybody who didnt write the pak file code, using it is easy. You can read the contents of a file just like its on disk, except you have to use functions that read from memory, not ones that explicitly read disk files.

In my case, that meant stepping into the engine code, and the opengl stuff that reads in graphics files (we are only using a pak right now for dds and pngs), and just changing the contents of one function. Instead of using this code to load the data ready for creating a dds:

fread(filedata, filesize, 1, fp);

I now use this

memcpy(filedata, GetPakFiles()->GetData(pentry->StartOffset), filesize);

Big deal :D. Similar changes happen for pngs. To keep things super-simple, the old code for loading a file will run if the pak file reports it cant find that file, so you can stick a ‘loose’ png or dds file into the bitmaps folder structure and it will still get found, and the rest of the code doesnt even know the difference, which is perfect for mod support.

Most of the hassle in getting this to work was just writing some code to enumerate (that means list really…) the contents of a folder from within the pak file. I had to support this for stuff like minister profile pics, because the code previously would ask ‘what files are in this folder, I need to know so I can select a random one’, and now that code gets handled by the index at the start of the pak file instead.

So why bother with this?

Basically speed. Do you know wwhat the read speed of your hard drive is? Checking a random new one on amazon.com shows 6Gb/s. I assume thats bits not bytes, so thats 750MB per second. My hard drive is a little bit older, so lets say 500MB/second. I’ll just copy a big chunk of the source and obj files from D3 to another disk, brb…

Ok…copy speed is between a low of 1MB/second up to 100 MB/second. Wow. Thats so much slower. Why?

A HUGE amount of bullshit happens on a PC when you access files. To simplify it, it goes something like this: *deep breath* You ask to read in a file. The OS then looks up the file table to check that file exists. it then asks the security system if the current user has permission to access that file. When it gets a yes, it then opens that file, and sets attrributes so other processes will know that file is in use. The antivirus software then kicks in, and hooks into the file read so that it can check to see if that file is excluded from scans or not, and gets ready to analyze its contents. The O/S then has to use the file-table to work out where all the various scattered chunks of that file are, and start reading in each block. This means talking to the driver, and ultimately to the hardware, which may also have to check its cache to see what blocks have been cached and whether or not it has to start the glacial process of spinning an old physical drive or not (faster with SSDs obviously).

THEN! when the file read is complete, we can close that file again, notify the system that its not in use by our process any more. We can then start the process of opening the next file in our list..

You do that bullshit for EVERY DARNED FILE. But the good news is… if you have a big phat pak file…you do it once. Just once. The rest is free.

So Democracy 4 goes the extra mile, because our pak file is small (only a few hundred MB). We dont just open the file on startup, we stream all 200MB into RAM. That should take way under a second. We then have the entire file system of dds and png files in memory already, and able to be loaded almost-instantly into our engine. (RAM->VRAM is mega fast)

99% of players will not notice the speed difference. But if you have especially shit anti-virus running on a laptop, in low-battery mode, with an extremely fragmented hard drive, running democracy 4 on a train, you will be glad I bothered. Its really easy to code. My PakFile code has 263 lines in it. Many of them are whitespace or comments.