4
\$\begingroup\$

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 &lt; 0
     * or &gt; 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;
            }
        }
    }
}
  1. Class CollisionSet is simply a class that extends TreeSet, this is a work around, since arrays in Java and generics don't work together.
  2. CollisionRecord is basically a Collidable with a timestamp.
  3. Collidable (interface) is a form of Sprite that has the ability to collide with other Collidables.
  4. 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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I hope you get some helpful answers. \$\endgroup\$ – SirPython Jan 12 '16 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.