re: SPAM-LOW: Re: SPAM-LOW: Re: [stella] Reflex: Online level editor

Subject: re: SPAM-LOW: Re: SPAM-LOW: Re: [stella] Reflex: Online level editor
From: "Lee Fastenau" <stella@xxxxxxxxxxxxxxx>
Date: Thu, 9 Sep 2004 14:16:00 -0700
> I just had a brief look a the code. Are you really building a full huffman tree
> there? Wow!

Yes.  I've only ever (in the past few months) created algorithms that build fully optimized huffman trees.

> But wouldn't it be easier to define something more static? E.g.
> 3 bits for the most frequent layouts, 4 bit for average frequent ones 
> and 5 or more bits for rarely used layouts.

I think it would be easier to do it that way if I were compressing the levels by hand, but I'm planning to build a utility that will aggregate all the level data I want to include and generate the optimum huffman tree for that set.

> Then you would simply stream the bits from ROM into a buffer.
> And after 3..5 bits you compare the buffer value with the higest value 
> of that length +1 (010, 1111, 100000). If the buffer value is lower, then
> you found the correct length. Take the buffer value, subtract an offset for 
> that length (-0, -2, -16) and you have your index into an ordered(!) 
> levelBrickTable.

I understand what you're saying.  That could give a potential byte savings on the lookup tree itself, but it still sounds like you're hand-selecting the patterns to assign to the compressed codes...  whereas using the huffman algorithm to build the tree will always yield optimal results.  If a few patterns actually take more bits to encode than are in the pattern itself, that just means they are extremely rare and that compression of other more frequent patterns will still yield a net compression benefit.  Also, I believe the more data that is compressed, the more advantage I'd gain from a full huffman table versus direct layout lookups.
> True, but you allow some less fun, but nasty levels, where the reaction time 
> would be extremely limited then.

Ball speed increases based on level / timers should provide that challenge!

> Have fun!
> Thomas

As always, thanks for the thoughtful feedback.

Current Thread