3 - Case Study 1 - I Smell Your Fear

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

• predict the actions of a hostile ghost
• use diagrams to outline a solution

Okay, now we've spoken a little bit about what APE is and how it works, let's look at writing a solution to an APE puzzle. The map we're going to use is called i_smell_your_fear, and this has been set up as a hard map. This refers to the difficulty of the puzzle, not the difficulty of the code you are going to write.

APE Pacman offers three levels of difficulty - at the easiest level you can eat power pills and have a comfortable length of time to eat the ghosts in your way. Also, the ghosts will stay stationary. On the hard level, you have limited time before your pill wears off, and the ghost will hunt you down and kill you. Scary stuff!

Because we are going to have a great degree of control over what pacman does here, the map has been set to hard - when we're putting more of the emphasis on pacman doing things himself, it becomes more difficult for us to make him responsive to situations (such as a ghost bearing down on him). This is our first challenge - we need to eat all of the pills before we are killed by the ghost.

So, let's get to it, and solve our very first APE puzzle.

As has been indicated, the map is called i_smell_your_fear, and so the first thing we do in APE is setup that map in the game:

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

The map is quite simple - only a collection of walls, pills and ghosts:

Fig 3.1: The Map

So, that's our challenge - eat the dots, stay alive, and eat the ghost - it'll be gunning for us so we need to be careful.

The way the ghosts move in APE is wholly predictable - they will move towards you one space at a time along the Y axis if they can until they are in the same row. Then they will move along the X axis. If they cannot move the preferred axis (perhaps they are blocked by a wall, for example), they will move along the other. This predictability is what makes the puzzle possible to solve. The ghosts do not attempt to find paths to you themselves - they merely move as close to you as they can, and they can be blocked by walls. That's very handy, considering we have a nice little wall shield between us and the ghost to begin with.

Okay, let's take this puppy out for a spin - first we'll just move Pacman along a few spaces to see what happens... this is the first time we've seen the ghosts, so we need to be sure of what we're doing:

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

We see that because the ghost moves at the same speed as Pacman, it's possible to outrun it - the only way the ghost can catch us if it's suitably far behind is if we slip up. That's useful to know:

Fig 3.2: The Fast and the Furious: Pacman Drift

We only die if pacman and the ghosts occupy the same square - we do not die if we are merely touching on an axis. We can easily commit suicide to show this, turning pacman towards the right and moving him on by one:

Fig 3.3: Alas poor Pacman

So, we avoid the ghost as best we can. This means we need to get into the habit of getting pacman to move the right ways - it can be very difficult to visualise this in your head, so we resort to the staple of software developers everywhere - pen and paper. Let's think this thing through.

Some graph paper will come in handy here - we draw a representation of the map onto the graph paper, and then think through the consequences of each of our actions. Doing it on paper is always going to be easier than doing the code because of the many different ways of approaching this problem... you can test them out on paper much more quickly than you can in code. We'll only draw the relevant part of the map here:

Fig 3.4: Map Graph

We're going to use an arrow to represent pacman because of how important that way he is facing is to the whole thing - he only moves in the direction he faces, so we need to know which way he is facing at all times.

To begin with, he is facing upwards, and that's no good to us. None of the pills in the map are in that direction, so we need to get him facing towards the right. We know how to do this - we issue him an instruction to turnRight().

Before we start doing this in code, it's a good idea to sketch out the code you will write without actually writing the code - we use a formal English alternative that is commonly known as pseudocode. We just state what we want to happen:

Turn Pacman Right

We'll keep a note of the pseudocode as we go along - it may not be especially obvious from this case study how useful pseudocode can be, but when we look at more complex programs with more complicated logic flows, we'll have more use for it. Still, start as you mean to go on!

So, what's the first thing we do here? We turn right:

Fig 3.5: Step One

What does our turning do to the ghost? Absolutely nothing - the ghost only moves when we move. But then, that's our next step - moving pacman on by one:

Fig 3.6: Step Two - Pacman's Move

Remember how the ghost behaves at this point - it will attempt to move closer to pacman along the Y axis (in short, it will move down one space):

Fig 3.7: Step Two - Ghost's Move

So, what happens if we turn left and then move three spaces to get the dots that way? Let's check and see:

Fig 3.8: Step Three

And then

Fig 3.9: Step Four

Followed by:

Fig 3.10: Step Five

Alas, pacman will soon occupy the same place as the ghost and die, so that's a non-started. That leaves us with only one other direction to get pills - we need to go straight ahead:

Fig 3.11: Step Six

This has the benefit of protecting us with the wall - the ghost cannot go through the wall, and it won't attempt to go around since it is already in the same Y axis. We've put the wall between ourselves and danger, and we can freely take a step towards the wall.

From the map it's easy to see that there is a lot of turning involved, which is why we need to know what our facing is - it makes it much easier to know how we get Pacman to behave if we know in what direction he needs to turn. Here, he needs to turn left and move on one space.

Fig 3.12: Step Seven

Fig 3.13: Step Eight

No problem from the ghost, but we will have a problem if we attempt to go left. That leaves only right as an option:

Fig 3.14: To The Edge

We can safely move forward to the edge of the wall without risk - it's the gap in the wall that gives us cause for concern:

Fig 3.15: The Ghost In The Wall

Now, what's going to happen here? We're going to make our move, and the ghost will move as it has in the past:

Fig 3.16: The Ghost In The Wall

But then what? We can't move upwards - that would be madness, it would leave us within striking distance of the ghost's vicious ectoplasmic fangs. We can only move downwards, but the ghost will chase us... can we make it to the other side of the wall in time? Well, let's see... we turn right:

Fig 3.17: Turning Right

We move:

Fig 3.18: Run Away!

We turn left now:

Fig 3.19: Flee!

And we move - the ghost cannot get to us on the Y axis so it has to chase us on the X axis:

Fig 3.20: RUN FOREST RUN!

Oh, the tension! What happens now? We make another move and the ghost has gotten to the same gap we're going through:

Fig 3.21: It's at the gap!

Now we are surely undone! But no - even though the ghost is right behind us, it moves only one space for our one space - it will remain that far behind us until we can get to the pill. That's lucky - except for one thing. We turn left, and we move - and what does the ghost do?

Fig 3.22: Phew!

It chases up its preferred axis - it's going to try and head us off at the pass! Now it's a race against time - who gets to the pill first? If it's us, we'll eat the ghost, arr num num. If it's the ghost, we'll die with our puzzle incomplete. Oh, the tension!

We turn right:

Fig 3.23: We're safe!

We move, and the ghost remains where it is:

Fig 3.24: Race to the Power Pill

And will continue to remain there until we get to the edge of the wall:

Fig 3.25: There's a ledge at the edge!

We turn left and move, and the ghost moves with us:

Fig 3.26: Trimming around the Edge

And move again:

Fig 3.27: It's within our grasp!

The Gods are on our side - the pill is closer to us than it is to the ghost! We turn left and move towards it:

Fig 3.28: Move your little round body!

And now (we'll use a capital G to show an eatable ghost):

Fig 3.29: Eat The Tasty Ghost

And again, munch munch munch:

Fig 3.30: Munch munch munch

And oh no for the ghost - it's now eatable! Pacman makes one more move and 'arr num num num'! The ghost is no more, for we have consumed it with our mighty pill poppin' powers.

Fig 3.31: I eat the ghost

And oh no for the ghost - it's now eatable! Pacman makes one more move and 'arr num num num'! The ghost is no more, for we have consumed it with our mighty pill poppin' powers.

Now the map can be solved at our leisure. We have a limited number of steps we can take for this, but the path of least resistance dictates that we eat all of the nearest pills rather than follow the main trail and them come back for the rest. We get that one pill that was in the gap in the wall first:

Fig 3.32: Why oh why didn't I take the blue pill?

And then head back upwards to eat the rest:

Fig 3.33: Follow the taste of tasty tasteness

Follow the trail of sweeties, and we get to the end of the map and a successful solution! Congratulations to us!

Fig 3.34: Success!

There's a lot of code to go with this though, as you can see:

import draconia.APE.pacman.*; public class ISmellYourFear { public static void main (String args[]) { PacmanGame main = new PacmanGame(); main.setMap ("i_smell_your_fear"); main.showGame(); main.turnRight(); main.move(); main.move(); main.turnLeft(); main.move(); // At this point we're at the first wall. main.turnRight(); main.move(); main.move(); main.move(); main.move(); // Now we're at the gap in the walls. main.turnRight(); main.move(); main.turnLeft(); main.move(); main.move(); // By now we're at the Crunch Point. main.turnLeft(); main.move(); main.turnRight(); main.move(); main.move(); main.move(); main.turnLeft(); main.move(); main.move(); // We're npw now in line with the pill. main.turnLeft(); main.move(); main.move(); // Arr num num, we eat the ghost, it tastes salty. main.move(); // Now we just have to eat the rest of the dots and we're done. main.move(); main.move(); // Turn and get that lone dot in the gap. main.turnLeft(); main.move(); // And then turn around main.turnLeft(); main.turnLeft(); // Move out, and turn to the left and eat the trail of pills. main.move(); main.turnLeft(); main.move(); main.move(); main.move(); main.move(); main.move(); // And turn around to get the last few dots main.turnLeft(); main.move(); main.move(); // And success! } }

Zounds - thank goodness we're not working over the full-sized map!

Since we know very little about programming at the moment, this map is more about the puzzle itself than the programming statements you use to solve it. All we know for now are sequential statements, and a program of any real complexity will be too much for us until we've got a few more tools under our belts.

The biggest thing that we did in this map was take a structured, step by step approach to the problem, and document it as we went along. We checked out the consequences of bad decisions on paper before we put them into a program - this is important, since it's easier to change things on paper than it is to change them in a computer program of any real complexity. Changes in a computer program can very easily have unintended side-effects.

This case study has shown us one other important thing - how the ghost works. There is no randomness (this is very important) - the ghost is entirely predictable. If the ghost had a random element, or artificial intelligence that allowed it to choose a path to us, then we would be completely unable (at this point) to write a program that could solve the puzzle all of the time. In technical computing terms, the ghost behaves deterministically - its behaviour is entirely predictable, and it will always behave in the same way when confronted with a particular situation.

The opposite of a deterministic ghost would be a stochastic ghost - one that had an element of chance or probability. This would be impossible for us to reliably solve because as of yet we have no way of making pacman respond to what is going on around him. All we can do is give him a set of instructions and hope they work. Imagine if we were Powerful Generals in command of an army - at the moment we are issuing a list of orders for our troops in enemy territory, but we have no idea of what the enemy is doing. Pacman will walk right into the ghost if you tell him to, because he obeys orders without question.

Consider this situation (let's call it the Crunch Point):

Fig 3.35: The Crunch Point

Although there is no way the ghost could have caught you in either situation, the ghost has two choices when you move upwards here. It can either chase you on the X-axis or chase you on the Y-axis. The system is deterministic, so it will always chase you on the Y axis first, and on the X-axis only if it cannot (or does not need to) chase you on the Y axis. Imagine if the ghost just randomly picked one of these each time you ran the program - it's easy to imagine a situation in which this has real consequences, and we will see examples of these later on in the book when we look at puzzles of fiendish difficulty.

What this problem hopefully outlined to you also is how much repetition is going into your coding - it's easy to lose count when making him move for a while. Sequential statements are the backbone of any program, but they are very inflexible. In the next two chapters you'll see how to tighten up this code to a remarkable degree... you want pacman to move four spaces? Then you give him the move command and tell him to repeat it four times.

Likewise you'll also learn how to make pacman respond to the world around him - why should you tell him which way to turn? Why can't you just tell him to turn until he has a dot in front of him? That's exactly the kind of thing you'll be able to do by the time we get to the next case study.

Although this map was marked as 'hard' difficulty, it didn't require any extra programming from us. The difficulty was in the way the ghost responds to pacman. On easier difficulty levels, the ghost does not move, and so you can skirt around it.

Our code listing for this is huge because of all the different instructions we need to issue to pacman. In chapters to come, we'll see how to reduce that to something substantially more manageable!

Further Reading

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