Thursday, May 2, 2013

The Last Melon....


I indeed did pass my physics test and with a whopping 85. It is the highest grade I have gotten all semester. Also, with the curve it gets bumped up to a 90. Therefore, I technically earned an A. Woo! I also got my motor to work. I had to throw out the old blueprint. It wasn't working. I couldn't figure it out. I also went and got magnet wire. This improved the workage of my motor by at least 249%. I first built the simplest of motors. Then I made the prototype bigger with the capability of running on 6 volts. My motor looks kind of sad and unprofessional but it works and it runs. Therefore I should get an A. Hopefully.

Most Basic of Motors


I also presented my research paper on Newton’s Universal Law of gravity. That went swimmingly. The class did not fall asleep. They understood and reacted to my message. I give myself an A- overall. All that is left is to pas my physics and calculus final. I will be graduating this semester so I will not be back in the fall. I think I’m going to miss S STEM because I now have no idea of what to do on my afternoons. I hope that the University of Houston has a program that is similar. Well, good luck to everyone. Don’t burn and have a nice summer!

Recap


Last week I pretty much spent the entire time trying to build a motor and preparing for physics. If you remember, I claimed that I am god awful at physics. I told you all that I was attempting to build a motor and attempt I did. With very little success all week. I built the model I showed you all but the nails refused to become magnetized. I couldn't figure out what I was doing wrong. Furthermore, I couldn’t figure out if I built it wrong or if it couldn't handle the current because I was using a 12 v battery instead of the recommended and required 6v. I as so annoyed I had to give up for the week and commit to coming back this week.

Last week I also finished my final report on mazes. I have only to finish the citation in APA style. Basically:
My paper  explores maze types and the basic maze solving algorithms. The algorithms presented can be understood without the use of or previous knowledge of computer science. The algorithms vary according to the types of mazes they can solve. Some algorithms require the use of two or more methods or the repeated use of an algorithm to find the solution of the maze. The algorithms are guaranteed to find a solution but not necessarily a single solution or the only solution. My paper is focused on 8 basic algorithms as presented by Walter D. Pullen.

That is pretty much my abstract. It is short, but I wasn't really doing an experiment or any research. It was pretty much for my own knowledge. Last week I also had to prepare for my physics test. I was pretty sure it was going to wind up like this:

Did I pass? Find out Next....

Friday, April 19, 2013

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. 




Friday, April 5, 2013

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.

Friday, March 29, 2013

Because a Picture is Worth A Thousand Words

DISCLAIMER: These pictures are not mine. I simply used the internet to find examples for you all


Arrow Maze

See. It has arrows as mentioned that must be used to get solve the maze. You would start at the gray block and follow the arrows until you found your way to the chekerboard center
Block Maze

I know we have all played this game. You move the blocks until you clear a path for  your freedom. This is actually a block maze. Who knew? Remain silent if you actually did so that I may have the credit.
Logic Maze

This maze is using basic math as a set of rules for getting through the maze. I don't know the rules for this maze though it interests me. Next update I shall share with you all how to get through this.
Unicursal Maze

This maze has only one pathway. It is near impossible to get lost in. As such, it is a labyrinth.
Multicursal Maze

I know that we probably all know at this point what a multicursal maze is. There is no need for an example. However, to keep consistency with the rest of my blog, I have provided a picture anyways.
Multiply-Connected Maze
and
Simply-Connected Maze

As you can see, the multiply connected maze has many areas where it is possible to make a circular path. To keep the concept simple and easy to understand, I found the most basic of pictures to demonstrate the idea.
Take it a step further and we get a Braid maze. See how it has no dead ends? Makes your head hurt doesn't it? Multiply connected mazes are used more often then one might think, such as in the case below. 
Pacman is a perfect example of a multiply connected maze. Many video games with around the corner suspense also use simply connected mazes (or mazes in general).
Weave Maze

Like stated, A weave maze has many passages that go over and under each other like bridges and tunnels.
Number Maze

For this particular maze. You start at the yellow number block. You can only move the number of spaces that is indicated on the block in a strait line. You keep jumping around using these rules until you find your way to the finish block. Personally, I can only do these types of mazes by starting at the finish and moving to the start. 
Planair Maze

This is a simple planair maze. Notice how the maze was made on the surface of a stack of cubes. They can be made on all types of surfaces to achieve  a variety of interesting  layouts.

Thursday, March 28, 2013

There is so Much More to Know


There is so much more to know about mazes. Let's start off with the types. I'll try to keep it interesting.

Arrow Maze
This is a type of logic maze containing some passages that may only be followed in one direction (denoted by the arrows). All mazes can be reduced to an arrow maze.

Block maze
A maze that cannot be solved without clearing the maze pathways of movable blocks is called a block maze (who knew?).

Logic maze
This maze must be navigated by following logical rules in addition to following its passages. One type may be a maze containing different colored symbols that must be passed in a certain order, or a maze that has some passages that may only be followed in one direction (like the arrow maze mentioned before).

Unicursal maze
A maze with a single path (like the labyrinth I discussed before).

Multicursal maze
A maze with at least one junction or more than one path (aka, not a labyrinth).

Multiply-connected maze
A multiply-connected maze contains one or more passages that loop back into other passages, rather than leading to dead ends. A well-designed multiply-connected maze is  difficult to solve because maze solvers will  spend a very large amount of time going around in circles. To take it a step further, a multiply connected maze can have no dead ends at all thus leaving a lot of solvers very irritated. This is called a Braid maze.

Weave maze
A weave maze has pathways that go under and over each other. They are three dimensional mazes because it exists in more than two dimensions. For example an outdoor maze that has bridges or tunnels is a partial weave maze. If it is drawn on paper, we are just looking at it from directly above.

Number Maze
This maze uses numbers (or letters or other symbols) by which the maze solver can jump to other areas in the maze by following the numbers, avoiding the usual walls. In other words, it is a teleportation maze.  For instance, a number maze with the letter "A" in two places would allow you to jump from one "A" to the other. Because of the teleports, these mazes are also partial weave mazes.

Planair maze
A mind-bending maze whose underlying topology is unusual (non-Euclidean) and which has edges that connect with one another. This is the technical term, to put it in plain English: A planair maze has a weird geometry. The edges are connected in more than abnormal ways. For example the maze might be made on the surface of a cube or ring.

Simply-connected maze
Simply-connected mazes have pathways that never re-connect with one another, so every path you choose either leads to another path or to a dead end. These mazes are easy because there is only one solution to a simply-connected maze, and it can always be found by following the "left hand rule.” You walk forward, keeping your left hand on the wall at all times and voila, the maze is solved.