Re: sparse bitset compression
Jon Watte <[email protected]> Wed, 15 Jan 2014 13:21:22 -0800
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <CAJgyHGNPt-+vxh_MKpVdYu2Da5VJQYifTOnk4YenVaHLZaymgg@mail.gmail.com> |
--===============7833529884849141380== Content-Type: multipart/alternative; boundary=001a11c30ce2fd041e04f008e3d4 --001a11c30ce2fd041e04f008e3d4 Content-Type: text/plain; charset=UTF-8 I would question this assumption: This is too much for sending over the network regularly as part of a save. How often do you send the savegame? 7k entities, times 20 bits, equals less than 18 kB of data. By comparison, the amount of cookie and image data involved in a single mouseover-and-click event in a web browser these days is probably about that same size. Are you saying that your save data must be more lightweight than a mouse click? Where does this limitation come from? Are you targeting a modem where a 5 second background upload is not acceptable? If I had to compress the data you talk about, I might want to look into some implicit representation, like a quad tree with filled/not nodes. Something like: "Does the current sub-area have entities? If not, store 0, and terminate. Else store 1. If the size of the sub-area is greater than one, subdivide, and recurse for each sub-quadrant." Depending on how clustered the entities are, this may compress well or poorly (but with a max 7% fill rate, it ought to at least compress somewhat.) Apply gzip on top of any encoding you come up with for possible bonus gains. Sincerely, jw Sincerely, Jon Watte -- "I pledge allegiance to the flag of the United States of America, and to the republic for which it stands, one nation indivisible, with liberty and justice for all." ~ Adopted by U.S. Congress, June 22, 1942 On Tue, Jan 14, 2014 at 4:37 AM, Richard Fabian <[email protected]> wrote: > The web is full of different solutions for compressing things, but some of > you have probably already done this and found a really good ratio > compression scheme that fits what I'm asking about. > > I've got a load of entites, (4-7k) that live on a grid (1024x1024), and I > need to persist them to a savegame which gets sent across the network to > keep the save safe. I need to compress it. I'm compressing the entities in > the world already, ones that have been affected cost a few bytes, but the > but for the ones that don't have any changes, all I'm left with is the > coords. There are only a few that need the fatter compression, but at the > numbers I'm looking at, those "unchanged entity" coords add up to a lot of > data when storing as 20 bit structs. This is too much for sending over the > network regularly as part of a save. > > I've had some ideas on how to compress the data, but they might be crap. I > don't know. > > I can't easily regenerate the set so thought someone who wanted to > compress consumables might know the name of a good solution for sparse > bitset compression. The bits are clumped around different areas of the > grid, so I feel that something that leverages spatial coherence might do > well. > > Any leads would be highly appreciated. > > -- > fabs(); > "The fact that an opinion has been widely held is no evidence whatever > that it is not utterly absurd." - Bertrand Russell > > > ------------------------------------------------------------------------------ > CenturyLink Cloud: The Leader in Enterprise Cloud Services. > Learn Why More Businesses Are Choosing CenturyLink Cloud For > Critical Workloads, Development Environments & Everything In Between. > Get a Quote or Start a Free Trial Today. > > http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk > _______________________________________________ > GDAlgorithms-list mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > --001a11c30ce2fd041e04f008e3d4 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">I would question this assumption:<div><br></div><blockquot= e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width= :1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-lef= t:1ex"> <span style=3D"font-family:arial,sans-serif;font-size:12.800000190734863px"= >This is too much for sending over the network regularly as part of a save.= </span></blockquote><div><span style=3D"font-family:arial,sans-serif;font-s= ize:12.800000190734863px"><br> </span></div><div><span style=3D"font-family:arial,sans-serif;font-size:12.= 800000190734863px">How often do you send the savegame? 7k entities, times 2= 0 bits, equals less than 18 kB of data.</span></div><div><span style=3D"fon= t-family:arial,sans-serif;font-size:12.800000190734863px">By comparison, th= e amount of cookie and image data involved in a single mouseover-and-click = event in a web browser these days is probably about that same size.</span><= /div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px">Are you saying that your save data must be more lightweight than a mo= use click? Where does this limitation come from? Are you targeting a modem = where a 5 second background upload is not acceptable?</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px"><br></span></div><div><span style=3D"font-family:arial,sans-serif;fon= t-size:12.800000190734863px">If I had to compress the data you talk about, = I might want to look into some implicit representation, like a quad tree wi= th filled/not nodes. Something like:</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px">"Does the current sub-area have entities? If not, store 0, and t= erminate. Else store 1. If the size of the sub-area is greater than one, su= bdivide, and recurse for each sub-quadrant."</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px">Depending on how clustered the entities are, this may compress well o= r poorly (but with a max 7% fill rate, it ought to at least compress somewh= at.)</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px"><br></span></div><div><span style=3D"font-family:arial,sans-serif;fon= t-size:12.800000190734863px">Apply gzip on top of any encoding you come up = with for possible bonus gains.</span></div> <div><span style=3D"font-family:arial,sans-serif;font-size:12.8000001907348= 63px"><br></span></div><div><span style=3D"font-family:arial,sans-serif;fon= t-size:12.800000190734863px">Sincerely,</span></div><div><span style=3D"fon= t-family:arial,sans-serif;font-size:12.800000190734863px"><br> </span></div><div><span style=3D"font-family:arial,sans-serif;font-size:12.= 800000190734863px">jw</span></div><div><span style=3D"font-family:arial,san= s-serif;font-size:12.800000190734863px"><br></span></div><div><br></div></d= iv> <div class=3D"gmail_extra"><br clear=3D"all"><div><br><br><br>Sincerely,<br= ><br>Jon Watte<br><br><br>--<br>"I pledge allegiance to the flag of th= e United States of America, and to the republic for which it stands, one na= tion indivisible, with liberty and justice for all."<br> ~ Adopted by U.S. Congress, June 22, 1942<br></div> <br><br><div class=3D"gmail_quote">On Tue, Jan 14, 2014 at 4:37 AM, Richard= Fabian <span dir=3D"ltr"><<a href=3D"mailto:[email protected]" target=3D= "_blank">[email protected]</a>></span> wrote:<br><blockquote class=3D"gma= il_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-lef= t:1ex"> <div dir=3D"ltr">The web is full of different solutions for compressing thi= ngs, but some of you have probably already done this and found a really goo= d ratio compression scheme that fits what I'm asking about.<div><br></d= iv> <div>I've got a load of entites, (4-7k) that live on a grid (1024x1024)= , and I need to persist them to a savegame which gets sent across the netwo= rk to keep the save safe. I need to compress it. I'm compressing the en= tities in the world already, ones that have been affected cost a few bytes,= but the but for the ones that don't have any changes, all I'm left= with is the coords. There are only a few that need the fatter compression,= but at the numbers I'm looking at, those "unchanged entity" = coords add up to a lot of data when storing as 20 bit structs. This is too = much for sending over the network regularly as part of a save.</div> <div><br></div><div>I've had some ideas on how to compress the data, bu= t they might be crap. I don't know.</div> <div><br></div><div>I can't easily regenerate the set so thought someon= e who wanted to compress consumables might know the name of a good solution= for sparse bitset compression. The bits are clumped around different areas= of the grid, so I feel that something that leverages spatial coherence mig= ht do well.</div> <div><br></div><div>Any leads would be highly appreciated.<span class=3D"HO= EnZb"><font color=3D"#888888"><br clear=3D"all"><div><br></div>-- <br><div = dir=3D"ltr">fabs();<div> <span style=3D"line-height:20px;font-size:14px;font-family:'Helvetica N= eue',Helvetica,Arial,sans-serif">"The fact that an opinion has bee= n widely held is no evidence whatever that it is not utterly absurd." = - Bertrand Russell</span><br> </div></div> </font></span></div></div> <br>-----------------------------------------------------------------------= -------<br> CenturyLink Cloud: The Leader in Enterprise Cloud Services.<br> Learn Why More Businesses Are Choosing CenturyLink Cloud For<br> Critical Workloads, Development Environments & Everything In Between.<b= r> Get a Quote or Start a Free Trial Today.<br> <a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D119420431&iu= =3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam= pad/clk?id=3D119420431&iu=3D/4140/ostg.clktrk</a><br>__________________= _____________________________<br> GDAlgorithms-list mailing list<br> <a href=3D"mailto:[email protected]">GDAlgorithms-lis= [email protected]</a><br> <a href=3D"https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" = target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms= -list</a><br> Archives:<br> <a href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgo= rithms-list" target=3D"_blank">http://sourceforge.net/mailarchive/forum.php= ?forum_name=3Dgdalgorithms-list</a><br></blockquote></div><br></div> --001a11c30ce2fd041e04f008e3d4-- --===============7833529884849141380== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline ------------------------------------------------------------------------------ CenturyLink Cloud: The Leader in Enterprise Cloud Services. Learn Why More Businesses Are Choosing CenturyLink Cloud For Critical Workloads, Development Environments & Everything In Between. Get a Quote or Start a Free Trial Today. http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk --===============7833529884849141380== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list --===============7833529884849141380==--