I have started a project on my free time were I'm writing a 2D game engine in Java. One of the more challenging and interesting aspects of such a project is collision detection between sprites on the screen. I have previously written a game engine in C++ were the more naive approach (O(n2)) of using a list of all sprites and iterating over it in nested for loops was used. This time I wanted something better in terms of performance, and if possible, also thread safety.
Just as I finished programming this data structure I became aware of the data structure called Quadtree. Unlike my CollisionTable, it must as far as I understand, be completely cleared and all elements be inserted again for each new frame where the sprites has moved. This is something that I wanted avoid with my CollisionTable.
There are probably a lot of things that can be improved in my CollisionTable, but since my primary reasons for creating it was performance related, I am most curious what you think is good/bad from a performance point of view and what can be improved. With that said, all input is of course welcome!
As far as the JavaDocs go, I know it's a bit verbose and some of the comments describes the internal operation in the methods, which is usually discouraged. But since I wrote the JavaDocs specifically for this code review, I chose not to hold back.
I have included all the code that should be relevant for this data structure here. The entire project can be found on GitHub.
/**
* This class implements a data structure with the use of hash functions for
* {@link Collidable} objects, in order to better perform collision calculations
* at a lower performance cost. The goal is to reduce the time complexity
* compared to more naive approaches as usually are O(n<sup>2</sup>).
*
* The CollisionTable does not perform any actual collision detection, it only
* tries to reduce the amount of elements that are used in the calculation of
* each collision detection.
*
* Unlike many other more complex data structures/solutions to this problem (not
* the naive O(n<sup>2</sup>) ones) this implementation is not intended to add
* or recreate the entire data structure upon each frame, but rather let each
* {@link CollisionRecord} stay in the data structure until it's considered obsolete.
*
*/
public class CollisionTable
{
private final static int[] PRIMES = {23, 53, 97, 193, 389, 769, 1543,
3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241,
786433, 1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
private CollisionSet[] collidableArray;
private volatile int arraySize = 11;
private volatile int primeIndex = -1;
private volatile int count = 0;
private final long maxTime;
private final Lock hashLock = new ReentrantLock();
private final Condition hashFinished = hashLock.newCondition();
private final BlockingQueue<Collidable> incoming = new ArrayBlockingQueue<Collidable>(300);
/**
* Constructor for this class.
*
* @param elementCount the expected amount of elements that this data
* structure will hold.
* @param maxTime the maximum amount of time in nanoseconds that may elapse
* before a stored position from a {@link Collidable} object is considered
* obsolete and will be removed. What value that is appropriate depends on
* the pace of the {@link Collidable} objects in this game. Setting this
* value to high will generate less overhead since each
* {@link CollisionRecord} can be kept for a longer time, but it also
* increases the chance of missing collisions because the
* {@link CollisionRecord} instances in this table will not updates its
* position as often.
*/
public CollisionTable(final int elementCount, final long maxTime)
{
setArraySize(elementCount / 3);
collidableArray = new CollisionSet[arraySize];
this.maxTime = maxTime;
}
/**
* Constructor for this class. This constructor will use the default array
* size of 11 upon initialization and set the max time for a
* {@link CollisionRecord} to 0.1 seconds.
*/
public CollisionTable()
{
this(0, PhysicsEngine.ONE_SECOND / 10);
}
/**
* Adds a new to {@link Collidable} to the internal {@link Queue}.
*
* @param collidable the {@link Collidable} object that should be added.
* @return true if it was successfully added to the queue, else false.
*/
public boolean add(Collidable collidable)
{
return incoming.offer(collidable);
}
/**
* Poll the queue for new {@link Collidable} objects and add it to the
* table, if it's not empty.
*/
synchronized void addFromQueue()
{
if(incoming.isEmpty())
return;
if(size() > arraySize * 5)
expand();
while(!incoming.isEmpty())
{
addToTable(new CollisionRecord(incoming.poll()), collidableArray);
count++;
}
}
/**
* Gets the size for this CollisionTable.
*
* @return returns the current amount of {@link CollisionRecord} instances,
* not taking into account the amount of objects in the queue.
*/
private int size()
{
return count;
}
/**
* This method will retrieve all nearby {@link Collidable} objects (wrapped
* in a {@link CollisionRecord}) that are candidates for a collision with
* the given parameter {@link Collidable}.
*
* @param collidable the {@link Collidable} we want to find collision
* candidates for.
* @param scanPercentage determines how big part of the internal array that
* should be scanned for likely candidates, where 0 means the absolute
* minimum scan range and 1 will check the entire array for elements.
*
* Increasing the number will increase the time complexity and reduce the
* performance but also reduce the chance of missing any collisions. Setting
* this to 1 will give a time complexity of O(n<sup>2</sup>) if this method
* is called for every {@link Collidable}, but with more overhead than a
* simple double for-loop. It is recommended that this parameter is set as
* low as possible, as long as no collisions are missed
* @return a set containing {@link CollisionRecord} of all collision
* candidates.
* @throws IllegalArgumentException if <code>scanPercentage</code> is < 0
* or > 1.
*/
public Set<CollisionRecord> getCollidables(final Collidable collidable, float scanPercentage)
{
if(scanPercentage < 0)
throw new IllegalArgumentException("Parameter scanPercentage cannot be negative.");
if(scanPercentage > 1)
throw new IllegalArgumentException("Parameter scanPercentage cannot be greater than 1.");
final Set<CollisionRecord> collisionCandidates = new HashSet<CollisionRecord>();
hashLock.lock();
waitForHash();
final int hashRadius = Math.round(arraySize * scanPercentage);
final int index = hashIndex(collidable, collidableArray);
for(int i = index - hashRadius; i <= index + hashRadius; i++)
{
if(i < 0)
i = 0;
final Set<CollisionRecord> set = collidableArray[i % collidableArray.length];
if(set != null)
collisionCandidates.addAll(removeObsolete(set));
}
hashLock.unlock();
return collisionCandidates;
}
/**
* Removes all instance of {@link CollisionRecord} which is considered
* obsolete. If the {@link CollisionRecord} is considered obsolete but
* {@link Collidable#isReadyToRemove()} returns false, then it will be added
* to the queue in order to receive a new {@link CollisionRecord}.
*
* @param collisionCandidates a set of {@link CollisionRecord}.
* @return the remaining {@link CollisionRecord} instances which are not
* considered obsolete.
*/
private Set<CollisionRecord> removeObsolete(Set<CollisionRecord> collisionCandidates)
{
final Iterator<CollisionRecord> recordIterator = collisionCandidates.iterator();
while(recordIterator.hasNext())
{
final CollisionRecord record = recordIterator.next();
if(record.isObsolete(maxTime) || record.getCollidable().isReadyToRemove())
{
recordIterator.remove();
count--;
if(!record.getCollidable().isReadyToRemove())
add(record.getCollidable());
}
}
return collisionCandidates;
}
/**
* Adds a {@link CollisionRecord} to array of {@link CollisionSet}.
*
* @param record the {@link CollisionRecord} that should be added.
* @param array the array that the record should be added to.
* @return true if it was successfully added to the {@link CollisionSet} at
* the given array index, else false.
*/
private boolean addToTable(CollisionRecord record, CollisionSet[] array)
{
try
{
hashLock.lock();
final int index = hashIndex(record.getCollidable(), array);
if(index >= array.length)
throw new ConcurrentModificationException("Illegal state: Trying to insert in index "
+ index + " but size of array is " + array.length + "(" + arraySize + ")\n");
if(array[index] == null)
array[index] = new CollisionSet();
return array[index].add(record);
}
finally
{
hashLock.unlock();
}
}
/**
* Expands the size of the internal array.
*/
private void expand()
{
hashLock.lock();
advanceTotNextPrime();
rehashTable();
hashFinished.signalAll();
hashLock.unlock();
}
/**
* Shrinks the size of the internal array. This method is currently not
* used.
*/
private void shrink()
{
hashLock.lock();
previousPrime();
rehashTable();
hashFinished.signalAll();
hashLock.unlock();
}
/**
* Waits for this class {@link ReentrantLock} to be released that is locking
* the internal array.
*
* A more compact version of {@link Condition#await()} with exception
* handling taken care of, so this will not have to repeated every time
* <code>hashFinished.await()</code> would be called.
*/
private void waitForHash()
{
try
{
while(collidableArray.length != arraySize)
hashFinished.await();
}
catch(InterruptedException e)
{
hashLock.unlock();
e.printStackTrace();
}
}
/**
* Creates a new array when the conditions require it change size. All
* elements will have to be rehashed to fit in the new arrays size.
*/
private void rehashTable()
{
final CollisionSet[] rehashedArray = new CollisionSet[arraySize];
for(int i = 0; i < collidableArray.length; i++)
{
final CollisionSet set = collidableArray[i];
if(set != null)
for(CollisionRecord record : set)
if(!record.getCollidable().isReadyToRemove())
addToTable(record, rehashedArray);
}
collidableArray = rehashedArray;
}
/**
* Computes the hash for a {@link Collidable} and converts it to an index
* matching the size of an array.
*
* @param collidable the {@link Collidable} to compute the hash for.
* @param array the array which length has to be taken into consideration.
* @return an index based on the hash for the {@link Collidable} and is
* within bounds for the array.
*/
private int hashIndex(Collidable collidable, Object[] array)
{
final int hash = computeHash(collidable.getCenterOfSprite());
final int index = Math.abs(hash % array.length);
return index;
}
/**
* This is where the magic happens.
*
* Computes the two dimensional data of a {@link Coordinate2D} (x and y
* value) so it can be sorted into a one dimensional array. This is done by
* measuring the distance from the given coordinate and three other
* coordinates on the screen and with those variables compute a hash. The
* purpose of this hash is that it should turn out the same (or very
* similar) for coordinates that are located close to each other.
*
* @param screenCoordinates the coordinates that will be computed.
* @return the hash for this coordinate.
*/
private int computeHash(Coordinate2D screenCoordinates)
{
final double d1 = screenCoordinates.distance(0, 0);
final double d2 = screenCoordinates.distance(0, GameSettings.heightWindow);
final double d3 = screenCoordinates.distance(GameSettings.widthWindow, GameSettings.heightWindow);
final double diff = d1 - d3;
final double d2Squared = Math.sqrt(d2 + 1);
final double result = diff / d2Squared;
return (int) result;
}
/**
* Changes the array size (on next rehash of table) to the next greater
* prime number.
*/
private void advanceTotNextPrime()
{
arraySize = PRIMES[++primeIndex];
}
/**
* Changes the array size (on next rehash of table) to the next lesser prime
* number.
*/
private void previousPrime()
{
arraySize = PRIMES[--primeIndex];
}
/**
* Finds the next prime number that is equal or greater to the given
* argument, and sets the future array size to that number.
*
* @param initialApproximateArraySize the number that should be compared to.
*/
private void setArraySize(int initialApproximateArraySize)
{
if(initialApproximateArraySize < 11)
return;
for(int i = 0; i < PRIMES.length; i++)
{
if(PRIMES[i] >= initialApproximateArraySize)
{
arraySize = PRIMES[i];
primeIndex = i;
return;
}
}
}
}
- Class CollisionSet is simply a class that extends TreeSet, this is a work around, since arrays in Java and generics don't work together.
- CollisionRecord is basically a Collidable with a timestamp.
- Collidable (interface) is a form of Sprite that has the ability to collide with other Collidables.
- Coordinate2D can be considered equivalent to Java FX Point, except it's not immutable.
public class CollisionRecord implements Comparable<CollisionRecord>
{
private final Collidable collidable;
private final long timestamp;
public CollisionRecord(final Collidable collidable)
{
this.collidable = collidable;
this.timestamp = System.nanoTime();
}
public Collidable getCollidable()
{
return collidable;
}
public long getTimestamp()
{
return timestamp;
}
public boolean isObsolete(long nanoSeconds)
{
return System.nanoTime() - timestamp > nanoSeconds;
}
@Override
public int compareTo(CollisionRecord o)
{
return (int) ((this.timestamp - o.timestamp) % Integer.MAX_VALUE);
}
}
I think this is all the code that is relevant for the data structure.
