Thread: Bit-Field Class Help

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    26

    Bit-Field Class Help

    In a recent program of mine I make a fairly high number of over-lap checks at once. The checks take place between two 2D vectors of integers (well, a vector of vectors of ints). At the moment, it simply loops through every tile in the smaller one, and then check if it overlaps with certain numbers on the other, given an offset. The project is a rogue-like, and I use this to check if a room can be placed on the map.

    In order to speed up map generation, I'd like to have bit-fields that I can just bitwise-or together to check for an overlap. I've written a class that dynamically allocates an array of enough chars (although I could replace it with just about any other type by changing a single typedef) that add up to enough bits for the array. (The class is passed a width and height in the constructor, then it generates enough "chars" to hold width*height bits)

    I've gotten that working well enough, I can set, reset and check the individual bits using member functions I've written to do so, but I still need a bit more functionality. I need to be able to bitwise-or two of the class objects together, so I can add a room's mask to the map after it is placed, and bitwise-and two of the class objects together, so I can check for an overlap.

    I've attached the class header file as it currently stands. I've tried the following, but it doesn't seem to work. Any ideas what I've messed up?

    Code:
    		bool CheckOverlap (BitField& otherField)
    		{
    			int w = width;
    			int h = height;
    
    			if(w>otherField.width) {w = otherField.width;}
    			if(h>otherField.height) {h = otherField.height;}
    
    			int size = w*h;
    
    			for(unsigned int i=0; i<(size/data_size)+1; i++)
    			{
    				if( (data[i] & otherField.data[i]) > 0 )
    				{
    					return 1;
    				}
    			}
    
    			return 0;
    		}
    
    
    		void Combine(BitField& otherField, int x, int y)
    		{
    			int w = otherField.width;
    			int h = otherField.height;
    
    			int x2 = x+w-1;
    			int y2 = y+h-1;
    
    			int startBit = x+(y*width);
    			int endBit = x2+(y2*width);
    			
    			int startData = startBit/data_size;
    			int endData = endBit/data_size;
    
    			for(int i=0; i<=endData-startData; i++)
    			{
    				data[startBit+i] |= otherField.data[i];
    			}
    		}
    Thank you for your time!
    Timothy Sassone
    My Dev Blog - The most up-to-date info on my current projects.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I don't think you can ignore different sizes. Assuming bytes, if the width of the first was 16 and the width of the second was eight, you'd be comparing the second row of the second room to the second half of the first row of the first room, which doesn't seem at first glance to be what you wanted to do.

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    26
    Quote Originally Posted by tabstop View Post
    I don't think you can ignore different sizes. Assuming bytes, if the width of the first was 16 and the width of the second was eight, you'd be comparing the second row of the second room to the second half of the first row of the first room, which doesn't seem at first glance to be what you wanted to do.
    Sorry, the overlap function was actually written a bit before the other, and wasn't written with different sized rooms in mind... I should have made that clear in the original post.

    I'll go ahead and rewrite it now, and update the post once I've finished.

    Thanks!

    [EDIT]: Okay... I did screw that up.... I'm going back to the drawing board, see if I can find another algorithm to use, and advice or pointers would be great... thanks!

    [EDIT2]: No luck so far, although I've redefined the problem a little more clearly...

    I have two, 1D arrays of characters. Each is used to represent a 2D array, and when accessed, takes 2D coordinants (x,y). The accessors access a single bit in one of the chars, allowing the array to simulate a bit-field.
    Each array is split into blocks of 8 bits (1 char). I need to be able to check for an overlap between two arrays, that may not be the same size, and may have an offset (I.E. checking a 3,3 grid on a 10,10 grid, with the top-left corner of the first grid at 2,3 on the larger one).
    Checking the overlap will be done via the binary or operator. But first, I have to align the bits in the section of the first array to those in the second, so that the correct bits match up.
    For example, an 10x7 array would be split into characters like this:
    0000000011
    1111112222
    2222333333
    3344444444
    5555555566
    6666667777
    7777888888
    where each number represents the ID of the character in the array. So the first character would hold the bits for 0,0-0,7, the second would hold 0,8-0,9 and 1,0-1,5. Getting it to store the information is simple enough, but I need to be able to pull out smaller parts of the individual bytes to compare, and add too...

    Any ideas would be much appreciated, I've got a piece of scrap paper on my desk literally covered in failed attempts at coming up with some sort of algorithm that doesn't involve looping through bits one at a time (which would kind-of make the whole effort pointless, since I'm trying to avoid a loop since this function might be called several thousand times in quick succession...
    Last edited by timmeh; 04-28-2010 at 08:54 PM.
    My Dev Blog - The most up-to-date info on my current projects.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  2. Please critique and suggest improvements for parser
    By Queue in forum C Programming
    Replies: 14
    Last Post: 09-28-2006, 08:28 PM
  3. Bit field
    By vaibhav in forum C++ Programming
    Replies: 1
    Last Post: 12-25-2005, 06:22 AM
  4. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2005, 11:21 PM