Collision Detection
Added on 20190925
5 Pages2383 Words284 Views



1. Problem DescriptionThis 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 3D 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 acrossa 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 theLineSegmentandPointADTs. Your task is to design and implement theAsteroidADT so that it works with the provided code.An asteroid will be represented as a polygon, so your ADT implementation will need to storeeither 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 toconvexpolygons  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 widthw > 0but zero height ).The major operations you must support with your Asteroid ADT are:Construction: you will need a constructor that builds a newAsteroidobject, 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 computingcxas the average of thexcoordinates of all vertices andcyas the average of theycoordinates of all vertices.Detecting collisions: you will need a function to determine if your asteroid is collidingwith another.Two asteroids are colliding if any vertex ofeitherasteroid is inside the polygon of the other asteroid. (This is also a bit of an oversimplification. 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.)
End of preview
Want to access all the pages? Upload your documents or become a member.