Bitwise gems – fast integer math

May 10, 2007 on 2:34 pm | In Actionscript | 75 Comments

Bitwise operators are very fast in AS3, so here is a small collection of code snippets which can speed up certain computations. I won’t explain what bit operators are and how to use them, rather pointing to an excellent article hosted on gamedev.net: ‘Bitwise Operations in C’.
If you know any good tricks that are not included here, feel free to leave a comment or send me an email. All benchmarks were done in AS3.

Left bit shifting to multiply by any power of two

Approximately 300% faster.

x = x * 2;
x = x * 64;

//equals:
x = x << 1;
x = x << 6;

Right bit shifting to divide by any power of two

Approximately 350% faster.

x = x / 2;
x = x / 64;

//equals:
x = x >> 1;
x = x >> 6;

Number to integer conversion

Using int(x) is 10% faster in AS3. Still the bitwise version works better in AS2.

x = int(1.232)

//equals:
x = 1.232 >> 0;

Extracting color components

Not really a trick, but the regular way of extracting values using bit masking and shifting.

//24bit
var color:uint = 0x336699;
var r:uint = color >> 16;
var g:uint = color >> 8 & 0xFF;
var b:uint = color & 0xFF;

//32bit
var color:uint = 0xff336699;
var a:uint = color >>> 24;
var r:uint = color >>> 16 & 0xFF;
var g:uint = color >>>  8 & 0xFF;
var b:uint = color & 0xFF;

Combining color components

'Shift up' the values into the correct position and combine them.

//24bit
var r:uint = 0x33;
var g:uint = 0x66;
var b:uint = 0x99;
var color:uint = r << 16 | g << 8 | b;

//32bit
var a:uint = 0xff;
var r:uint = 0x33;
var g:uint = 0x66;
var b:uint = 0x99;
var color:uint = a << 24 | r << 16 | g << 8 | b;

Swap integers without a temporary variable using XOR

Pretty neat trick, it is explained in detail in the link at the top of the page. This is 20% faster.

var t:int = a;
a = b;
b = t;

//equals:
a ^= b;
b ^= a;
a ^= b;

Increment/decrement

This is much slower than the pre/post decrement operator, but a nice way to obfuscate your code ;-)

i = -~i; // i++
i = ~-i; // i--

Sign flipping using NOT or XOR

Strangely enough, this is 300%(!) faster.

i = -i;

//equals
i = ~i + 1;

//or
i = (i ^ -1) + 1;

Fast modulo operation using bitwise AND

If the divisor is a power of 2, the modulo (%) operation can be done with:
modulus = numerator & (divisor - 1);
This is about 600% faster.

x = 131 % 4;

//equals:
x = 131 & (4 - 1);

Check if an integer is even/uneven using bitwise AND

This is 600% faster.

isEven = (i % 2) == 0;

//equals:
isEven = (i & 1) == 0;

Absolute value

Forget Math.abs() for time critical code. Version 1 is 2500% faster than Math.abs(), and the funky bitwise version 2 is again 20% faster than version 1.

//version 1
i = x < 0 ? -x : x;

//version 2
i = (x ^ (x >> 31)) - (x >> 31);

Comparing two integers for equal sign

This is 35% faster.

eqSign = a * b > 0;

//equals:
eqSign = a ^ b >= 0;

Fast color conversion from R5G5B5 to R8G8B8 pixel format using shifts

R8 = (R5 << 3) | (R5 >> 2)
G8 = (R5 << 3) | (R5 >> 2)
B8 = (R5 << 3) | (R5 >> 2)

‘Data Structures For Game Development’ finished

May 2, 2007 on 3:55 pm | In Actionscript, data structures | 6 Comments

My data structures library is finished and will be released next week as open source under the MIT-license. It has been converted to AS3, enhanced and simplified in numerous ways. What’s left to do is writing some code examples and improving documentation.

The library, of course, can be used for anything, not just games. But I have developed it with games in mind, where each structure is designed to be as simple and fast as possible, leaving only a minimum implementation (which also means that I didn’t care much about applying strict design patterns and OOP-rules).

Firefighter – The Mission

May 2, 2007 on 3:55 pm | In Actionscript, Games | 4 Comments

I just want to introduce a game called ‘Firefighter – The Mission‘ that can be played here. It’s somewhat a milestone for me because it’s the first game I coded as a freelancer. It was finished at the end of last year, but was just published now. The game is build upon an efficient isometric game (which you probably won’t notice that much because the animated fire and smoke effects are serious performance killer).

A unique game feature is the collision detection. All collisions are computed in 2d, so the game does not need coordinate space transformations (rotation about y and x axis). In fact, 90% of the code only uses additions, multiplications and bit shifting, so I think it should also run well on mobile devices.

Collision handling is divided into two parts, which are often referred to as broad phase and narrow phase. The broad phase step just checks if the 4 adjacent tiles on which the player stands are walkable and adjusts the player position accordingly. The narrow phase step uses a system I like to call ‘Micro Collision Cells’. Every tile has a fine grid of cells – much smaller than the player itself, and each cell can be turned on/off in the level editor. When the engine is fired up, all flagged cells are merged into the smallest possible amount of larger axially aligned bounding boxes (AABB). For example, if a tile has a resolution of 5×5 cells, and each cell is flagged, the engine would have to check 5×5 = 25 cells in total, but the simplification leads to one box covering the full tile.

Another feature I worked on was exact line-of-sight computation. This is used to get a valid range of tiles in front of the player that can be extinguished (very important for z-sorting the water particles). Scrolling is tile based and follows the principle of tonypa’s well known tutorial about tile based games.
Because there wasn’t much time to develop the game, I left out some advanced features like ‘line of sight’ for visibility determination (similar to a fog of war in strategy games), but I will definitely port and extend the engine to AS3, since it is easily adapted to other graphics sets or tile sizes which should come in handy if a similar project comes along.