6 - Case Study 2 - All Along The Watchtowers

By the end of this chapter, the reader will be able to:

In our second case study we are going to pull in the powerful idea of a for loop to solve a particular map - this one has no ghosts we need to worry about, instead the challenge is based on providing the instructions to Pacman that allow him to navigate this puzzle.

For this puzzle we are going to need to approach it in stages - first we will do the easy bit, and then look at the harder bit. But before we talk about the solution, we need to look at the map itself!

As always, we begin with the first few lines of code that open up the map:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); main.setMap ("all_along_the_watchtowers"); main.showGame(); } }

The map looks like this:

Fig 6.1: All Along The Watchtowers

Yowza - right away we can see that there are too many instructions for us to reasonably code using sequential statements. We need Java to do most of the work for us because, as has been indicated previously, we are fundamentally lazy people. Pacman in this case starts near the middle of the map, meaning that we don't even have a clear starting point for eating the pills - we just need to pick where we're going to start.

Well, Pacman is facing upwards to begin with, so let's just move him along to the wall he's facing - that seems like a reasonable starting point. By counting, we can see there are ten spaces between him and the wall. We could hard-code this ourselves with sequential statements if we were feeling masochistic:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); main.setMap ("all_along_the_watchtowers"); main.showGame(); main.move(); main.move(); main.move(); main.move(); main.move(); main.move(); main.move(); main.move(); main.move(); main.move(); } }

But why should we? We know what we want Pacman to do - we want him to move. We also know how many times we want him to move - ten times. This sounds like an excellent place to make use of the for loop we learned in the last chapter.

First we need our counter variable - as tradition dictates, we'll call this i:

int i;

And then we need our for loop - remember the three pieces of information we need to supply to the for loop. The first of these is the value to give the counter variable at the beginning of the loop - as is usual, we set this to 0. Second, we need to tell Java how many times to repeat the loop, and in this case it will be repeated while our counter variable is less than ten. Finally, we need to tell Java what to do with the counter variable each time around the loop - we're going to add one to it:

Fig 6.2: The Structure of the For Loop

The code that goes inside the braces is simple - we just want Pacman to move. Putting this all together gives us the first piece of code that moves Pacman ten times, bringing him to the edge of the map:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i; main.setMap ("all_along_the_watchtowers"); main.showGame(); for (i = 0; i < 10; i++) { main.move(); } } }

Running this program gives us Pacman at the border:

Fig 6.3: Pacman at the Border

That's a start - now our problem is much more traditional - following the trail of pills. Now we move onto the second part - eating the pills around the edge of the map.

Now, the process for Pacman moving around each of the edges is no different from getting him to the edge in the first place - we face him in the right direction, and tell him how many times to move. To begin with, let's face him towards the right and move to the top right-hand corner - that's ten spaces from where he is now, and so we use a for loop that is identical to our first:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i; main.setMap ("all_along_the_watchtowers"); main.showGame(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 10; i++) { main.move(); } } }

This brings us to the first corner:

Fig 6.4: Pacman at the Corner

Okay, now we turn him right again and move him to the next corner - that's a total of nineteen spaces away (a figure obtained by counting the dots), and so we use a slightly different for loop to get him there:

for (i = 0; i < 19; i++) { main.move(); }

The only thing that changes here is the condition we use to tell how many times we repeat - for this for loop, we repeat while the counter is less than nineteen. Adding this into our program gets him to the bottom left corner:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i; main.setMap ("all_along_the_watchtowers"); main.showGame(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } } }

Like so:

Fig 6.5: Pacman at the next Corner

The process for getting to the remaining corners is exactly the same - turn him towards the right and move nineteen spaces. One repetition of this code takes us to the bottom left corner:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i; main.setMap ("all_along_the_watchtowers"); main.showGame(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } } }

And one more to take us to the top left:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i; main.setMap ("all_along_the_watchtowers"); main.showGame(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } } }

Like so:

Fig 6.6: Pacman at the next Corner

And now to finish off the edge, we turn him to the right and step him to the last pill on that line:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i; main.setMap ("all_along_the_watchtowers"); main.showGame(); // This takes us to the edge. for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); // This takes us to the top right corner. for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); // This takes us to the bottom right corner. for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); // This takes us to the bottom left corner. for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); // This takes us to the top left corner. for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); // This eats the last of the pills on that edge. for (i = 0; i < 8; i++) { main.move(); } } }

And voila - all the pills around the edges have been consumed by our voracious yellow dot:

Fig 6.7: No More Pills On The Edge

Remember why we use for loops in the first place - they reduce repetition... and yet, we've repeated our for loops a number of times throughout here - specifically the for loops that take us the nineteen steps between one corner to another.

In the last chapter we talked about nested for loops - for loops located within for loops. We can use a for loop to repeat a for loop giving us much tighter code, and they work a little like the hands on a clock - for every X number of iterations of the inner loop, there is a single iteration of the outer loop. Let's look at how we actually perform this part of the program at the moment:

main.turnRight(); // This takes us to the bottom right corner. for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); // This takes us to the bottom left corner. for (i = 0; i < 19; i++) { main.move(); } main.turnRight(); // This takes us to the top left corner. for (i = 0; i < 19; i++) { main.move(); }

See a pattern there? You should - first we turn right, then we move nineteen spaces. Then we repeat that pattern twice. How about if we put that code within a for loop of its own:

// This is the outer loop. for (j = 0; j < 3; j++) { main.turnRight(); // This is the inner loop. for (i = 0; i < 19; i++) { main.move(); } }

We need to give ourselves another counter variable for this - we can't operate nested for loops off of the same counter without some exceptionally freaky results. So we declare an integer variable called j and use that as the counter variable for the outer loop - for every iteration of the outer loop, the inner loop will iterate nineteen times, and it is the two separate counter variables that allow us to achieve this.

Breaking this repetition into a nested for loop tightens up our code considerably and makes it easier for us to do the next part of it - we've already identified that the process of getting from corner to corner is identical. So too is the process of eating the pills around the towers at each corner, so we just need to put them, where appropriate, into our new nested for loop.

Let's look at the towers and see what we need to do to eat all the pills around these when we get to a corner. It's actually a microcosm of what we're doing to eat all the pills around the edges. Let's say we're looking at the top right corner - when pacman gets there, this is the state of affairs for the map:

Fig 6.8: Step By Step 1

Now, what does Pacman have to do to eat the pills around the wall? First he has to turn right:

main.turnRight();

Then move two spaces:

main.move(); main.move();

This brings him to the bottom right hand corner of the wall:

Fig 6.9: Step By Step 2

What now? Well, he turns right and moves two spaces:

Fig 6.10: Step By Step 3

And then he turns right again, and although he has only to move one space to eat the pill, he still has to get back to where he started to continue on his journey - so he needs to move two spaces in reality, then turn right and move two spaces to get back to the corner he started in:

Fig 6.11: Step By Step 4

In full, that code is as follows:

main.turnRight(); main.move(); main.move(); main.turnRight(); main.move(); main.move(); main.turnRight(); main.move(); main.move(); main.turnRight(); main.move(); main.move();

Say, that looks like an awful lot of repetition! Let's break that up into another loop:

for (i = 0; i < 4; i++) { main.turnRight(); main.move(); main.move(); }

And then put it into the context of our program:

for (j = 0; j < 3; j++) { for (i = 0; i < 4; i++) { main.turnRight(); main.move(); main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } }

Run this, and you'll see that Pacman quite happily munches along the rows, does a circuit around the tower, and then continues on where he left off onto the next corner where he repeats the process.

Pacman now almost eats all of the dots on the map - there's just one problem - when he gets to the top left corner, because we only repeat our circuit around the tower code three times, he leaves those tasty dots alone:

Fig 6.12: You missed a spot

How do we deal with that? Well, we have two choices.

• The map is considered to be complete when there are no dots left - the game won't execute any code that occurs after all the dots are gone. Our first solution is to simply ignore the special handling code for the last few dots and extend our for loop by one iteration - it will never walk Pacman to the last corner because it'll stop running when he's finished the map.
• We can add a repetition of the loop for that specific corner.

That gives us two possible solutions - which is best? Solution one looks like this:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i, j; main.setMap ("all_along_the_watchtowers"); main.showGame(); // This takes us to the edge. for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); // This takes us to the top right corner. for (i = 0; i < 10; i++) { main.move(); } for (j = 0; j < 4; j++) { for (i = 0; i < 4; i++) { main.turnRight(); main.move(); main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } } } }

Solution two looks like this:

import draconia.APE.pacman.*; public class AllAlongTheWatchtowers { public static void main (String args[]) { PacmanGame main = new PacmanGame(); int i, j; main.setMap ("all_along_the_watchtowers"); main.showGame(); for (i = 0; i < 10; i++) { main.move(); } main.turnRight(); for (i = 0; i < 10; i++) { main.move(); } for (j = 0; j < 3; j++) { for (i = 0; i < 4; i++) { main.turnRight(); main.move(); main.move(); } main.turnRight(); for (i = 0; i < 19; i++) { main.move(); } } for (i = 0; i < 4; i++) { main.turnRight(); main.move(); main.move(); } main.turnRight(); for (i = 0; i < 8; i++) { main.move(); } } }

Which of the solutions is better? Both will work completely, both will complete the map in the same number of steps - what is there to distinguish the two?

Solution one relies on a feature of the game itself - the excess steps will never be executed because the game terminates before that is the case. Relying on a feature of the programming environment like this is somewhat risky - that could change in future versions of APE, at which time your solution will not behave the way it should. On the other hand, it is very tight code with a minimum of repetition.

Solution two doesn't make use of a feature of the APE engine, and so if that particular behaviour of APE changed in the future it wouldn't alter the way our solution worked. On the other hand, we're repeating a well-defined process which could cause maintainability problems in the future.

In the real world, neither of these would be considered acceptable solutions - the proper solution is to break off repeated functionality (such as skirting around the towers) into a separate method and call that where appropriate. For now though, either of these solutions would be appropriate considering the limitations we have regarding programming syntax. For the purposes of this book though, we'll go with Solution one because the downside to that solution is hypothetical and may never happen, whereas the downside to solution two is a feature of the program structure.

Anyway, we put it all together, and run - and Pacman skirts around the edges of our walls like a hover mower. He consumes each and every pill in his path, and comes to a neat stop when the last of these has been digested. A win for us!

A Further Improvement for the Reader

There's one more area we could tighten up the code here:

for (i = 0; i < 4; i++) { main.turnRight(); main.move(); main.move(); }

The repetition of the move here is a minor annoyance, but it could be resolved with an application of another for loop - this would give us a for loop within a for loop within a for loop. Implementing that is left as an exercise for the reader.

For loops reduce repetition in a program and allow us to easily deal with what would otherwise be complex and unwieldy sequential statements. Although there is nothing in this program that could not have been achieved using only sequential statements, the program would be virtually unreadable, very tedious to code, and difficult to change should the map be altered. Our solution on the other hand means that if the map changes, it doesn't take us much effort to change our code to adapt.

If you want to see the level of difference this makes, try developing a solution to all_along_the_watchtower that uses only sequential statements. Then change the map you are using to all_along_the_watchtower_revisited and see what you have to change to make it work properly. Then compare it to how much you have to change to get your looped solution working - the difference is quite staggering.

Further Reading

The following table details further reading on the topic in this chapter, and also any external resources that you may find useful.