Due Tuesday 30 October at midnight
In this project, you will work with a graphical environment called GridWorld (partly described in chapter 5 of the textbook). In this environment, we can implement methods using conditionals and recursion, and see the results on the screen.
Create a new project named a3 within your gis502 folder, and call your new class BugRunner. Detailed instructions are available in assignment zero.
Before you get started programming the GridWorld, we need to import the library into your project structure. The last time you committed, git should have placed a lib folder within your gis502 folder, containing the file gridworld.jar. If you do not have this file, make sure your a3 project is has its “git root” configured and then select VCS » Update Project on the menu. You can also download the file here to add it to your folder manually: gridworld.jar (98k).
Next, make sure the ‘a3’ folder is selected in your Project window, and choose File » Project Structure from the menu. In the Project Settings section at the left, select Libraries. Then push the plus sign above the second column, and select “Java.”
You’ll see a file selector dialog. Navigate to your gis502 folder, then to the lib folder within, and select gridworld.jar. Click OK on both dialogs.
Now, back in your BugRunner class, add the import statements and the main method so it looks like the following. Customize the opening comment to your liking.
/* Assignment 3: A GridWorld[TM] production by Chris League
* GIS 502, October 2012
*/
import info.gridworld.actor.ActorWorld;
import info.gridworld.actor.Bug;
import info.gridworld.actor.Rock;
public class BugRunner
{
public static void main(String[] args)
{
ActorWorld world = new ActorWorld();
world.add(new Rock());
world.add(new Bug());
world.show();
}
}Select Run » Run BugRunner, and you should see the grid pop up. The rock and bug are placed randomly, so yours may not be in the same positions as shown below.
You are welcome to experiment with some of the suggestions and ideas in chapter 5. This task is related to exercise 5.1.
Create a method in BugRunner called moveBug. It takes the bug to be moved as a parameter.
public static void moveBug(Bug someBug) {
// Your code here.
}You can call this method from main by separating the new Bug expression from the world.add call, like this:
Bug theBug = new Bug();
world.add(theBug);
moveBug(theBug);Make sure this revision of the program still compiles. Its should not (yet) have any different effect on the grid that pops up… still one bug and one rock in random locations.
Now, we’ll start to add code to the moveBug method:
someBug.move();As described in the book, calling move() on a bug (in this case, someBug) moves the bug forward by one grid location along its current direction.
When the bug moves, it leaves behind a flower to show where it has been. Your bug is facing North by default, so when you run, you should see (without having to use the Step or Run buttons in the GridWorld interface), your bug with one flower behind it.
Now, let’s manually repeat that a bunch of times. Later on, we can automate the repetition using recursion. Inside moveBug:
someBug.move();
someBug.move();
someBug.move();
someBug.move();
someBug.move();
someBug.move();When you run this version, sometimes you won’t see the bug at all – she walked right off the edge of the grid!
Bye-bye, bug!
Protecting our bug from the horrors of the edge of the world calls for a conditional statement. Bugs have a method canMove() that determines whether the road ahead is clear. If it’s the edge of the world, or there is on obstacle in that location, canMove() returns false. If the next location in the direction she is heading is valid and empty, it returns true. This so-called boolean value is exactly the kind of thing we can use in an if expression.
Modify your moveBug method so that it checks canMove() before asking the bug to move(), something like this:
if(someBug.canMove()) {
someBug.move();
}Again, use copy/paste to repeat this action (including the conditional) 5 or 6 times. Now, on runs where the bug starts out in the upper half of the grid, you’ll see her stop short of falling over the edge, even if she didn’t make all 6 moves.
In this case, the first three occurrences of canMove() return true, so she moves forward. From that point on, canMove() returns false, so she stays put in row zero.
You can also see the bug encountering a rock as an obstacle, but you’ll have to place many more rocks to make it more likely. Just temporarily repeat the world.add(new Rock()) in main a bunch of times (before you call moveBug) and you may get something like this:
In this section, we’ll modify moveBug so that it uses alternative execution (if/else). Simply put, if the bug can move, it should move, but otherwise it should turn. Recall that the turn() method rotates the bug clockwise by 45 degrees.
Repeat that a few times (manually for now) on your rock obstacle course, and you’ll start to see some interesting behavior. In the example below, the bug had to turn right upon hitting the first rock, and it is in the process of turning right upon hitting another one.
Okay, now it’s time to do away with this manual repetition. I’ll guide you through the recursion for the moveBug method, and you’ll have to replicate the technique for the other methods, below.
We’re going to give moveBug one extra parameter, representing the number of times to move.
public static void moveBug(Bug someBug, int numberOfMoves) {
// Your code: Move or turn, just once (using if/else)
}Then, at the call site in main, we can ask the bug to make 40 moves, or 4,096 moves, or whatever you want.
moveBug(theBug, 40);Back in the body of moveBug, we already have the if/else code to move the bug once. Next we can call moveBug again, recursively, subtracting one from numberOfMoves, and do the rest:
// Now repeat N-1 times
moveBug(someBug, numberOfMoves - 1);There’s a problem with this recursive method as described so far: there is no base case. You should still try it out, just to see what happens. Your program should end with an error message in the IntelliJ output window, something like this (you’ll have to scroll all the way to the top of the output window to see this portion):
Exception in thread "main" java.lang.StackOverflowError
at info.gridworld.grid.BoundedGrid.get(BoundedGrid.java:87)
at info.gridworld.actor.Actor.moveTo(Actor.java:159)
at info.gridworld.actor.Bug.move(Bug.java:79)
at BugRunner.moveBug(BugRunner.java:45)This StackOverflowError is exactly what can happen if a recursive method goes on too long, which ours certainly did. We keep subtracting one from numberOfMoves, racing right past zero and into negative numbers. And before we ever get to show the grid, the program crashes.
The base case for moveBug is very similar to the one in the nLines method in section 4.8 of the book. It doesn’t make sense to move a bug a negative number of times, and to move a bug zero times, we just do nothing. So we really should only be handling cases where numberOfMoves is positive. Then, when numberOfMoves becomes zero, we do nothing and the recursion is over.
Your method will now look something like this (although I’m still not giving away the if/else portion from the previous section!)
public static void moveBug(Bug someBug, int numberOfMoves) {
if(numberOfMoves > 0) {
// Your code: Move or turn, just once (using if/else)
// Now repeat N-1 times
moveBug(someBug, numberOfMoves - 1);
}
}Now in main, you can just call moveBug with large numbers, and it does the repetition for you. Below is an example with 256 moves over a substantial set of obstacles.
Give the recursive treatment to the obstacle course, too. Instead of calling
world.add(new Rock());a whole bunch of times, create a method addObstacles so that you can just specify how many as its parameter:
addObstacles(world, 12);The declaration of addObstacles will look something like:
public static void addObstacles(ActorWorld world, int number) {
// Your code here
}Think about your recursive case: how do we add one rock, and then what do we call to add the rest? Once you have that, you’ll be headed for another StackOverflowError, so what should your base case be?
Once your recursive addObstacles is working, you won’t need to repeat statements manually to get a specified number of rocks on the screen.
Your last method in this assignment will take the bug on a random walk. (Don’t worry, you won’t need any of the crazy math on that page.)
public static void randomWalk(Bug someBug, int numberOfMoves) {
// Your code here
}Section 5.3 of the book gives an introduction to random numbers using Math.random(). You should experiment a bit with those sample expressions, to see the results. For example, print the last expression several times, in main:
System.out.println((int)(Math.random()*6)+1);
System.out.println((int)(Math.random()*6)+1);
System.out.println((int)(Math.random()*6)+1);
System.out.println((int)(Math.random()*6)+1);Every time, you’ll get numbers in the range 1…6. Here are a few sample runs I got:
5 1 3
1 1 3
4 6 5
5 4 3Now… to take a random walk, we don’t need numbers in that particular range, so you’ll have to adapt the expression accordingly. Instead, we want to generate a random angle, either 0 (North), 90 (East), 180 (South), or 270 (West). Think about how to achieve that using Math.random().
Once you have a random angle, you can call setDirection on your bug, and then do the same canMove()/move() logic. You don’t have to use turn() this time – if the angle we chose doesn’t allow us to move forward, then we’ll just try again next time.
Make the randomWalk recursive, so it makes numberOfMoves steps. Below is an example of a random walk with 12 obstacles and 256 steps. It’s hard to tell the exact path the bug took, but it’s visiting a substantial portion of the map.
When finished, as before, you will have to commit and push using git in the Changes window of IntelliJ. Detailed instructions are available in assignment zero, if you need a reminder.