ECE264 Programming Assignment 3

Finding Your Way in a Maze

The test sets used for grading can be downloaded here.

Sample Solution & Checker for PA3 is available.  You can see the sample solution or check the correctness of your program with it.  For more maze samples, you can exploited some online maze generator like this one (you need to modify the output a little bit).  (by far the --treasure option has no effect.)

You were looking for hidden treasure in a lost civilization and went into a temple.  As you were searching for clues, all of a sudden, the floor collapsed you were falling and falling. After regaining consciousness, you realized that you were trapped in an ancient unknown maze. You could see nothing but walls. You have to develop a strategy to get out, alive.

Purpose

To traverse a maze by using a stack and back track when reaching a dead end.

Sample Mazes

To simplify the program, we will take a 2-dimensional aerial view. However, remember that you are trapped in the maze and cannot see the whole maze. You can see only walls.  There are six pre-generated mazes of different sizes. The mazes are generated by using MazeGen in "Killer Game Programming in Java" by Andrew Davison.

The characters represent

• 'b': brick
• ' ': (space) corridor
• 'E': exit, i.e. the destination
• 's': original location of the player

You can click this to see screenshots when the bricks are shown as squares. The exits in the sample mazes are at the center of the top. This is not necessarily true. Make sure your program can handle the mazes in which the exits may be somewhere else, such as at the bottom or at a corner. Each maze has one and only one exit. An exit is always at the boundary of the maze.

Strategy

As you are thinking about how to get out, you are searching for the courses that have taught you problem-solving skills. You need to remember where you have been and to avoid visiting the same place twice. Every time you encounter an intersection, you have to remember the decision made at this intersection.  You do not know the size of the maze so you have to store data of an unknown size. You remember learning dynamic data structures (linked list, queue, stack, or binary tree) in ECE 264 and these structures can be expanded as needed. You decide the take the following strategy

1. Go as far as possible until reaching the exit or reaching a dead end.
2. When there is an intersection, go east first if it is possible. If it is not possible, go south. If going south is not possible, go west. Finally, go north. This four directions are clockwise. Fortunately, your compass still works. (GPS does not work indoors.)
3. After reaching a dead end, go back to the last intersection and take a different route, following the clockwise rule.
4. If all routes at an intersection reach to dead ends, go back to the previous intersection.

This strategy is called the depth-first-search with backtracking because you go as far as possible and backtrack when a route turns out to be a dead end.

A demo video has been created for you to understand the strategy. You can download this sample solution. Please remember that this program can run on ECN Intel-Linux computers only (such as msee190pcx).  After you download the file, please change the permission so that it is executable.

chmod 700 pa3sample

This visualization contains the solution to this assignment; hence, the source code of this visualizer is not released.  If you discover that the sample solution does not meet the requirements, please post the problem in Blackboard - Discussion.

Requirements

The program takes one input argument as the maze file. If this input file name is not provided, the program prints an error message and terminates. Your code is responsible for 

• reading the maze and keeping track of all necessary information.
• deciding where the player should move to and back tracking if necessary.
• the player always tries to move east (right) first. If the player cannot move right, choose the next direction clockwise (down, left, and then up). This is extremely important. If the program uses a different order, the program will generate different outputs (and lose points).
• for each step, print out a string "move to (x,y)\n" where (x,y) is the coordinate of the new location.  You must move only one step each time, e.g., from (x,y) you can only reach (x+/-1,y) or (x,y+/-1) for the next step.
• include a Makefile in your submission.  Your program will be compiled and built using your Makefile.  If there is no Makefile, your submission will not be graded.  The name of the executable file must be pa3 (no extension, not pa3.exe).

Do not use graphical user interface (GUI). Instead, print the location of every step (in the same way as the sample solution). Your program will be graded based on the textual output.

Assumptions

The width (number of columns) of a maze does not exceed 80.

Grading

The full score of this assignment 8 points.

• 1: read the maze from a file and print it on the screen (using printf). The input file may include empty or invalid lines (only the line with bricks are valid). Ignore any line that has no brick.
• 2: can correctly traverse mazes that contain no intersection.
• 3.5: produce correct traversal sequence (i.e. visit correct locations) for general mazes (containing intersections).
• 0.5: README file that explains your algorithm and data structures in details.  Only the explanation of your algorithm/data structure will be graded.
• 1: Code style.
  • 0.2 meaningful variable names (not just i, j, k, x, y...).
  • 0.2 proper indentation.
  • 0.2 proper names (noun for variables, verb for functions).
  • 0.2 one statement per line, no overly complex statements, no line exceeds 80 characters (at least one newline every 80 characters).
  • 0.2 sufficient comments in the code.
• -2: Memory leak reported by valgrind memtest
  • For self-checking: You must receive "no leaks are possible" at the end of valgrind's report to pass this test.
• -0.5: each warning message reported by -Wall -Wshadow.

Bonus

• 1: when your program is run with argument --shortest,it only prints out the shortest path from start point to exit (without traversal).  You may obtain this shortest path by first traversing the maze using existing method silently, then find the shortest out of the candidates and print it out. [BONUS1]
• 1: greedy escaper: while you are finding your wat out, you discover some treasure pots along the way.  A treasure pot is denoted by '$' on the map.  You want to get all the treasures before running out of the maze ($_$).  This mode is activated by --treasure command-line argument.  In this mode, you may output any valid path that solve this problem (meaning you don't need to follow the rule described in the Strategy section). [BONUS2]
• 1: super greedy escaper: if your program is run with both arguments --shortest and --treasure (can be in either order), it only prints out the shortest path that can pick all the treasures and then run of the maze.  The shortest path here means the path that takes the least number of steps among all possible paths. [BONUS3]
• Very Important: If your program can solve any bonus tasks, please include file(s) named BONUSx (x=1,2,3) in your submission.  These files will tell the grading script to test your program for bonus tasks.  For example, if your program can handle --shortest argument, please include a dummy file named BONUS1 in your submission (the content of the file can be empty);  if your program can solve all the bonus tasks, include BONUS1, BONUS2, BONUS3 in your submission.  If you do not submit such files, or you submit files with wrong names, no bonus tasks will be graded.

The extra arguments for bonus tasks (--shortest and/or --treasure) comes before the input file name when your program is executed from command-line prompt.  For example, your executable is named "pa3", input file (maze) is "maze", then BONUS3 will be tested by calling either "./pa3 --shortest --treasure maze" or "./pa3 --treasure --shortest maze".

Good news: You may receive a grade exceeding 8 points.  This is a good chance to make up for your PA grade, if you think you've lost too many points in the last two assignments.

Congratulations!

You come out of the maze alive! (...and probably become a millionaire by the way...)  After all, C programming isn't just writing code. It helps you survive the most dangerous situation (...and make some money...) in your life. You are so happy that you study ECE 264 very hard and can apply the knowledge. With this near-death experience, you appreciate life much more.  You will lead an expedition team back to the maze and find the hidden treasure. You will also come back to tell younger ECE 264 students that the course has saved your life.

Extension

This is not part of the assignment.

• The mazes used in this assignment have one common restriction: there is exactly one path between two points in each maze. We can easily create mazes in which there are multiple paths (by removing some bricks). How would your strategy be different? 
• If there is exactly one path between two points and there is no intersection, the maximum traveled distance does not exceed the number of accessible squares. When there are intersections, the traveled distance can be longer because of back-tracking. Can you derive a relationship that describes the number of intersections and the maximum traveled distance?
• This assignment asks you to go east first and north last. Since the exit it at the top, this strategy is not always the best. You may pass the exit without knowing it. As a result, you have to travel farther than necessary. However, going east is not always bad because it may be the right decision at the intersection just before reaching the exit.  Suppose you keep the clockwise rule but you can choose to go east (or north, or south, or west) first. Can you determine whether going east is the best or the worst for a particular maze without trying the four possible choices?