Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's Your Projects subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. Sonic => Your Projects
United-TI Archives -> Sonic
 
    » Goto page Previous  1, 2, 3  Next
» View previous topic :: View next topic  
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 Very Happy
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 Very Happy
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

Posted: 05 Dec 2008 05:21:29 pm    Post subject:

have you tried:
http://en.wikipedia.org/wiki/Huffman_coding

btw, you cant really create an compression tecu untill you made some levels..
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:
have you tried:
http://en.wikipedia.org/wiki/Huffman_coding

btw, you cant really create an compression tecu untill you made some levels..
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 Very Happy
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... Very Happy
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
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    » Goto page Previous  1, 2, 3  Next
» View previous topic :: View next topic  
Page 2 of 3 » All times are GMT - 5 Hours

 

Advertisement