Designing a Breadth First Search Maze Algorithm

Efficient maze algorithms have immense practical value. Think about the future; what do you see? I see a bunch of robots cleaning my house, vacuuming and gathering up all the stuff I left on the floor. But any house is bound to have a tangle of furniture sitting around. To an unthinking robot, this is a maze, an unknown area with impassable ‘walls’ seemingly randomly placed around. If we want our robot butlers, we’re going to have to design some sort of program that can solve this traversal puzzle.

First, we must establish the rules of the mazes we’ll be solving. Each maze will consist of any number of square tiles. Each tile will have up to three impassable walls on any of its sides. Each maze will have one start tile and one end tile. The goal is, of course, to travel from the start to the end. In pursuit of this, we will be able to move only straight up, down, left, or right. Never diagonally. Lastly, our vision will be limited to the tile we’re on, we can only tell if a tile is the end tile if we’re standing right on it.

With these new rules, let’s take a look at our first maze:dfs 1When we begin, the location of the end tile is unknown. Keeping this in mind, there’s clearly only one thing to do: we must systematically search every tile until we find the end tile. In other words, we must create a search algorithm

If we assume that there will be no dead ends, only two rules are needed to start:

  1. Go straight until you hit a wall, a previously visited tile, or the end tile. If you are on the end tile, stop. If you’re not on the end tile, go to rule 2.
  2. Turn and move to the next unvisited adjacent tile. Then go back to rule 1.

Let’s see what happens when we use these two rules on the maze from before:
dfs 2
This is the result we were looking for. But we’re not done yet. If you remember, we assumed with those rules that we would never reach a dead end, so now let’s look at an example where there is a dead end:dfs 3

We are now trapped, and neither of the two rules from before work in this situation. To come up with the next rule, let’s think about what we want. Clearly, we want to move up and around to the center tile. In this case, if we simply retrace our steps we’ll end up right next to the open space.This give us a possible third rule:

       3. Trace your moves back until there is a clear path to an unvisited tile, then move there.dfs 4You may think we’re finished, since we seem to be able to navigate through any problem we come up against, and to some extent, you’re correct. With the three rules we have so far, any maze that follows the format we’ve designed can be navigated. However, now certain inefficiencies must be dealt with. Take a look at this next map:dfs 5

Suddenly, our problem becomes apparent. The open space is only a few tiles away, but with the “retrace steps” rule, many more tiles will be checked then need to be.

So if the first version of rule 3 doesn’t work, what will? Well, instead of retracing, we will have use a list to evenly search the already traveled spaces. Let me show you how:dfs 6I want to pause for a second to talk about the type of list we just used. Please notice, whenever a tile was added to the list, we always put it at the end. Whenever we removed a tile to check it, it was taken from the beginning of the list. In Computer Science, this is known as a queue. A queue is a ‘first in, first out’ data structure, and in this case it serves the purpose of searching the maze evenly as we spread out, a breadth first search.

Look back at before. If we had not found that unvisited tile, what would have happened? Well, because we were using a queue, our search would have continued down the two paths; one tile from one side, then another tile from the other side. If we had not used a queue, depending on how else we designed rule 3, we might have the same inefficiency problem as when we were just going back along the path we came.

With that quick aside, let’s restate the rules with the new rule 3:

  1. Go straight until you hit a wall, a previously visited tile, or the end tile. If you are on the end tile, stop. If you’re not on the end tile, go to rule 2.
  2. If there is an adjacent unvisited tile, move to that tile, then go back to rule 1. If not, go on to rule 3.
  3. Add all adjacent tiles to a queue. Get the the next tile from the queue and add all of its adjacent tiles to the queue. Keep doing this until one of the tiles you remove from the queue is an unvisited tile. Then. go back to rule 1.

 

With this, we’re finally done with our maze algorithm! Rules 1 & 2 give us simple movement around the maze, and rule 3 will kick in whenever we hit a dead end. Because of the queue, rule 3 should work as quickly and efficiently as is reasonable. And, since we designed our rules well, any maze that follows the template from the beginning can be traversed by this simple maze algorithm. One step closer to robotic servants!

 

If you want to see my implementation of this algorithm, you can click here to view it on GitHub.

If you want to see more articles, click here.

Dijkstra’s Algorithm Explained

One of the classic human problems is getting from point A to point B. This is because, whenever you move, you’re faced with a choice: how are you going to get there?

If I want to get to Los Angeles from New York City, I have several options. I could use a train, a plane, or a car, and I have many different routes I could take. I could even drive to Dallas first, then fly the rest of the way. Deciding which mode of transportation and path I want to use all comes down to finding one final “total cost.” This total cost is time, hassle, and money, all combined into one easy to compare number for any one part of the trip. This is the heart of Dijkstra’s algorithm.

Dijkstra’s algorithm, given a map of points and paths between those points, will give you the cheapest path from one point to any other point. Cheapest meaning total cost, not necessarily miles or money. Going back to our NY to LA example:

Dijkstra 1

Above, you can see several different points you can go to. Notice the costs assigned to each path. Remember, this is the total cost. It is always better to take a path with a lower cost.

With this map we return to our question: what is the best way to get from NY to LA? First, let’s simplify:

Dijkstra 2

Despite the lack of city names and background map, for our purposes this simplified map is exactly the same as the first. Whatever the shortest path from A to D is will also be the shortest path for NY to LA.

On to Dijkstra’s algorithm itself, which is easy to do by hand. All we need is a chart to keep track of a few things:

Dijkstra Chart

In this chart each row represents a point on the map. The ‘cost’ column keeps track of how expensive the path that leads to that point is. The ‘previous’ column keeps track of what point is before that one in the chain back to the starting node. The default value in the cost boxes is infinity because to start with, there are no connected points, so anything would be better.

That may be a lot to take in, but I think it will become clear how it works as we go through the algorithm. The process is simple; we need to check every point’s paths against the chart. Let’s begin:

Dijkstra 3

A is the starting node, so we need to check its paths first. A to B has a cost of 3, and B’s current number in the cost column is infinity. To see if we need to update the chart, we see if the new path is less than the current cost. 3 is less than infinity, so we change that row into:

Dijkstra 4

The chart has been updated. We have the new cost of the path leading to B (3), and the previous point in the chain back to the starting point (A). Now, it’s time to do the same thing for A to C and A to D. Traveling to C from A costs 7. 7 is less than infinity. Traveling to D from A costs 9, which is also less than infinity, so we can update the chart with both of these new numbers:

Dijkstra 5

We have examined all of A’s paths, so now we can move on to point B. The first B path is B to A, however, with this algorithm, any paths leading to points that have already been examined can be skipped. B to A leads to A, and we just looked at A, so we skip that path. Next up is B to C.

To evaluate this path, I need to explain what we’re doing a bit more. You may think we should compare 1 (the cost of B to C) and 7 (the number in C’s cost column). That is almost correct. However, when we compare the numbers, we actually have to use the total cost of the current point added to the cost of the path, and the total cost of the other point.

What do I mean when I say total? Total in this case refers to the number in the point’s cost column, plus the cost of all previous points, going back to the starting point. Again, this will be more clear as we continue with the algorithm.

Back to B to C. The total cost of B (the cost all the way back to A) is 3. The cost of the path we’re looking at is 1. 3 plus 1 gives us our first number, 4. The second number is the total cost of C, which is 7. 4 is less than 7, so we update the chart again:

Dijkstra 6

Notice, we did not put 4 in the cost column, instead we have 1 there. To reiterate: the cost column is the cost of the path leading to that point, not the total cost to get to that point.

I’d like to pause for a moment to explain what else could have happened there. We updated the chart because the total cost of our new path (A to B to C) was cheaper than the cost of the old path (A directly to C).

Now imagine the path from B to C had a different cost, let’s say 20. What would we have done then? Well, the total cost comparison would have been, is 23 less than 7? 23 is, of course, not less than 7. Whenever the new number is not less than the one in the chart, you simply move on to the next path. In this example, the C column would have remained 7, A.

Back to the algorithm itself, which we can already see working. We can use the ‘previous’ column and work backwards to find the shortest path. Starting from the C row, C’s previous is B. B’s previous is A. This means the shortest path from C to A is C-B-A, which, if we look at the map, is true. There is no cheaper path from C to A.

The next path is similar to the last, B to D. adding the numbers together, We see that 6 is less than 9. So:

Dijkstra 7

Almost Done! With point C we can skip C to B and C to A, because we have already checked A and B. That leaves C to D.

To get the first number, we need C’s current total cost. At first glance, it may seem to be 1, but remember, total cost is the cost all the way back to A. So we take 1 (C-B), add that to 3 (B-A), add 2 (The new path, C-D), and we get our first number, 5.

The second number is just the total cost of D. D-B is 3 plus B-A which is also 3, which gets us 6.

5 is less than 6, so we update the chart one more time:

Dijkstra 8

We don’t actually need to check the last point, because every path it has leads to a point we’ve already done.

And with that, the Dijkstra’s algorithm is complete! The original question was: what is the best path from D to A? Looking at the chart, D’s previous is C, C’s previous is B, and B’s previous is A. What does that mean? It means the best path from A to D is A-B-C-D!

Transferring that to the other map:

Dijkstra 1

Based on the answer we got, the best way to LA from NY is NY to Bismarck to Dallas to LA. If you look carefully, you can see that there is no cheaper path between these two cities, which means Dijkstra’s algorithm has worked!

After all of that, you may not be too impressed. Just looking at the original map you could probably find the correct path pretty quickly. However, what if we had included every city and flight path in America? You might never be able to figure out the cheapest way to get anywhere! That’s the real advantage of Dijkstra’s algorithm, it works on any map of this format, no matter the size.

The other advantage is it’s relatively simple to remember. Go through each point’s paths. If the path plus the total cost of the current point is less than the total cost of the other point, update the chart. If not, move on the the next path. That, is Dijkstra’s algorithm.

 

If you want to watch my video demonstration of Dijkstra’s algorithm, you can watch that here.

You can see my implementation of Dijkstra’s algorithm on GitHub here.

To see more articles, click here.

Basic Minimax Tic-Tac-Toe

basic minimax 1Making a computer play any type of game is difficult. You need to make it consider every element, every possible situation that could arise. Because of this, some games are considerably more complicated to program for than others. Chess, with its 8×8 board, dozens of individual pieces, and millions of possible moves, is more complex than Tic-Tac-Toe, which only has a 3×3 board, one type of action, and limited possible moves. For ease of programming, we will begin with Tic-Tac-Toe.

Like the game, our goal is simple; make a program that will play against a human player. We will design the program to try to win the game. However, if it can’t win, it will try to tie the game. To begin our planning, let’s look at a simple example.

basic minimax 2That wasn’t very complicated, but it’s good to start with simple cases. Let’s try another board.

basic minimax 3From these two examples, we now have two rules for how our program should behave:

  • If there is a move that will make you win, play there.

And if there is no winning move:

  • If there is a move that will block the other player from winning, play there.

Both of these rules have something in common. They require the program to analyze the board. Playing in the winning spot is impossible if you don’t know where that spot is. Let’s go back to the previous example. The image above only showed one of the possible actions we could have taken. It skips an important step; choosing the correct action. We have one arrow leading to one board, but what if we showed every possible move the computer could have made?

basic minimax 4This branching map demonstrates exactly what we want our program to do. When given a board, it should simulate every possible move that the computer could make, and give a score value to each option based on what the outcome of each branch is. We can use this same algorithm at any point on the board. Let’s continue this example tree.

basic minimax 5.pngDo you see what’s happened here? Using this simple system, we can break a winning Tic-Tac-Toe strategy down into a few basic steps.

  1. Simulate playing in each open space.
  2. Rank each of those possibilities based off of who wins. one for a program victory. zero for a tie or there still being open moves. Negative one for human victory.
  3. Choose the highest number available.

A program that follows these steps will be able to win many Tic-Tac-Toe games. However, there is still one big problem. Strategy. Our program blocks the opponent if they are about to win. But, it doesn’t plan ahead to stop unwinnable situations. Additionally, It doesn’t maximize winning. There is no method of making a board that will increase the likelihood of winning. All it does is stop itself from losing.

This version of our program isn’t completely non-functional, though. It acts like a human child playing the game. It stops itself from immediately losing, wins if it can, but has no plans for the future.

Click here to read about how to add strategy to this algorithm.

First Week of Teaching

I had been taking robotics and programming classes at Storming Robots for four years, when I was offered a job there. Over the summer, Storming Robots holds week long robotics and programming camps for grades four through eight. It’s eight students, and two instructors per class. There are usually five classes going on at a time. Most of the instructors are high school or college students.

image1

Let me walk you through my first week, the class was called vex IQ quadruped. Vex IQ being the hardware the students were using, quadruped being the type of robot they were building. All instructors show up an hour before students for setup. When I arrived, I met the main instructor for my class, and we went over what we would be covering that day.

We had a full class of eight students. Two of the students said they had no programming experience, the rest said they had a small amount of experience. Opening the class, we gave out the Vex IQ robot brains and programming exercises. As we had planned, all the students spent the whole first day working the the exercises.

The  second day, robot construction began. Previously, in preparation for the class, I had constructed the quadruped robot the students would be building. It took me an hour. In a classroom environment, working in teams of two, with some help from two instructors, it took the students a whole day. This ended up being a pattern for all future classes. Apparently, it’s much easier to get distracted while building than when programming.

The next two days were all about programming simple movements, Turning, walking with one leg at a time, walking with two legs at a time, and so on. Trying to get get even basic movements done is difficult with the four legged quadruped design. Most of the classes at Storming Robots use wheeled robots for a simple reason, legs are hard. Any motion required each leg to move just the right amount at exactly the right time, or else the entire robot would lose its balance and fall over.
The last day of the week is always presentation day. All the parents arrived in the classroom forty five minutes before the end of class. Each team talked about one thing they worked on, and showed off one of the simple movements they programmed.

All the presentations went well. As I learned in the coming weeks, each class tends to be fairly balanced when it comes to talking in front of people. My first week was no exception, I had two students who were very comfortable and entertaining, and one student who would rather not have talked at all.. The bulk of the class weren’t experts or super happy about it, but they all did well.
Once presentations were over, the head teacher and I had the fun job of disassembling all of the robots. Watching the students build the things was riveting enough, but taking them apart was even more exciting.

My first week of teaching was a bit stressful, since it was basically my first time teaching anybody anything, but it was a good example of what a typical week at Storming Robots is like. Trying to keep the class focused, trying to help someone figure out what they did wrong, and trying to make it all entertaining and educational for the kids.

About Dan Carroll

I’m told that in writing you’re supposed to have something at the beginning to grab the reader, a joke, or something interesting that pulls them in. I couldn’t think of anything, so I decided to describe a writing principle in a desperate attempt to sound profound.

Anyway, let me actually begin. My name is Daniel Alexander Carroll I’m currently a home schooled Junior in high school. For two years I was on an FTC robotics team called Team Overdrive. I spent last summer teaching kids how to program robots at a learning center called Storming Robots. Now I teach one class a week at Storming Robots, in addition to the C++ algorithms class I take there. When I’m not trying to make computers do what I tell them, I like making comic books. My only problem with the comics is my incessant inability to draw.

That was a good summary. Quick and to the point. Unfortunately, most of the things on this website will not be able to be described in that way. I’m going to use this blog as a place to put some stories of my many teaching and robot adventures. If I ever finally finish a comic book I’ll probably put it up here too. Lastly, I’m going to make some summary and demonstration pages about some of the C++ projects I’ve done. Minimax Tic-Tac-Toe AI, Huffman compression programs. That sort of thing.