Highest Fit Packing Algorithm

December 10th, 2011

This algorithm is something I’m very proud of. When I started doing Spritey I didn’t know if I would be able to write a packing algorithm that can compete with other packing tools. But after comparing the results with my favourite Sprite Sheet Packer I was amazed to see that Spritey does not only pack sprites faster but it’s also  more efficient with a larger number of sprites. Here are just a few examples of what Spritey can do. ;)

Sprites: 9 Time: 0.01s Size: 130x120

Sprites: 512 Time: 0.034s Size: 368x368

Sprites: 720 Time: 0.025s Size: 1416x1012

Sprites: 1241 Time: 0.045s Size: 1544x1012

So what makes Spritey so fast? Well, I think it’s the utilization of a “free zones” technique that I used in my previous First Fit Algorithm. Free zones are calculated and stored in such a way that the calculation of where to put sprite is instantaneous unless sheet needs to be resized.

The algorithm itself is very simple. First, it sorts sprites by their width in descending order, thus making widest sprites go first. Then a location where to put sprite is calculated by checking if sprite fits into any of the free zones. When the location is found the sprite is set to that location and free zones are recalculated and sorted so that the highest and left most zones are first. If the location is not found the size is expanded by first trying to expand the highest expandable zone. If no such zone exists then either width or height is expanded depending on which one is smaller.

Spritey Loses Weight

April 23rd, 2011

I’m happy to say that I’m back on this project and am ready to finish it off. The time I was off has been really good for me. Not only I’ve learnt a new language and framework but also opened up a new perspective on how one should write applications. You have to have a certain mindset or coding style when developing application in Ruby on Rails. ;)

One of the valuable things I’ve learnt about RoR was that the reason why it is so great, apart from the fact that it is written and maintained by very smart people, is that it favours convention over configuration thus making it very simple and clean. Therefore, all internal code changes that I’m about to make in Spritey will be about defining conventions.

I’ve also looked, critically, at the usability of this tool and the requirements that I defined a long, very long time ago. The most annoying and useless feature I found in all sprite sheet tools was the graphical representation of a sprite sheet that I blindly copied without giving it any thought. Why do I find it annoying and useless? Well, it occupies most of the space but doesn’t add any real value. It gives a user an idea about how a sprite sheet will look like but does the user even care? Sure, a user can select a sprite in a sprite sheet and change properties but the same can be achieved with selecting sprite in a tree. And from the implementation perspective, GEF hasn’t really met my expectation. Unfortunately, it doesn’t handle a large number of EditParts and requires a lot of code to integrate a framework-independent model with itself. Needless to say, I dropped the requirement for graphical representation of a sprite sheet. Overhead associated with implementing it overweighted the usefulness of this feature.

Another feature that I dropped was the property sheet. Again, I found no strong use cases for displaying properties. In fact, renaming a bulk of sprites via a property sheet is not what anyone would want to do. Let zombies do it!

After striping these two features off I was left with a very naked application. Implementing this tool as an RCP application became pointless and bulky, therefore, I decided to convert this application into a wizard, a single dialog with four steps. Step one, define sprite sheet properties. Step two, add sprites to a sprite sheet. Step three, rename sprites in bulk. Step four, save sprite sheet to a disk. Nice and simple! ;)

Facelift isn’t the only change I’m going to do with Spritey. I was very unhappy about how I handled validation failures in my RCP so I decided to refactor it while applying a “coding by convention” mentality. The reason why the old approach was so convoluted was because I wanted to make validators generic, therefore, making them unaware of which property they were validating. I had the ability to retrieve a message and an error code after validation failed but if I wanted to handle multiple failures I had to write a massive switch statement in order to identify which validation has failed before displaying an appropriate error message that came from RCP resource messages, messages that came from validators have actually never been used.

The ideal approach is to have the validation to return a property specific internationalized string which can be displayed directly to a user. To achieve this the property ids and the validation error codes were turned into strings. Doing this also improved readability and debugging. The convention now is the property id and validation error code have to be an upper case. Validation message comes from resource messages in the core. The resource key is a combination of property id and validation error code separated with an underscore. For example, if id of the name property is “NAME” and validation error code of a “not a string” is “NOT_STRING” then the resource key for the validation message is “NAME_NOT_STRING”. So, now when validation fails, model retrieves the error code and concatenates it with id of the property being validated to get the key of the resource string. It then gets the message from the resource bundle and stores it in the exception.

Postponed

February 20th, 2011

Today was a house keeping day for me. My site was broken after Google updated their jQuery library so I had to do a little bit of fixing, which eventually brought me to this blog.

I feel like I should explain why there hasn’t been any updates on this project’s progress. Well, I simply haven’t been working on it since November! I’m currently working on a web project and once it’s finished I will continue working on this tool.

Add Sprites – Changed

November 20th, 2010

As I was working on my next user story I stumbled upon a problem (more like my misjudgement than a problem) that was unsolvable without changing the current implementation of importing sprites too much.

Initially, I thought  that when sprite sheet configuration is exported as XML, group and sprite names should be exported as tags to allow users access nodes directly with XPath. So, for example, the following sprite tree

would’ve produced the following configuration

<sheet>
    <buttons>
        <default x="" y="" width="" height="" />
        <pressed x="" y="" width="" height="" />
    </buttons>
</sheet>

But, I did not take into account that I had no character restrictions on names and that they could include characters deemed illegal by W3C XML specification.

To fix this I decided to allow only characters defined by XML specification, fix names that contained illegal characters and let users change names manually when importing sprites into sprite sheet, if they wish so. I also decided to make the importing process a little bit more generic, as before, adding a single sprite and adding a whole folder of sprites were two separate operations.

I combined the two separate operations into one single wizard. Users can now specify whether they want to add a couple of sprites or the whole folder of sprites in one wizard. Sprites will then be loaded and displayed in a preview tree where users can choose which sprites to add to a sprite sheet. The image bellow illustrates this process.

When users are happy with selected sprites they can move to the next page where they can rename sprites and fix conflicts. At the moment, users can only rename one sprite at a time but in the future users will be able to rename a batch of sprites all at once. Controls will look something similar to Find/Replace tool in Eclipse.

As I was close to finishing these changes I talked to Alan Morey to get his input about this. He suggested that exporting names as tags was not a good idea and that instead I should export names just like other attributes to have something like this,

<sheet>
    <group name="buttons">
        <sprite name="default" x="" y="" width="" height="" />
        <sprite name="pressed" x="" y="" width="" height="" />
    </group>
</sheet>

I liked the idea but I was still concerned with allowing users to access nodes directly with XPath like so,

xml.selectNode("/sheet/buttons/default");

But he insisted that users will most likely be concerned with importing the whole sprite sheet configuration and then accessing nodes with my API, and I can also provide an API for addressing sprites similar to XPath. So, to keep story short, I took his suggestions in and now names are exported as attributes.

This brought my attention back to my original problem. If I keep names as attributes then there is no problem with illegal characters! Well, at least in XML configuration. Other configuration formats that will be implemented in the future may still have a problem with illegal characters but I’ll let it bother me when the time comes to implementing them.

So, at the end of the day, I have changed the way users import sprites, implemented the rename feature to allow users rename sprites in bulk and kept no restrictions on name characters.

Progress Update

October 8th, 2010

Slowly but surely I’m getting there! Have made a good progress since last week. Some major problems were overcome with workarounds, which need to be fixed later.

First Fit Strategy – Screenshots

August 9th, 2010

Here’re some screenshots of first fit strategy in action. ;)

Flow Strategy vs. First Fit Strategy

August 3rd, 2010

In my previous post I talked about researching and implementing the flow strategy as a default strategy for sprite organizer. When I started implementing it I found a better strategy called the First Fit Strategy and decided to abandon the flow strategy all together.

Flow Strategy

Approach 1

Sprites are positioned in a row from left to right. When a sprite doesn’t fit into the remaining space of a current row it’s wrapped onto a new row. Row’s inital size is equal to the sprite sheet width. A sprite is checked against how much space is left in a row. If the sprite fits in, the sprite width is subtracted from the row’s width and the result is cached for the next sprite. When a sprite does not fit into what ever is left in a row, it’s moved down to the beginning of a new row.

The new row is specified by the “baseline”, which is calculated by finding the highest sprite in a row and then adding its height to the cached baseline. The image below illustrates the end result of this strategy, the grey areas indicate wasted space and red lines represent “baselines”.

This is probably the easiest strategy to implement, but it’s very inefficient and requires a lot of manual arrangement.

Pros

  1. Easy to implement. Theoretically, there’re only a few computations. Subtract sprite width from row’s remaining space and add the highest sprite width to the “baseline”.
  2. Fast. There’re no iterations as all values can be cached.

Cons

  1. Very inefficient. Because sprites are positioned one after another in a flow, a lot of space is wasted.

Approach 2

This is an improvement on the first approach. Sprites are still positioned in a flow from left to right but this time they attach themselves to sprites above them.

I’m not going to theorise about how to implement it, because I haven’t found a “decent” way to shift sprites up, ;) but by trying to implement this approach I found a better strategy called the First Fit Strategy.

First Fit Strategy

I arrived to this strategy while looking at the second approach of the flow strategy. As it’s name suggests this strategy tries to put each sprite into first smallest area it finds by dividing empty area into zones. Initially, there’s only one empty area covering the whole sprite sheet.

Sprites are tested against empty zones. If sprite fits a particular zone its bounds are subtracted from all intersecting zones, generating largest remaining rectangles. These new zones are then sorted in ascending order and redundant zones i.e. zones completely covered by other zones, are removed. The green areas in the image below illustrate two generated zones as a result of subtraction.

Say, a new sprite is added and the strategy decides that the area under the first sprite is the best fit. The second sprite will be positioned like so.

The sprite area will be subtracted from both zones generating five new zones. Two zones will eventually be removed as they are overlapped by bigger zones resulting in only three zones.

Pros

  1. Quite efficient. It is relatively efficient as it tries to fill all available spaces in a sprite sheet by always filling in the smallest areas first.
  2. Relatively fast. I don’t have any stats to be 100% sure about it’s speed, but in theory it should have a normal distribution. Number of free zones will increase as a number of sprites increase but then as less and less space become available the number of free zones will start to decrease, resulting in the increased speed.

Cons

  1. Quite complex. It’s not the most complicated algorithm in the world but still it requires some explaining.

Sprite Organiser – Strategy Pattern

July 22nd, 2010

Before I can start on the user story #4144362 I have to spend a little bit of time looking at the story #4144404. In particular this part,

Arrangement algorithms should be easily swapped in and out, but should not necessarily be visible to the user.

Strategy pattern is an obvious choice for easy algorithm switching. I’m going to introduce a sprite organiser, which is effectively a sprite sheet packer that organises sprites according to the slected algorithm/strategy. The initial or default strategy will simply stack sprites one after another similar to flow layout.

I need to add a new story for default sprite arrangement and investigate how the flow layout works.

Quick Update

July 21st, 2010

Just a quick update on the progress. Five stories have been closed so far. You can find all open and closed user stories at PivotalTracker.

More User Stories

June 30th, 2010
  1. A user can create a deep hierachy of sprites. For example, a user can create a sprite group called “menu” and add another sub-group called “buttons”:
    • GROUP : menu
      • SPRITE : background.png
      • GROUP : buttons
        • SPRITE : default.png
        • SPRITE : pressed.png
  2. A user can move a group of sprites to another group by selecting a group and dragging it over onto a target group in a sprite tree.
  3. Sprite sheet can be exported to CSS. A user can use this CSS to display sprites on a web page using background positioning.