Bringing out the Big Guns

This whole time I have been working on my maze project, I have been avoiding maze creation algorithms. Why? Because I must use a computer and understand the code to create a maze. My personal level of experience in this field is low so I said to myself that I would focus on maze solving rather than maze creation. However, I was looking today and I found someone explaining the basic code for the generation of a perfect maze. It looks like the same format that I used to program the vex bots! I was not completely lost. As such, I decided to share with you all so that you too could relish in my excitement.

The Depth  First Search Algorithm is basically the simplest maze generation algorithm  I figure it be a perfect place for me to start. You begin with a grid like this.

1) Start at a random cell in the grid.  

2) Look for a random neighbor cell you haven't been to yet.  

3) If you find one, move there, knocking down the wall between the cells. If you don't find one, back up to the previous cell.  

4) Repeat steps 2 and 3 until you've been to every cell in the grid.

Simple yes?

The code for this looks like: 

create a CellStack (LIFO) to hold a list of cell locations  

set TotalCells = number of cells in grid  

choose a cell at random and call it CurrentCell  

set VisitedCells = 1  

   

while VisitedCells < TotalCells

          find all neighbors of CurrentCell with all walls intact   

          if one or more found 

                   choose one at random  

                   knock down the wall between it and CurrentCell  

                   push CurrentCell location on the CellStack  

                   make the new cell CurrentCell  

                   add 1 to VisitedCells

         else 

                   pop the most recent cell entry off the CellStack  

                   make it CurrentCell

         endIf

endWhile  

This might make no sense to you, but to me it looks quite familiar. So, thats my adventure for this week. See you all next week. The semester is ending soon so study hard!

Momentum maze

Like I said a couple of weeks ago, I found a logic maze but I did not know the rules for it. So today, I am posting them for you all. 

The rules for this maze are:

Find a path that travels from the start to the finish making vertical or horizontal movements of fixed length without hitting any walls. At the start of the maze, each movement must be 1-cell long. When you land on a shaded cell, this movement will change in length as indicated by the cell. Ignore values you pass over but do not land on. Length modifiers will only apply the first time you land on a cell, and your movement length will always be a positive integer.

Hooray for math in mazes.

Also I am being forced to build a motor. In physics 131, the greatest class ever, (University Physics Part II: Electricity and Magnetism) we have to build a motor using non plastic parts and original parts. This means that our parts can't come out of a kit. If I do well on this project I should be able to pass. Woo. I am god awful at physics so I'm pretty excited that I can potentially get an A at something in the class. So, I will be using this model. Please send me positive thoughts. 

If you get lost...

As promised, I have been looking for maze algorithms. I found two that are of particular interest because we can use them in real life size mazes. One is the left (or right) hand rule. It is technically called the...

Wall Follower algorithm

Start at the entrance and continue into the maze. Whenever you reach a junction always turn right (or left). This is equivalent to a human solving a maze by putting their hand on the right (or left) wall and leaving it there as they walk through the maze. If you like you can mark what cells you've visited, and what cells you've visited twice, you can retrace the solution by following those cells visited once. This method won't find the shortest solution. It is also ineffective when the goal is in the center of the Maze inside a closed circuit. In this case, you will end up going around the center and returning to the starting position. This method can also be used for 3d mazes by projecting the 3D passages onto the 2D plane. For example you would pretend up passages actually lead northwest and down lead southeast, and then apply normal wall following rules. The example starts out at the entrance to the maze following the left hand rule. As we go through the maze we make circles or loops and end up on a path that we were at before. The gray paths are these loops. We still follow the left hand rule, minding the areas that we have marked as loops and we eventually make it to end of the maze. As shown, this is not the shortest solution. It however, works on mazes with loops unlike the dead end filler method. 

The second, is the Pledge algorithm

This is a modified version of wall following that is able to jump between islands. It is used to solve mazes that wall following can't. It's a guaranteed way to reach an exit on the outer edge of any 2D Maze from any point in the middle. However it is not able to do the reverse, or find a solution within the maze. We start by picking a direction and continuing to move in that direction whenever possible. When a wall is hit, we start wall following until our chosen direction is available again. When wall following, we count the number of turns we make; a left turn is -1 and a right turn is 1. We stop wall following and continue in our chosen direction when the total number of turns we have made is equal to 0. Even if we have turned around 360 degrees or more, we keep wall following until we are untwisted and can continue in our direction. The counting ensures we eventually reach the far side of the island we are currently on, and jump to the next island in our chosen direction, where we will keep island hopping in that direction until we hit the edge of the maze. From here, wall following takes us to the exit. The pledge algorithm may make us visit a passage or the start more than once, although each time will always be with different turn totals. Thus this method can be extremely lengthy. As shown in the example, the solve continually tries to get to the right side of the maze while using the left hand rule.

As it turns out, these two examples have the exact same solution for the maze. I did not realize this until I posted the picture.