Texture-Packing (Texture Atlas) With a Binary Tree

Another project I want to start on this blog is posting solutions to various problems I’ve solved in the hopes that they might be useful to someone else. One such problem is packing a bunch of small images into a large texture. This is important for rendering speed since switching textures means a new draw call. This “image-packing” concept is often called a “texture atlas.” A lot of modern game engines handle this for you, but I think algorithms are cool and I’m sure someone else does too. Or maybe you’re making you’re own game engine! (NB: Making your own engine is probably a bad idea unless you want to learn or have a really good reason not to use something like Unity.) Anyway…

The algorithm works by conceptualizing a texture that grows from the upper-left as a space that can be partitioned off using binary tree nodes branching right and down that each are either exactly-sized to contain an image or are leaf nodes representing unallocated space. (I’ll provide links to example code at the end.)

Originally, the entire texture is the empty root node:

Whenever a new image is added, there are 3 possibilities:

1) The image is the exact dimensions of the node.

In this case, the image is just inserted into that node and nothing else happens.

2) Either the image width or height exactly matches that of the node.

Here the node is resized to match the image and then a single new node is created for the unused space in either the “right” direction (matching height) or the “down” direction (matching width).
Or

3) The image does not match the node in either dimension.

Here the node is resized to match the image and then 2 new nodes are created for the unused space. The new nodes are “sliced” in 2 possible ways depending on which one will leave a larger empty node behind.
Or

As the tree expands, this process is repeated, packing in more images with the leaf nodes representing unallocated space:

An important optimization happens before any actual packing is done- all images are sorted so larger ones are packed first. Just like in a moving van, it’s much easier to find a spot for the little stuff last!

The insertion node for an image is chosen by traversing the tree looking for the closest empty node to the upper-left that is also big enough. Since the largest images were sorted to be first, this means we are packing the biggest things “in the back.” Again, just like a moving van!

If no empty node is big enough for the image, the texture is alternately expanded horizontally / vertically to the next power-of-2 size. (See the BONUS at the end for something super-cool!)

*This class was extracted from a large project with some external dependencies, but it’s minimal and the core algorithm should be portable. The most interesting functions are GetEmptyNodeOfSize and RecursivelyFindClosestFittingNode.

*BONUS:
Learn this one weird trick from a local man for testing if an integer is a power-of-2!

n > 0 && (n & (n – 1)) == 0

Save billions of divides every month from your home! CPU manufacturers hate him!
How it works:

1) If n is positive and a power-of-2 (say 8 for example), then:
2) Only 1 of its bit will be on. (1000, if n = 8)
3) n – 1 will have that 1 bit off but every lower bit on. (0111, if n = 8)
4) Therefor bitwise AND of n and (n – 1) will be 0. (1000 & 0111 = 0, if n = 8)

Small Free Game- Traffic Control

I like learning new skills and nothing motivates me to learn something quicker than a cool game project. Several weeks ago, a friend asked if I was available to help on a game. I was, except the game was in JavaScript which I last used to make a table-top Dungeons & Dragons DM app in something like 10th grade in what I can only imagine must have been truly monstrous code. So I set aside 3 days to learn the language and make a game. A self-imposed game jam!

Fortunately JavaScript is similar to Lua in many ways, so even though my previous experience was nil undefined, I was up-and-running pretty quickly. Still learning the new tech constrained my dev time and how “fancy” I could be. I needed a concept that could be effectively presented with relatively simple shapes and colors.

I was pacing back-and-forth trying to pick a game mechanic when it hit me. Well maybe that’s a bit unfair since I was the one moving and I’d definitely known the table was there before, but I was deep in thought. Anyway, one apocryphal inspiration tale later, I decided to decided to go with a concept of using switches to keep moving objects from running into hazards on the way to a goal.

Photoshopped-border screenshot time:

Play Here (Any HTML5-capable web browser. Untested on mobile.)

You’re still reading so you must want to know more about Traffic Control!

*What you see here was actually the result of spending a 4th day later to polish a bit more. The original version only had 5 levels. Now there are 10 with 2 new hazards!

*If you can Lua, you can probably JavaScript. (Going the other way is fine too.) In both languages “objects” are actually hash tables you store functions and members in that are inited by a “prototype class.”

*I’m still not sure what I think about the last 2 levels. I feel like the fire hazards introduce a type of gameplay that’s different from the “plan-ahead-and-execute” style the previous levels build on. Were I to spend more design time on this, that’s where I’d look.

*The fitness of a language can be inferred by how quickly you can make it look like C++.

*The game I worked with my friend on was Alteil Horizons. An online card-dueling game that was in a time crunch to get a demo ready before it’s now-successful-but-still-ongoing (for now) kickstarter.

Small Free Game- Parasprite Herding

Backfilling a bit of content I’ve been wanting to write up for a while…

I always have a bunch of game ideas kicking around in my head, but the small projects (like making this post) always seem to get pushed aside for whatever big thing I’m working on. Flash backward to last summer when I heard about a local themed game jam on a weekend I had open. The theme was ponies.

Being something of a fan and generally finding the show eminently positive and upbeat, I was intrigued. The show follows the adventures of 6 mane characters working together on various adventures while learning how to be better friends. Thinking on the cooperation theme, I remembered a concept of simultaneously controlling multiple characters with different abilities to accomplish a common goal. The high-level mechanic was a perfect fit, I just needed to find a “gamey” goal. Surveying the source material, I found the “Swarm of the Century” episode in which Ponyville is attacked by a Biblical swarm of magical insects (“parasprites”) that eat everything in site- including the town. The ponies had to work together to herd them back into the Everfree Forest from whence they came.

I love it when the mechanics and the flavor of a game mesh together and this was a perfect “click.” (Especially given the constraint of a pre-defined setting.) Anyway, the game…

It’s an infinite series of levels with increasingly more numerous and hungry parasprites. Get them all back to the Everfree Forest in the upper-right while distracting them from eating too many buildings. Left-click to select a pony, right click to move, other (middle) click to use the ability. I like the way it turned out, but remember that it was only a 3-day project so it’s rough. There are in-game instructions, but read “How To Play.txt” if you get stuck.

Download (Windows .zip with executable)

You’re still here! Well, here’s some more development tidbits:

*Like any good game jam, this was the result of an insane and sleep-deprived weekend. It was also a blast.

*I’m often looking to insert a new technical challenge into my small projects. For this one I decided to implement my own pathfinding algorithms. It works pretty well although missed out on a bit of polish due to time constraints.

*It was relatively easy to figure out the abilities of 5 of the characters. Rarity was not easy. I thought of a series of mediocre ideas until I finally stepped back and realized that the difficulty in figuring out what she could do was the answer. This was one of those “ah-ha!” moments where you know it’s right as soon as you think of it and wonder why you didn’t see it earlier. It also resulted in one of the best jokes in the game.

*I generally like to create and build my own worlds. This is the only personal project I can think of where I was specifically working in an established universe. It forced a different way of thinking where I had to start with the “world flavor” and find the game mechanics that would fit. It was a nice change.

*This was written in C++ and was my excuse to update to version 2.0 of the wonderful SFML media library. If you’re looking for a quick multi-platform, multi-language library to handle a bunch of low-level stuff you might need for a 2D game, check it out.

Disclaimer: I don’t own any of the audio / visual assets used that I didn’t create. This game is free and non-commercial.