SC2Mapster

http://www.sc2mapster.com/

Well that's cliche but that owns :) Do not hesitate to leave comments!

I have been playing Element TD for hours and hours in War3. I am really glad you are doing a remake for Starcraft 2 :) I wish you good luck!

How does it work behind the scenes?

Oh yeah about huffman, I remembered there were variable-length values but I thought thas was from the input and not the output ... It reduces the usefulness of what I thought.

Anyway, I am conviced that a compression will give some gain anyway. Because the values won't be completly random, ie most player will only play the map one or two time, so the values will more likely be near 0. If you use a binary vector to tell if you have an item or not, again there will be many 0. In the general case, values are not going to be uniformly distributed, so there come the compression!

Now, we are working on a really limited space, so the compression overhead may be important. It needs to be tested :)

Nice :)

Quote:

Hashing: STARCODE reduces the size of information through hashing to it's smallest possible outcome.

A hash is a small amount of bits that "represents" a data. But in a one-way only, you cannot get your data back through that value. For example md5 or crc are hashing methods.

You may have been confused by the name of my lib SmallHash. In fact, Hash in this case is the part of the url after the # :) You probably want to name it Packing.

Omg you submissions are all so great :)

Since there are many of them, can you make sure you have

• The video
• The description
• The map download

all in the same post and not split around 3 differents posts. It gave me a hard time for the cinematic contest :) If you need someone to make you a video, please write in big (write in a line "== I need a video") that you need a video, so it is really easy to know what is left :)

Thanks and keep up the great work

Quote from s3rius: Go

I know it's hard to remember.. but it's s3rius ;P

vjeux, the idea of adding a Huffman algorithm is not a bad one, but it could potentially make the code longer. It's hard to predict the final outcome.

Sorry I did this on the train, my internet connection was too sloppy for me to check :( Anyway it's fixed!

The packing is already optimal given that you use all the values from the range equally. However this is not happening in real life applications. Therefore using the huffman algorithm will yield the best possible output since it's hard to know the repartition (LZW is great because we know that the recurring values are stored on 7 bits).

Omg it is really really great :)

Yesterday we've been talking about data compression to fit as many value as possible inside banks. I want to make a little write up of it.

Banks capacity are very limited therefore there is a need for compacting data as much as possible. In order to compact data it is convenient to work within a binary stream. Strings can be used for this purpose since they have a dynamic arbitrary length. However there are no native way to access each character as an integer.

Ord and Chr

We have found a trick to do the two basic operations: get the integer code of a character (ord) and write a character represented by the integer (chr). We need a string that will hold the alphabet. The position of the character in the alphabet determines its value. In order to create a character from the value, we just take the character at the offset "value" in the alphabet. To get the value we use StringFind to give us the position of the character in the alphabet.

const string alphabet = "abcdef...ABCDEF...01234...!@#$%^&*...";

string chr(int value) {
  return StringSub(alphabet, value, 1);
}

string ord(string character) {
  return StringFind(alphabet, character);
}

There are some limitations here: not all characters are valid in a string literal. s3rius said there was about 96 characters out of the 256 that did not make a script error.

We tried another technique which is using the hexadecimal value: "\x01" to "\xff" (\x00 is terminating the string like in C). It works great but when being written down in the xml file, it gets written as \x01 so it takes up 4 characters. We didn't test but we believe that it takes 4 characters in the bank limit. So this is not a viable solution.

Packing Data

Now that we have a solution to work on a binary stream, we can start packing data. What we want to store ultimately are bounded values. For example if you want to save the unit level, it's a number between 1 and 10. We need to store 10 different values, it means that it requires at least ceil(log2(10)) = 4 bits (2^4 = 16). And we want to store if he is dead or not so it takes 1 other bit.

Each character can hold 96 different values so it is 5 bits for us to work with (2^5 = 64). We will not use the range 64-96 as it does not fix a power of 2. We want to store a 4 bits data and a 1 bit data inside.

Insertion

Available space: 5 bits   xxxxx
Level: 4 bits:  llll
Dead: 1 bit:  d

Wanted Storage: dllll

How to do:

// Initialization
Result = 0
> 00000

// Inserting Level
Result = Result << 4
> 00000
Result = Result + Level
> 0llll

// Inserting Dead
Result = Result << 1
> llll0
Result = Result + Dead
> lllld

So you probably get the algorithm, for each value we shift by the number of slots we need and then we add the value. If you don't want to use a shift operation, you can multiply by 2^n. (x << n == x * (2 ^ n)).

Extraction

In order to decode here is how it works:

Result = lllld

// Extract Dead
Dead = Result % (2 ^ 1)
> 0000d
Result = Result / (2 ^ 1)
> 0llll

// Extract Level
Level = Result % (2 ^ 4)
> 0llll
Result = Result / (2 ^ 4)
> 00000

In order to get the data back, we need to use modulo and division (this time we need to use powers of 2).

Now that you have an example it is quite easy to write the algorithm. However we are using power of two here but this is not needed at all in fact. Instead of multiplying and dividing by 2 ^ n you can do the operation with the maximum of values you want to store. For example if you want to store 10 different levels, just multiply and divide by 10!

The following is a javascript pseudo code of the algorithm:

SmallHash = {
  // encode( [2, 4], [10, 15], '0123456789' ) : '42'
  encode: function (input, ranges, base) {
    var result = 0
    for offset = ranges.length - 1 downto 0
      result = result * ranges[offset]
      result = result + input[offset]
 
    return int2str(result, base)
  },
 
  // decode( '42', [10, 15], '0123456789' ) : [2, 4]
  decode: function (input, ranges, base) {
    input = str2int(input, base)
    var result = []
 
    for offset = 0 to ranges - 1
      result[offset] = inputs % ranges[offset]
      inputs = inputs / ranges[offset]
 
    return result;
  }
};

What you have to know is that each character gives you 96 possibilities. In order to know how many space you need, you have to multiply all the number of possibilities of each value. In our example 10 (Level) * 2 (Dead) = 20. We could insert one more value from 1 to 4. It would take 10 * 2 * 40 = 80. We cannot insert more in the character.

Beyond one character

We can now insert as many values as possible in one character, but as you can see, in the last example there are still 16 unused values. We want to use them along with the next character. It is possible to do so! But quite complicated in fact.

Instead of considering our character as a whole value, we want to view it as a "digit". One character holds 96 values. Therefore two characters hold 96 * 96 values, and so on. If we have 10 characters at our disposition, it will hold 96^10 values. You can multiply all the ranges to know the space you need, and you can get the characters needed.

But I didn't said how to accumulate characters. You have to consider the characters as a big number. You have to recode the basic operations + * / % for these numbers. Addition and subtraction aren't that complicated, however division and multiplication using elementary school algorithm are a bit tougher to code.

Epilogue

The last method gives you the best (yes the best!) possible packing. The downside is that it requires a big integer library which is not trivial to implement. I have coded it in Javascript: the SmallHash library.

I am pretty sure that applying the Huffman algorithm on top of it will gives an even better compression as your data are not likely to have an uniform distribution.

Sadly I don't have the time to code it. However the whole algorithm is described here and is working perfectly. If you want to work on it and don't understand some details, just ask me :)

Oh I see ... Well nevermind then :)

Nice :)

However that's sad they do not credit sc2mapster nor the authors of the maps.

Quote from gh0st00: Go

on another note, im happy we get our minigame contest because its really really more easily approachable than doing custom units with attachment points and generated wapons..

The goal is to make many different contests to cover all the spectrum of the Galaxy Editor and especially new things. For example the spell contest was launched to make great use of the new Data editor and actors. The creature contest was about attachements and the cinematic contest was to promote the new lightning stuff.

Minigame contest is all about gameplay. It is less a technological challenge and focuses on what the editor was made for: making great games!

I really hope that many of you will participate. A minigame can be done in an evening, it does not have to be big to be fun :)

Quote from OneTwoSC: Go

@vjeux: Go

Thanks Vjeux! Are you working on any cool secret maps? I never know what you're up to haha.

During the day i'm mostly at school. And I spend the rest of the time finding great stuff to news, writing the news (this is some work!), harassing people so they promote their work (making videos, description ...), reading the forums and hanging out on irc, organizing contests, (being with my girl friend: really important!) ...

Administrating mapster is a full time job :) I focus on mapster than on a personal project as it will touch a lot more people (there are around 10k people coming on mapster each day).

But one day, I'll make an awesome map. It will blow up your mind! :)

Curse Premium is mostly WoW stuff for now. However in the future there is going to be Starcraft 2 related stuff with it.

About icons, do you mean custom avatar? People can already customize their avatar. I'm really open to any suggestion for the rewards as I know the Curse Premium is really useless for you guys.

Anyway, if you make it to the first 3 you get a front-page news with your name on it :) That's also another "bonus".

Really nice tutorial :)

I really like how you explain things.