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).

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.

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.

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.

PAX-Dev 2013 Recap

My 6-Day PAX marathon kicked off with 2 days of PAX-Dev. This is the third year PAX-Dev has happened and the second year I attended. I had a great a time and will likely be back next year. There’s a strict “no-media” policy, so I won’t go into to much detail and won’t have pics but will just give general impressions instead. Incidentally, the no-media policy itself is great. It keeps the event focused on Devs just hanging out, networking, and sharing stories- preventing it from becoming yet another media event. I also really appreciate PAX’s efforts to make sure it’s affordable for indie devs to attend.

The first day got off to a great start until I realized I’d left all my sweet business cards at home. Since a big part of the reason for PAX-Dev is networking, I decided I had to go fetch them during the lunch break. This should have been easy, except paid parking lots apparently don’t like you leaving and returning. Come early and stay all day, you get a special (somewhat) reasonable rate. But if you want to leave at some point, then you’re on the (unreasonable) hourly rate. Not knowing this, I asked the attendant if it was okay if I left for about 40 minutes. She said yes, so I got my car and tried to leave. At the gate I found out she thought I was just asking permission to walk around downtown Seattle for 40 minutes. But they cut me a “deal” and would retroactively sell me an “in-and-out pass” for $30. Never wanting to miss a good pun, I almost asked if I could get that “animal style,” but then realized that might be tragically misinterpreted and get me slapped (or forced to play the hourly rate). I went home, got my cards, and returned. Immediately after grabbing a ticket to re-enter and re-park my car, I read on my “in-and-out pass” that I was supposed to use that to get back in instead of getting another ticket. It took another trip to the attendant and about 15 minutes to sort that out. I received a stern warning that if I lost my pass, I’d be paying the hourly rate for the full day.

The Science Game!:
The series of delays pushed me beyond lunch time, but fortunately the awesome Reuben Fries saved me a seat in the “make a science game” workshop. We were given a choice of designing a card game to teach concepts of starch digestion, stoichiometry, or evolution. Naturally, we selected the third option. We didn’t quite finish, but had the clear beginnings of a decent game in the space of a half hour. Designing a game with Reuben was definitely a highlight and we have discussed the possibility of a www.GoodGamery.com game jam. I intend to make that happen and intend for it to be sweet.

Other Panels:
I felt like the panels I attended this year were not quite as good as last year, but a lot of that might be related to trying to guess the best panel from a paragraph in the con booklet. (I heard the indie marketing panel was great, but I didn’t attend it.) Also, last year Richard Garfield (of Magic: The Gathering fame) gave a great talk on the role of randomness in games. I still remember how insightful that talk was, so it might have colored my perception of this year. But there were still some highlights including a sick demo of Cadenza Interactive’s internal tools and development practices and a panel on how indie devs can (and should) help each other out.

But the best part of the Dev conference isn’t the panels, it’s the reception / hang-out time after the panels close. You get to talk to cool people, try out game prototypes, etc. If you make it out to PAX-Dev, make sure to plan to stay a few hours late. It will be worth it. Finally, don’t be afraid to just walk up to people and start a conversation about your game or their game. It’s a chill environment that encourages those things.

The Journey Home:
Oh, back to my car. So apparently my monthly phone plan ran out exactly on this night. Lacking GPS, I had to ask the parking attendant how to get to I-5. She told me to turn right and then right again at the second light. The problem was the street at the second light was a one-way. Going the wrong way. With a hidden cop on it. My tiredness, the bad directions, and lack of any other non-cop cars made it an easy mistake. While I was waiting for whatever it is cops do when they pull people over, multiple people walked by and told me as long as I wasn’t drunk I’d probably be fine. (Seattle people are nice like that.) Fortunately, I’d left all my O’Douls at home and ended up with a warning. At this point, all the car nonsense had officially passed from annoying to comical. I finally got home and resolved to take the bus for the rest of the conference.

New Versions, iOS, and Kindle

It’s been a while since the “new” trailer. Anyway, Jacob’s Ladder is now available on Android, iOS, and Amazon Kindle. It’s also been updated multiple times based on player feedback, addressing minor bugs, and improving play control. Oh and there’s a free-to-try demo too!

Here are some links!

iOS full game
Android full game
Amazon Kindle full game

iOS demo
Android demo
Kindle demo

I guess it’s been a while and I need to update this thing more… fortunately I have a lot of cool PAX stories coming shortly!