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
[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
[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
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.)
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
class inherits the
BoxIntersectable interface, which is the interface for any
object with a bounding box that can be tested for intersection among other
In order to manage collision detection between various
you will provide two implementations to the
is a set of objects for which collisions can be tested and detected. The ADT for
CollisionSet is as follows:
build(List<E> items): adds all items in the
itemslist 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
Boxclass 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
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.
You need to modify the following files:
ArrayCollisionSet.java: implement the
CollisionSetADT using an array list.
QuadTreeCollisionSet.java: implement the
CollisionSetADT using a quad-tree. This should store a single root node of type
QuadTreeNode.java: finish implementing the
QuadTreeNodeand use your implementation in
GamePanel.java: Once you have implemented
QuadTreeNode, you can change the game from using
QuadTreeCollisionSets by uncommenting the return statements in
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
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.