assemblerbot [Lexaloffle Blog Feed]https://www.lexaloffle.com/bbs/?uid=51756 LZ77 picture compression <p>Hello,<br /> as any of you guys I need some decent picture compression for the Pico Off Road game I'm making. PX-9 is very good choice but one of my passions always were compression algorithms. So I've decided to implement one myself. Sometimes is better and sometimes is worse than other available algorithms here. Consider it as my addition to the community and use it wherever you need.</p> <h1>Algorithm</h1> <p>LZ77 is very simple compression method that works similar to RLE with the exception: while RLE copies the same character N times LZ77 copies chunk of already decoded data of length N. I've used 3 different blocks: direct color output, offset + length block and just length for coherent rows (sequence that starts on the same X position but in previous row). Compression allows self-overlapping (for example offset 3 and length 20 is valid, it just copies itself with offset).</p> <p>For more information check <a href="https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77">https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77</a></p> <h1>Limits</h1> <ul> <li>designed for PICO-8 pictures only (or any arrays of values in interval 0..15), don't try it on map or other binary data</li> <li>picture size limit is 128x128</li> <li>compression uses simple brute force search and can be very slow (up to a minute on fast PC), but who cares?</li> <li>decompressor is 131 tokens long and is relatively fast</li> <li>it's guaranteed that the compressed stream never contains <strong>]</strong> character so it's safe to keep it in <strong>[[..]]</strong> raw lua string</li> <li>compressed stream doesn't contain capital letters (A..Z)</li> <li>size of the picture <strong>is not in the compressed stream</strong> so you have to know it ahead</li> </ul> <h1>Tips</h1> <p>LZ77 from it's nature is good for compressing repeated patterns. For example images that use 2 color gradients with Bayer-Matrix dithering have usually much better compression ratios than images with random dithering.</p> <p>Large blocks of single color are also compressed with high rations but expect much longer compression times.</p> <h1>Example</h1> <p>Load cartridge, <strong>import yourimage.png</strong>, in function <strong>_init</strong> edit <strong>w,h</strong> (width and height of the area you want to compress) and run. Result is written to <em>compressed.txt</em>.<br /> For example following image is ideal for LZ77 - compressed size is just 1157 bytes.</p> <img style="" border=0 src="/media/51756/c.png" alt="" /> <h1>Code</h1> <p>Whole code including cartridge and test picture is on Git (license CC0) <a href="https://github.com/assemblerbot/pico8-lz77">https://github.com/assemblerbot/pico8-lz77</a> .</p> <p>If you want to copy-paste it, here it is:</p> <h3>Compressor</h3> <div> <div style="max-width:800px; overflow:auto; margin-bottom:12px"> <table style="width:100%" cellspacing=0 cellpadding=0> <tr><td background=/gfx/code_bg1.png width=16><div style="width:16px;display:block"></div></td> <td background=/gfx/code_bg0.png> <div style="font-family : courier; color: #000000; display:absolute; padding-left:10px; padding-top:4px; padding-bottom:4px; "> <pre>max_run_len=100 function lz77_out_a(value) -- 0..15 if value&lt;0 or value&gt;15 then stop(&quot;value 𝘢 out of range! &quot;..value) end return chr(value+32) end function lz77_out_b(value) -- 0..178 if value&lt;0 or value&gt;178 then stop(&quot;value 𝘣 out of range! &quot;..value) end if value&lt;17 then return chr(value+48) else return chr(value+94-17) end end function lz77_out_c(value) -- 0..194 if value&lt;0 or value&gt;194 then stop(&quot;value 𝘤 out of range! &quot;..value) end if value&lt;33 then return chr(value+32) else return chr(value+94-33) end end function lz77_comp(x0,y0,w,h,vget) local pixels={} for y=0,h-1 do for x=0,w-1 do add(pixels,vget(x0+x,y0+y)) end end local out=&quot;&quot; local i=1 while i&lt;=#pixels do local p=pixels[i] local run=0 local ofs=0 for j=max(1,i-195),i-1 do local k=0 while i+k&lt;=#pixels and pixels[i+k]==pixels[j+k] do k+=1 end if k&gt;run or (k&gt;=run-1 and i-j==w) then run=k ofs=i-j end end if run&lt;2 or (run==2 and ofs~=w) then -- direct pixel output out=out..lz77_out_a(p) i+=1 elseif ofs==w then -- row with coherence run=min(run,178-(max_run_len+1)+2) out=out..lz77_out_b(run-2+max_run_len+1) i+=run else -- run run=min(run,max_run_len+2) out=out..lz77_out_b(run-2) out=out..lz77_out_c(ofs-1) i+=run end end return out end</pre></div></td> <td background=/gfx/code_bg1.png width=16><div style="width:16px;display:block"></div></td> </tr></table></div></div> <h3>Decompressor</h3> <div> <div style="max-width:800px; overflow:auto; margin-bottom:12px"> <table style="width:100%" cellspacing=0 cellpadding=0> <tr><td background=/gfx/code_bg1.png width=16><div style="width:16px;display:block"></div></td> <td background=/gfx/code_bg0.png> <div style="font-family : courier; color: #000000; display:absolute; padding-left:10px; padding-top:4px; padding-bottom:4px; "> <pre>function lz77_decomp(x0,y0,w,h,src,vset) local i,d=1,{} while i&lt;=#src do local c=ord(src,i) if c&lt;48 then add(d,c-32) else local ofs,run=w,c-46 if c&gt;=94 then run-=29 end if run&gt;=103 then run-=101 else i+=1 ofs=ord(src,i)-31 if ofs&gt;=63 then ofs-=29 end end local pos=#d-ofs for j=1,run do add(d,d[pos+j]) end end i+=1 end for i=0,w*h-1 do vset(i%w+x0,i\w+y0,d[i+1]) end end</pre></div></td> <td background=/gfx/code_bg1.png width=16><div style="width:16px;display:block"></div></td> </tr></table></div></div> <h3>Main</h3> <div> <div style="max-width:800px; overflow:auto; margin-bottom:12px"> <table style="width:100%" cellspacing=0 cellpadding=0> <tr><td background=/gfx/code_bg1.png width=16><div style="width:16px;display:block"></div></td> <td background=/gfx/code_bg0.png> <div style="font-family : courier; color: #000000; display:absolute; padding-left:10px; padding-top:4px; padding-bottom:4px; "> <pre>function _init() local x,y=0,0 --source position local w,h=128,128 --source size local lz77=lz77_comp(x,y,w,h,sget) print(&quot;size=&quot;..#lz77) printh(lz77,&quot;compressed.txt&quot;) --lz77_decomp(x,y,w,h,lz77,pset) flip() stop() end </pre></div></td> <td background=/gfx/code_bg1.png width=16><div style="width:16px;display:block"></div></td> </tr></table></div></div> <p>Have fun! :-)</p> https://www.lexaloffle.com/bbs/?tid=42198 https://www.lexaloffle.com/bbs/?tid=42198 Sat, 27 Mar 2021 10:23:42 UTC Pico Off Road <p> <table><tr><td> <a href="/bbs/?pid=88643#p"> <img src="/bbs/thumbs/pico8_picooffroad-5.png" style="height:256px"></a> </td><td width=10></td><td valign=top> <a href="/bbs/?pid=88643#p"> picooffroad</a><br><br> by <a href="/bbs/?uid=51756"> assemblerbot</a> <br><br><br> <a href="/bbs/?pid=88643#p"> [Click to Play]</a> </td></tr></table> </p> <h1>About</h1> <p>Pico Off Road is a racing game inspired by the classic Ironman Super Off Road. There are 5 car colors to choose from (equal by parameters), three tracks that can be played in both directions. Player can choose from two modes - single race or tournament. There is one &quot;hidden&quot; mode: single race with 0 opponents can be considered as a practice.</p> <h2>Menu controls</h2> <ul> <li><strong>Z</strong> = confirm</li> <li><strong>X</strong> = back</li> </ul> <h2>Driving controls</h2> <ul> <li><strong>arrows</strong> = turning, throttle, reverse</li> <li><strong>Z</strong> = nitro</li> <li><strong>X</strong> = throttle (for controllers if you can't press left/right + forward at the same time)</li> </ul> <h2>Tech</h2> <p>Pico Off Road uses combination of 2D sprites, 3D height map and real-time rendered meshes (cars).</p> <h2>Contact</h2> <p><a href="https://twitter.com/assembler_bot">@assembler_bot</a></p> <h2>Links</h2> <p>Standalone builds: <a href="https://assemblerbot.itch.io/pico-off-road">itch.io</a><br /> Sources: <a href="https://github.com/assemblerbot/pico8/tree/main/picooffroad">GitHub</a></p> https://www.lexaloffle.com/bbs/?tid=41897 https://www.lexaloffle.com/bbs/?tid=41897 Sun, 07 Mar 2021 17:51:02 UTC