BitSets, BitFields and BitBoards

This is probably well known for the more experienced programmers among you, but since I just recently made the discovery of BitSets myself I felt compelled to share my findings with those among you who have not stumbled upon these data-structures yet. Especially since I got only 1 match on this forum for bitfields and none for bitsets nor bitboards.

So what are BitSets? BitSet is a class that gives you access to an array (well, more like a vector) of bits and easy methods for modifying said array. The most immediate benefit that one can get from it is memory usage - using an array of booleans takes 8x more space than using a bitset. This offers your the chance of storing more information readily in memory and having to calculate less during program execution - only do look-ups into the table. Bitsets are slower than using a boolean array, but only if you use them in identical ways. If you structure your code better and try to take advantage of the benefits of bitsets, then you are golden, because bitsets also support something that boolean arrays do not- fast bitwise operations… in bulk.

This means being able to call AND, OR etc methods on your 2 bitsets, getting very fast results. You would be performing functions on entire fields of data in one fast swing instead of iterating over them. Check out this article on Bitwise Optimization in Java. It dates back to 2005, but for me was just full of ideas I can use.

Anyways, in case you have not known about BitSets yet, I hope this will open some new avenues for you. In case you HAVE used them, could you perhaps give some feedback - on their performance and usefulness. Negative feedback is also very welcome since I feel I am a bit too excited about this for my own good  :smiley:

I too have gotten overly excited about bit operations.  I find them fascinating: it's like another world of programming  :D.  If you're clever you can implement some things a lot faster and memory efficient using Bitsets, like the author of the book you linked to said.  I should check out that book and "Hacker's Delight": good stuff  :D.  You shouldn't get carried away, though, as these micro-optimizations can make your code harder to read, and it's best to write a morestraight-forward algorithm first and then profile to see if you need to optimize.   

In what parts of your game do you use the bitfields?

Well what I am working on now:

My game is a turn based strategy game set in space. The universe is represented as a grid of tiles. I know quite memory intensive but actually its not that bad as most of the space is empty (Does not matter for BitSets I know… but for other stuff).

Now in this map we have several players controlling planets and ships. Each of these objects has its 'scan' or sight range. Since I want to keep the Clients unaware of the entire world data (which is only available on Server), I need to calculate which objects are visible to whom on the server side and then expose those objects to the relevant Clients. This is where BitSets come in.

I maintain numerous BitSets in memory formatted as a grid where each bit represents one tile on the map. In one BitSet I can maintain the sigh-trange of all of Client1's planets (These change rarely so this BitSet gets updated infrequently). In another BitSet I have Client2's ships all over the universe. Now I do an AND operation on the two BitSets - Which will result in a bitset which has only those bits marked which correspond to the Client2's ships inside Client1's field of view.

Another way I plan to use it is in AI calculations - have a BitSet represent different areas in their empire - border area, core, near their border etc. This will allow for quicker implementation of methods like 'is someone collecting ships on my borders?' or 'where is my secure core space where enemy will not touch my new research station?'. Once I have the BitSets ready, it is a simple matter of combining them to get any relevant data.

A 10K10K times grid takes 12,5MB of memory. I am estimating my game map to be around 1K1K.

Speed of bulk operations has been good so far but I have not tested it very much yet.

sounds pretty smart :slight_smile:

and'ing or or'ing those bitfields for various checks seems pretty nice.