CS 300: Implementing Asteroid ADT for Collision Detection Simulation

This assignment requires the implementation of an Asteroid Abstract Data Type (ADT) for a collision detection simulation, drawing inspiration from the classic Atari game Asteroids. The task involves designing the Asteroid ADT in C++ to represent asteroids as convex polygons, using provided ADTs for Points and LineSegments. The implementation must support key operations: construction (initializing asteroids with vertices), moving (translating asteroids across a simulated screen), center calculation (finding the center of gravity), and collision detection (determining if two asteroids intersect). The input to the program consists of descriptions of two asteroids, including the number of vertices and their coordinates, along with movement vectors. The output includes the coordinates of each vertex at each time step and a final message indicating whether a collision occurred. The goal is to create a functional Asteroid ADT that integrates with the provided simulation code, enabling accurate collision detection and visualization.

1. Problem Description
This assignment hearkens back to the classic Atari video gameAsteroids, although the basic
problem it addresses, collision detection among moving objects, is common to many games.
It is common to represent objects as polygons. If this seems a bit crude, that is because the
example shown here uses very fewvertices (“corner” points). With enough points, quite
sophisticated shapes can be rendered. Filling in the shape with colors, textures, or picture
bitmaps often disguises the fact that the outer edges are actually quite simple. (Even 3-D
models of game objects are often formed by stitching together polygonal plates.)
In this assignment, you will be given most of a simulation that moves two such shapes across
a simulated screen. We will refer to the shapes as “asteroids,” though they could just as
easily represent the rocket, flying saucer, or even the bullets fired by the rocket in this game.

You are being given the driver (main program) for the simulation (collision.cpp) and
the LineSegment and Point ADTs. Your task is to design and implement the Asteroid ADT
so that it works with the provided code.
An asteroid will be represented as a polygon, so your ADT implementation will need to store
either the vertices of the polygon or the line segments that make up the perimeter of the
polygon. You will be provided with ADTs for both Points and LineSegments and are
expected to make use of them in your code.
To simplify the problem a bit, we will restrict this simulation to convex polygons - polygons
in which all the corners point “out” away from the center. (The asteroids and rocket in the
picture are all concave polygons.) We will also not permit polygons that
aredegenerate (polygons with no internal area because the edges lie directly on top of one
another, e.g., a rectangle of width w > 0 but zero height ).
The major operations you must support with your Asteroid ADT are:
 Construction: you will need a constructor that builds a new Asteroid object, given an
array of Points representing its vertices and an integer counter indicating how many
vertices are in the array.
 Moving: you will need a function to move your asteroid. This function will be given
the amount to move in the x and the y directions as parameters.
To move a polygon without altering its shape, you add the same value to the x
coordinates and/or to the y coordinates of each vertex.
 Center: you will need a function to compute the center (technically the “center of
gravity”) of your asteroid.
You can find this location (cx,cy) by computing cx as the average of
the x coordinates of all vertices and cy as the average of the y coordinates of all
vertices.
 Detecting collisions: you will need a function to determine if your asteroid is colliding
with another.
Two asteroids are colliding if any vertex of either asteroid is inside the polygon of the
other asteroid. (This is also a bit of an over-simplification. For example, two
rectangles forming a cross or “+” shape would not be judged as colliding by this
definition. But if we use a small enough time step compared to the speed at which the
objects are moving, we should never see those kinds of exceptions unless we have
first seen at least one vertex inside the other polygon.)

You can determine if a point P is inside a convex polygon by checking to see if, for
every line segment L along the perimeter of the polygon, P is on the same side of that
line L as is the center of the polygon.
 Printing: The print(out) function should print the coordinates of each vertex in the
asteroid, all on one line, with some form of blank space or punctuation separating
each number.
For the exact details on the names and parameters of these functions, you will need to
examine the application code that manipulates asteroids in this simulation. Don’t be afraid to
use the compiler to help you on this. Instead of freaking out over messages about
undefined/undeclared symbols and function calls with “no match for” the supplied
parameters, recognize that these are the compiler’s way of directing you both to the things
that are missing from the program and the places where they are being used.
2.1 Input
Input for this program may be taken from the standard input or, if a file is named as a
command line parameter, input is read from that file.
Input consists of a description of two asteroids and of their rate of movement.
1. The description of each asteroid begins with an integer indicating how many points
constitute the vertices of the polygon used to represent that asteroid.
2. This is followed by twice that number of floating point numbers. Each successive pair
of these floating point numbers represents the (x,y) coordinates of one vertex of the
polygon. The points are listed consecutively as they would be encountered when
tracing the circumference of the polygon. The points might be given in either
clockwise or counter-clockwise order.
The polygon is “closed”, i.e., the last vertex is assumed to connect back to the first
vertex.
3. This is followed by an additional pair of floating point numbers that describe the
asteroid’s movement. The two numbers give the amount of movement in the x and y
directions, respectively, on each time step during the simulation.
For example, the input
3 100 100 120 100 120 120 100 120 -1.0 0.5

describes a perfect square, 20 units on a side, initially located with its lower left
corner at (100,100). After one time step, the polygon will move so that the lower left
corner will be at (99,100.5) - i.e., one unit to the left and half a unit up.
4. The entire input consists of two repetitions of the data described above, portraying a
pair of asteroids.
2.2 Output
The program runs a simulation, eventually printing a message indicating whether the two
asteroids collided before moving off the screen.
For example, given the input
7 50 0 125 0 150 100 75 150 25 150 0 125 0 50 5.0 7.0 6 325 300 375
300 425 350 375 375 325 375 300 325 -10.0 -2.5
the output will be
0 poly [(55,7), (130,7), (155,107), (80,157), (30,157), (5,132), (5,57)]
0 poly [(315,297.5), (365,297.5), (415,347.5), (365,372.5), (315,372.5),
(290,322.5)]
1 poly [(60,14), (135,14), (160,114), (85,164), (35,164), (10,139), (10,64)]
1 poly [(305,295), (355,295), (405,345), (355,370), (305,370), (280,320)]
2 poly [(65,21), (140,21), (165,121), (90,171), (40,171), (15,146), (15,71)]
2 poly [(295,292.5), (345,292.5), (395,342.5), (345,367.5), (295,367.5),
(270,317.5)]
3 poly [(70,28), (145,28), (170,128), (95,178), (45,178), (20,153), (20,78)]
3 poly [(285,290), (335,290), (385,340), (335,365), (285,365), (260,315)]
4 poly [(75,35), (150,35), (175,135), (100,185), (50,185), (25,160), (25,85)]
4 poly [(275,287.5), (325,287.5), (375,337.5), (325,362.5), (275,362.5),
(333,312.5)]
5 poly [(80,42), (155,42), (180,142), (105,192), (55,192), (30,167), (30,92)]
5 poly [(265,285), (315,285), (365,335), (315,360), (265,360), (240,310)]
6 poly [(85,49), (160,49), (185,149), (110,199), (60,199), (35,174), (35,99)]
6 poly [(255,282.5), (305,282.5), (355,332.5), (305,357.5), (255,357.5),
(230,307.5)]
7 poly [(90,56), (165,56), (190,156), (115,206), (65,206), (40,181), (40,106)]
7 poly [(245,280), (295,280), (345,330), (295,355), (245,355), (220,305)]
8 poly [(95,63), (170,63), (195,163), (120,213), (70,213), (45,188), (45,113)]
8 poly [(235,277.5), (285,277.5), (335,327.5), (285,352.5), (235,352.5),
(210,302.5)]
9 poly [(100,70), (175,70), (200,170), (125,220), (75,220), (50,195), (50,120)]
9 poly [(225,275), (275,275), (325,325), (275,350), (225,350), (200,300)]
10 poly [(105,77), (180,77), (205,177), (130,227), (80,227), (55,202), (55,127)]
10 poly [(215,272.5), (265,272.5), (315,322.5), (265,347.5), (215,347.5),
(190,297.5)]
11 poly [(110,84), (185,84), (210,184), (135,234), (85,234), (60,209), (60,134)]
11 poly [(205,270), (255,270), (305,320), (255,345), (205,345), (180,295)]
12 poly [(115,91), (190,91), (215,191), (140,241), (90,241), (65,216), (65,141)]

12 poly [(195,267.5), (245,267.5), (295,317.5), (245,342.5), (195,342.5),
(170,292.5)]
13 poly [(120,98), (195,98), (220,198), (145,248), (95,248), (70,223), (70,148)]
13 poly [(185,265), (235,265), (285,315), (235,340), (185,340), (160,290)]
14 poly [(125,105), (200,105), (225,205), (150,255), (100,255), (75,230), (75,155)]
14 poly [(175,262.5), (225,262.5), (275,312.5), (225,337.5), (175,337.5),
(150,287.5)]
15 poly [(130,112), (205,112), (230,212), (155,262), (105,262), (80,237), (80,162)]
15 poly [(165,260), (215,260), (265,310), (215,335), (165,335), (140,285)]
16 poly [(135,119), (210,119), (235,219), (160,269), (110,269), (85,244), (85,169)]
16 poly [(155,257.5), (205,257.5), (255,307.5), (205,332.5), (155,332.5),
(130,282.5)]
17 msg Collision at time 17
Much of this output is generated by the driver code already provided. Your task is limited to
providing the Asteroid ADT that permits this simulation to make that determination.
3.
Running the Viewer Program
The program output may carry more detail than you really want to inspect. The final “msg”
line is probably the most important in determining if your code is working.
The reason for all the detail is that this program is designed to feed a viewer that plots the
course of the moving asteroids. To run this viewer, make sure your compiled executable
(which I will assume is named “collision”), your test input file(s), and the Animator.jar file
are all in the same directory. Then from a command line (Unix or Windows) you can do
collision < yourTestInputFile > output.dat
java -cp Animator.jar Animator.Viewer < output.dat
or, in one step,
collision < yourTestInputFile | java -cp Animator.jar Animator.Viewer`
If running on Linux, you will need to be running X and may need to add “./” in front of your
program name (e.g., ./collision).