1 Introduction

1.1 Summary

In this assignment you will implement a version of Trémaux’s algorithm for solving simple mazes. The algorithm in this assignment has a slight variation, so make sure you check the details here!

In this assignment you will:

• Practice the programming skills covered throughout this course, such as: – Pointers

– Dynamic Memory Management

– Provided API
• Correctly Implement a pre-defined API
• Implement a medium size C++ program
• Use a prescribed set of C++11/14 language features

This assignment is marked on three criteria, as given on the Marking Rubric on Canvas:

• Milestone 1: Writing Tests
• Milestone 2-4: Implementation of the Maze Solving Task
• Style & Code Description: Producing well formatted, and well documented code.

1.2 Relevant Lecture/Lab Material

To complete this assignment, you will requires skills and knowledge from lecture and lab material for Weeks 2 to 4 (inclusive). You may find that you will be unable to complete some of the activities until you have completed the relevant lab work. However, you will be able to commence work on some sections. Thus, do the work you can initially, and continue to build in new features as you learn the relevant skills.

! For Assignment 1, you may only use C++ languages features and STL elements that are covered in class. 1.3 Academic Integrity and Plagiarism

! CLO 6 for this course is: Demonstrate and Adhere to the standards and practice of Professionalism and Ethics, such as described in the ACS Core Body of Knowledge (CBOK) for ICT Professionals.

Academic integrity is about honest presentation of your academic work. It means acknowledging the work of others while developing your own insights, knowledge and ideas. You should take extreme care that you have:

•                                                                         
•                                                                                 

  Acknowledged words, data, diagrams, models, frameworks and/or ideas of others you have quoted (i.e. directly copied), summarised, paraphrased, discussed or mentioned in your assessment through the ap- propriate referencing methods

                                                                          
•                                                                        
•                                                                                 

  Provided a reference list of the publication details so your reader can locate the source if necessary. This includes material taken from Internet sites. If you do not acknowledge the sources of your material, you may be accused of plagiarism because you have passed off the work and ideas of another person without appropriate referencing, as if they were your own.

                                                                                 

  RMIT University treats plagiarism as a very serious offence constituting misconduct. Plagiarism covers a variety of inappropriate behaviours, including:

                                                                                 

  • Failure to properly document a source
  • Copyright material from the internet or databases • Collusion between students

                                                                                 

  For further information on our policies and procedures, please refer to the RMIT Academic Integrity Website.

                                                                                 

  The penalty for plagiarised assignments include zero marks for that assignment, or failure for this course. Please keep in mind that RMIT University uses plagiarism detection software.

                                                                          
•                                                                 

2

2 Background

A maze is a very typical puzzle. To solve a maze you must find a path that connect the entry (starting) and exit (ending) points of the maze.

In this assignment, we will represent a simple 2D maze as a grid of ASCII characters. For example:

Aspects of the maze are represented by different symbols:

========== S........= ========.= =......=.= ==.=.=...= =..=..=.== =.===....= =..==.==.= =====E====

Symbol

= (equal) . (dot) S
E

Meaning

Wall or Obstacle within the maze. The robot cannot pass obstacles Empty/Open Space.
The starting point (entry) of the maze.
The ending point (exit) of the maze.

* (asterisks)                                                                         Used to show the solution of the maze, which is a trail of breadcrumbs The solution to the above maze can be shown as:

========== S********= ========*= =...***=*= ==.=*=***= =..=**=.== =.===*...= =..==*==.= =====E====

Each location in the maze (including the maze edges) is indexed by a cartesian (x,y) co-ordinate. The top-left corner of the maze is always the co-ordinate (0,0), the x-coordinate increases right-wards, and the y-coordinate increases down-wards. For the above maze, the four corners have the following co-ordinates:

Finally, we also define 4 cardinal directions, so we can talk in terms of moving/walking about the maze.

(0,0) . . (10,0) .. ..

(0,10) . . (10,10)

north ^

west <- | ->  east        v

south

3

3 Task

The task for this assignment is to write a full C++ program that:

1. Reads in a 20x20 maze from standard-input (std::cin).
2. Solves the maze (using the Simplified Trémaux Algorithm in Section 2.1).
3. Prints out the solution to the maze to standard output (std::cout).
4. (Optionally) prints out walking/navigation directions (that you could follow to walk through the maze).

For the purposes of this assignment (except for Milestone 4), you may assume that the maze is always a fixed size of 20x20.

This assignment is divided 4 Milestones. To receive a PA grade, you only need to complete Milestones 1 & 2. To receive higher grades, you will need to complete Milestones 3 & 4.

! Take careful note of the Marking Rubric on Canvas. Milestones form a sequence. For example, if you attempt Milestone 3, but your Milestone 2 is buggy, you won’t get any marks for Milestone 3.

3.1 Milestone 1: Writing Tests

Before starting out on implementation, it is good practice to write some tests, so that you can know if your implementation is 100% correct. We are going to use I/O-blackbox testing. That is, we will give our program a maze to solve (as Input), and then test that the program’s Output is what we expect it to be.

This a test consists of two text-files:
1. .maze - The input maze for the program to solve

2. .out - The expected output which is the solution to the maze. A test passes if the output of your program matches the expected output.

You should write enough tests so that, if your program passes all of your tests pass, you are confident that your program is 100% correct.

Recall that you can “run” a test, by I/O redirection, and capturing your programs output: ! ./assign1 program.out

Then you can test if the actual and expected outputs match with the diff command: diff program.out testname.out

3.2 Milestone 2: Maze Solving

Even for a relatively small algorithm, it is important to have the right design for our programs, and use appropriate data structures and classes. To help you in Assignment 1, we done this design for you to implement1. We will implement 3 classes, plus a main file:

• Breadcrumb class - to represent a single breadcrumb in the trail.
• Trail class - to and update the trail of breadcrumbs as we explore the maze.
• MazeSolver class - to encapsulate the maze solving algorithm.
• The main file that uses these classes, and does any reading/writing to standard input/output.

You are given these classes as header files in the starter code. You may add any of your own code, but you must not modify the provided class methods and fields. If you implement the class, you will have a working Milestone 2.

3.2.1 Breadcrumb Class

The Breadcrumb class represents one breadcrumb in our trail. It is a tuple (x,y,stale), which is the x-y location of the breadcrumb in the maze, and whether breadcrumb is fresh or stale. It has accessor methods for this information and one method to change if the breadcrumb is fresh or stale.

1This won’t be the case for Assignment 2, where you will have to make these decisions for yourself. 5