Mazes:
One of the most basic kinds of games that we can represent in software is a maze. A maze is defined as a rectangular grid (n by m) of cells. By convention in this writeup, the first coordinate cab be thought of as the column number and the second as the row number. Each cell has between 1 and 3 walls. Also, the walls at the outside cells (along the top, left, right and bottom of the maze) are closed. A cell that has 4 walls is a dead end and one that has zero walls of course floats and has no impact.
A basic 4x4 maze might look like this if it has all cells with 4 walls. This is not a valid maze.
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
Here’s a valid maze:
+-+-+-+-+
| | |
+-+ + + +
| | | |
+ +-+ + +
| | |
+-+ +-+ +
| | |
+-+-+-+-+
That maze can be described more concisely with a series of 1’s (for wall) and 0’s (for space)
as follows:
111111111
100010001
111010101
100010101
101110101
100000101
111011101
100000101
111111111
Note that a row with 4 cells has 4 spaces and at least 2 but potentially 5 walls. So each row in the 1/0 notation has 9 ones or zeros.
More compactly, I could represent a maze as a string:
"111111111100010001111010101100010101101110101100000101111011101100000101111111111"
(By the way, unless you are very clever I wouldn’t be fooled into thinking of that as a number)
Assignment specifics:
Here’s the puzzle/assignment. Write a program in Ruby that does as many of these as you can. You probably will not get to (6) but its there if you are adventurous. Make sure you print results as you go along because you will also be submitting the output that your app generates to show it’s results.
- Represent a n by m maze in an appropriately designed class called Maze. Each position in the maze can be designated by two coordinates, x (across) and y (down). For a 4x5 maze the top row of positions (x,y) would be (0,0), (1,0), (2, 0) and (3,0). The constructor of the Maze class should take two parameters for n and m. Note of course that you need to represent the walls between cells not just the cells.
- Implement a Maze#load(arg) method that initializes the maze using a string of ones and zeros as above
- Implement a Maze#display method that prints a diagram of the maze on the console. It can be just a simple character based printout like above or any other format you want.
- Implement a Maze#solve(begX, begY, endX, endY) method that determines if there’s a way to walk from a specified beginning position to a specified ending position. Of course it can return an error or false if there is now way.
- Implement a Maze#trace(begX, begY, endX, endY) method that is just like solve() but traces the positions that the solution visits.
- Implement a Maze#redesign() which will reset all the cells and walls and come up with a random new maze of the same size. There are lots of algorithms out there to do this. Feel free to google for ideas, but the code you hand in should be your own.
Deliverables
- The code for your solution
- A file containing the result of running your solution that demonstrates each of the specifics above.