Packing data for a gazillion levels

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Andrew Davie

The attached binary has 403 levels. That's all I can fit at the moment.
I have "rudimentary" packing in there; here's how it goes...


The grid is 6x6 in size.
On that grid we have "any number" of cars.

The (special) car that we are exiting is 2x1 in size and always appears on row 2 (the third)
It can appear in any column 0 to 3 inclusive

Current packing format;
the special car only records its column (one byte)

All the other cars record x,y,type

Types and sizes are
0 = 2 x 1 horizontal
1 = 1 x 2 vertical
2 = 3 x 1 horizontal
3 = 1 x 3 vertical

So we need 2 bits to identify car type
X and Y require 4 bits each (0-5 values each).

So, 10 bits total for x,y and 2 bits for type = 12 bits.
I currently pack this into a short int (16 bits), so each room takes

1 byte (special car)
+ number of cars x 2 bytes (packed short)

OK, that's version 1. Functional




Andrew Davie

#1
Another way:

All I need to mark the "0" cells is 36 bits. Keep that in one array, and a 2nd to mark the cars
This can even be RLE packed if that proves efficient.
But let's say 5 bytes for the blank cell indicator

Then we have 4 states for each cell (4 car sizes/shapes).
That's 36 x 2 bits = 72 bits.  So, 12 bytes.

So that would be roughly 17 bytes for each level.

-----------------------------------------------------------


But maybe we can be "dynamic" here.


If we know that cell(0,0) has a horizontal 3-wide car -- because its contents are (say) 01
Then we don't need to encode cell (1,0) or (2,0) - we know contextually that the rest of the first car is there.  So we skip those cells and next encoded cell is cell(3,0).

We can look at the blank array (36 bits on/off) and see if there's a car there.

If there is we encode it (2 bits for the type).  And we mark it in some way on a board to indicate the cells it occupies (as per the first part of this algorithm).  In other words, we only encode the first location of each car (as they are "to the right" or "down" from their first coordinate.

So here we'd need 2 bits per car, on the starting cell of that car, plus the 36 bits indicating blank cells.

    ....E.
    C...ED
    C.XXED
    ...BBB
    .AA...
    ......

Let's look at an actual level (as above and in picture).

So firstly, each letter group is a car.  XX is the player's special car.


The zero-mask is

    ....1.
    1...11
    1.1111
    ...111
    .11...
    ......

but we know the location of the player car (XX) which is encoded separately as 3 bits indicating start position. That can be blanked out on the zero mask... I will put "0" to indicate newly-blanked bits.

    ....1.
    1...11
    1.0011
    ...111
    .11...
    ......

Now we proceed across then down the zero mask

First car is at (0,4). It's car "E" which happens to be a 1x3 car. Let's say these are the encodings...

00 = 2x1 car (horiz)
01 = 1x2 car (vert)
10 = 3x1 car (horiz)
11 = 3x1 car (vert)

So E will encode to "11".
We now clear the cells that E occupies in the zero mask...

    ....0.
    1...01
    1...01
    ...111
    .11...
    ......

Next non-zero bit in the zero mask is (0,1) which is car C (type 01)
so our encoding is now 11[01]  -- newly added item in brackets

We clear the appropriate zero mask bits...

    ......
    0....1
    0....1
    ...111
    .11...
    ......

Next car is car D (1x2) type (01) again.
add to the encoding --> 1101[01]

Clear the zero mask bits

    ......
    .....0
    .....0
    ...111
    .11...
    ......

Then car B, type 10
encoding: 110101[10]

    ......
    ......
    ......
    ...000
    .11...
    ......

Finally, car A type 00
encoding: 11010110(00)

    ......
    ......
    ......
    ......
    .00...
    ......

Mask is now empty - we have encoded all cars

Final encoding

(010) - special car column
11 - car E (1x3) at (0,4)
01 - car C (1x2) at (1,0)
01 - car D (1x2) at (1,5)
10 - car B (3x1) at (3,3)
00 - car A (2x1) at (2,4)

That's 36 bits zero mask + 13 bits cars == 49 bits
7 bytes.  Of course we can have more or less cars.
But for THIS level, the original (short int) packing scheme requires 5 shorts + a byte = 11 bytes.

It's better. Not fantastic, but always going to be better I think.
Assume RLE packing the zero mask might at best halve its size.

So, 18 + 13 = 31 bits = 4 bytes.
A bit better than 50% in that case, at the cost of pain in the butt unpacking.

Each additional car in the short-int packing takes 2 bytes.
Each additional car in THIS packing takes 2 bits.  So in the more complex screens (which all are) we get better savings.

The formula (bits required)
1. short-int version = 3 + (16) * cars
2. this version:  3 + 2 * cars

So for a 12-car board
1) 195 bits
2) 27 bits

Technically we are wasting bits in the short-int version and we could use fractional bits there for even more savings. But ultimately it's way more expensive than this proposal.

I think this new way would work nicely.  (say, 15% - 20% of the size).
That would mean I could fit roughly 2000 levels.


Andrew Davie

#2
... because the special car position is defined separately (3 bits), we don't need to store the 2 bits in the zero mask that it occupies; that can be built on unpacking.  So, reduce the zero mask to 34 bits.

OK, I'm making this up as I go :P

Consider we're unpacking... we could have a bit stream, which indicates the presence of an *unhandled* car.  So, 0 0 0 0 for blank squares, followed by 1 indicaing an occupied square and then 2 bits indicating the type of car at that position. As we're unpacking, we stream bits into our unpacking 6x6 zero mask (36 bits).  We have already put the 2 bits for the special car in position. We plonk down the appropriate bits for the car we just encountered. And the stream continues -- 0 for blank squares, and e *skip* in the stream itself any 1-bits in our 36-bit mask (they are HANDLED squares). So the zero mask only really handles NEW cars (a 1-bit) or blank squares (a 0-bit).

    ....E.
    C...ED
    C.XXED
    ...BBB
    .AA...
    ......

Let's say we are unpacking a stream...from the above level
So, we put XX down in our 36-bit unpack mask to indicate car in that position

    ......
    ......
    ..11..
    ......
    ......
    ......

Our stream will be 0 0 0 0 and then we hit car E (so, 1) followed by car E type (2 bits) 11
And we fill in E in the zero mask
Our stream so far:  0 0 0 0 1 1 1

    ....1.
    ....1.
    ..111.
    ......
    ......
    ......

Next we have a 0 (row 0 col 5) and then we hit car C. This adds 1 (car) + 01 (2x1 vert) to the stream.
Our stream so far:  0 0 0 0 1 1 1 1 0 1

    ....1.
    1...1.
    1.111.
    ......
    ......
    ......

next we stream 0 0 0, taking us to cell (4,1).  This is part of car E.
BUT ***here's the trick*** we see that our zero mask already processed this square
so the stream does nothing. The unpack skips to the next blank zero mask square (5,1).

Here the stream detects a car (D, type 01) so it inserts 1 (car) 01 (type)
Our stream so far:  0 0 0 0 1 1 1 1 0 1 1 0 1

    ....1.
    1...11
    1.1111
    ......
    ......
    ......

Next square of interest is (2,1) which is blank, so stream inserts 0
Our stream so far:  0 0 0 0 1 1 1 1 0 1 1 0 1

The rest of row 2 (0-based) has 1's in the zero mask, so we ignore - already have unpacked data there.
We then have 3 empty cells on the next row, so stream + 000

Our stream so far:  0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0
Then there's a car - B - so stream + 1 (car) + 10 (type)

Our stream so far:  0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0

    ....1.
    1...11
    1.1111
    ...111
    ......
    ......

the rest of the stream
stream + 0 1 (car) 00 (A)
+ 000000000 (to end of 36-bit area)


Full stream:
010 (special car x)
0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
= 35 bits. This includes the car positions, their types (shape), AND the zero squares.

That's 5 bytes for this example level.



Andrew Davie

Here's a more complex level - 10 cars...

    .GFCCC
    .GF.DD
    XXFE..
    H..EBI
    H.LLBI
    H.AAAI

stream
000 (car x)
01xx1xx1xx001xx1xx001xx001xx1xx01xx01xx
where xx is the appropriate 2-bit representing type.
That's a total of 42 bits; 6 bytes.

The original scheme required approx 21 bytes