Lode Runner 4K

[Rick]

Suggestion to add some sparkle: Make the background dark blue and have pixel stars scroll from right to left

Thanks for the suggestion. Here is a new version with blue sky and stars. http://elmkom.tripod.com/cgi-bin/l.pl
I had to drop a level to get it to fit. See what you think. How do you get so many levels in your game. It takes me about 100 bytes per level.

[DonaldEKnuth]

Wow! It looks really awesome if you ask me! The stars could go a little lower though so that we can see more of them, but it looks fine the way it is now as well.

Regarding how I could fit that many levels in the game:

I rely on the lzw-compression to do a good job, for compression to have a high efficiency the data should be represented with a small amount of symbols and patterns should occur frequently (preferably close to each other). To represent the levels in my game I only need a couple of symbols. Normally the "standard" for storing Sokoban game levels looks like this:
######
#    #
# #@ #
# $* #
# .* #
#    #
######
With the symbols meaning:
# wall
<space> empty square
* A "box" on top of a box-goal square
$ A "box" on top of a normal square
@ the player

It's easy to assume right now that a textfile with lots of levels next to eachother would compress fairly well. I wanted this to compress fairly well inside a class-file (which will be in a compressed Jar-file). First I introduced a new symbol, N, which means a new line. The map now looks like this:
######N
#    #N
# #@ #N
# $* #N
# .* #N
#    #N
######

I now decided that I want to store all my levels in a single (very long) string, this will result in the characters lying next to eachother inside the classfile without any code in between them (thus the "preferably have patterns next to each other" will be fulfilled). At first this is how I store one level (the above one):
String level = "######N#    #N# #@ #N# $* #N# .* #N#    #N######";

As I want to store all my levels in a large string until run-time I need to separate them. I decided that the sequence NN will be used to separate levels, as two new lines in a row never occurs and I don't want to introduce a new symbol. This is how I store the first two levels.
String levels = "######N#    #N# #@ #N# $* #N# .* #N#    #N######NN####N# .#N#  ###N#*@  #N#  $ #N#  ###N####";

To handle the levels I decided to have them in an array, position 0 being the first level and so further. The actual line in my source code looks something like:
String[] levelArray = "######N#    #N# #@ #N# $* #N# .* #N#    #N######NN####N# .#N#  ###N#*@  #N#  $ #N#  ###N####NNGG####N###  ####N#     $ #N# #  #$ #N# . .#@ #N#########NN########N#      #N# .**$@#N#      #N#####  #NGGGG####NNG#######NG#     #NG# .$. #N## $@$ #N#  .$. #N#      #N########".split("NN");

The only difference is that my line includes 95 levels and is several thousand characters long. My class file compresses very well, from over 10kb to <4kb. The complete source for my game is available last in my blog entry about the game: Click.

[Rick]

Thanks for the info on how you do your levels. I use almost the same method I have not been able to beat the LZW compression.
As my levels are all 26*16 I do not need the line or level separators. For example the first level looks like this

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17

byte [] level=(      "   G                     H"+      "H##X##H          G       H"+      "H     H    HXXXXXXXXH G  H"+      "H G E H    H        HXXX H"+      "HX#X#XH    H        H    H"+      "H     H----H-----  EH    H"+      "H     H    H    HXXX#####H"+      "H     H    H G  H        H"+      "H   E H G  HXXXXH        H"+      "#XXX#XX#XX#H        HXXHXX"+      "#XXX#      H        H  H  "+      "#G  #      H  ------H  H G"+      "XXXXXXXXHXXX###     H XXXX"+      "        H           H     "+      "        H   P       H     "+      "XXXXXXXXXXXXXXXXXXXXXXXXXX").getBytes();

By the way you can use the + oprerator to keep the levels readable without any size cost. The compiler puts the strings together for you.
I guess I just have too many images and game logic to get many levels in. 

Games published by our own members! Check 'em out!

[DonaldEKnuth]

But how do you store many levels then? (You just showed one level.) I'm able to put all my levels into one big chunk, which will make it easier for the LZW compression as the patterns are all close to eachother.

Also, by looking at your example level as well as other levels. I think you will gain in compression efficiency if you store them row by row, instead of column by column as you do now. It seems like a Lode Runner maps has more patterns if it is stored in that direction. If you do it like that, your first lines on the map you showed would be:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17

byte [] level=(    " HHHHHHHH###X  X"+    " #  X    XXGX  X"+    " # G#    XX X  X"+    " X  X    XX X  X"+    " # E#   E###X  X"+    " #  X    X  X  X"+    " HHHHHHHHX  X  X"+    "     -   #  X  X"+    "     -  GX  HHHX"+    "     -   X  X  X"+    "     -   #  X  X"+    "  HHHHHHHHHHX  X"+    "  X  -  X   # PX"+    "  X  - GX   #  X"+    "  X  -  X  -#  X"+    ..... and so on....

It's worth trying out if you really want more levels in the game. How much space are you lowering your jar-fie size with if you exclude all levels?

[Rick]

Yes I just showed one level. I in fact do put all the levels together in one big string. If I exclued all the levels it saves about 400 bytes for 4 levels. So on average about 100 butes per level. Note uncompressed it is 416 bytes per level. I could try and switch the rows for columns as you suggest. But I am not sure It will make a difference.

[DonaldEKnuth]

It probably wouldn't make that big a difference to switch rows into columns, it was more or less a "desperate" advice. If you only have around 400 bytes for level data I doubt you can do anything magically to have that many levels, the compression won't kick in until you have a larger chunk of level data with patterns which it could recognize.

As you know which symbols you are using (a limited set) and roughly how often they occur you could try using a Huffman encoding. As it is a symbol encoding scheme the main goal is to encode each symbol with as few bits as possible (as in morse code), you might know this already but now it's said anyway. If you tried that you might use a Huffman encoding scheme set like:

<empty>      0
<X>          10
<H>          110
<#>          1110
<->          11110
<G>          111110
<E>          1111110
<P>          11111110
<EndOfLevel> 11111111


And write the entire level down as a long binary string, with 11111111 terminating said string, you would end up with: (line breaks there for clarity, one line per line in your map (not the row->columns switched one.)

000111110000000000000000000000110
11011101110101110111011000000000001111100000000110
1100000011000001101010101010101010110011111000110
11001111100111111001100000110000000001101010100110
110101110101110101100000110000000001100000110
110000001101111011110111101111011011110111101111011110111100011111101100000110
110000001100000110000011010101011101110111011101110110
11000000110000011001111100011000000000110
110000111111001100111110001101010101011000000000110
1110101010111010101110101011101100000000011010101101010
11101010101110000000110000000001100011000
111011111000111000000011000111101111011110111101111011110110001100111110
101010101010101011010101011101110111000000110010101010
000000001100000000000011000000
0000000011000011111110000000011000000
101010101010101010101010101010101010101010101010101011111111

This gives us 800 bits under something pretty close to optimal symbol encoding (it would have been optimal if the encoding scheme would have been based on statistical data from your levels, which you could hard code as it will make for a higher compression in this case).

The above level could be stored in 80 bytes, but it will vary depending on the symbol frequency in each level. This data will get some additional compression from the LZW algorithm if it had a larger chunk of level data, but as you only have 400 bytes to play with I guess you are out of luck.

Anyway, it's still a nice game! Even if it only has a few levels, I guess your best bet is to optimize your code instead of level data. If you succeed in that and get more space for your level data, then your level data will hopefully be compressed better as well.

[Rick]

Thanks for the suggestion. I had already tried the huffman encoding. But it did not do any better that with out it. I think you are right the place to look is not in the level data but in the images and code logic.

[darionis]

hi all,

lode runner 4k is great game, it is amazing what can you do with only 4k.

i have problem that i can't complete first level. there is last gold piece behind wall and i can't get it. what am i supposed to do to get the final piece and finish the level?


tahnkyou

[DonaldEKnuth]

If you want to dig down two layers, first dig out 2 floor tiles on layer 1, and 1 on layer 2..

[Rick]

In case you mised it in the post use the comma and period keys to dig.

Games published by our own members! Check 'em out!

[DonaldEKnuth]

I think that he meant the place where you have to dig through two layers of ground to get to the gold, don't you? (And if you do, did I explain it clearly enough?)

[Rick]

Yes you are most likely correct. I thought he might not even know how to dig. That is why I put the boxed in gold on the first level to make sure the player knew how to dig. As it makes it much more interesting if you are not just running away from the guards all the time, but instead taunting them into holes.

[darionis]

ok, thank you everybody!  i was finaly able to collect all gold on first level.

cheers!