Author Topic: map compression  (Read 7827 times)

0 Members and 1 Guest are viewing this topic.

Offline shmibs

  • しらす丼
  • Administrator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2132
  • Rating: +281/-3
  • try to be ok, ok?
    • View Profile
    • shmibbles.me
map compression
« on: September 21, 2010, 11:04:28 pm »
ok, it's looking like unit 533D is going to have some hella-massive map sizes, so i was wondering...
what would be a compression algorithm well suited to a one byte per tile, 8 bites tall by n bytes wide(where n is >=13), and quite a bit of variance in tile types(so rle wouldnt work all that well)

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: map compression
« Reply #1 on: September 21, 2010, 11:09:22 pm »
well for one, i wouldn't rule out RLE just yet.  You might want to try it just to see if you like it.  How many tiles are you planning?

Offline shmibs

  • しらす丼
  • Administrator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2132
  • Rating: +281/-3
  • try to be ok, ok?
    • View Profile
    • shmibbles.me
Re: map compression
« Reply #2 on: September 21, 2010, 11:19:10 pm »
im not sure just yet(as it's still being worked out), but a mega ton
maybe 100

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: map compression
« Reply #3 on: September 21, 2010, 11:24:43 pm »
Ah i see, so no half byte compression for you.  In that case i can only suggest RLE or Huffman.  Unfortunately neither can be decompressed in real time, so you must be able to decompress them to a location before you start with displaying the map.

Offline shmibs

  • しらす丼
  • Administrator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2132
  • Rating: +281/-3
  • try to be ok, ok?
    • View Profile
    • shmibbles.me
Re: map compression
« Reply #4 on: September 22, 2010, 01:09:01 am »
beforehand is what i was planning on anyways. i think i might have an idea for a different algorithm, though(running it past kerm)
thanks, builder!

Offline Madskillz

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 488
  • Rating: +32/-2
    • View Profile
Re: map compression
« Reply #5 on: September 22, 2010, 01:16:51 am »
RLE can provide wonderful results on the right type of things. I know we used it in Sonic, at least I ran some tests with it and it had pretty decent results.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: map compression
« Reply #6 on: September 22, 2010, 01:37:36 am »
Alright sounds good :) Although i am curious as to what it is ;D

And why do you need so many tiles out of curiosity?

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55913
  • Rating: +3152/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: map compression
« Reply #7 on: September 22, 2010, 11:14:46 am »
I really need to try compression at one point x.x

Builderboy some games really requires more tiles than usual. See E:SoR and Reuben Quest, for example. It can't be helped.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: map compression
« Reply #8 on: September 22, 2010, 11:16:58 am »
Yeah I guess so, I wonder what kind of compression he dreampt up though o.O

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55913
  • Rating: +3152/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: map compression
« Reply #9 on: September 22, 2010, 11:19:15 am »
Not sure either. I know in Reuben Quest there are several tiles in a row that are the same in maps, though. In such game, I wonder if RLE would be applicable?

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: map compression
« Reply #10 on: September 22, 2010, 11:21:44 am »
I don't know, really the only way to know for sure is to test.  I had an idea to combine RLE with Huffman but I don't know how complicated that would be.

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55913
  • Rating: +3152/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: map compression
« Reply #11 on: September 22, 2010, 11:32:43 am »
Yeah my concern is if some maps are complex, they may end up a bit larger x.x

Offline shmibs

  • しらす丼
  • Administrator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2132
  • Rating: +281/-3
  • try to be ok, ok?
    • View Profile
    • shmibbles.me
Re: map compression
« Reply #12 on: September 22, 2010, 10:06:03 pm »
Yeah I guess so, I wonder what kind of compression he dreampt up though o.O
it's nothing all that special. basically it detects when the parser(which is running through the code and decompressing it to an appvar) encounters a certain tile(all the tiles for which this applies are predifined and will be clumped together in the tile data so instead of checking for each tile individually it merely checks if the tile number is greater than a set number and less than another[or just greater, as i'll probably be putting this at the end of the tile data] and if so the following byte is read as the length over which to stretch a predefined pattern of tiles like this messy ground:
)
additionally, there will be tiles that are always next to one another to form objects which are too large to fit in an 8*8, and these can be expressed by a single tile value after which the one or two others that make up the object width-wise will be automatically appended(again by predefined patterns)

all told, this will make the code required for decompression rather large, but with the map sizes im dealing with it would definitely be worth it.

as for the number of tiles, i like things that look pretty

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55913
  • Rating: +3152/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: map compression
« Reply #13 on: September 22, 2010, 11:06:57 pm »
I agree sometimes to have complex maps and ones that won't look too simple in certain games, it's better to have more tiles. Look at Reuben Quest forests and compare them with ROL3, for example. IMHO the ones in Reuben looks better, because it looks less like a grid of trees, but I needed 9 tree tiles.

Offline ralphdspam

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 841
  • Rating: +38/-1
  • My name is actually Matt.
    • View Profile
Re: map compression
« Reply #14 on: February 14, 2011, 02:32:50 pm »
Can someone explain how to save a tree for Huffman compression? That would be helpful.
ld a, 0
ld a, a