MazeLab Overview:
MazeLab is a Java based 3D game I developed. The concept of the game is an arcade style speed map exploration game. Currently the game is still in Beta, but major progress has been made. Here are some quick facts about MazeLab:
- Redering achieved with OpenGL
- Bullet physics for physics engine
- Randomly generated infinite maze extending in 3-D imensions
- Developed using Java Monkey IDE (http://jmonkeyengine.org/)
Maze Algorithm:
Mazes are actually surprisingly easy to generate. The particular algorithm I selected for the generation of mazes is Kruskal's algorithm. The theoretical concept of Kurskal's algorithm is quite simple:
The beauty of this algorithm is that it can be implemented in an extremely abstract and general form. When thinking about the algorithm it is easy to visualize a conventional 2D grid maze, however the algorithm can be applied to n-dimensional space. also while walls are typically imagined as the pathways between cells complex path ways, teleporters, and ladders serve the same function. This algorithm can then create navigable mazes in 3D space where every room is a different polyhedron. An important trait of the algorithm is that it ensures a unique path between any two cells in the merged set.
My usage of the algorithm is applied in the following ways, A maze is defined as a N dimensional collection of cells. Each maze is created by providing the location of the "start" cell and then randomly selecting an "exit" cell that is a greater distance away from the start cell then a predefined minimum. In general each cell is defined dimensionaly as a 1x1 square with four "neighbors," However a defined number of "medium" and "large" cells are created from a combination of connected cells. Once these larger rooms have been created the standard algorithm is then applied to the space. Each start and end cell connects to another maze of a higher or lower plane through a ladder arrangement. This allows for an unbounded 3D maze of varied and interesting complexity. The intentionally "medium" and "large" cells provide some bearing to the player and present them with a wide set of simultaneous choices compared to a conventionally generated maze.
- Define a cell as space which contains connections to other cells.
- Create a space of mapped cells with every path between them initially "blocked."
- Define a set as a collection of cells and create a unique set for every cell.
- Select a path between two cells (randomly or by a selection paradigm)
- If the cells connect by the path are not contained in the same set "unblock" the path and merge the sets of the two cells
- Repeat 4-5 until all cells are contained in the same set
The beauty of this algorithm is that it can be implemented in an extremely abstract and general form. When thinking about the algorithm it is easy to visualize a conventional 2D grid maze, however the algorithm can be applied to n-dimensional space. also while walls are typically imagined as the pathways between cells complex path ways, teleporters, and ladders serve the same function. This algorithm can then create navigable mazes in 3D space where every room is a different polyhedron. An important trait of the algorithm is that it ensures a unique path between any two cells in the merged set.
My usage of the algorithm is applied in the following ways, A maze is defined as a N dimensional collection of cells. Each maze is created by providing the location of the "start" cell and then randomly selecting an "exit" cell that is a greater distance away from the start cell then a predefined minimum. In general each cell is defined dimensionaly as a 1x1 square with four "neighbors," However a defined number of "medium" and "large" cells are created from a combination of connected cells. Once these larger rooms have been created the standard algorithm is then applied to the space. Each start and end cell connects to another maze of a higher or lower plane through a ladder arrangement. This allows for an unbounded 3D maze of varied and interesting complexity. The intentionally "medium" and "large" cells provide some bearing to the player and present them with a wide set of simultaneous choices compared to a conventionally generated maze.
Physiological Manipulations:
Inspired by games such as Portal and The Stanley Parable, I introduced spatial manipulations into the game to add an additional level of complexity and psychological stress. As the player runs through the maze he will discover physical impossibilities. For instance taking 4 right turns and not winding up where he started. This is achieved by making each "cell" in Kurskal's algorithm contain not 4 by 5 possible neighbors. The 5th neighbor is a switch between two separate dimensions where two separate mazes are maintained. A raycast check on the generation algorithm ensures that two simultaneous transitions are never visible. This ensures that the player will never see a physical impossibility on screen, but must rely on their memory to know they exist. Since the 5th dimension of the cell is still bound in Kurskal's algorithm the generated maze contains one unique solution which requires navigation between both maze dimensions to achieve.
Players encountering these complex spatial anomalies are left with a disturbed sensation in the mind. Often they do not consciously realize that the map they are exploring cannot exist, however as they try to explore it and mentally map they become confused and disoriented in seemingly simple situations. Players I have talked to after trying the game felt significant mental distress until the consciously realized the manipulations the maze was perpetrating on them. Even then few players were able to understand the extent or mechanism of these manipulations.
Players encountering these complex spatial anomalies are left with a disturbed sensation in the mind. Often they do not consciously realize that the map they are exploring cannot exist, however as they try to explore it and mentally map they become confused and disoriented in seemingly simple situations. Players I have talked to after trying the game felt significant mental distress until the consciously realized the manipulations the maze was perpetrating on them. Even then few players were able to understand the extent or mechanism of these manipulations.