Introduction

In class you have learned how to store 1-dimensional data hierarchically using binary search trees, which allow for fast search operations. One of the primary search operations we’ve looked at so far is the find(x) operation, which finds whether the parameter x is or is not in the tree. Pseudocode for a recursive find operation looks something like:

public boolean find(x):
    return find(x, root)

private boolean find(x, node):
    if node == null:                    // x is not in the null tree.
        return false
    else if node.element() == x:        // we found it!
        return true
    else if x < node.element():
        return find(x, node.left())     // Look in the left subtree
    else:
        return find(x, node.right())    // Look in the right subtree

Now, consider the following modified version of the search problem. Instead of finding just a single particular element x in our tree, we wish to find all elements that fall within a certain range. For instance, all elements in the range [7, 25]. This is called the 1D range search problem. We modify the pseudocode above to solve this problem in the following way (in the code below min represents the minimum value of our range, and max is the maximum value).

public List findInRange(min, max):
    List foundList = new List()
    findInRange(min, max, foundList, node)
    return foundList

private void findInRange(min, max, foundList, node)
    if node == null:
        return
    else if min <= node.element() and node.element() <= max:
        foundList.add(node.element())
        findInRange(min, max, foundList, node.left())
        findInRange(min, max, foundList, node.right())
    else if min > node.element():
        findInRange(min, max, foundList, node.right())
    else:
        findInRange(min, max, foundList, node.left())

Take a minute to understand how the code above works, and the differences between it and the normal find(x) operation. The biggest difference is that if the element at the current node falls within the range [min, max], then we have to recurse on both the left and right subtrees. Why? Suppose our range is [5, 10] and the element is 7. The left subtree could possibly contain a 6, which would fall in the range, and the right subtree could possibly contain a 9, which would fall in the range. Thus, I must recursively search on both sides. Only in the event that x is outside the range, can I recurse on only one node.

The binary search tree discussed above allows for 1-dimensional data to be stored and searched. In this PA, you will code a data structure for storing 2-dimensional data and performing 2D-range searches. The data structure is called the quad-tree (because each node will have four, rather than two children).

Before explaining quad-trees, let’s first take a look at the application you are coding.

Boxian Battalion Blaster

Starter Code

• PA4Starter.zip

Setting

The Boxian republic is in shambles after a disastrous election between a blockhead and a square, causing many (including you) to question the now ancient overthrow of the Polygonal Empire’s monarchical sovereignty over the Boxian galaxy. Due to a lengthy philosophical conversation with a collegial colleague on the issue, you’ve gone full-on Royalist, and decided to single handedly restore the Queen’s rule to the Boxian lands. The Boxians, always ready to take a hand grenade to a fist fight have sent an entire battalion against your lone fighter ship. Fortunately, you are the first scientist-warrior to have invented projectile weapons, so the best they can do is ram you with their Box-like vessels. Their technology is good enough, however, to make them stronger in numbers, particularly when their ships overlap. Since overlapping ships are harder to damage, your heads-up display colors overlapping Boxian ships green, and lone (easier to destroy) Boxian ships white. Can you defeat the oncoming hordes and renew the Sovereign’s reign? (You can’t, since you can never win this game, but you can try… it’s more of a Greek Tragedy than a Happy Ending.)

Controls

Your ship appears on the left side of the screen (red box).

Control your ship with the up and down arrows to avoid being hit by the boxians.

Fire your projectile weapon using the space bar, but watch out. Running out of ammo incurs an interminable 5 second reload.

Collision Detection (SpriteCollisionSet ADT)

Many games (and other types of simulations) include some type of collision detection. Collision detection is the problem of detecting when some set of simulated physical objects collide or intersect. In our Boxian game, we need to test for collisions between a few types of objects.

• We need to detect collisions between Boxians.
• We need to detect collisions between projectiles and Boxians.
• We need to detect collisions between the player’s ship and Boxians.
• There is also a star field that is drawn in order to give some “atmosphere” to the game. Collisions between various star bits are detected, and colliding star are drawn in a different color. This creates a twinkling effect on the star field (and also adds a lot of computation).

All of these objects are bounded by an axis aligned bounding box on the screen.

To implement all of the various objects, we have a Sprite class that serves as the parent class to any object that is going to be drawn on the screen. The Sprite class inherits the BoxIntersectable interface, which is the interface for any object with a bounding box that can be tested for intersection among other BoxIntersectable objects.

In order to manage collision detection between various BoxIntersectable objects, you will provide two implementations to the CollisionSet. The CollisionSet is a set of objects for which collisions can be tested and detected. The ADT for the CollisionSet is as follows:

• build(List<E> items): adds all items in the items list to the set.
• add(E item): adds item to the set.
• remove(E item): removes the sprite from the set and returns true if it exists; otherwise, returns false.
• clear(): clears all items from the set.
• findIntersecting(Box box): find all items that intersect the box. Use the .intersects(box) method of the Box class for testing intersections.
• contains(E item): returns true if the item is in the set
• size(): returns the number of items in the set

Additionally, a collision set is Iterable, and thus you must define an iterator() method that allows for iterating over all sprites in the set. NOTE: you must support the removal method in your iterator.

First Implementation: Array based

Your first task is to implement the CollisionSet ADT using an ArrayList for storing the sprites. Implement these in the ArrayCollisionSet class.

Once this is implemented, the game should run by loading the GameFrame class.

On our test machine the code runs at about 20 frames per second. Your mileage may vary.

Second Implementation: Quad-tree based

For the second implementation, you are going to code a quad-tree. A quad-tree is a data structure for storing and searching 2D data. In our case we want our quad-tree to store 2D axis-aligned rectangles (or “boxes”) and support the operation of finding all boxes that intersect a given query region.

Each node in a quad-tree represents a rectangular area of space. The rectangular area of space covered by a particular node is called the node’s region and in the starter code is stored in the region attribute. Sprites are only stored at the leaf nodes of the tree. A given sprite is stored in every leaf node whose region it overlaps.

A leaf node of depth less than MAX_DEPTH stores from 0 up to MAX_ITEMS nodes. If the number of nodes in a given leaf exceeds MAX_ITEMS then the node must be split. A node is split by dividing its region into four equal quadrants: the north-east, north-west, south-east, and south-west quadrant. Child quad-tree nodes are created for each quadrant, and each item in the current node is recursively added to any quadrant node that it’s bounding box overlaps. A leaf node that is already at the MAX_DEPTH is never split.

The following PDF gives an example of adding 5 boxes to a quad-tree where MAX_ITEMS is 2: Example 1 which illustrates this concept.

Range searching is similar to range searching in binary search tree. The query is a Box object representing the search area. At each internal node, the query box is intersected with the region for the north-east, north-west, south-east, and south-west child nodes. We then recursively search in any node whose region intersects the query node. For a leaf node, simply loop over the sprites stored in the leaf and for any that intersect the query box add them to a return output set.

Removal is similar to searching: for a given BoxIntersectable, recursively find every leaf node whose region intersects the BoxIntersectable’s bounding box, then remove the BoxIntersectable from the node’s items set. For this PA you do not need to consolidate nodes on removal.

Code Overview:

You need to modify the following files:

• ArrayCollisionSet.java: implement the CollisionSet ADT using an array list.
• QuadTreeCollisionSet.java: implement the CollisionSet ADT using a quad-tree. This should store a single root node of type QuadTreeNode.
• QuadTreeNode.java: finish implementing the QuadTreeNode and use your implementation in QuadTreeCollisionSet.
• GamePanel.java: Once you have implemented QuadTreeNode, you can change the game from using ArrayCollisionSets to QuadTreeCollisionSets by uncommenting the return statements in newBoxianSet() and newStarSet().

Other files:

• Box.java: class for storing an axis aligned box. Has methods for getting the minimum and maximum x and y coordinate bounds of the box and testing whether a box intersects another box.
• BoxIntersectable.java: interface for any object that allows testing of its intersection with a Box.
• BoxianSprite.java: the class for a boxian fighter ship sprite.
• GameFrame.java: the main class.
• Interval.java: a class for storing 1-dimensional intervals and testing interval intersections.
• LaserSprite.java: the sprite for the laser weapon projectiles.
• PlayerSprite.java: the player’s sprite (stores the players health, handles player motion, etc.).
• Sprite.java: the parent class for all sprites.
• StarSprite.java: the sprite class for the background stars.