CIS2168 - Homework 8: PLAYING WITH MAZES
Thank you Professor Lakaemper
Assignment given: October 26, 2010
Due Date: November 1, by 10pm
We are given code by Professor Lakaemper that creates a maze and diplays
it. We are to write code that, starting from a cell identified by clicking
the mouse, will build a path to the exit. Professor Lakaemper's code will
take care of displaying the path on the maze.
This assignment requires us to write very little code:
- Add the main method which will instantiate a Maze object.
- Implement the interface Maze Listener. It will call a method
pathFinder that will determine a path from the clicked cell to the exit
cell
- Repaint the maze - Professor Lakaemper's code will take care of
displaying the path.
To make life more exciting there is a button that when clicked will
create a new maze.
The difficulty of the assignment is to understand the code that is given
to you! There is GUI code that, by now, it should not be too difficult to
understand. The problem is to understand the maze code. The maze is
represented as an array of cells, with noRows rows and noColumns columns.
A cell is represented with a single byte. A cell may have walls going
North (to the cell one less row, same colums), West (to the cell one less
columns, same rows), South (to the cell one more row, same columns), East
(to the cell one more column, same rows). We build the maze by setting all
the cells to have all the walls up. Then we break walls gradually building
the maze. Note that if I want to go from a cell to a neighbor, I will have
to break the wall on my side and on my neighbor's side. So, going South, I
break my South wall and in my neighbor I have to break the North wall. And
similarly in the other directions.
As I said, a cell is represented by a byte, and we use bits in this byte
to represent different properties of the cell
- Bit 0 represents the North direction. It will be 1 when there is a
wall going North, 0 otherwise. Say cell is the cell under consideration,
cell & 1 (or preferably cell & 0x01) will be true if there is a North
wall, 0 otherwise. To remove the wall we say cell -= 1;
- Bit 1 represents the West direction. It will be 1 when there is a
wall going West, 0 otherwise. Say cell is the cell under consideration,
cell & 2 (or preferably cell & 0x02) will be true if there is a West
wall, 0 otherwise. To remove the wall we say cell -= 2;
- Bit 2 represents the South direction. It will be 1 when there is a
wall going South, 0 otherwise. Say cell is the cell under consideration,
cell & 4 (or preferably cell & 0x04) will be true if there is a South
wall, 0 otherwise. To remove the wall we say cell -= 4;
- Bit 3 represents the East direction. It will be 1 when there is a
wall going East, 0 otherwise. Say cell is the cell under consideration,
cell & 8 (or preferably cell & 0x08) will be true if there is a East
wall, 0 otherwise. To remove the wall we say cell -= 8;
- Bit 4 indicates that this cell is in the solution path. Say cell is
the cell under consideration, cell & 16 (or preferably cell & 0x10) will
be true if the cell is on the path, 0 otherwise. We can set it with
cell += 16 (or preferably cell |= 0x10). Unset it with cell -= 16 (or
preferably cell &= 0xef).
- Bit 5 indicates that this cell is the exit cell. In the program this
is always the cell at row 0, column 0. Say cell is
the cell under consideration, cell & 32 (or preferably cell & 0x20) will
be true if the cell is the exit cell, 0 otherwise. We can set it with
cell += 32 (or preferably cell |= 0x20).
The code provided by Professor Lakaemper builds the maze using a recursive
method. I give you a copy of the maze code which does not use recursion,
uses a stack [remember I told you of the 60s when in FORTRAN we had no
recursion and had to build our own stacks?]. You may judge which one is
easier [usually the recursive]. But there is an advantage for the stack
solution. Where the recursive method bombs out (stack overflow!) when
building an 80x80 maze, the non-recursive goes fine into hundreds. You may
wonder why [I will discuss in class].
Your findPath method can be written recursively [it is brief, I have it
in 18 lines] or, again, using a stack. You decide.
Have fun doing this homework. Start early. Ask for help from TA or me as
soon as you get stuck.
Code from Professor
Lakaemper.
My version of Maze code
Here is an example of maze that is created
by
the program, and here is a maze with a
path.