LMICSE: Lego Mindstorms in Computer Science Education

Prerequisite Knowledge

Materials

The robot, but it should be rebuilt so that the center of gravity is as much over the center of the axle as possible.

Declaring a World

The first move in programming the bot so that it can move around in a world, is to create the world. The best way to do this, is to create a 'World' class. The world class should have a constructor that creates some two dimensional array that will hold values corresponding to each grid location in the world. We found, that a grid with dimensions 8 cells x 5 cells works best due to the limited memory inside the bot.

We will also need to create a method in the main class which can compute the distance to travel in order to move from one square to another. To do this, you can simply measure the width of one cell, and then have the method return the number of squares to move times the width of one cell in millimeters.

public static double cellDistance(int toMove) {
	return (toMove * cellWidth);
}

It would also be a good move set all of the cells on the outer edges of the grid to be -1, and all of the inner cells to be some high value so that later, when we populate the grid, the process is much easier. MOVE DOWN!

Setting the Goal and Populating the World

Now, we will need to populate the grid. The values inside the grid are going to be the number of steps that it takes to get from that cell to the goal. So we will need to initialize a goal cell with an internal value of 0 (0 steps needed to get from that cell to the goal). At this point, it is recommended that you create another class to represent the data of a cell. That way, each cell can be referenced as a single object. Keep in mind that when declaring the goal cell

legoworld.setEnd(x, y);

the x and y values should be between 1 and either 8 or 5, depending on what dimension it is. We do this to make sure that the goal cell is not placed in the exterior cells that are designated as bounding walls.

Once we've got the goal cell initiated, we are going to need to use a breadth-first search type implementation to assign values to the remaining cells in the grid. This can be done using a vector. It is suggested that you implement the vector with an array of cells, so as to save memory in the bot. To populate all of the cells inside the grid, the first step is to choose a starting cell, in our case the goal cell, and compare the value of the starting cell's value+1 to the value in the cells left, right, above, and below it. If this new value is less than the value that the cell currently holds, then we will want to change that cell, and move on to the next cell in the vector.

Building Obstacles

Next, we will need to be able to create obstacles in our world so that our bot does not always follow a direct line to the goal cell. To do this, create a method that reads in 2 sets of x and y coordinates

public void buildObstacle(int x1, int y1, int x2, int y2)

where the first set of coordinates is the lower-left corner of the obstacle, and the second set is the upper-right corner of the obstacle. This way, we don't need to build an obstacle for each individual cell that we want to block out, rather we can use the method to create a span of obstacles. However, if we only want an obstacle to fill one cell, then the two sets of coordinates should be the same. The purpose of this method, is to set the values of each of the cells within the span to -1 (unreachable by the bot).

Now, if we have written our populate method correctly, it should populate the grid so that the values in the obstacle cells do not change, and the values in the cells around the obstacle correspond to how many steps it would take to get by the obstacle on our way to the goal cell. The following picture shows how the grid should be populated if we were to call the following build obstacle methods: legoworld.buildObstacle(5,1,5,3); legoworld.buildObstacle(6,5,6,5); Note that all obstacles should be built before the goal cell has been initiated so as to not overwrite the goal cell.

Finding the Next Cell

Now that we've built a world and populated it, we should start to figure out how to get from a starting point to the goal. So first we need to initialize a starting point. To do this you should create a global cell that maintains the current position of the bot and just set the position of this cell to the coordinates that it receives as parameters:

public void setStart(int x, int y) {
	currentCell = new gridCell(x, y);
}

Next we need to write a method that looks at the cells left, right, above, and below the current cell and makes a decision as to what cell to move to. The method will also need to update the current cell so that it knows that it has moved. When looking at the cells around the current cell, we need to check to see if the value inside the cell is less than the cell inside our current cell. We also need to make sure that the value inside the surrounding cells is not -1; if it is, it should not be considered as a possible spot to move to, because according to how we have populated our grid, all obstacles and surrounding walls (positions not accessible by the bot) have values of -1.

The following is a the path that the bot could take to get to the goal after the following calls have been made: legoworld.buildObstacle(5,3,5,1); legoworld.buildObstacle(6,5,6,5); legoworld.setEnd(8,1); legoworld.setStart(1,1); *** Note that your bot may move up first, rather than right. It all depends on which location you look at first to see if the value is less than the value for the current location.

Some Additional Problems

Some additional methods that you may consider writing include:

• a method to reset all of the cell values
• a method that checks to see if the bot is in a 'high-value' cell (a cell that has not been populated because it is blocked off by obstacles)
• a method that checks to see if a cell is a wall / obstacle (has a value of -1)
• a method that checks to see if we are at the goal cell

Conclusion

In this lab, you learned the following:

• How to implement the right(), left(), calibrateDegreesPerMillisecond functions.
• How to declare and manipulate/use variables.
• How to use math functions on variables.