[Algorithms] sparse bitset compression

[Richard F. <ra...@gm...>]

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