Saturday, August 23, 2008

Compression Depression

At work I've been coming up with a new method of managing monsters by giving them a Logo style script. It's a list of letters followed by numbers. The real tough part was nesting scripts within each other so I can have monsters spawn other monsters. This is tough because I have the new script in between brackets and regex can't do a balanced search. It's okay to spawn one monster, but what if that monster wants to spawn as well?

The solution was to match the deepest spawn that wasn't spawning itself and work back from there. I store that in an array, then replace it with a marker to that point in the array:

var path_string:String = "a bunch of commands go here"
// spawn commands look like: S(monster commands)
const SPAWN_COMMANDS:RegExp = /(?<=S \()[^\(\)]*(?=\))/;
const SPAWN_COMMANDS_REPLACE:RegExp = /S \([^\(\)]*\)/;
var subroutines:Array = new Array();

if (subroutines.length == 0){
// extract spawn instructions and replace with an index to the subroutine list
// matching works from the deepest nest up as the parenthesis is replaced
var spawn:Array = path_string.match(SPAWN_COMMANDS);
if(spawn != null) subroutines = subroutines.concat(spawn);
path_string = path_string.replace(SPAWN_COMMANDS_REPLACE, "S "+(sub_index++));
} while (spawn != null);

I then give each spawn a reference to the subroutine array, which means I only have to parse subroutines once and I save on memory. Even if the parent monster is erased, the reference by the spawn to the subroutine array saves it from being garbage collected.

The crazy thing is that the first spawn command will get replaced with "S 1". If I'm wise to this when I write a monster's script, I can type "S 1" any where in the script and it will call that subroutine. Even inside the first spawn's own script. This means my monsters can recursively generate.

All well and good. But now I have a massive XML full of instructions for every monster. Chris Burt-Brown at work had already opted for an RLE compression method that I've also adopted (multiples of the same item you replace with a quantifier and the item), but this isn't enough for complicated instruction sets. Looking around I found an LZW compression algorithm in AS2. It even produces XML safe output! Problem solved right? Wrong. My level editor uses a javascript method to save the XML that I cribbed from Galasoft. That method only saves ANSI encoded text files. The LZW algorithm produces UTF-8 encoded output. Saving those strings as ANSI destroys all the data. I was lucky enough to find out that Mozilla browsers have the ability save XML with the XMLSerializer method in UTF-8. There's a thread on the topic here. A quick mod to the Galasoft script and I was home free.

Now if I could figure out how to operate FZip, then I could take the operation further and get more assets within the game packed down to size.

Self Aware Robots (TED talk)
Simplicity Patterns (TED talk)
Big Buck Bunny (Blender made cartoon)
Curved electronic eye created
Double Taker (Golan Levin)
A robot with a biological brain

Alternativa 3D for Flash
AS3 Mouse Gesture class