next »

[st33d]

I think I can eventually get my head around this problem, but I'm currently stuck and I'm wondering what suggestions other people have.

(Any mention of compression and I will strap you to a rocket and fire it into the sun.)

Here's the problem:

I have a data stored like so:

"2,3,4,(1,2,3,4,(1,2),2),3,(4,5,6),((12,3,23),2,1),4"

So I want to convert that into an array. Each section in parenthesis implies a nested array.

What would that array be structured like? Well in as3 it would be like so:

myArray:Array = [2, 3, 4, [1, 2, 3, 4, [1, 2], 2], 3, [4, 5, 6], [[12, 3, 23], 2, 1], 4];

My first guess was to split the string at the commas and then try to start pushing and poping a stack whenever I hit any brackets.

(Actually my first guess was to use regex, but I know what you're going to reply to that.)

And my brain has kind of melted at the point where I'm trying to visualise how this pushing and popping business works in code. Any pointers?

[BorisTheBrave]

Assuming you've got just numbers, and a fixed dimension of array, I'd say regexes are ok for this.

Otherwise, got for a tokenizer/scanner combination like every other parser in the world;

// Regex for tokenizing is more acceptable, but this can also be done manually:
var tokenize = input.split(/\b/g);
var arrayStack = [[]];
for each(var token in array)
{
  switch(token)
  {
    case ",": break; // Ignore
    case "(": arrayStack.push([]); break;
    case ")":
      var current = arrayStack.pop();
      arrayStack.last.push(current);
      break;
    default:
      arrayStack.last.push(parseInt(token));
      break;
  }
}
assert(arrayStack.length==1,"Unbalanced array");
return arrayStack[0];


So yeah, pretty much what you thought. Note that you *can* do tokenizing and parsing in the same scan, but this is not advised.

[Mikademus]

The best solution to this is to reshuffle the items through a pseudo-random seed until you have a linear array without nesting. Then it can be compressed to less than 69 bits.

I'll go look for a rocket now...

[Pineapple]

 

[grapefrukt]

i was bored: http://wonderfl.net/c/7B1c

[st33d]

Nice! 

I'd gotten halfway into the problem and then fucked it up. I'll have a proper look when I get home.

[David Pittman]

I'd make it a recursive function that takes as input an array and the current index in the string. When the parser hits an opening parenthesis, it allocates an inner array and recurses. Though maybe the string index would have to be global so it would persist as the recursion unwinds. That would defeat the elegance of doing it recursively. Maybe the return value of the function could be the modified string index? That would probably work. Also, this becomes a harder problem if you don't have dynamic arrays because you have to allocate up front for an array whose size isn't known yet. Maybe do two passes in that case: one to count and one to build the arrays.

[st33d]

I think grapefrukt's number does the job nicely. 

Recursion is a dodgy thing in Flash. I had to implement a flood fill using a couple of functions once because it got past 15 levels so easily. In this case it won't happen.

My task was to create a format for generating parameters for monsters and items. I could indeed just generate all the objects prior to the level loading on the fly, but I wanted something I could possibly output to xml without having to come up with loads of different separators. And I like breaking objects down to idents when I not using them to save memory.

[BorisTheBrave]

Gad, why not just use XML, then? It's pretty good for recursive datatypes, and very easy to use in AS3.

[Draknek]

I would probably be tempted to convert it to JSON (i.e. wrap the whole string in [] and replace () with []) and find an AS3 JSON library, mostly because that would be a useful thing to have lying around in general.

[st33d]

Gad, why not just use XML, then? It's pretty good for recursive datatypes, and very easy to use in AS3.

Because I have a mutidimensional array describing the layers of the map and I wasn't keen on having floating chunks of xml in what was mostly loads of just zeros and ones describing if a wall was there or not.

Makes for easier reading when I trace out an entire layer of ids.

But having an external list of monsters and items referenced by id in the map may be an idea. I'll sleep on it.

[iopred]

If you absolutely must have it as a string, and you can decide how its encoded try this:

Code:

for(var y:int = 0; y < array.length; y++) {
array[y] = array[y].join("|");
}

var string:String = array.join("#");

Now string should be: 1#3#4#5#3|34#23#2#9#2|3,5,5|5#12

Reverse it with:

Code:

var array:Array = string.split("#");

for(var y:int = 0; y < array.length; y++) {
array[y] = array[y].split("|");
for(var x:int = 0; x < array[y].length; x++) {
array[y][x] = array[x].split(",");
}
}

[st33d]

Yeah, but there's three levels of splitting, possibly four.

That would require even more separators. I just wanted to go from the outset knowing I could endlessly nest stuff without exausting all the silly characters on my keyboard. This is useful also from a scripting point of view.

I'll probably move over to an xml format in the end anyway. A list of external assets for the level would be easier to edit and load back in.