Boolean BitFlags

[DrHalfway]

So here it is, a code snippet for setting and checking if two pair of individual ID’s have been set. We use a very similar method in our GameEngine to ensure that two of the same objects are not checked for collision more than once, unfortunately I can’t provide the exact code we use in our engine however here is an alternative, Hope it helps. It is the Java implementation of the BitFlags found in RealTime Collision Detection Book by Christer Ericson (Excellent Book!).

Update 09/08/2012 -
Got rid of long mask, cheers Roquen
Updated the Benchmark suite to include the (long) version and (int) version. Tried to make it as less biased as possible. The new results are very surprising.

Update 14/11/2012 -
Added New Benchmark Suite - 4 new classes performing same operation based on
Integer (32bit - 4 bytes) -
Long (64bit - 8 bytes) -
BitSet(?bit - ? bytes) -
Boolean 1D Array (8bit - 1 byte) -

New Cleaner Benchmark for benchmarking all versions

Removed Older Stuff

ORIGINAL VERSION

public class BooleanBitFlag {
	private final int[] bits;
	private final int size;
	
	public BooleanBitFlag(final int size) {
		this.size = size;
		/* construct a bucket of bits depending on size. 
		 * Normally you would need a 2D array of "booleans" to check
		 * for pair-pair collisions, this system uses less memory by using "bits"
		 * as flags instead. By definition, it can squeeze 32 bits from a single
		 * integer, allowing you to store 32 pair collisions per integer.
		 */
		bits = new int[((size * (size - 1) / 2) + 31) / 32];
	}
	
	public boolean setPair(final int flag1, final int flag2) {
		/* 
		 * ensure that the flags are not the same, we don't check same object-object
		 * collisions. (doesn't really make much sense to do so).
		 */
		
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			/*
			 * Perform a min and max operation, swap the values if one is larger than the other
			 * This way the result (5,6) shares the same bit index as (6,5)
			 */
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			/*
			 * Compute the bit index and the mask, is the value of these two flags
			 * stored in the bits range
			 */
			final int bitIndex = min * (2 * size - min - 3) / 2 + max - 1;
			int mask = 1 << (bitIndex & 31);
			
			/*
			 * Perform a check - if the bit is not set, no collisions have been performed
			 * set the bit as checked and return
			 */
			if ((bits[bitIndex >> 5] & mask) == 0) {
				
				/*
				 * Set the bit if not set and return true
				 */
				bits[bitIndex >> 5] |= mask;
				
				return true;
			}
		}
		
		/*
		 * Bit was set already, no need to check for this objects collision since its already happened this frame
		 * return false
		 */
		return false;
	}
	
	/*
	 * Same process as above, not terribly useful but good for debugging purposes
	 * 
	 */
	public boolean checkPair(final int flag1, final int flag2) {
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = min * (2 * size - min - 3) / 2 + max - 1;
			
			int mask = 1 << (bitIndex & 31);
			
			return (bits[bitIndex >> 5] & mask) != 0;
		}
		
		return false;
	}
	
	/*
	 * Return the bucket size
	 */
	public int bucketSize() {
		return bits.length;
	}
	
	/*
	 * Clear the buckets. Use this at the end of the frame (or collision frame) 
	 * or whenever the engine completes its collision tasks
	 */
	public void clear() {
		Arrays.fill(bits, 0);
	}
}

Using is is VERY easy

public class BitFlags {
	public static void main(String[] args) {
		BooleanBitFlag bitFlag = new BooleanBitFlag(10);
		
		System.out.println(bitFlag.checkPair(5, 6));
		
		bitFlag.setPair(5, 6);
		
		System.out.println(bitFlag.checkPair(5, 6));
		System.out.println(bitFlag.checkPair(6, 5));
	}
}

Below is the code that checks the maximum bucket (or array size) for different sized scenes.

public class BitFlags {
	public static void main(String[] args) {
		BooleanBitFlag bitFlag10 = new BooleanBitFlag(10);
		BooleanBitFlag bitFlag100 = new BooleanBitFlag(100);
		BooleanBitFlag bitFlag1000 = new BooleanBitFlag(1000);
		
		/*
		 * Check the Bucket Size of the different bitFlags. For example
		 * 10 dynamic objects in a scene have a potential maximum of 10 x 10 (100) collisions
		 * assuming each object is only checked against another object only once.
		 */
		System.out.println("Bucket Size Of 10x10: " + bitFlag10.bucketSize()); // bucket size is 2
		System.out.println("Bucket Size Of 100x100: " + bitFlag100.bucketSize()); // bucket size is 155
		System.out.println("Bucket Size Of 1000x1000: " + bitFlag1000.bucketSize()); // bucket size is 15600
	}
}

And that’s pretty much it, say you have two GameObjects with ID of 5 and 6, using this class you can check that a single operation is only done once on those pair of objects, namely collisions. If you have any improvements over the code, please post it for everyone to see! Good Luck and have fun =]

NEW UPDATED VERSION - as of 14/11/2012

INTEGER - 32BIT VERSION

/**
 * @author David Arayan (DrHalfway)
 * @version 1.0 - 	Used as part of HGE (Halfway Game Engine) Utility Library
 * 					Uses 32Bit Integer as buckets
 */

public class BooleanBitFlagInt {
	private final int[] bits;
	private final int size;
	
	public BooleanBitFlagInt(final int size) {
		this.size = size;
		
		bits = new int[((size * (size - 1) / 2) + 31) / 32];
	}
	
	/**
	 * Sets the Pair in use, the order does not matter. This function will also perform the same operation as checkPair() Function.
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean setPair(final int flag1, final int flag2) {		
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			final int mask = 1 << (bitIndex & 31);
			final int bucketIndex = bitIndex >> 5;
			
			if ((bits[bucketIndex] & mask) == 0) {
				
				bits[bucketIndex] |= mask;
				
				return true;
			}
		}
		
		return false;
	}
	
	/**
	 * Check to ensure that the pair has not been set - rarely used
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean checkPair(final int flag1, final int flag2) {
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			final int mask = 1 << (bitIndex & 31);
			
			return (bits[bitIndex >> 5] & mask) != 0;
		}
		
		return false;
	}
	
	/**
	 * Returns the current Bucket Size in use
	 * @return
	 */
	public int getBucketSize() {
		return bits.length;
	}
	
	/**
	 * Returns Approximate usage of memory in bytes - does not take into account array headers/GC vars
	 * @return
	 */
	public int getApproxMemoryUsage() {
		return bits.length * 4;
	}
	
	public void clear() {
		Arrays.fill(bits, 0);
	}
	
	public void fillFalse() {
		Arrays.fill(bits, 0);
	}
	
	public void fillTrue() {
		Arrays.fill(bits, Integer.MAX_VALUE);
	}
}

LONG - 64BIT VERSION

/**
 * @author David Arayan (DrHalfway)
 * @version 1.0 - 	Used as part of HGE (Halfway Game Engine) Utility Library
 * 					Uses 64Bit Long as buckets
 */

public class BooleanBitFlagLong {
	private final long[] bits;
	private final int size;
	
	public BooleanBitFlagLong(final int size) {
		this.size = size;
		bits= new long[((size * (size - 1) / 2) + 63) / 64];
	}
	
	/**
	 * Sets the Pair in use, the order does not matter. This function will also perform the same operation as checkPair() Function.
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean setPair(final int flag1, final int flag2) {		
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			final long mask = 1L << (bitIndex & 63);
			final int bucketIndex = bitIndex >> 6;
			
			if ((bits[bucketIndex] & mask) == 0) {
				
				bits[bucketIndex] |= mask;
				
				return true;
			}
		}
		
		return false;
	}
	
	/**
	 * Check to ensure that the pair has not been set - rarely used
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean checkPair(final int flag1, final int flag2) {
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			final long mask = 1L << (bitIndex & 63);
			
			return (bits[bitIndex >> 6] & mask) != 0;
		}
		
		return false;
	}
	
	/**
	 * Returns Approximate usage of memory in bytes - does not take into account array headers/GC vars
	 * @return
	 */
	public int getApproxMemoryUsage() {
		return bits.length * 8;
	}
	
	public int getBucketSize() {
		return bits.length;
	}
	
	public void clear() {
		Arrays.fill(bits, 0);
	}
	
	public void fillFalse() {
		Arrays.fill(bits, 0);
	}
	
	public void fillTrue() {
		Arrays.fill(bits, Integer.MAX_VALUE);
	}
}

BITSET - ??BIT VERSION

/**
 * @author David Arayan (DrHalfway)
 * @version 1.0 - 	Used as part of HGE (Halfway Game Engine) Utility Library
 * 					Uses Java.Util BitSet for bits - Slowest Method
 */

public class BooleanBitsetFlag {
	private final BitSet bits;
	private final int size;
	
	public BooleanBitsetFlag(final int size) {
		this.size = size;
		bits = new BitSet(size * (size - 1) / 2);
	}
	
	/**
	 * Sets the Pair in use, the order does not matter. This function will also perform the same operation as checkPair() Function.
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean setPair(final int flag1, final int flag2) {		
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			
			if (!bits.get(bitIndex)) {
				bits.set(bitIndex);
			}
		}
		
		return false;
	}
	
	/**
	 * Check to ensure that the pair has not been set - rarely used
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean checkPair(final int flag1, final int flag2) {
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			
			return bits.get(bitIndex);
		}
		
		return false;
	}
	
	/**
	 * Returns Approximate usage of memory in bytes - does not take into account array headers/GC vars
	 * @return
	 */
	public int getApproxMemoryUsage() {
		return bits.size();
	}
	
	public int getBucketSize() {
		return 1; // only uses 1 BitSet object
	}
	
	public void clear() {
		bits.clear();
	}
	
	public void fillFalse() {
		bits.clear();
	}
	
	public void fillTrue() {
		bits.set(0, bits.size(), true);
	}
}

BOOLEAN 1D ARRAY

/**
 * @author David Arayan (DrHalfway)
 * @version 1.0 - 	Used as part of HGE (Halfway Game Engine) Utility Library
 * 					Uses Raw boolean Array as buckets - fastest - most memory hungry method
 */

public class BooleanFlag {
	private final boolean[] bits;
	private final int size;
	
	public BooleanFlag(final int size) {
		this.size = size;
		bits = new boolean[size * (size - 1) / 2];
	}
	
	/**
	 * Sets the Pair in use, the order does not matter. This function will also perform the same operation as checkPair() Function.
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean setPair(final int flag1, final int flag2) {		
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			
			if ((bits[bitIndex] == false)) {
				
				bits[bitIndex] = true;
				
				return true;
			}
		}
		
		return false;
	}
	
	/**
	 * Check to ensure that the pair has not been set - rarely used
	 * @param flag1
	 * @param flag2
	 * @return
	 */
	public boolean checkPair(final int flag1, final int flag2) {
		if (flag1 != flag2) {
			int min = flag1;
			int max = flag2;
			
			if (flag2 < flag1) {
				min = flag2;
				max = flag1;
			}
			
			final int bitIndex = (min * (2 * size - min - 3) >> 1) + max - 1;
			
			return bits[bitIndex];
		}
		
		return false;
	}
	
	/**
	 * Returns Approximate usage of memory in bytes - does not take into account array headers/GC vars
	 * @return
	 */
	public int getApproxMemoryUsage() {
		return bits.length * 1;
	}
	
	public int getBucketSize() {
		return bits.length;
	}
	
	public void clear() {
		Arrays.fill(bits, false);
	}
	
	public void fillFalse() {
		Arrays.fill(bits, false);
	}
	
	public void fillTrue() {
		Arrays.fill(bits, true);
	}
}

BENCHMARK - Test for speed

public class BitflagBenchmark {
	public static void main(String[] args) {
		
	      final int size = 1000;
	      final int runs = 1;
	      
	      long startTime = 0;
	      long stopTime = 0;
	      
	      float intRun = 0.0f;
	      float longRun = 0.0f;
	      float boolRun = 0.0f;
	      float bitRun = 0.0f;
	      
	      BooleanBitFlagInt intBits = new BooleanBitFlagInt(size);
	      BooleanBitFlagLong longBits = new BooleanBitFlagLong(size);
	      BooleanFlag boolBits = new BooleanFlag(size);
	      BooleanBitsetFlag setBits = new BooleanBitsetFlag(size);
	      
	      System.out.println("Running Benchmark For BooleanBitFlagInt   -BUCKET SIZE: " + intBits.getBucketSize());
	      System.out.println("Running Benchmark For BooleanBitFlagLong  -BUCKET SIZE: " + longBits.getBucketSize());
	      System.out.println("Running Benchmark For BooleanFlag         -BUCKET SIZE: " + boolBits.getBucketSize());
	      System.out.println("Running Benchmark For BooleanBitsetFlag   -BUCKET SIZE: " + setBits.getBucketSize());
	      System.out.println();
	      System.out.println("Benchmark Size: " + size + " X " + size);
	      System.out.println("Benchmark Runs: " + runs);
	      
	      /*
	       * RUN BENCHMARK
	       */
	      for (int i = 0; i < runs; i++) {	    	  
	    	  /*
	    	   * LONG BITS
	    	   */
	    	  
		      startTime = System.nanoTime();
	    	  
	          for (int j = 0; j < size; j++) {
	              for (int k = 0; k < size; k++) {
	                 longBits.setPair(j, k);
	              }
	           }
	          
	          longBits.clear();
	          
		      stopTime = System.nanoTime();
		      
		      longRun += ((stopTime - startTime) * 1e-6);
	    	  
	    	  /*
	    	   * INT BITS
	    	   */
	    	  
	    	  startTime = System.nanoTime();
	    	  
	          for (int j = 0; j < size; j++) {
	              for (int k = 0; k < size; k++) {
	                 intBits.setPair(j, k);
	              }
	           }
	          
	          intBits.clear();
	          
		      stopTime = System.nanoTime();
		      
		      intRun += ((stopTime - startTime) * 1e-6);
		      
	    	  /*
	    	   * BOOLEAN ARRAY
	    	   */
		      
		      startTime = System.nanoTime();
	    	  
	          for (int j = 0; j < size; j++) {
	              for (int k = 0; k < size; k++) {
	                 boolBits.setPair(j, k);
	              }
	           }
	          
	          boolBits.clear();
	          
		      stopTime = System.nanoTime();
		      
		      boolRun += ((stopTime - startTime) * 1e-6);
		      
	    	  /*
	    	   * BITSET ARRAY
	    	   */
		      
		      startTime = System.nanoTime();
	    	  
	          for (int j = 0; j < size; j++) {
	              for (int k = 0; k < size; k++) {
	                setBits.setPair(j, k);
	              }
	           }
	          
	          setBits.clear();
	          
		      stopTime = System.nanoTime();
		      
		      bitRun += ((stopTime - startTime) * 1e-6);
	      }
	      
	      System.out.println();
	      System.out.println("Benchmark For BooleanBitFlagInt   -RUNS: " + runs + " -TIME: " + intRun + "ms" + " -Approx Memory Usage in Bytes: " + intBits.getApproxMemoryUsage());
	      System.out.println("Benchmark For BooleanBitFlagLong  -RUNS: " + runs + " -TIME: " + longRun + "ms" + " -Approx Memory Usage in Bytes: " + longBits.getApproxMemoryUsage());
	      System.out.println("Benchmark For BooleanFlag         -RUNS: " + runs + " -TIME: " + boolRun + "ms" + " -Approx Memory Usage in Bytes: " + boolBits.getApproxMemoryUsage());
	      System.out.println("Benchmark For BooleanBitsetFlag   -RUNS: " + runs + " -TIME: " + bitRun + "ms" + " -Approx Memory Usage in Bytes: " + setBits.getApproxMemoryUsage());
	}
}

Some Bench marking Results of all 4 types

RESULT1

Benchmark Size: 100 X 100
Benchmark Runs: 100

Running Benchmark For BooleanBitFlagInt -BUCKET SIZE: 155
Running Benchmark For BooleanBitFlagLong -BUCKET SIZE: 78
Running Benchmark For BooleanFlag -BUCKET SIZE: 4950
Running Benchmark For BooleanBitsetFlag -BUCKET SIZE: 1

Benchmark For BooleanBitFlagInt -RUNS: 100 -TIME: 12.933322ms -Approx Memory Usage in Bytes: 620
Benchmark For BooleanBitFlagLong -RUNS: 100 -TIME: 13.420231ms -Approx Memory Usage in Bytes: 624
Benchmark For BooleanFlag -RUNS: 100 -TIME: 12.178276ms -Approx Memory Usage in Bytes: 4950
Benchmark For BooleanBitsetFlag -RUNS: 100 -TIME: 17.690512ms -Approx Memory Usage in Bytes: 4992

RESULT2

Benchmark Size: 1000 X 1000
Benchmark Runs: 100

Running Benchmark For BooleanBitFlagInt -BUCKET SIZE: 15610
Running Benchmark For BooleanBitFlagLong -BUCKET SIZE: 7805
Running Benchmark For BooleanFlag -BUCKET SIZE: 499500
Running Benchmark For BooleanBitsetFlag -BUCKET SIZE: 1

Benchmark For BooleanBitFlagInt -RUNS: 100 -TIME: 452.11435ms -Approx Memory Usage in Bytes: 62440
Benchmark For BooleanBitFlagLong -RUNS: 100 -TIME: 449.2133ms -Approx Memory Usage in Bytes: 62440
Benchmark For BooleanFlag -RUNS: 100 -TIME: 410.08444ms -Approx Memory Usage in Bytes: 499500
Benchmark For BooleanBitsetFlag -RUNS: 100 -TIME: 514.00934ms -Approx Memory Usage in Bytes: 499520

RESULT3

Benchmark Size: 1000 X 1000
Benchmark Runs: 1000

Running Benchmark For BooleanBitFlagInt -BUCKET SIZE: 15610
Running Benchmark For BooleanBitFlagLong -BUCKET SIZE: 7805
Running Benchmark For BooleanFlag -BUCKET SIZE: 499500
Running Benchmark For BooleanBitsetFlag -BUCKET SIZE: 1

Benchmark For BooleanBitFlagInt -RUNS: 1000 -TIME: 4436.8813ms -Approx Memory Usage in Bytes: 62440
Benchmark For BooleanBitFlagLong -RUNS: 1000 -TIME: 4194.7773ms -Approx Memory Usage in Bytes: 62440
Benchmark For BooleanFlag -RUNS: 1000 -TIME: 4012.772ms -Approx Memory Usage in Bytes: 499500
Benchmark For BooleanBitsetFlag -RUNS: 1000 -TIME: 5003.187ms -Approx Memory Usage in Bytes: 499520

[jonjava]

This looks awfully complicated for a rather simple/straightforward thing - then again I’m not really sure what this is.

What’s its purpose? What’s going on? :L

[quote]a code snippet for setting and checking if two pair of individual ID’s have been set.
[/quote]

[quote]Java implementation of the BitFlags found in RealTime Collision Detection Book (Excellent Book!).
[/quote]
Checking bit flags is a rather trivial task what’s going on?

[Roquen]

Look at the example: It sets a bit based on a pair of integers. Assume the set is empty and ‘a’ & ‘b’ are integers (within size), then set(a,b) sets a single bit for the pair. so check(a,b) and check(b,a) will return true, everything else false.

[sproingie]

The example doesn’t make it clear that it sets exactly one unique bit per pair. Still not entirely sure what the use of that is unless you can scan down the array like a bitmap index and construct pairs from it. I imagine the book has a more fleshed out use case?

[jonjava]

So the size is the maximum number of unique ID’s possible in the system. And for each pair of ID’s you need to single out a unique bit?

So say a 100 unique ID’s would give us [((100 * (100 - 1) / 2) + 31) / 32] = 155 ints of data = 4981 bits.

And because each ID can’t pair with itself and an already paired pair can’t be paired you can have a unique amount of 99+98+97…+2+1 == n(n+1)/2 == 4950 pair combos.

So each pair combo should indeed have its own unique bit.

The uncommented code makes this atrocious to decipher. I’m not even sure I’ve got it right.

bitIndex = min * (2 * size - min - 3) / 2 + max - 1;
mask = 1L << (bitIndex & 31);
(bits[bitIndex >> 5] & mask)

Is quite a handful to wrap your head around.

I don’t know why this is useful? Surely there are better ways to accomplish the scenario that’s described. Blockmaps for dividing a world into smaller pieces of buckets holding instances to check for collision makes sense but when does this come into use and in what sort of logical architecture?

[Roquen]

For normal instantaneous or continuous collisions…you wouldn’t. My guess is that could be for tracking in a real physics engine…but don’t quote me on this.

[appel]

Your code is unreadable, you need to explain it to use like we are babies what you’re doing.

Have you considered BitSet?

And then again, is it such a game-killing overhead to check for collisions twice?

[ctomni231]

I’m still trying to figure out how this is very useful for collisions. Even if you had to check multiple sets of objects against each other, wouldn’t you just do it by checking an array twice. Below is a very lightweight example if all the hitboxes were 1x1 pixel each.

int[] hitbox = new int[<enter valid number here>];

for( int i = 0; i < hitbox.length; i++ ){
    for(int j = i; j < hitbox.length; j++ ){
        if( hitbox[i] == hitbox[j] ){
             // Do something when it collides
        }else{
             // Do something when it doesn't collide (optional)
        }
    }
}

Even if you had flags for objects, I an still trying to grasp how this method would be any quicker or easier than just a straight check. Maybe I just need more information, or maybe there is something I’m missing. I’m trying to stay optimistic here ::).

[DrHalfway]

Sorry guys, I checked this thread last night and no replies, wake up this morning and there seems to be a whole lot of arguments going around! I’ve updated the above code with some comments, hopefully they clarify on how the code works. As for as where the code is useful, it all depends on your implementations of the “Game” or “GameEngine”, for us, it was something that was extremly useful.

Consider a Scene of 100 Dynamic GameObjects, just moving around doing their own thing. Our engine at this point performs collision detection in steps.

First Step -> Insert or update the GameObjects into a BroadPhase Collision System, We use a Grid and a variant of Quadtree
Second Step -> The BroadPhase does a sweep and build a list of potential “pair-pair” Collisions
Third Step -> The NarrowPhase detector takes this list, performs a bounding volume test as an early “out” reducing the size of the list
Fourth Step -> A more expensive Collision Test is performed on the rest of the list, which generates more accurate data needed for physics and such
Fifth Step -> Resolution is performed on the data generated on the fourth step, when needed callbacks are performed, telling the “user” that something happened

The problem is during the 2nd step, where potential pair-pair collisions are generated, depending on your implementation of the Broadphase, The system may generate pairs which have already been generated
previously, especially if you have an implementation of a Grid for example, where a single object can overlap multiple grid cells.

So we use something similar to the above bitflags to check first to ensure such a pair has not been added to the list, and if it has, its simply ignored, saving precious frame time and simplifying the entire collision process.

Hope that answered a few questions =]

[sproingie]

Great explanation. That book sounds pretty awesome

[jonjava]

+1

[Roquen]

OP: Showing up and posting code straight away = awesome. Minor notes on your code: since java doesn’t have unsigned (and I don’t know if static analysis will change it) I’d change the divides by power-of-two to shifts. Likewise mask doesn’t need to be a long. Also it could be interesting at the end of your project to test a variant which is backed by longs instead of ints (assuming 64-bit VM).

WRT: Usage. Personally I don’t THINK I’d go this route (don’t take this to mean I think you should change something working…if it works, move on). Assuming uniform grid and 2D (to keep things simple), then grid-based sweeping handles objects which cross boundaries (as you note, the need is implementation specific…I’m just providing details for everybody). Potential collision from broadphase I’d place in a container (probably an ArrayList). Why? On building you’re only performing writes on linear memory. Narrowphase digests this list (linear reads) and spews into a different (say ArrayList).

[Nate]

BitSet uses longs for performance, probably you should to. Using bits saves memory, but is likely slower than using booleans.

[DrHalfway]

Thanks for the feedback guys, i’ve updated the benchmark and included a (long) version above.

Question, is long 64 bits or 32 bits in Android Platform? and is it always 64Bit on Desktop or depends on VM and OS? (my Java knowledge is fairly limited)

[sproingie]

Long is always 64 bits on any Java, including Android.

[DrHalfway]

I updated the code above to the latest version we use in the engine, Due to the concerns raised before in terms of speed I’ve taken the time to create 4 versions using 4 different storage methods.

1D Boolean Array
1D Int Array
1D Long Array
Using BitSet as suggested earlier in post.

According to benchmark, the fastest method is a straight 1D Boolean Array while slowest method is BitSet. In higher runs of the benchmark using larger data types of 1000x1000 potential pairs, The difference in speed between BitFlag using Long and 1D Boolean Array is only approx 5-10% compared to memory usage of (approx) Long using 62440 bytes vs Boolean 499500 bytes. Assuming of course the VM gives 8 bits (1 byte) per boolean value.

Use it how you will gentlemen ;D

~DrHalfway

[Roquen]

Note that micro-benchmarking is hard. You’re test case doesn’t seem likely to reflect a real world access pattern…so nobody should read too much into these numbers.