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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
| public class BooleanBitFlag { private final int[] bits; private final int size; public BooleanBitFlag(final int size) { this.size = size; bits = new int[((size * (size - 1) / 2) + 31) / 32]; } 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) / 2 + max - 1; int mask = 1 << (bitIndex & 31); if ((bits[bitIndex >> 5] & mask) == 0) { bits[bitIndex >> 5] |= mask; return true; } } return false; } 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; } public int bucketSize() { return bits.length; } public void clear() { Arrays.fill(bits, 0); } } |
Using is is VERY easy
1 2 3 4 5 6 7 8 9 10 11 12
| 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| public class BitFlags { public static void main(String[] args) { BooleanBitFlag bitFlag10 = new BooleanBitFlag(10); BooleanBitFlag bitFlag100 = new BooleanBitFlag(100); BooleanBitFlag bitFlag1000 = new BooleanBitFlag(1000); System.out.println("Bucket Size Of 10x10: " + bitFlag10.bucketSize()); System.out.println("Bucket Size Of 100x100: " + bitFlag100.bucketSize()); System.out.println("Bucket Size Of 1000x1000: " + bitFlag1000.bucketSize()); } } |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
|
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]; } 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; } 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; } public int getBucketSize() { return bits.length; } 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
|
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]; } 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; } 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; } 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
|
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); } 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; } 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; } public int getApproxMemoryUsage() { return bits.size(); } public int getBucketSize() { return 1; } public void clear() { bits.clear(); } public void fillFalse() { bits.clear(); } public void fillTrue() { bits.set(0, bits.size(), true); } }
|
BOOLEAN 1D ARRAY
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
|
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]; } 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; } 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; } 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
| 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); for (int i = 0; i < runs; i++) { 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); 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); 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); 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