9 - Case Study 3 - Sensing The Environment

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

We've covered a lot of ground over the past few chapters, and at this point we can start pulling together all of the topics we've discussed into a piece of code for Pacman that can help him make decisions about how best to solve a particular map. Pulling together different topics in this way is known as assimilation, and it is the hallmark of successful programming - none of the topics we discuss should be practised in isolation, it is only when they are brought together that they become truly powerful.

In this chapter we're going to write a routine for Pacman that allows him to navigate a number of different maps with no change in the code - we have all of the tools we need to accomplish this now; it's just a matter of approaching the problem from a particular perspective.

There is a particular approach that we need to take when programming - to write code to be as general as possible so it can be applied to multiple different situations. Code that can be applied to many different situations is known as generalisable code. Developing such code is very important to software development - any program of real complexity is too difficult to write without minimising the work you have to do, and generalisble code has a number of properties that makes writing code simpler:

1. Once you've written a general piece of code, it means you don't need to write it again - you just apply it to all the situations where it can be used.
2. Generalised code is easier to read, usually. A feature of a generalised piece of code is that it is largely abstracted away from the fine detail, which means you can concentrate on the structure of the code rather than on the specifics.
3. Generalised code is easier to fix, again because of the structure. It's also the case that when you fix it once, it's fixed for everything using it - this is something that isn't true of code that is written for one specific purpose (or what is known as ad-hoc code).

At the moment, we're missing discussion of two particular tools designed to allow for generalisible programming (specifically, methods and arrays), but we can start getting into the habit of thinking about programs in as general a way as possible to ease our development.

It's impossible to write a purely general program, because every program you write will have its own little features that must be coded around - the first thing we need to write a good solution to a program therefore is a sound understanding of what the problem is.

The next thing we need is an understanding of which parts of the program can be generalised and which cannot. Partially this comes from experience, but it also comes by looking at each separate part of the program you have to write and asking the question 'Will there be a situation in the future when I may want to do this or something similar?' If the answer is yes, then you should look for opportunities to make your code as general as possible to save you development time in the future.

Finally, we need to consider how to make our code general, and this involves a process called abstraction. We ignore the specific details of the situation and concentrate only on the structure of the situation, and then we consider how we could develop a solution to this structure that would work for other similar situations.

This is something harder to explain than it is to show, so let's consider first a potential 'real world' problem and then a corresponding APE problem to show the techniques.

The 'real world' situation is this - you've woken up one morning and found yourself in a room in an unknown hotel in a strange city. How do you get home?

Well, let's look at the first of our techniques - truly understanding the problem. The problem isn't that we're in a hotel room; it's that we don't know where we are. It doesn't matter if we're in a hotel room, or a strange car, or the gutter. The fact is we don't know where we are and thus we don't know where we have to go to get home. Our problem therefore is an information gathering task, and then applying the information we gather to get home.

The second technique is to get an understanding of what parts of this problem have general solutions and which don't. Finding out where we are when we're in a hotel is pretty easy - ask at the front desk and hope they speak a language with which you are familiar. That's not going to be the case if you simply wake up in a gutter. Gathering the information isn't generalisible in this case.

But once we've gathered the information, it becomes the same problem for every starting situation. Once you know where you are, you want to know where the nearest mass transport location is. Once you get there, the solution to every starting situation is the same. So our solution to waking up in a strange hotel may be:

1. Ask at the front desk where you are.
2. Use your credit card to get a cash advance.
3. Call for a taxi
4. Take a taxi to the nearest most appropriate mass transit location.
5. While you are not home use the mass transport system to take you to the next mass transport system that will allow you to move closer to your destination

On the other hand, waking up in a gutter:

1. Make your way to a main street.
2. Look for an information point or a police officer or a passer-by to ask where you are and where the nearest cash machine is.
3. Make your way to a public telephone box.
4. Call for a taxi.
5. Take a taxi to the nearest most appropriate mass transit location.
6. While you are not home use the mass transport system to take you to the next mass transport system that will allow you to move closer to your destination

The last three steps of both situations are the same, and so they call for a general solution to that part of the problem, although the first few steps are markedly different and so can't be easily generalised.

Now let's look at that in the context of an APE program. Imagine we've been tasked to write a program for Pacman that will be able to solve any map that conforms to a basic structure:

1. The dots on the map define an unbroken line, and that line begins in a square adjacent to pacman's starting position.
2. Only one dot is ever adjacent to pacman at his starting position.
3. There may be many obstacles on the map.
4. The line of dots on the map does not cross over at any point, and there are never more than two dots touching any other dot on the line.
5. The number of dots on a map is variable.

Let's say we've been given three such maps (these are unbroken_line_1, unbroken_line_2 and unbroken_line_3):

Fig 9.1: unbroken_line_1

Fig 9.2: unbroken_line_2

Fig 9.3: unbroken_line_3

The solution that we may have taken in the past is to simply solve each of them individually making use of an appropriate selection of for loops. However, a generalisible solution is one that will work for all maps that have the properties outlined above. Our solution won't necessarily work for maps that don't conform to all of these properties, but that's okay - we can only go so far after all.

Let's apply our first of our techniques - understand the problem fully. In this case, we've actually got the problem outlined for us in the properties of the maps... usually we'll need to derive these ourselves. But let's look at what the implications are here for how these maps work.

An unbroken line of dots means that there is full continuity between the start point and the end point. There is no ambiguity over where the dots begin and end - they begin at Pacman, and they continue until they reach and end-point.

The second property means that we don't need to make any decisions for Pacman as to which way he should go at the start, he just follows the dots.

The third property means that we can't simply have Pacman move over every square in the map, because he will be blocked by obstacles and it's perfectly possible that certain parts of the map will be completely blocked off by obstacles or the obstacles will be placed in such a fiddly way that we can't guarantee coverage of the map without some sophisticated code to deal with the layout of the map.

The fourth property is the most important one here, because it means that there is never any ambiguity over which way Pacman has to move. He just has to follow the dots, and the dots will only ever lead in a single direction.

Understanding these properties is the key to solving any of the maps, and more importantly to solving all of them with one piece of code. We don't know how many dots there are on any given map, which means that we can't use a for loop to step over each of the dots. We just need to continue until there are no dots left. We don't know to begin with in which direction dots will lie, but we know there will always be another dot adjacent to Pacman until he reaches the end of the line.

The dots can change their relative position to Pacman at any time, which means he has to follow a twisty, windy path. These are the consequences of the rules we have, and they give us a full understanding of the problem we have.

Let's define once again the properties of the problem as we have analysed them:

1. We don't know how many dots there are on the map.
2. We can't simply step over every square on the map because there can be any number of obstacles in any order.
3. There is always a dot next to Pacman when he starts, but it may not be in the direction in which he is currently facing.
4. There is always a dot one square further on in the line from where Pacman is, unless he has reached the end of the map.
5. There is only ever one direction Pacman can go to get to the next dot.

So, what can we do? Answering that question requires us to know what tools we have to deal with each of the properties of our problem:

1. We don't know how many dots there are, so we don't know how many steps we need to take. We have a while loop though to deal with this kind of conditions.
2. We can't step over each square on the map, so we must follow the trail of dots as it is provided to ensure we get them all.
3. There is always a dot adjacent to Pacman, so we need to turn him around until he sees the dot. We have the isObstacleAhead method for this.
4. As above.
5. As above.

Well, Pacman can tell what obstacles are ahead of him - we saw that in chapter seven. So, with the rules we have, we know this - if there is no dot ahead of Pacman, he can just turn around until there is a dot ahead of him. If there is no dot ahead of him after he has turned fully around, then he has reached the end of the map.

As it turns out, that's the general solution for all three of these maps, and indeed for all maps that conform to the properties given. The whole solution is general:

First of all, we turn Pacman around until he is facing a dot. While there are dots left While there is no dot ahead of Pacman Turn left Move

And that's it! A gigantic number of possible maps solved with a few tiny lines of code. In fact, if you look at it a bit closer, it breaks down to even fewer lines of code since step one is actually the same thing as step two - step one is a general case of step two:

While there are dots left While there is no dot ahead of Pacman Turn left Move

So this breaks down into the following code:

import draconia.APE.pacman.*; public class Unbroken_Lines { public static void main (String args[]) { PacmanGame main = new PacmanGame(); main.setMap ("unbroken_line_3"); main.showGame(); while (true) { while (!main.isObstacleAhead ("dot")) { main.turnLeft(); } main.move(); } } }

Try it out with the other two maps, and you'll see it works just as well, which is pretty impressive I'm sure you'll agree.

Okay, so one solution solves all the maps - that's pretty damn funky. But the fact that one solution solves them all gives a number of benefits - the main one being, if the properties change, then we only need to fix our program once and it'll still work for all of our maps. Imagine for example, that one of the properties changed:

The line is mostly unbroken.  Whenever a gap in the line is encountered, 
 then the next dot lies in the same direction as Pacman is currently travelling.

So for example:

Fig 9.4: broken_line_1

Such changing requirements are not unusual in the world of software development, and a good programmer understands that all code they write is only a draft. If we had different ad-hoc solutions to all three maps, we'd need to fix each individually to deal with any changing requirements. With a general solution, we fix it once and then it works for everything.

We solve this problem in exactly the same way - except that we can't just turn Pacman around until he sees a dot because there isn't guaranteed to be a dot. We turn him around a maximum of four times - at this point, he's facing the way he did originally. If he didn't find a dot in another direction at this point, he moves anyway:

import draconia.APE.pacman.*; public class Unbroken_Lines { public static void main (String args[]) { int counter = 0; PacmanGame main = new PacmanGame(); main.setMap ("broken_line_1"); main.showGame(); while (true) { while (!main.isObstacleAhead ("dot") && counter < 4) { main.turnLeft(); counter += 1; } main.move(); counter = 0; } } }

And with that change, it'll work for every map with the updated requirements. Try it out on broken_line_2 and broken_line_3.

This is a giant benefit of generalised code - programming is hard enough without making extra work for ourselves. Cutting down on effort by making sure that code works in as many situations as possible is a sensible strategy that will ensure we retain what little sanity that we have remaining.

We still lack some of the important tools needed to make generalisability something we can strive for with every program we develop, but it's something we should be bearing in mind in every program we write from now on. It's what separates a good programmer from a mediocre programmer, and saves you much effort in the long run. Get into the habit of writing generalisable code and your life will be more fulfilling because of it!

Further Reading

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