Monthly Archives: December 2016

Texture Atlases

Texture atlases for 2D games is a great optimization for batching together tons of different sprites (especially quads) with a very few number of draw calls. Making them is a pain. For pixel art or other 2D art, DXT compression is often not a great choice due to the lossyness. One good way to make atlases for 2D games is with the PNG format. Single-file loaders and savers can be used to load and save PNGs with a single function call each.

Here’s an example with the popular stb_image, along with stb_image_write:

This requires two different headers, one for loading and one for saving. Additionally the author of these headers also has a bin packing header, which could be used to make a texture atlas compiler.

However I have created a single-file header called tinydeflate. It does PNG loading, saving, and can create a texture atlas given an array of images. Internally it contains its own bin packing algorithm for sorting textures and creating atlases. Here’s an example:

The above example (if given a few more images) could output an atlas like so:


Followed by a very easy to parse text formatted file containing uv information for each atlas:

The nice thing about tinydeflate is the function to create atlases has a little bit of anti UV bleeding code inside of it. Most places on the internet will tell you to solve texture atlas bleeding by adding padding pixels around your textures. This might be important for 3D applications or when mip-mapping is important, however, I don’t have this kind of 3D experience. For 2D pixel art games it seems squeezing UVs ever so gently inside the borders of a texture works quite well, and so tinydeflate takes this approach. No complicated padding necessary.

And finally here’s an older video I did with some more information on writing the code yourself to do some of the above tasks.


Binary Heaps in C

After conducting a short search for a decent implementation of a binary heap in C I ended up having to write one. Some requirements were: no dependencies, no dynamically allocated memory, no need to modify the source to extend to new types.

The first result found from a google search yielded this OK implementation. Unfortunately it makes use of allocation routines and has a couple annoying header dependencies. It also defines the macro CMP, a fairly commonly used macro. The idea is a good idea — if we define a modifiable macro the heap can be converted to a min or max heap as needed. However in practice this is not that useful; if we use min heap first, and later require max heap, we then still need to copy + paste out a new set of heap source files. Why not just make the two different sources up-front once and for all? It also typedefs the internal type, so use of the header would require alteration of the header. This triggers recompiles, and is a pain to maintain as new types of data are needed, perhaps copy and pasting new implementations around, modifying the build system as necessary to accommodate the new files, etc.

This implementation suffers almost identical downsides, and has no way to store auxiliary data at all. Heaps of only single integers are not very useful!

One nice strategy is it uses a void* and stride size so the heap could hold arbitrary pieces of POD memory. A small downside to this strategy is the requirement to constantly multiply stride with indices, which sort of clutters the source. Not really a big deal, just a nit-pick. I actually could not find a single implementation that takes this strategy.

In the end I decided to use an indirection trick: sort an array of struct { int key, int val }, where the val member is used as an index into an array of auxiliary data. The key integer is used for sorting, and the val integer is used to lookup data associated with a key. This implementation style can be re-used for any kind of data without C++ templates, and without requiring the user to mess with the source, ever.

And here’s the output:

Cross Platform Time for dt

Generally a game loop will look something like this:

Generally the delta time slices between each game loop are useful to advance the game to the next frame, or tick. dt stands for the elapsed time since the last moment we asked for elapsed time, or, delta time. In effect we are using one frame’s worth of delayed time to advance state, so the visuals of the game are actually always one tick behind — but that’s totally acceptable and not noticeable to the user.

Getting that time slice is a little tricky. Usually games would want somewhat sub-millisecond resolution, since milliseconds is a pretty easy to reason about metric. 60 fps is about 16 milliseconds, so if we want to run a game at 60 fps we better use less than 16 milliseconds during each tick. If a major system of a game starts taking upwards of 5 or so milliseconds, then that system better be what the game is about! If a major system takes less than a millisecond, or roughly 1-2 milliseconds, it’s probably pretty well optimized. So we need sub-millisecond precision in our time function. Many time functions provided by operating systems are at best millisecond precision (not good enough if we want to measure less than a millisecond), or sometimes seconds precision.

Also, the time function itself should just be a straightforward function that returns a float, and has no parameters. So, I went through some digging and came up with a cross platform solution:

These functions should work on majority of major game platforms and give high resolution elapsed times between calls. They are intended to be used on the main thread within the main loop, once per tick.

If one wanted to use these functions for performance timing they should be modified to pass in some state, rather than rely on using static state. Static state is perfectly acceptable for the intended use case of main-loop main-thread. Be sure to read the comments in the source code!

I posted this source code in a finalized version here on github inside of tinytime.h.


git isn’t so bad!

If readers are anything like myself they may have tried out git from the command line and decided it was way too ridiculous to be worth the time. A quick google search for git tutorials yields very passionate authors with all too much information that a lot of people just do not care about.

Recently I have found git can be OK. I mostly just want to add files, commit changes, and push those changes to the server. This process is similar for mercurial and perforce, and I just cannot be bothered with more complicated things.

Here is what it looks like to add files to source control, make some commits, and then push all commits at once:

It is actually really easy. One gotcha is that -m option, it stands for message (sort of obviously). If you forget this the command seems to thrust you into a vi instance to create a message file. In my case I’ve never used vi, and like most things, I just can not be bothered to learn random crap I don’t care about. -m lets you avoid the vi thing and just type out a message right there.


Seriously, what the heck is this? I’m not some Linux hipster or programmer from 1998, I don’t write code or edit text in strange command prompt consoles. This text editor is context sensitive, so good luck exiting from it without googling for the vi shortcuts and wasting yet more of your life.

Creating a new repo is also easy: git init. Then go create a new repo via browser on your git account and it will prompt you with a nice message, saying to do:

Out of all these commands the only annoying piece was that -u command. What is it? I can not be bothered to google random things! I just do not care, and want to put some of my code on github. I ignored the -u flag and just used the command without knowing what it does. In short, these two commands do not need to be memorized and appear on your fresh github repo in your browser when first creating a new repo :)

Merge conflicts were also a breeze. I’ve dealt with merge conflicts in perforce a lot and I can say, doing it in git makes a lot more sense. In the past I’ve had to use complicted GUI merge tools with way too many buttons (like Araxis merge) to get anything done. What a pain. When hitting a merge conflict your source code will have some markup placed inside of it that looks sort of like this:

All that needs to be done is to edit the text file and pick which side of each conflict to keep. Dead simple. Delete the markups once done, and add/commit the file like normal. Couldn’t be much simpler!

All in all, as long as we avoid very passionate tutorials, bloggers, and stack overflow answers, git isn’t so bad!