Labyrinth

Mark Saenger
CPE 471 Spring 2009

Project Overview

For my final design project, I decided to recreate the classic game Labyrinth. The basic idea of this game is to navigate a ball through a maze from one side to the other by tilting the plane that the ball rests on. To make it interesting though, holes are strategically placed throughout the board. If the ball falls through any of these holes, you must start over at the beginning. My game accurately follows these rules.

Game Mechanics

I've always been intrigued by how physics are simulated in a computer environment. This game involves collision detection between spheres, holes, and walls and also the physics behind a rolling ball.

Although it may not seem obvious, the entire game is one big hierarchical model, including the ball. This may seem weird, but it makes things much easier to develop and has the same look. My first attempt involved a ball that was independent of the game board and used plane/sphere collision detection so that the ball did not fall through the board. This was fairly easy to implement, but things got much more complicated when I started on collision detection between the board obstactles and the ball. This is because the world coordinates of the ball are different than that of the board. If a wall is at x = -5.0 in world coordinates and then tilts a certain amount, that x value is no longer the same with respect to the ball's world coordinate position. This is when I had the idea to incorporate the ball within the same world coordinates as the playing board. This also negated the need for plane/sphere detection as the ball would act accordingly as the board tilted.

After I had set up the world the way I wanted, I needed to create semi-realistic physics for a rolling ball. This proved to be the hardest part of the entire project. Before I even could use the classic Newtonian physics equations to simulate acceleration and movement, I needed a couple of vectors. I calculated the normal vector to the plane with some fairly simple trigonometic math. Once I had that, I could cross the up vector with the normal to find the axis of rotation. Then, I could cross the axis of rotation with the normal to find the ball direction vector. The math went something like so:

  • axis_of_rotation = (normal X up)
  • direction_vector = (normal X axis_of_rotation)

    The direction vector came in very handy to construct a compass to let the user know in what direction the board is tilted. Sometimes its hard to tell from a top-down view.

    To get the ball to act according to Newtonian physics, I used the following equation:

  • displacement = (0.5) * (acceleration) * (time)^2

    I found acceleration with some more clever trigonometric math by finding the acceleration at the exact spot the ball was at according to the plane degree tilt and adding that amount to the current acceleration. I am using the glut timing function to update my rolling ball 30 times every frame, so every 0.33 milliseconds. I use that 0.33 for the time variable above. It is also important to note that all of the above operations are done in both the x and the z directions. The board rests on the xz plane so the y direction is out of the screen.

    With my testing I've found that the ball rolling simulation is extremely accurate to what you would expect to happen in real life. After getting my math to work correctly, the physics worked fantastically.

    Level Design

    Due to time constraints, I only had time to make one level design for the game. But, due to the way I designed the game making new levels would be extremely easy. I designed it so that when I drew a specific wall or hole obstacle that it placed those the obstacle properties (position, size) in an array of walls or holes. My collision detection code is generic in that it loops through both arrays of obstacles every frame and checks to see if the ball is in contact with any of them. With this design in place I could easily make new level designs by putting the obstacles values in a text file and parsing the data. Sadly, I didn't implement this feature.

    Known Bugs

    The biggest problem with this game is the accuracy of the collision detection between the ball and the internal walls obstacles. My design works fairly well, but there are some cases where it fails. Since I only check collisions by comparing the positions of the ball and the position of the wall along with the help of the direction vector, sometimes the ball can warp through a wall to the other side if the x or z displacement is just right so that it skips over the code where I check for that collision. Fortunately, this only happens if the ball is going extremely fast, much faster than one would normally play this game. So, since I assume the user will play the game the way it is intended, my collision code works very well for my purposes.

    Screenshot

    The ball is slightly hard to distinguish, but it has a green hue and is in the center of the screenshot. The black circles everywhere are the holes. The black circle in the upper right hand corner with the red needle is the compass. It points in the tilt direction of the board. You can also use the needle to verify the accuracy of the rolling ball.

    Controls

  • Left mouse button - click and drag across the screen to tilt the board in the desired direction
  • Up arrow key - increase gravity
  • Down arrow key - decrease gravity
  • 'w' key - remove the walls
  • 'h' key - remove the holes

    The gravity is constrained between 1.0 and 12.0. I added the features to remove the holes and walls to create a sort of sandbox mode so that the user can play around with the ball physics to verify its accuracy.

    References

    Angel, Edward; OpenGL: A Primer; 3rd Edition

    http://www.swiftless.com/tutorials/opengl/collision.html

    http://nehe.gamedev.net/