Treating a 2D Point as a Built-In Type

programming flash
1

In a 2D grid based game, an integer 2D point is the most commonly used data structure.

Unfortunately, Flash’s built in flash.geom.Point has the following problems:[LIST=1]
[]It’s a class so it must be allocated on the heap and eventually garbage collected.
[]It can’t be logically compared using ==. For example: new Point(2,3) != new Point(2,3);
[]It can’t be used as the key to Dictionary. For example: dict[new Point(2,3)] is not necessarily equal to dict[new Point(2,3)]
[]It stores the x and y values as numbers not int.
[/LIST]An alternate solution is to convert the X and Y values of the point into 16 bit signed values, then pack them both into a 32 bit uint. Treat the uint like normal for operations of equality, hashing, and assignment. Unpack the values if you actually need the X and Y.

The code for packing and unpacking two integers into a uint is below:

    public class PointPacker
    {
        public static const MIN_VALUE:int = -32768;
        public static const MAX_VALUE:int = 32767;


        public static function pack(x:int, y:int):uint
        {
            if (x < MIN_VALUE || x > MAX_VALUE 
                || y < MIN_VALUE || y > MAX_VALUE)
            {
                throw new ArgumentError("Argument is out of range: " + x + "," + y);
            }
            return (x << 16) | ((y << 16) >>> 16);
        }
        
        public static function unpackX(value:uint):int
        {
            return (0xFFFF0000 & value) >> 16;
        }
        
        public static function unpackY(value:uint):int
        {
            return ((0x0000FFFF & value) << 16) >> 16;
        }
    }

The most obvious use for this is a sparsely populated grid. Imagine your grid has two items on it, one item is at -100,-100 the other is at 25, 25. Now, you could allocate a 125*125 array, but that makes no sense – it’s a huge waste of memory. And if one item moves to 26,26, you’ve got to reallocate the entire array. Instead, do this:

var grid:Dictionary = new Dictionary();
grid[PointPacker.pack(-100,-100)] = someItem;
grid[PointPacker.pack(25,25)] = someOtherItem;

There are some down sides to using this trick:[LIST=1]
[]Your point’s x and y must be between -32768 and 32767 inclusive.
[]If you want to extract the x or y value from the point, you have to call two functions: unpackX and unpackY.
[*]You can’t use flash.geom.Point’s helper methods like: add, subtract or interpolate.
[/LIST]How does the PointPacker work? Well, Flash stores signed numbers using twos complement for negative numbers. The algorithm uses sign extension and sign contraction to switch between 16 bit and 32 bit integers. The bitshift right >> operator kindly preserves sign, making sign contraction and sign extension very simple. (As an aside, use unsigned bitshift right >>> to not preserve sign. I didn’t even know that existed until I started work on this!)

I found this very useful and I hope this helps someone else!