# 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

## 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`ArrayCollisionSet`

s to`QuadTreeCollisionSet`

s 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.