Untitled Document

CSC 630 - Computer Graphics System Design
Documentation for the Term Project
Sebastian Maier and Barbara Schneider

Content

The Project
Functionality
The Implementation Process
The Strong Point - Collision Detection
The Code
Results

The Project

The task was to create a game with user interaction in 3D. The user should be able to take different view points. The project should have one strong point which could be almost anything we like.

For our term project, we decided to build a labyrinth game in OpenGL. The goal for the player is to enter the labyrinth though the entrance and leave it through the exit. On his way, he can collect gold coins and a key. The labyrinth consists of two floors, where the entrance is on the first floor and the exit on the second floor. The player can get from the first floor to the second floor by using an elevator which he can only use when he has already found the key and which beams him up to the second floor.

to the top of the page

Functionality

Player movement :

Testing keys :

Key	Function
w	move forwards
s	move backwards
a	move left
d	move right
q	turn left
e	turn right

Keys	Function
y	move up
z	move down
n	position player in front of the key
m	position player in front of the elevator

to the top of the page

The Implementation Process

First we decided to build the term project on top of assignment 3, as this already had a working OpenGL framework, the possibility to read in world data from a file and some functions for texture. We changed these functions during the development, but the basics are still there.
Our first two big goals were to create the labyrinth world and to implement the movement of the player. The first one could be achieved by simply changing the world file "world.txt", and although it was a lot of work it went pretty straight forward. Although it sounds easy, the second goal proved much more difficult. The first idea was to let the camera stay at the origin all the time with the word translating and rotating around it. The implementation of forward, backward and sideward movement like this was easy, and also the implementation of a left and right turn was not difficult. But the tricky part was that as soon as we wanted to combine them, the player either still walked in the old directions when turned instead of in the direction he was facing, or he rotated around the origin instead of around himself which didn't correctly implement the turning. We then tried a lot of different possibilities: we tried to move the camera and rotate the world, rotate the camera and move the world, or implement the complete player's movement as camera movement with a fixed world. Neither of these changed anything to our problem. It was not until the very end of the project that we finally got it working. Now, like planned in the beginning, the camera always stays at the origin and the world turns and rotates around it. But the translation is now not only increasing/decreasing the x, y or z position, but the "movement vector" is rotated around the y-axis. It still took a lot of thoughts and debugging until it finally worked correctly.
The next thing was to find and load nice textures for the labyrinth. The code is done so far that all the walls have the same texture, and each floor / ceiling can have a different one. This separation can be changed easily in the file and by adding a few variables. We decided it looked nicer with the same texture for both floors, which is a darker version of the texture for the walls, and a sky with stars for the ceiling of the second floor. Like this, the labyrinth doesn't look to colorful, but you can well see the difference between the first and the second floor.
Now it was time to create items that the player can collect on his way through the labyrinth. We thought it would be nice to have a file from which all these items can be controled, so they are read in from "events.txt". There are two different kinds of items: Gold coins (item type 1) and keys (item type 2). The position and the type of each item is read in from the file and rendered in a loop. To render the coins, we used the functions gluDisk and gluCylinder, where gluCylinder creates the cylinder which is closed on both sides by disks from gluDisk. The keys are a cylinder (created in the same way as the coins) and three cubes. We thought it would be more interesting if the items rotate all the time as you then can better see what they are and as like this they attract the attention of the player, so all items rotate all the time.
Having nice coins and keys, we also wanted a sign to indicate the elevator and decided to create a rotating arrow which points up. The arrow is hard-coded as it can not be considered as an item (it cannot be collected and it exists only once) and consists of three cubes.

The plan of the finished labyrinth now looks like this:

The last part was to build the collision detection, which is first to detect if the player is hitting a wall and second to implement the different events, like finding an item, leaving the labyrinth, or using the elevator. We will go into this point in the next section.

to the top of the page

The Strong Point - Collision Detection

Like we already said in the previous direction, we used collision detection for different purposes. The first thing, of course, is that a player cannot walk through walls and therefore the collision of the player with a wall has to be detected and forbidden. The second thing is the detection of events: A message is put on the screen as soon as the player leaves the labyrinth through the entrance or the exit, and it must be detected if he finds a coin or a key or if he steps into the elevator. The cases are implemented as two different things, although the technique used is similar.

We will start with a survey of possibilities to implement collision detection.
First you can divide collision detection algorithms in a priori and a posteriori algorithms. A priori algorithms check to see if a collision wil happen before the actual collision, and a posteriori algorithms first change the position of all objects and then check if a collision has happened. Both methods have advantages: a priori algorithms have to know what will happen in the future, whereas a posteriori algorithms just work on the current set of the objects. Still, it might be difficult to react on a collision after it has happened, as it may be necessary to undo the movement and this is not always simple.

We will begin with our first problem: the player cannot be allowed to walk through the walls. What we know about this problem is that
- walls are represented as triangles, or more exactly, as the vertices of the triangles. Two following triangles create one wall.
- they have a height and a width, but no depth.

The probably easiest way would be to use the vertices of the triangles to check collision with every triangle. But this means a waste of computational time: We can always combine two triangles to a rectangle, and each rectangle can be computed only by two opposite vertices. As each triangle contains two opposite vertices, we only need one triangle to know the position of one wall. This means that we can skip every second triangle.
From this, there are three obvious possibilities to handle the problem.

1. A real a priori algorithm. Each time the player moves, we compute the distances to the next walls when moving forward, backward, left and right. We then only allow him to go this far. This computation could use the previous distances when moving, but on a turn we would have to recompute all values. We could use an algorithm to detect the intersection of a line and a plane and use it on all walls to find the nearest intersecting point. This would give us a running time of O(w) each time the player moves or turns, as all the walls have to be checked 4 times and all the other computations are constant in their running time (T(w) = 4*c1*w/2 + c2 for some constants c1 and c2). We would achieve a physically correct answer, but the computations are pretty difficult to implement.

2. A real a posteriori algorithm. We could also let the player move whereever he wants, and before rendering, we could check if he collides with a wall. This only takes a running time of O(w) each time the player moves but not on turns: T(w) = c*w/2. But we have to note here that a collision takes two 3D-objects, as the probability for the player to exactly hit the 2D wall is close to 0. This means that we have to create virtual 3D walls, creating a space around them which also cannot be hit. This space has to be deep enough such that the player cannot simply step over it. For example, if he moves a distance of 4 units each step, but the wall only has a depth of 2, it can happen that the player first is on the one side and after his movement on the other side of the wall, which is not to be allowed. We also have to think about what happens after we have detected a collision: We would have to move him out of the wall in the direction where he came from. Desirable would be that he is moved to the same position he had before.

3. These conclusions lead to the third possibility and the one we decided to use. For our game, it is not important to have a physically exact solution, a wall with a certain depth works just fine. The walls have a depth of two times the step size of the player guaranteeing he will definitely be caught in a wall when trying to pass it. We solved the problem of undoing a step like this: Each time the player moves, his potential position is calculated. We then check this position on collisions with walls. Only if no collision is detected, the player is actually moved to his new position.

Now to the second problem: Detection of events. Events can again be splitted into the items the player can collect, further leaving the labyrinth through the entrance or through the exit and the item event. The detection works similar for all of them.

First we can notice that we do not have the problem here with the a posteriori approach that we had with the walls: We do not have to undo anything on a collision. This is why we used a real a posteriori algorithm here: The player is moved to his new position, and before rendering a function takes care of event detection. Again, we do not have to build in physical accuracy: a cube around the items work well, we do not have to implement the detection of the player actually hitting a part of a key, for example, which would be much more expensive. Also, as the player is represented only as the position of his eyes, we have to keep in mind that his actual body is much bigger and therefore an exact collision detection would imply the modeling of his body. The check can be done similar to problem one: It is checked if the position of the player is inside one of the event cubes or not. If he is, the corresponding action is provoked. This gives us a running time of O(e), where e is the number of events in the labyrinth. The difference between the items and the other events is that the cube around the items is calculated dynamically around the position of the item, whereas the position of the elevator, entrance and exit cannot be changed and is hardcoded.

In general, collision detection can be more complicated than in this application. Here, only the player is moving through the labyrinth, which means that we only have to detect collision of the player with objects of the game. If there are more moving objects (for example the balls in a billiard game), the collision of all these objects have to be checked. The more of these objects we have in the world, the more effort has to be put in the algorithms to gain an acceptable running time. One of the techniques which can be used here is temporal coherence, which takes into account that physical objects most of the time do not change their position by a large distance, to decrease the number of pairs which have to be checked for collision.

to the top of the page