Homework 2

Quadtrees


Due: February 18, 2010



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 clock tick.

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.

Submission

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.

Extra Credit

You may receive up to 15 points of extra credit by adding all of the following features:

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.

Evaluation Criteria

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?
  • Do the squares correctly bounce at the edges of the window?
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.

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