LMICSE: Lego Mindstorms in Computer Science Education

Prerequisite Knowledge

A basic understanding of how to control the Turtle's movements as well as using data structures and other fundamentals in java.

Materials

Standard Turtle robot.

Task One

The first step is to design a world. We'll provide you with the a world class, all you have to do is copy the file over to your project folder and then add code to your main class to initialize the world and its aspects.

world name = new world(x, y);	Declares a new world with width x and height y. To the right, we can see a pictorial representation of a 8 x 5 world and the values of each cell. The world is implemented so that the upper-left most cell has an address of (0, 0) and the lower-right most cell has an address of (7, 4). However, due to the way that the world is implemented, in most cases the cells must be accessed by their value.
name.setStart(0);	Sets the starting point of the world to be the cell with value 0 (upper-left most cell).
name.setEnd(39);	Sets the final point of the world to be the cell with value 30.
name.buildObstacle(x1, y1, x2, y2);	Building obstacles in the world is a bit more difficult than declaring the start and finish cells because it uses a different value system. To build an obstacle, you need to pass the method a 'range' of cells where x1 is the left edge of the range, y1 is the upper edge of the range, x2 is the right edge of the range, and y2 is the lower edge of the range. So the following method calls would build the obstacles we see at right. name.buildObstacle(1,1,1,4); name.buildObstacle(3,2,6,2); name.buildObstacle(5,0,5,1); name.buildObstacle(6,1,6,1);

For information on how to use any other methods available through the world class look here.

Task Two

Now that we've got a world with all of the necessary parts built, it's time to start finding a path from the start cell to the finish cell. This time, we're going to use a depth-first search to find the path. In addition to using the depth-first search, you will have to make your method to implement the depth-first search recursive (the method calls itself either directly or indirectly). To do this you will need to use the stack that you implemented in Lab 13. The basic algorithm for a depth-first search is:

public static void dfs() {
	pop the stack;
	go to the popped cell
	mark the popped cell as gray
	if (item popped == final cell)
		done!
	else {
		while (more adjacent cells to process (children)) {
			push a child cell onto the stack
			visit the child cell
			dfs();
		}
		mark the popped cell as black
	}
}

Task Three

So we've built a world and found a path from start to finish. Now all we have left to do is traverse through the world with our bot. To do this, you will need to get the order with which the cells were visited from the world (x.getOrder(), which returns an array of cell values). From there, you will need to convert each cell value into x and y coordinates (x.getCoords()) and then tell the bot to go to that cell. But in order to get our bot to move any where, we must first initialize a control structure. You can do this by copying the control class into your project folder, and then declaring a control object in your program. With that being done, you can tell your bot to move to a specific set of (x, y) coordinates (bot.goTo(x, y)).

For information on how to use any other methods available through the control class look here.

Additional Problem

Try implementing a breadth-first search through the world. To do this you will need a queue rather than a stack, but the basic idea is the same.

Conclusion

In this lab, you learned the following:

• How to use a stack to store items
• How to implement a depth first search
• How to use a recursive method