Overview
What if an entire, small planet were a hedge maze starting at the north pole and finishing at the south pole? With Spherical Labyrinth, you can experience it! Fly in from outer space and see how quickly you and your friends can solve the mazes you create. Spherical Labyrinth is a simple, yet enjoyable and visually appealing 3D challenge.
Features
The primary goals of this project was to explore the visual effects of manipulating the camera “up” vector, procedurally generate 3D geometry based on user input, implement collision detection, and create positional cues with a seamless skybox.
Camera Orientation & Manipulation
The “up” vector for a given position on a sphere is easy to calculate if the position is definied as a vector relative to the center of the sphere. In that case, the “up” vector is equal to the normalized position vector.
The true difficulty of implementing a free-look camera on the surface of a sphere is maintaining the camera’s look orientation when moved to a new position. For example, if you were looking along an arbitrary tangent vector to the sphere in your previous position, you would expect to be looking along a new tangent vector to the sphere in the same direction at your new position. It turns out that the appropriate camera basis vector rotation is easily performed with just vector and dot products and trigonometric functions.
Custom Maps
Solving a labyrinths would not be very fun if they were all the same! To allow users to specify their own mazes, I developed a simple file format that looks like a two-dimensional maze and nicely maps to a sphere. A labyrinth file has eighteen (18) lines of thirty-two (32) characters that follow the following rules and interpretations:
- The first character in the file represents a “wall.”
- Any other character represents a “floor.”
- The first line represents the entrance, and the last line represents the exit.
- Every line must contain at least one “floor.”
- The first and last characters in a line are adjacent positions on the sphere.
Given this design, an entire map can be packed into an eighteen-element array of four-byte (32-bit) integers.
The problem with mapping a two-dimensional labyrinth to spherical coordinates is that linear distances between longitudes become smaller at latitudes near the poles. Such small spaces would be frustrating from the perspective of both the user and the collision detection implementor (see below). Therefore, a tradeoff was made between maximal utility of the sphere’s surface area and minimal potential for claustrophobia. The sphere was split into twenty-six (26) latitudinal rings, but only eighteen (18) of them are actually used for the labyrinth, leaving four (4) latitudinal rings at each pole.
Finally, recall that spherical coordinates are, in fact, three-dimensional. Any position defined in spherical coordinates requires a radius, inclination, and azimuth. Therefore, the positions within the bitmap map to the azimuth and inclination angles, and the actual bit represents the radius (1 for wall radius, 0 for floor radius).
Collision Detection
In a labyrinth, collision detection is important because the walls represent actual, physical barriers. Because of the nature of the internal representation of the maze, collision detection can be position-based instead of purely geometric sphere-plane collision. All collisions were calculated based on the angle defined by the arc tangent of the ratio of the camera radius to the camera’s distance from the origin (the “eye” radius) and the player’s current and destination positions on the sphere. However, the “camera angle” has to be scaled up by an arbitrary factor to ensure a sufficient linear distance is maintained from walls near the poles.
For all collisions, it is safe to assume that the current position is valid (i.e. not within a wall). First, the destination position has to be checked if it is in the margin that would make it a possible collision. Then, at most three of the eight adjacent positions in the map would have to be checked for the existence of a wall. Finally, if there was a collision, a new destination position would be calculated based on the angle of intent if necessary.
Celestial Skybox
The starry skybox is perhaps icing on the cake in terms of visual cues. Without it, it is still fairly obvious that the player is walking along a sphere. However, the skybox adds an external point of reference to the otherwise visually constraining labyrinth. Because the orientation of the sky does not change, the player can use it to get a feel for relative positions on the sphere, especially within a latitudinal ring.
To create the textures for the seamless, outer space skybox, I used a free program called Celestia. In principle, a skybox is a cube that encloses the camera and whose faces are textured on the inside with two-dimensional projections of a sphere in six, mutually orthogonal directions with a 90-degree field of view. Celestia allows such states as viewing direction and field of view to be scripted, so I chose an arbitrary point in our galaxy, wrote scripts for views of all six sides of the skybox, and captured the output to a BMP format which I used for all of the other textures in the game.
References
Angel, Edward. OpenGL®: A Primer. 3rd ed. Boston: Addison-Wesley, 2008. Print.
Breitenbach, Jerome R. A Mathematics Companion for Science and Engineering Studies. New York: Oxford University Press, Inc., 2008. Print.
Celestia. http://www.shatters.net/celestia/
“Spherical Coordinates.” Wolfram MathWorld. Wolfram MathWorld, 2010. Web. 26 Nov. 2010. http://mathworld.wolfram.com/SphericalCoordinates.html
Wright, Richard S., Benjamin Lipchak, and Nicholas Haemel. OpenGL® SuperBible. 4th ed. Boston: Addison-Wesley, 2007. Print.