$24
LAB ELEVEN SOLUTION
In this lab and the next, you are going to write a program that explores a maze. This provides an example of arrays being used to do interesting things, introduces an interesting area of artificial intelligence (robotic navigation), and may give you some ideas about game programming if you are interested in that kind of thing.
Keep in mind that lab twelve is a continuation of this program, so don’t lose it. It would probably be a good idea to read the lab 12 assignment too, so that you know what’s coming.
Today you will be getting the display to look good, and making sure you can move a little robot about inside the maze. In the second session, you will work on automation, making the robot/man/woman/whatever move around on his/her/its own, and making it more of a game. From now on, I’ll just refer to the moving thing as “the robot”.
The first task for your program will be to read a picture of a maze from a file, and store a suitable representation of it in memory. The file containing the picture will be called "maze.txt", and it will contain a text representation of a rectangular maze, with the character ‘#’ used to represent a wall, and ‘.’ will be used to represent open space. This is an example of one possible maze file:
######..#..#####...
#####
.............#
...#..........
#.....
##.#
..##.###.###.####.#..#.#.#.##.#
#..##..#.##...
#.#.##...
#
...#..#
##..##.#
....#.....
###.##.###.##
#.#.#....
#..#.###..#..#..#.#...
#.#..#.########.#####
....
#.##..
..#........
##A
.....#####
...##..
....##.###..##.#.###...
###.#..#
..#.#................
#...
#.#B.#
..###############......
########
It would be a little easier to look at if we used spaces instead of dots, but remember that C++ likes to ignore spaces when reading input, and we don’t want to introduce unnecessary complications. To save typing, you can download that maze file from:
http://rabbit.eng.miami.edu/class/een118/labs/maze.txt
Notice that there isn’t a solid wall of #s around the maze. This means that you will have to be careful to prevent your robot from falling off the edge of the world. It is not permitted to get around obstructions by going outside the maze.
Notice also that there is a single ‘A’ and a single ‘B’ in the maze. Every valid maze will have one ‘ A’ and one ‘B’ in it. The ‘B’ represents the treasure, and the ‘A’ marks the starting point. The object is to get your robot from its starting point to the treasure staying within the maze and without using any squares marked ‘#’.
Diagonal moves are not allowed, and no maze will have more than 100 rows or 100 columns.
1. Read the Maze
Build a program that creates an appropriate array to store the maze, opens the file, reads the maze into the array, then closes the file and proves to you that it read the maze correctly by printing it again in a slightly different format.
How should you print the maze after reading it? Remember that the reason for doing this is to be absolutely certain that you really have read the maze correctly, we don’t want there to be any risk that you’ll accidentally print out the contents of the file and trick yourself. Wait until you have read the entire file and closed it, then reprint the maze from your array, using different symbols. Perhaps ‘@’ for walls and real spaces for the spaces. It will be easy to see that the maze is the right shape, but it will obviously not be just a copy.
2. Detect A and B
Modify your program so that it notices where the ‘A’ and ‘B’ are, and stores the coordinates (row and column) in suitable variables.
3. Draw it Properly
Instead of drawing the maze with stars and spaces, open a graphics window and draw it properly. I would suggest first drawing a grid of the right size, then filling in the wall parts with a solid colour. Make sure each square occupies enough pixels to be seen clearly. Then mark the position of the ‘A’ and ‘B’ in some way that stands out. Perhaps a different coloured blob:
4. Make the Robot Move
The library contains a function called wait_for_key_typed(); it waits until the user types a key on the keyboard, then returns as its result the ASCII code for that key. Use it to make the robot move around under your direct control.
Remember that C++ does not expect you to have memorised all the ASCII codes. If you put a single character inside single quotes, C++ sees it as the ASCII code for that character. So, if you choose to use the letters l, r, u, and d to stand for left, right, up, and down, you might have something like this in your program.
while (true)
{ char c = wait_for_key_typed(); if (c == 'l')
{ /* make the robot move one square to the left */ } else if (c == 'r')
{ /* make the robot move one square to the right */ } else if (c == 'u')
{ /* make the robot move one square up */ }
else if (c == 'd')
{ /* make the robot move one square down */ } }
Note that this function does not behave like “ cin ”. It does not wait until enter has been pressed at the end of the line, and it only takes keystrokes that were aimed at the graphics window. If the black text window is selected, keys typed go to cin, and wait_for_key_typed() doesn’t get to see them. The graphics window must be selected.
You might like to take advantage of the fact that all the non-ASCII keys have also been assigned numeric codes. In particular, the arrow keys have negative numbers assigned to them as follows:
down arrow
-88
right arrow
-89
up arrow
-90
left arrow
-91
It might also be a good idea to have an x (exit) or q (quit) command for when you get fed up with playing.
Do not worry about walking through walls or falling off the edge of the world yet. Just update the robot’s position after each move. The player will have to be careful to navigate properly.
Try it out, make sure you can navigate the robot to his target. I hope you remembered to update the picture after each movement, so that you see the robot in its new position.
5. Prevent Walking Through Walls
Make the exploration more realistic by refusing to obey impossible commands. If a movement would result in the robot walking through (or into) a wall, or off the edge of the world, then that movement command must not be obeyed.
6. A Foolish Robot
Your robot does not move except under your direct command. Add another command letter, perhaps ‘A’, that puts him in Automatic mode. When in automatic mode, the robot should repeatedly select a random neighbouring empty square, and move into it, until he happens upon the treasure.
One way to achieve this would be simply to stop calling wait_for_key_typed() once the robot is in automatic mode, but then you would never be able to get him out of automatic mode. Fortunately, the wait_for_key_typed() has a little bit of extra functionality. It can take one optional parameter, a floating point number telling it how long (in seconds) to wait for the user to type a key.
This statement
char c = wait_for_key_typed(O.O);
will not wait at all. If the user has already pressed a key, then everything is fine, and c is set to that key’s ASCII code as usual. Otherwise, c is just set to zero instantly.
Add another letter command, perhaps ‘M’ for Manual, that turns off automatic mode, and puts the robot back obediently under your command. You will probably find that 0.0 seconds isn’t the ideal maximum wait for keyboard input.
7. Enemies
A maze is very easy to solve without any opposition. You now need an enemy. First edit the maze text file, and replace one of the ‘#’s or ‘.’s with an ‘E’. This is to indicate your enemy’s starting position.
Now make your program take note of the position of the ‘E’, just like it did for the ‘A’ and ‘B’. On the display, choose another colour to represent the enemy, and make sure he appears correctly.
Every time your robot makes a move, your enemy should also make a move. Just like the robot in automatic mode, make the enemy move into a random neighbouring non-wall square. That won’t make for a very impressive enemy, but you’ll improve it later.
And naturally, a useful enemy has to do something inimical. If the enemy ever walks into your robot, you lose. Game over.
