The Mouse and the Cheese --

This program gives us a chance to play around with 2-dimensional arrays

and to use classes and methods.

In the description below I will give many hints; they will

appear in parentheses and marked with an H (H:watch for these hints).

The program you will write is designed to simulate an experiment in

mouse behavior. The mouse is supposed to be in a maze which is like a

15 X 20 checkerboard. You can represent the maze as a 15 X 20 integer

array. From a cell the mouse can move to any of the

eight adjacent cells IF that cell has never been occupied by the mouse

before (H: If the mouse is on an edge or corner then you need to be

careful). Extra credit: Instead of 15x20 write program/class so it can use

any (perhaps with a minimum size) 2-dimensional array.

We plan to have the mouse start from one of the nine cells in the upper left

hand corner of the array. And we will put some cheese in one of the nine

cells in the lower right hand corner. (H: Use some number that can not

appear in the array in some other context to represent the cheese. Use

zero (0) to represent a cell that has never been occupied.)

Use the random number generator to generate a pair of integers which

are the coordinates of the cell the mouse starts from. Use the random

number to generate a pair of integers which represent the square that

the cheese is in.

The mouse has a sense of smell that makes him TEND to move towards the

cheese. The diagram below shows his probability of TRYING to step in

the various directions. I say TRYING because if a step would take

the mouse out of the maze or onto a previously occupied cell, then

the mouse tries again. (H: For each successful step we can mark the cell

with the number of the step. This allows us to later print the mouse's

entire path. Note that you will need a counter to keep track of the successful

steps.)

0.06	0.09	0.12
0.09		0.16
0.12	0.16	0.20

Note that these probabilities will tend to make the mouse move towards the

lower right corner of the maze which is near the cheese. Extra credit: Experiment

other probabilities. Which gives best chance of mouse finding cheese?

We need a function to generate these steps with these probabilities.

Here is one way to do it (pseudocode, NOT java):

double y;

y=Math.random();

if (y <= 0.06) step(-1,-1) else

if (y <= 0.15) step(-1, 0) else

if (y <= 0.27 step(-1,+1) else

if (y <= 0.43) step( 0,+1) else

if (y <= 0.63) step(+1,+1) else

if (y <= 0.79) jstep(+1, 0) else

if (y <= 0.91) step(+1,-1) else

if (y <= 1.00) step (0,-1);

}

Before we can try to make a step, we need to be sure the mouse hasn't

gotten trapped. E.g. suppose the mouse's path begins:

4	3
1	2

This is how the output from the program will look.

Then the mouse is trapped and we will never find a legal step for it.

(H: A boolean method would be the best structure for this purpose.)

The output should include:

1. A printout of the maze showing the mouse's path.

Above is a sample of how the output might look.

2. A count of how many actual steps and how many step attempts were made.

(A step attempt is when the mouse wanted to step out of the maze or onto

a previously occupied cell.)

3. A statement as to whether the mouse found the cheese or got trapped.

You should run the program several times. On some of these the mouse should

find the cheese and on others it should not. I.e. on some runs the mouse will get trapped

before it finds the cheese.

(H: A single run of the mouse through the maze should terminate if

the mouse gets trapped or the mouse finds the cheese.)

(H: The author discusses and we discussed in class one way of handling “subscript

out of bounds” problems when the mouse is at the edge. Here’s an alternative approach.

Though the mouse can only go to squares in an array 15X20, declare the array to be 17 X 22.

Then mark all the edges as unavailable. Now you won’t have to worry about “subscript out of bounds”.

Be sure your mouse starting routine, and your cheese placing routine, and your print out the maze

routine take these extra rows into account by NOT using them. )

Supplementary class.

As we’ve seen in other topics, a problem often involves using more than one class. For this problem,

there are many situations in which we need to refer to a pair of integers. For example: The square

the mouse starts on, the square the cheese is placed on, the position of the mouse at any given

step, the change in the mouse position like (-1,+1). And you will want to have methods that return

a pair such as placeCheese(). For these reasons, I suggest that you have a class which can hold two ints.

You may want (I did) to write some methods for this class.