The quadtree is an important data structure for optimizing the speed of
collision detection in 2D computer games with many potential object
collision pairs. In this assignment, you will implement a quadtree, and
then create a simple simulation of 100 independently moving and
colliding squares to test your implementation. The goal of the
assignment is to develop deep proficiency with the quadtree data
structure, work with list data structures, develop a simple physical
simulation, and implement simple graphics using XNA.
For this assignment, you must create a simulation of 100 squares, each
16x16 pixels wide. Each square is initially white in color. Each square
should be given a random position on screen, and a random initial
velocity of between 0 and 5 pixels per clock tick in both x and y axes
(i.e., x and y velocity can be different from each other). Square
positions are updated every clock tick.
When squares collide, they change color to red, and remain red until
they finish colliding. When a square no longer is intersecting another
square, it reverts back to white.
A quadtree data structure of at least depth 4 must be part of the
implementation of collision detection. Square position updates must
result in updates to the quadtree, rather than a complete recomputation
of the quadtree. It is unacceptable to regenerate the quadtree in each
When a square hits the edge of the window, it should "bounce", and
thereby stay in the visible part of the playfield.
Use of the GOTO statement outside of case statement blocks is forbidden.
Submit a single zip file with
all source code, executables, and a readme file for your project on the
moodle class page. The readme file should contain precise instructions
on how to run your assignment including any text commands or keyboard
shortcuts. In some cases, we may request a demonstration of your
working assignment in order to correct your submission.
You may receive up to 15 points of extra credit by adding all of the
Make the number of squares (with no maximum number) and size of squares
controllable by the XBox 360 controller.
Have the squares bounce off one another.
Add 10 blue stationary rectangles of size 48x144 into the playfield,
and have all squares bounce off of these rectangles.
ssessment of the Quadtrees assignment focuses on two areas: correctness
(75%) and design (25%).
For correctness, assignments will be examined to ensure they correctly
implement the assignment specification. In particular:
- Is the quadtree data structure implemented correctly? Does
it correctly handle position updates and lookups? Are squares that span
multiple quadtree regions handled correctly?
- Does collision detection correctly detect collisions, even
with squares whose boundaries extend over the edge of a region in the
quadtree? Do the squares change color when a collision occurs? Does
collision checking make use of the Quadtree data structure ?
- Is the physics simulation implemented correctly? That is,
do the squares change position on each clock tick?
For design, we will examine your source code to ensure it follows
reasonable object-oriented design technique. In particular, we expect
to see a class for the quadtree, an array or list holding the squares,
and a class or structure representing each square. The quadtree data
structure should be completely separate from the display of squares
(model-view separation). That is, there should be no XNA display code
inside the quadtree class. The quadtree data structure should also be
separate from the update of square positions. That is, inside the class
or structure representing squares, there should be a method that
updates the position of the square, then calls into the quadtree to
cause an update.
- Do the squares correctly bounce at the edges of the window?
Use of the GOTO statement outside of case statement blocks is
forbidden, and will result in an assignment grade of zero.
<<< Back to Class Home Page