| Author |
Message |
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
 Posted: 20 Oct 2008 01:09:13 pm Post subject: |
|
|
ok, so
the original version of apack is here:
http://www.ibsensoftware.com/products_aPACK.html
the newer versions are on here: http://kuwanger.net/apack/
which version of that did you use to write sonic's decompressor? either way, it should be *really* easy since those are all in Python which I didn't realise when I suggested it 
and how should the maps and sprites be stored *before* getting run through? |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 05 Nov 2008 12:40:30 pm Post subject: |
|
|
*bumpity*
digi, I have plenty of free time right now, so if you let me know the details, I'll start on it. |
|
| Back to top |
|
|
GloryMXE7
Puzzleman 3000
Active Member
Joined: 02 Nov 2008
Posts: 604
|
| Posted: 14 Nov 2008 09:18:37 pm Post subject: |
|
|
| this is all confusing to me ill never even get close to understanding any of this |
|
| Back to top |
|
|
DigiTan
Unregistered HyperCam 2
Super Elite (Last Title)
Joined: 10 Nov 2003
Posts: 4468
|
| Posted: 15 Nov 2008 01:01:02 am Post subject: |
|
|
Ah, it just takes practice. The first time I ever heard of on-calc decompression was playing Blockbuster back in highschool. I didn't know what the heck he was talking about.
elfprince13 wrote: which version of that did you use to write sonic's decompressor? either way, it should be *really* easy since those are all in Python which I didn't realise when I suggested it
and how should the maps and sprites be stored *before* getting run through?
[post="128093"]<{POST_SNAPBACK}>[/post]
So far, I've used the newer version from kuwanger. Basically what I do with maps is have Apack put them in the classic ".db" format. At runtime, the game will just point DE to the location of the compressed map, and decompress it straight to saferam. Even with 32x32 maps, it can do it in a split second. Which is a really good deal considering it only takes 250 bytes on-calc.
One idea I might have brought up before was a map editor could show compression percentages while you work. Like right now, if I want to test if moving a tile will improve or lower my ratios, I've got to export it, go into DOS, assemble, and compress the map data before I can the percentage. But a live calculation would be x1000 times better. If that's doable in Python, that would be dynamite.
Last edited by Guest on 18 Nov 2008 11:14:22 pm; edited 1 time in total |
|
| Back to top |
|
|
bananaman
Indestructible
Calc Guru
Joined: 12 Sep 2005
Posts: 1124
|
| Posted: 03 Dec 2008 02:50:52 pm Post subject: |
|
|
Alrighty,
I have some free time and am very interested in helping out with this project. If I understand everything correctly, we currently have a working physics engine and display engine, we are basically waiting for some maps to be made?
I have a mac, so most of the generic sprite editing programs will not work for me. I would like to help develop in any way possible. It looks like you want a special program that will let you see the compression from apack in real time. I do not know how we are creating maps current, so the information on that would be appreciated.
Also, what routine does apack use to compress data. I did some searching around, but I couldn't locate the scheme of compression. |
|
| Back to top |
|
|
DigiTan
Unregistered HyperCam 2
Super Elite (Last Title)
Joined: 10 Nov 2003
Posts: 4468
|
| Posted: 03 Dec 2008 11:17:59 pm Post subject: |
|
|
| I'll PM you the source. It's actually a really small algorithm somewhere around 250 bytes. I've just never really looked at it. For what I've heard, it's a mix a Run Length Encoding and some kind of simple pattern-detection. |
|
| Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008
Posts: 438
|
| Posted: 04 Dec 2008 12:24:20 pm Post subject: |
|
|
cant you just post everyting?
small chance somebody will steal the source |
|
| Back to top |
|
|
GloryMXE7
Puzzleman 3000
Active Member
Joined: 02 Nov 2008
Posts: 604
|
| Posted: 04 Dec 2008 05:48:37 pm Post subject: |
|
|
| im preety sure if someone wanted to steal it they would |
|
| Back to top |
|
|
bananaman
Indestructible
Calc Guru
Joined: 12 Sep 2005
Posts: 1124
|
| Posted: 05 Dec 2008 05:03:48 pm Post subject: |
|
|
I have been doing some experimentation with huffman encoding. I wrote my own java program that will encode calculator .db data and find the huffman code. It works quite well with small alphabets. The problem is that we are going to be using an alphabet of close to or over 100 tiles. As I increase the amount of tiles it decreases the compression. It is averaging about 20% compression when it compresses images that have about 150 characters. Another problem with huffman coding is that it requires a lot of overhead because we have to store a conversion table.
Apack's compression absolutely blows this out of the water. I am having a hard time comprehending exactly how apack works, but I went and spoke to one of my CS professors and he gave me a book that should help me understand compression techniques a little bit better. He is looking forward to seeing how we can implement the best compression on this graphical data. He also told my about jython. It is a wrapper that may let us use the python coded apack compressor under the java environment.
I am posting this before I have done any further research. I will be reading through his book and looking at jython. Maybe I will be able to modify a compression routine that will suit our purposes better than apack. Either way, I want to be able to actually understand what apack is doing. This can make a great Christmas break project for me. |
|
| Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008
Posts: 438
|
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 05 Dec 2008 06:49:12 pm Post subject: |
|
|
darkstone knight wrote: The link or the method? He indicated in his first sentence that he has tried the latter.
And why can't said "tecu" be fed experimental inputs not related to map data? If it works well on a random data stream, then the maps should follow suit with yet better results, I think.
Last edited by Guest on 05 Dec 2008 06:55:18 pm; edited 1 time in total |
|
| Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008
Posts: 438
|
| Posted: 06 Dec 2008 04:59:48 am Post subject: |
|
|
....
nevermind, im stupid |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 06 Dec 2008 09:28:02 am Post subject: |
|
|
Weregoose wrote: And why can't said "tecu" be fed experimental inputs not related to map data? If it works well on a random data stream, then the maps should follow suit with yet better results, I think.
[post="129977"]<{POST_SNAPBACK}>[/post] A problem with that is that no compression algorithm works well on a random data stream. In fact, that's how you test if a random number generator is random enough. You'd have to test compression on map data or something that at least looks a bit like map data, to get useful results. |
|
| Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008
Posts: 438
|
| Posted: 06 Dec 2008 10:00:21 am Post subject: |
|
|
| we might be able to help more if you post an sample map |
|
| Back to top |
|
|
bananaman
Indestructible
Calc Guru
Joined: 12 Sep 2005
Posts: 1124
|
| Posted: 06 Dec 2008 10:16:32 pm Post subject: |
|
|
| I think that I have a pretty good idea regarding compression now. Today I took a trip to Chicago and back. This was the stupidest trip ever. When we came back through Michigan it had snowed close to 7 inches throughout the day and it was whiteout conditions with 35mph winds. But in the car ride I was able to go through the compression book that my prof. loaned me. I now understand Arithmetic compression as well as dictionary compressions. I believe that apack uses a type of dictionary compression. I will be experimenting over my Christmas break and try to create an arithmetic decoder and some variants on dictionary decoders and see what form will give us high compression rates compared to their space on the calculator. Hopefully I will be able to create one that gets better compression than apack. If not, I will still have learned a ton about data compression. |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 07 Dec 2008 03:14:44 pm Post subject: |
|
|
DigiTan wrote: So far, I've used the newer version from kuwanger. Basically what I do with maps is have Apack put them in the classic ".db" format. At runtime, the game will just point DE to the location of the compressed map, and decompress it straight to saferam. Even with 32x32 maps, it can do it in a split second. Which is a really good deal considering it only takes 250 bytes on-calc.
One idea I might have brought up before was a map editor could show compression percentages while you work. Like right now, if I want to test if moving a tile will improve or lower my ratios, I've got to export it, go into DOS, assemble, and compress the map data before I can the percentage. But a live calculation would be x1000 times better. If that's doable in Python, that would be dynamite.
[post="128785"]<{POST_SNAPBACK}>[/post]
ok, sorry I missed that post. I'll get to work :)
[edit]
*which* of the Kuwanger's version?
Quote: Compressors
* Python Based
*
o apack.py - One of the first version. Quite slow.
o apack.hash.py - An "improved" version, using hashes (ie, classdict) to improve searches. Still rather slow.
o apack.merdian.py - A much faster version, using Python's built-in string matcher.
o apack.merdian.py - A simple reordering of what compression choice to use, averaging in a slight increase in compression ratio.
o apack.hash-new.py - A modified hash version, attempting to use many lessons learned from a C implementation to improve compression. This version is well commented.
* C Based
*
o repeat.tree.c - Much like the name suggests, uses a tree structure to find repeating strings of data. This is the first version to attempt to find the longest match for every position and then try to chose the smallest number of long matches. Development on this was mostly given up as the complexity of trying to effectively clamp range usage optimally was turning out to be a nightmare to manage. However, this version turned out to be much faster than most of the Python versions, considering.
Decompressors
* Python Based
*
o unapack.py - A very direct port of unapack.c.
o unapack-verbose.py - A verbose version of unapack, offering some information on the decompression stream.
o unapack-verbose2.py - A much more verbose version of unapack, offering enough information to be rather useful in attempting to optimize the compression output.
* C Based
*
o unapack.c - A rather useful and portable version of unapack. It would be well advised if using GCC to use -O3 when compiling to inline most functions (or use the comparable function in other compilers).
Last edited by Guest on 07 Dec 2008 03:16:16 pm; edited 1 time in total |
|
| Back to top |
|
|
calc84maniac
Elite
Joined: 22 Jan 2007
Posts: 770
|
| Posted: 07 Dec 2008 08:26:49 pm Post subject: |
|
|
| Wow... 250 bytes for 32x32 maps? I should look into this for F-Zero at some point... |
|
| Back to top |
|
|
tr1p1ea
Elite
Joined: 03 Aug 2003
Posts: 870
|
| Posted: 08 Dec 2008 12:30:46 am Post subject: |
|
|
| Maybe he meant the routine is 250-bytes big? |
|
| Back to top |
|
|
bananaman
Indestructible
Calc Guru
Joined: 12 Sep 2005
Posts: 1124
|
| Posted: 08 Dec 2008 07:13:46 am Post subject: |
|
|
Yes, the decompressing routine is 250 bytes.
If the 32x32 map has good patterns in it, then it may be compressed down to 250 bytes. I am currently trying to create a modified version of arithmetic coding and we are getting about 70% compression. There are a few bugs to work out, and I believe that I will still have to lower the precision to have the routine fit on the calculator. |
|
| Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008
Posts: 438
|
| Posted: 08 Dec 2008 08:50:21 am Post subject: |
|
|
70% doenst sould like a whole lot... proided you compress into 100/log(32*32*(amount of possible tiles))/log(2)/8 = 82% whit 128 possible tiles
if you simply add everyting to one giant number
edit: is think the math is wrong... but you can get the amound of bit needed to form anny number between 0 and X whit log(x)/log(2)
Last edited by Guest on 08 Dec 2008 08:52:58 am; edited 1 time in total |
|
| Back to top |
|
|
|
Sonic => Your Projects
