Compression

Roguelike developers often need to save data. Sometimes the data takes up a large amount of space and contains repetitive data. A solution to that is run-length encoding. It compresses "runs" of data, such as "aaaaaabbbb". To do that, it stores a "count" byte and a "data" byte. The count byte stores the number of times the data byte is repeated. Because the count can never by 0, we can subtract one from the count byte to compress extremely long runs of data even more.

Here is example code for using run-length encoding (using Visual Basic.net):

   Function RLEEncode(ByVal Bytes As Byte()) As Byte()
       Dim PreviousByte As Byte = Bytes(0)
       Dim ByteCount As Byte = 0
       Dim OutputBytes As New System.Collections.Generic.Queue(Of Byte)
       For CurrentByte As Integer = 1 To Bytes.Length - 1
           If Bytes(CurrentByte) = PreviousByte And ByteCount < 255 Then
               ByteCount = CByte(ByteCount + 1)
           Else
               OutputBytes.Enqueue(ByteCount)
               OutputBytes.Enqueue(PreviousByte)
               PreviousByte = Bytes(CurrentByte)
               ByteCount = 0
           End If
       Next
       OutputBytes.Enqueue(ByteCount)
       OutputBytes.Enqueue(PreviousByte)
       Return OutputBytes.ToArray
   End Function

   Function RLEDecode(ByVal Bytes As Byte()) As Byte()
       Dim OutputBytes As New System.Collections.Generic.Queue(Of Byte)
       For CurrentByte As Integer = 0 To Bytes.Length - 1 Step 2
           For I As Integer = 0 To Bytes(CurrentByte)
               OutputBytes.Enqueue(Bytes(CurrentByte + 1))
           Next
       Next
       Return OutputBytes.ToArray
   End Function

A more efficient way of RLE is to use some kind of token for identifying repetitive data.

   abcaaacba => abc<token>a3cba

To bypass the use of a token simply double the repetetive character and add a "countbyte".

   abcaaacba => abcaa3cba

a complete delphi-class can be found here http://svn.berlios.de/wsvn/declacol/trunk/classes/class_rle.pas