Maize - A Maze

A 3-D view of a 2-D maze that provides players with a map and guidance, but challenges players through a score system

Comment

Inspiration

I was doing math work around a week before the hackathon. The problem was extremely frustrating, and as a result, I took a break in order to collect myself. I picked up a maze book, and I solved it, and I wondered how a machine managed to generate thousands of mazes. I was learning processing at the time, as was my brother, and I decided to try and build a maze generator. However, I also realized that I needed something to do during the hackathon, so I set myself on doing it. However, more importantly, I was wondering how mazes are generated, solve and printed by computers. This thought intrigued me, and I decided to explore it at the best place possible, a hackathon. The day of the hackathon, I thought about expanding the maze beyond its primitive form, and I decided to do something I never did before, add 3-D. To develop the theme of corn for the maze, our entire group was making jokes in an attempt to name the creation, and my brother created the idea of a pun with corn, maize. Therefore, our idea was fully born, and we decided to theme the entire game after corn.

What it does

The maze is generated randomly, with a practically guaranteed unique arrangement every single time the program is started. It is possible for the same maze to be genereated twice, but it is based on an absurdly low probability. After this, the program chooses two distinct points, and labels them as the beginning and the end. Then, it uses an algorithm to determine the shortest path between the two points. After this, the player is dropped in at the beginning, and can walk around the maze. By using the ',' and '.' keys, the user can rotate the camera, but the camera can not see the entire maze, but only a small portion of it. The player is given their coordinates and the coordinates of the end point, and it is their job to find out how to get to the end. They are being timed, and a timer is constantly counting up. The player can use hints, such as accessing a picture of the entire maze, or even being able to look at the shortest path from them to the end. However, using these hints will cause the timer to count up faster, resulting in a higher time. This creates an interesting balance between whether the hints are truly worth their cost.

How we built it

To build the maze, we first declared a large array of objects called Cells. These objects each had a boolean array for its four walls. To generate a maze between these cells, we used an algorithm known as Recursive Backtracking. This algorithm goes through the maze, carving a path between cells, constantly going forwards until it reaches a point where it can no longer find more cells to generate. At this point, it backtracks until it can generate a cell, and it continues. This cycle continues, until the algorithm reaches the beginning, where the end result is a maze.

After this, we used an algorithm known as Breadth-First to find the shortest path to the end. This algorithm searches in concentric circles around the start, but it only searches neighbors it can access. These concentric circles expand until the end is finally scanned. Because the path was generated via concentric circles, the path generated was the shortest. While there were other algorithms that may have been more efficient, we chose Breadth-First because it was simple to implement, crucial during a hackathon.

To add 3-D functionality to this maze, we used Processing's 3-D capabilities. This allowed us the use of boxes, lights, and a camera that could be easily directed towards the angles wanted.

Finally, to add in a map, we drew a 2-D representation of the maze, using the prototype that we initially created to represent the cells. We constantly called the Breadth-First Search Algorithm to generate an efficient path towards the goal, albeit some minor hiccups.

Challenges we ran into

During the hackathon, one of the initial challenges we faced was 3-D functionality. None of us had ever delved in 3-D, but we were determined to make it work. The 3-D camera was a hassle to deal with it, and initial inexperience had us dealing with poor lightings, outlines, and incredibly displeasing aesthetics that also made us give up 3-D. However, by taking breaks and making sure that we broke down our project/code, we managed to finally learn how the 3-D worked and how we could implement the 3-D in our game.

Another challenge that we faced was a critical bug, where during the ending phase, the audio would constantly begin playing, creating absurd amounts of lag. However, it was difficult for us to hear the other audio channels, so we had no clue how to fix the lag. However, after delaying the frames and listening closely, we managed to isolate the problem and take care of it.

The final challenge we faced was making the player and camera follow a more smooth path. The movement was a more simple task, as all we had to do was set a beginning and an end, and tween the playerPos between the two values. However, the movement for the camera was more complicated, as we had to calculate a direction for the camera to swing in. Fortunately, my cousin had a key insight that greatly aided our efforts, and we managed to conquer this task.

Accomplishments that we're proud of

During the hackathon, we managed to accomplish many things we were proud of. First of all, we managed to implement two algorithms that allowed us to both generate a maze and solve it, no matter what. The satisfaction in seeing the algorithms in action was incredible. Additionally, the 3-D functionality was a huge accomplishment. All beginners start with simple 2-D games, and the jump from those to 3-D is a sizable one. It takes a lot of dedication to jump that gap, and we are proud to say that we managed to do it. We constantly struggled but after finally succeeding and producing the product we did, we are incredibly proud of what we did at this hackathon.

What we learned

During the project, we learned many things that we were hesitant to learn about before. The first and most obvious one is the 3-D. As said before, we had never worked with 3-D, and to try and do it within 24 hours was an incredibly educational experience. Another enlightening experience was when we had to generate the maze. Looking through the algorithms online gave us good insight into how most puzzles are generated, and it will greatly help us in our programming futures. Finally, all three of us learned something about dedication. We each stayed up for over 20 hours to help put this project together, and we depended on each other to help keep the project going. We knew that we had to truly dedicate ourselves to this project, and we did.

What's next for Maize

Despite how proud we are of the accomplishments that built up Maize, we still accept that there are things that we planned to implement/improve, but never could. One thing that we wanted to do towards the end, but we couldn't due to a lack of time, was a port to Android. Additionally, someone gave us a good idea of adding two players into the game, where two players are given the same maze, the same beginning, and the same ending. The two players can compete with the same situation and see who can get the lower time. The next thing that we wanted to add was an algorithm that would determine the score a person gained, based on their time, and the difficulty of the maze. Unfortunately, we once again ran out of time, but we look forward to implementing an algorithm in the future. As a followup, we could add in a leaderboard, where players compete for the best scores in overall points, or levels with similar difficulty levels. Maize is a game that we collaborated on to build, and we look forward to further collaboration in order to improve it.

Built With

Share this project:

Updates