Difference between revisions of "Maze Craze"

From ESE205 Wiki
Jump to navigation Jump to search
m (Protected "Maze Craze" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite)))
 
(65 intermediate revisions by 2 users not shown)
Line 3: Line 3:
  
 
== Overview ==
 
== Overview ==
 +
[[File:Maze Craze Box.JPG|thumbnail|Maze Craze!]]
 
Maze Craze is a challenging maze game where the player must navigate ever-changing walls to reach the end. The maze is a 5 x 5 grid of spaces where the user can place their game piece. The player can only move their piece one space in any cardinal direction as long as that direction is not obstructed by a wall. The first time the player moves a space, the entire maze will change to form a new maze. The next time, the maze will revert back to its original form. Each move the game board will cycle between two maze layouts creating an elaborate mental challenge for the player. The two mazes will be randomized at the start of every new game in order to create new and exciting challenges for the user. Every maze combination created will have a possible solution to ensure that the user can potentially conquer the maze. The game will keep track of how many spaces the user moves on his or her journey as well as provide a target (ideal) number of moves. Maze Craze is fun for the whole family! See who can solve the maze in the fewest moves and try to beat the high score!
 
Maze Craze is a challenging maze game where the player must navigate ever-changing walls to reach the end. The maze is a 5 x 5 grid of spaces where the user can place their game piece. The player can only move their piece one space in any cardinal direction as long as that direction is not obstructed by a wall. The first time the player moves a space, the entire maze will change to form a new maze. The next time, the maze will revert back to its original form. Each move the game board will cycle between two maze layouts creating an elaborate mental challenge for the player. The two mazes will be randomized at the start of every new game in order to create new and exciting challenges for the user. Every maze combination created will have a possible solution to ensure that the user can potentially conquer the maze. The game will keep track of how many spaces the user moves on his or her journey as well as provide a target (ideal) number of moves. Maze Craze is fun for the whole family! See who can solve the maze in the fewest moves and try to beat the high score!
  
Line 48: Line 49:
  
 
Plywood 2ft by 4ft (@ $7.92 [http://www.homedepot.com/p/Sanded-Plywood-Common-1-4-in-x-2-ft-x-4-ft-Actual-0-224-in-x-23-75-in-x-47-75-in-1502100/203116838 here])
 
Plywood 2ft by 4ft (@ $7.92 [http://www.homedepot.com/p/Sanded-Plywood-Common-1-4-in-x-2-ft-x-4-ft-Actual-0-224-in-x-23-75-in-x-47-75-in-1502100/203116838 here])
 
5V 10A power supply (@ $16.99 [https://www.amazon.com/100-240V-adapter-switching-display-power-US/dp/B01HYXAG04/ref=sr_1_1?ie=UTF8&qid=1487435650&sr=8-1&keywords=5V+10A+switching+power+supply here])
 
  
 
3-pack of 1/2 inch screws (@ $4.00 (for 8) [http://www.homedepot.com/p/Everbilt-8-x-1-2-in-Stainless-Steel-Flat-Head-Phillips-Drive-Wood-Screw-3-Piece-810368/204275503 here])
 
3-pack of 1/2 inch screws (@ $4.00 (for 8) [http://www.homedepot.com/p/Everbilt-8-x-1-2-in-Stainless-Steel-Flat-Head-Phillips-Drive-Wood-Screw-3-Piece-810368/204275503 here])
Line 55: Line 54:
 
20-pack of 10k resistors for use with Hall Effect Sensors (@ $1.90 (for 2 packs) [https://www.sparkfun.com/products/11508 here])
 
20-pack of 10k resistors for use with Hall Effect Sensors (@ $1.90 (for 2 packs) [https://www.sparkfun.com/products/11508 here])
  
10-pack of Number Displays (@ $4.99 [https://www.amazon.com/uxcell-Common-Cathode-Display-Digital/dp/B00EZBHYV8/ref=sr_1_1?ie=UTF8&qid=1487355181&sr=8-1&keywords=led+number+display here])
+
3-pack of Breadboards (@ $7.86 [https://www.amazon.com/Elegoo-Breadboard-Solderless-Distribution-Connecting/dp/B01EV6LJ7G/ref=sr_1_14?ie=UTF8&qid=1487437589&sr=8-14&keywords=breadboard here])
 
 
3-pack of Breadboards (@ $8.86 [https://www.amazon.com/Elegoo-Breadboard-Solderless-Distribution-Connecting/dp/B01EV6LJ7G/ref=sr_1_14?ie=UTF8&qid=1487437589&sr=8-14&keywords=breadboard here])
 
 
 
Female DC power adapter (@ $7.00 [https://www.amazon.com/Female-DC-Power-adapter-terminal/dp/B00KAE1QGS/ref=sr_1_1?ie=UTF8&qid=1487435886&sr=8-1&keywords=Female+DC+Power+adapter+-+2.1mm+jack+to+screw+terminal+block here])
 
  
 
Circular Magnets 1/2 in. dia (10 pack @$1.98 [http://www.homedepot.com/p/MASTER-MAGNETICS-1-2-in-Dia-Black-Disc-Magnet-10-per-Pack-96234/203613121 here])
 
Circular Magnets 1/2 in. dia (10 pack @$1.98 [http://www.homedepot.com/p/MASTER-MAGNETICS-1-2-in-Dia-Black-Disc-Magnet-10-per-Pack-96234/203613121 here])
Line 65: Line 60:
 
Black on/off Switch (@ $0.95 [https://www.sparkfun.com/products/8837 here])
 
Black on/off Switch (@ $0.95 [https://www.sparkfun.com/products/8837 here])
  
Black Spray Paint (@ $3.87 [https://www.amazon.com/Rust-Oleum-249061-Painters-Purpose-12-Ounce/dp/B002BWORSG/ref=sr_1_1?ie=UTF8&qid=1487352352&sr=8-1&keywords=black+spray+paint here])
+
Black Spray Paint (@ $3.87 [http://www.homedepot.com/p/Rust-Oleum-Painter-s-Touch-2X-12-oz-Gloss-Black-General-Purpose-Spray-Paint-249122/202071353 here])
  
 
Red Paint Pen (@ $1.97 [https://www.walmart.com/ip/Painter-s-Chisel-Tip-Paint-Pen-Red/24663617 here])
 
Red Paint Pen (@ $1.97 [https://www.walmart.com/ip/Painter-s-Chisel-Tip-Paint-Pen-Red/24663617 here])
  
20-pack of 1k resistors for use with the number displays (@ $1.90 for 2 [https://www.sparkfun.com/products/13760 here])
+
Solderable Breadboards(@ $9.99 [https://www.amazon.com/gp/product/B01ER06KXE/ref=od_aui_detailpages00?ie=UTF8&psc=1 here])
 +
 
 +
2-Line Display (@ $7.99 [https://www.amazon.com/gp/product/B00E5YJCBA/ref=od_aui_detailpages00?ie=UTF8&psc=1 here])
 +
 
 +
Pack of Push Buttons (@ $ $7.31 [https://www.amazon.com/gp/product/B00TGSS4CS/ref=od_aui_detailpages00?ie=UTF8&psc=1 here])
  
 
Wiring (provided)
 
Wiring (provided)
Line 75: Line 74:
 
==== Total ====
 
==== Total ====
  
$145.34 (includes sales tax)
+
$137.08 (includes sales tax)
 +
 
 +
== Design Solutions ==
 +
=== Hall Effect Sensors ===
 +
[[File:HallEffectSensorDiagram.JPG|thumbnail|left]]
 +
Our tutorial on Hall Effect sensors (with links to useful hookup guides and some sample code, as well as an in-depth explanation of latching vs. non-latching sensors) is located [[Use Hall Effect Sensors|here]].
 +
 
 +
In order to hide the sensors from the user and prevent damage to the game, we opted for Hall Effect sensors which respond to magnetic fields. These 25 sensors could detect a player's piece through the board, and could give the Arduino a player's location on the board.
 +
 
 +
We purchased 27 (fairly cheap) Hall Effect sensors and found when they arrived that they were "Latching" Hall Effect sensors (for more detail on the specifics of this, here's our page [[How to Use Hall Effect Sensors|again]]. We needed them to be non-latching, so we scoured the internet for a quick-fix for this issue. The answer came from comments on the sensor's [https://www.sparkfun.com/products/9312 Spark Fun page], where a user commented that rapidly turning the sensors on and off would "reset" the sensor and mimic a non-latching sensor. This was exactly what we needed.
 +
 
 +
But, we needed to do this for 25 sensors. To accomplish this, Professor Humberto recommended we attach all the Hall Effect sensors to a MOSFET switch, which is essentially a physical switch that the computer can control. This way, with one line of code, all the sensors could be turned on and off. This enabled us to use the latching sensors as non-latching sensors.
 +
 
 +
=== LED Light Strips ===
 +
Our tutorial on operating Addressable LED strips (with links to necessary libraries, links to helpful student tutorials, and an in-depth look at wiring, controlling, and manipulating the lights) is located [[Operate Adressable LED Lights|here]].
 +
 
 +
The entirety of the game code -- all the prototyping, troubleshooting, and even the final version of the code -- can be found on our public [https://bitbucket.org/mazecraze/ BitBucket].
 +
 
 +
The functioning game code is "finalCode.ino" if you'd like to peruse it.
 +
The maze generation code is "Maze1.java" if you'd like to peruse it as well.
 +
 +
The LED strips that we purchased (link is above in the budget) were addressable. This means that each pixel could be given an R, G, and B value and the LED would display that color. This is fairly straightforward when you're working on a strip of lights, it's easy to make patterns and fun colors using some very simple for loops. However, the game board had 180 pixels spread over 12 LED strips that needed to be interacted with intelligently. Every time the game needed to switch to the next maze, every pixel needed to be given an RGB value and told to display. On top of this, the pixels needed to be inherently linked to one another in triplets so that higher levels of code weren't dealing with "pixels" but with "walls". To even further abstract this, the main game algorithm that checks validity, waits for your start piece, and responds to your movement needed not to deal with "walls" but with "mazes". To handle this abstraction, we built each data type from ground up (from pixel all the way up to maze) to hide the nitty-gritty of setting each pixel to an RGB value and prevent the programmer from accidentally damaging any of the underlying code structure.
 +
[[File:LEDsUpClose.jpg|thumbnail|left|A close-up of our LED lights. Picture credit to SparkFun.]]
 +
 
 +
In order to accomplish this, the following abstractions were made:
 +
* Pixels were no longer just a pixel, they were part of a "wall".
 +
* The walls no longer received RGB values, but instead a Color (an enum) that was programmed to have the RGB inherent.
 +
* Walls were then combined into arrays that represented the entire board. Each wall could then be addressed with either ''horizontal'' or ''vertical'' and its location on the board in relation to the start point.
 +
*These arrays of walls were then made into "mazes" using the Java code integrated into C. The mazes were created and then interpreted into the wall arrays under the surface. Then, we needed only to call the function genrateMazes() and a set of 2 mazes with an 8-move solution would be interpreted in full all the way down to RGB vales, strand numbers, and pixels. The coder needed only to call changeMazes() and the mazes would flip back and forth and display appropriately on the board.
 +
 
 +
The whole goal of this lights protocol was to move forward and not have to go back and troubleshoot when doing the higher-level game algorithm coding. We spent time to really be sure that each step of the process worked without fail and correctly ever time before we moved forward into the next level of abstraction. This enabled us to deal with the mazes more intuitively and not have to manually set anything- the computer did all the functioning beneath the surface and did it without flaw. This meant no hunting and pecking through endless pixel-setting code to troubleshoot -- the mazes were always built correctly.
 +
 
 +
=== Maze Generator ===
 +
 
 +
The main problem faced with the maze generator was creating mazes that have a solution in them 100% of the time. In addition, the generator could not use too much computing power since an arduino must be generating the maze which is not a strong computational device. In order to circumvent the computational problem it was realized that the program could not simulate solving mazes until one with a solution was found. Instead, we realized that the maze can be generated and then a random solution could be inserted into the maze.
 +
 
 +
[[File:Maze Diagram.JPG|thumbnail|Sample Maze with Solution]]
 +
 
 +
The first step in this process was to generate a random maze which starts by simply randomly generating a 5x5 array of 4-digit binary numbers. For example, a given space might have the number 1001, which (using the index: [up][, down][right][left]) would represent a space with red walls on bottom and to the right. The maze coordinates range from [0][0] to [4][4]. If we look at the diagram of a maze with its 2 boards present we can see that an even number of player moves put the player on board 1 while an odd number of moves puts that player on board 2.
 +
 
 +
en the information above, the determined solution to the problem was to put a random solution into an already generated maze. Since the player starts at the point [0][0] and finishes at [4][4], that means a solution can be created as a random combination of up and right players moves. The generator creates such a combination and changes the according values on the maze array to 0 from 1. This allows for a minimum of one solution to the maze. There are still other possible solutions for the player to discover which is still satisfactory for the game's functionality.
 +
 
 +
== Videos of Maze Craze ==
 +
[[File:IMG 1572.MOV|400px|thumbnail|left|Player solving the maze]]
 +
 
 +
[[File:IMG 1573.MOV|400px|thumbnail|right|Player attempting an invalid move]]
 +
 
 +
[[File:IMG 1574.MOV|400px|thumbnail|center|Player trying to start the maze from a point other than the start point]]
  
 +
   
 
== Gantt Chart ==
 
== Gantt Chart ==
[[File:Maze_Gantt_0216.JPG|thumb|1100px|left|Gantt Chart]]
+
[[File:Maze_Gantt_430.JPG|thumb|1300px|center|Gantt Chart]]
<gallery>
+
 
 +
 
 +
== Results ==
 +
The end result of Maze Craze was very successful relative to our initial goals. The game itself was playable and included several of the most crucial features. Some of these include the fully operational LED walls that could be customized however we saw fit. The game always generated a maze with at least 1 solution in it which ensures the player always has an opportunity to win. The board was also very aesthetically pleasing in that it was an enclosed black box with flush flashing lights, a flush reset button and clear starting and end points. The only exposed wires were those connecting the game to the power supply; however, these would have been hidden if the power supply was included in the box or if the game had run on batteries.
 +
 
 +
 
 +
Although our demo satisfied some of our initial objectives, there were a few aspects of the game that either did not come to fruition or we were unable to implement properly. The most prominent of these issues was that the game board had several faulty hall effect sensors that inhibited the gameplay. We were able to isolate these sensors to one corner of the maze and shift from the game being on a 5x5 scale to effectively a 4x4. The broken sensors also disabled the game's ability to check for invalid moves were the player pass over a red wall when they are not permitted. When the player makes a move such as this, the faulty sensors output a false reading and the game then reacts improperly to the players invalid movement. We thus had to disable this feature of the game. On the other hand, it does still check for the validity of moves when the player moves too many spaces at once.
 +
 
 +
There were some other additions to the game we had planned to add but were unable to because of time constraints:
 +
* On/Off switch
 +
* Multiple game difficulties
 +
* Display to show the user how many moves they have made
 +
* Multiplayer
 +
 
 +
=== Poster ===
 +
[[File:Maze Poster.JPG|1200px|thumbnail|center]]

Latest revision as of 16:08, 3 May 2017


Overview

Maze Craze!

Maze Craze is a challenging maze game where the player must navigate ever-changing walls to reach the end. The maze is a 5 x 5 grid of spaces where the user can place their game piece. The player can only move their piece one space in any cardinal direction as long as that direction is not obstructed by a wall. The first time the player moves a space, the entire maze will change to form a new maze. The next time, the maze will revert back to its original form. Each move the game board will cycle between two maze layouts creating an elaborate mental challenge for the player. The two mazes will be randomized at the start of every new game in order to create new and exciting challenges for the user. Every maze combination created will have a possible solution to ensure that the user can potentially conquer the maze. The game will keep track of how many spaces the user moves on his or her journey as well as provide a target (ideal) number of moves. Maze Craze is fun for the whole family! See who can solve the maze in the fewest moves and try to beat the high score!

Detailed Game Description

The game board will be a 12in x 12in x 5in wooden box with the top side of the box being the game board that the user interacts with. The maze game itself will be created using on an Arduino that will be stored inside the box. One side of the box will contain a number counter created using number displays that will show the user's current number of moves. This side will also have another number display to convey the target number of moves for the player to complete the maze in.

En example of one maze and solution

The walls of the maze will be comprised of LED RGB strips which will display green when the player is permitted there is no wall and red when a wall is present. Since the board is a 5 x 5 grid, the outside border of the maze will all be painted, permanent walls that are always red. Each space where the user can place their game piece will have a hall effect sensor underneath it to track if the user's piece is on that space. The START and FINISH squares will remain constant and will be labeled in paint on the board. This data will then be used to track the user's number of moves as well as to determine when to change the maze. There will also be an on and off switch that will act as a reset for the game. Thus, the player will simply need to turn the game off and on again to reset the board. The game piece will be a 3-D printed object with a magnet attached to its base which will set of the hall effect sensors when on a space. All of the wiring will be enclosed the in box in order to make the game readily portable.

Contributors

Created by Jason Christal and Liz Halter.

TA: Natalie Ng

Objectives:

1. Construct a functioning game board with all wiring enclosed in a box.

2. Make the board aesthetically pleasing. This includes painting and decorating.

3. Make a random maze generator that ensures mazes are solvable.

4. Add user selection of game difficulty (through incorporating a switch) if time allows.

Challenges

1. Learn Arduino.

2. Constructing a box that contains the game board on the lid/top surface and the Arduino and wiring inside.

3. Wiring the game board.

4. Optimizing magnetic sensor readings by removing noise.

5. Creating a program that solves the mazes in the shortest number of moves possible

6. Creating a program that can make mazes of varying difficulty.

Budget

LED RGB Strips, 1m (3x @ $59.85 here

27 Hall Effect sensors (@ $25.65 (for all 27) here)

Arduino Mega (Provided)

Plywood 2ft by 4ft (@ $7.92 here)

3-pack of 1/2 inch screws (@ $4.00 (for 8) here)

20-pack of 10k resistors for use with Hall Effect Sensors (@ $1.90 (for 2 packs) here)

3-pack of Breadboards (@ $7.86 here)

Circular Magnets 1/2 in. dia (10 pack @$1.98 here)

Black on/off Switch (@ $0.95 here)

Black Spray Paint (@ $3.87 here)

Red Paint Pen (@ $1.97 here)

Solderable Breadboards(@ $9.99 here)

2-Line Display (@ $7.99 here)

Pack of Push Buttons (@ $ $7.31 here)

Wiring (provided)

Total

$137.08 (includes sales tax)

Design Solutions

Hall Effect Sensors

HallEffectSensorDiagram.JPG

Our tutorial on Hall Effect sensors (with links to useful hookup guides and some sample code, as well as an in-depth explanation of latching vs. non-latching sensors) is located here.

In order to hide the sensors from the user and prevent damage to the game, we opted for Hall Effect sensors which respond to magnetic fields. These 25 sensors could detect a player's piece through the board, and could give the Arduino a player's location on the board.

We purchased 27 (fairly cheap) Hall Effect sensors and found when they arrived that they were "Latching" Hall Effect sensors (for more detail on the specifics of this, here's our page again. We needed them to be non-latching, so we scoured the internet for a quick-fix for this issue. The answer came from comments on the sensor's Spark Fun page, where a user commented that rapidly turning the sensors on and off would "reset" the sensor and mimic a non-latching sensor. This was exactly what we needed.

But, we needed to do this for 25 sensors. To accomplish this, Professor Humberto recommended we attach all the Hall Effect sensors to a MOSFET switch, which is essentially a physical switch that the computer can control. This way, with one line of code, all the sensors could be turned on and off. This enabled us to use the latching sensors as non-latching sensors.

LED Light Strips

Our tutorial on operating Addressable LED strips (with links to necessary libraries, links to helpful student tutorials, and an in-depth look at wiring, controlling, and manipulating the lights) is located here.

The entirety of the game code -- all the prototyping, troubleshooting, and even the final version of the code -- can be found on our public BitBucket.

The functioning game code is "finalCode.ino" if you'd like to peruse it. The maze generation code is "Maze1.java" if you'd like to peruse it as well.

The LED strips that we purchased (link is above in the budget) were addressable. This means that each pixel could be given an R, G, and B value and the LED would display that color. This is fairly straightforward when you're working on a strip of lights, it's easy to make patterns and fun colors using some very simple for loops. However, the game board had 180 pixels spread over 12 LED strips that needed to be interacted with intelligently. Every time the game needed to switch to the next maze, every pixel needed to be given an RGB value and told to display. On top of this, the pixels needed to be inherently linked to one another in triplets so that higher levels of code weren't dealing with "pixels" but with "walls". To even further abstract this, the main game algorithm that checks validity, waits for your start piece, and responds to your movement needed not to deal with "walls" but with "mazes". To handle this abstraction, we built each data type from ground up (from pixel all the way up to maze) to hide the nitty-gritty of setting each pixel to an RGB value and prevent the programmer from accidentally damaging any of the underlying code structure.

A close-up of our LED lights. Picture credit to SparkFun.

In order to accomplish this, the following abstractions were made:

  • Pixels were no longer just a pixel, they were part of a "wall".
  • The walls no longer received RGB values, but instead a Color (an enum) that was programmed to have the RGB inherent.
  • Walls were then combined into arrays that represented the entire board. Each wall could then be addressed with either horizontal or vertical and its location on the board in relation to the start point.
  • These arrays of walls were then made into "mazes" using the Java code integrated into C. The mazes were created and then interpreted into the wall arrays under the surface. Then, we needed only to call the function genrateMazes() and a set of 2 mazes with an 8-move solution would be interpreted in full all the way down to RGB vales, strand numbers, and pixels. The coder needed only to call changeMazes() and the mazes would flip back and forth and display appropriately on the board.

The whole goal of this lights protocol was to move forward and not have to go back and troubleshoot when doing the higher-level game algorithm coding. We spent time to really be sure that each step of the process worked without fail and correctly ever time before we moved forward into the next level of abstraction. This enabled us to deal with the mazes more intuitively and not have to manually set anything- the computer did all the functioning beneath the surface and did it without flaw. This meant no hunting and pecking through endless pixel-setting code to troubleshoot -- the mazes were always built correctly.

Maze Generator

The main problem faced with the maze generator was creating mazes that have a solution in them 100% of the time. In addition, the generator could not use too much computing power since an arduino must be generating the maze which is not a strong computational device. In order to circumvent the computational problem it was realized that the program could not simulate solving mazes until one with a solution was found. Instead, we realized that the maze can be generated and then a random solution could be inserted into the maze.

Sample Maze with Solution

The first step in this process was to generate a random maze which starts by simply randomly generating a 5x5 array of 4-digit binary numbers. For example, a given space might have the number 1001, which (using the index: [up][, down][right][left]) would represent a space with red walls on bottom and to the right. The maze coordinates range from [0][0] to [4][4]. If we look at the diagram of a maze with its 2 boards present we can see that an even number of player moves put the player on board 1 while an odd number of moves puts that player on board 2.

en the information above, the determined solution to the problem was to put a random solution into an already generated maze. Since the player starts at the point [0][0] and finishes at [4][4], that means a solution can be created as a random combination of up and right players moves. The generator creates such a combination and changes the according values on the maze array to 0 from 1. This allows for a minimum of one solution to the maze. There are still other possible solutions for the player to discover which is still satisfactory for the game's functionality.

Videos of Maze Craze

Player trying to start the maze from a point other than the start point


Gantt Chart

Gantt Chart


Results

The end result of Maze Craze was very successful relative to our initial goals. The game itself was playable and included several of the most crucial features. Some of these include the fully operational LED walls that could be customized however we saw fit. The game always generated a maze with at least 1 solution in it which ensures the player always has an opportunity to win. The board was also very aesthetically pleasing in that it was an enclosed black box with flush flashing lights, a flush reset button and clear starting and end points. The only exposed wires were those connecting the game to the power supply; however, these would have been hidden if the power supply was included in the box or if the game had run on batteries.


Although our demo satisfied some of our initial objectives, there were a few aspects of the game that either did not come to fruition or we were unable to implement properly. The most prominent of these issues was that the game board had several faulty hall effect sensors that inhibited the gameplay. We were able to isolate these sensors to one corner of the maze and shift from the game being on a 5x5 scale to effectively a 4x4. The broken sensors also disabled the game's ability to check for invalid moves were the player pass over a red wall when they are not permitted. When the player makes a move such as this, the faulty sensors output a false reading and the game then reacts improperly to the players invalid movement. We thus had to disable this feature of the game. On the other hand, it does still check for the validity of moves when the player moves too many spaces at once.

There were some other additions to the game we had planned to add but were unable to because of time constraints:

  • On/Off switch
  • Multiple game difficulties
  • Display to show the user how many moves they have made
  • Multiplayer

Poster

Maze Poster.JPG