这个作业是完成机器人走迷宫的程序
COSC1076 Assignment 1 (v1.0) | Robot Wall Following

One challenge in robotics is navigation. This is the process of a robot moving between two different locations
within some environment. A very simple algorithm that lets a robot drive about a very simple 2D maze is called
Wall Following. In this assignment you will implement a simple wall following algorithm for a robot moving
about a simple 2D maze. We will represent a simple 2D maze as a grid of ASCII characters. For example:
==========
=>…….=
========.=
=……=.=
==.=.=…=
=..=..=.==
=.===.=..=
=..==G==.=
==========
Aspects of the maze are represented by different symbols:
Symbol Meaning
= (equal) Wall or Obstacle within the maze. The robot cannot pass obstacles
. (dot) Empty/Open Space.
> The robot (see below for more information)
G The goal point that the robot is trying to reach.
Each location in the maze 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:
(0,0) . . (9,0)
. .
. .
(0,8) . . (9,8)
Mazes can be designed in different ways. For this assignment we will use mazes where:
2
1. There is one goal (ending) point.
2. The robot’s starting point is denoted by an “orientation” symbol (described below)
3. The maze is always surrounded by walls.
4. The maze only contains junctions and corridors. That is, you can’t have “open” space, loops or islands.
The robot is represented by two properties:
• Its (x,y) co-ordinate within the maze
• The direction that it is “facing” , that is, its orientation. The orientation is represented by four characters:
Symbol Key-code Meaning
< less-than symbol Robot is facing west
> greater-than symbol Robot is facing east
^ hat/exponent symbol (shift-6) Robot is facing north
v lowercase letter v Robot is facing south
To describe the robot’s orientation, we use the 4 cardinal directions:
north
^
west <- | -> east
v
south
Thus, the position of the robot within the map is described as a 3-tuple of (x,y,orientation). For example,
in the above maze the robot starts at position (1,1,east).
The robot can move about the maze using one of three actions:
1. Rotate clockwise 90◦
, changing it’s orientation
2. Rotate counter-clockwise 90◦
, changing it’s orientation
3. Move one space in the direction it is facing, , changing it’s x,y co-ordinate
In this assignment you will implement a simplified right-wall following algorithm to enable the robot
navigate from its starting position to the goal, which is described below.
!
While there are many ways to navigate a maze, you must implement this algorithm.
Pseudocode for the Right Wall Following
1 Let M be the maze
2 Let T be the trail of the robot’s positions
3 Let G be goal location for the robot to get reach
4 Let r be the current position (x, y, orientation) of the robot
5 repeat
6 (
7 until The robot reaches the goal, that is, r == G
8 igorning the robot’s orientation) if There is a wall to the right-side of the robot then
9 if The space in front of the robot is empty then
10 Robot moves one space forward, and update r accordingly
11 Add the updated r to the end of the trail T
12 else if The space in front of the robot is not empty then
13 Robot turns left (i.e. counter-clockwise), and update r accordingly
14 Add the updated r to the end of the trail T
15 end
16 else
17 Robot turns right (i.e. clockwise), and update r accordingly
18 Add the updated r to the end of the trail T
19 Robot moves one space forward right, and update r accordingly
20 Add the updated r to the end of the trail T
21 end
3
2.1 Wall Following Algorithm
The algorithm (given above) simulates the robot moving about the maze by imagining it places a “hand” on the
wall to its right, and the moves by following the wall, never removing its “hand”. This algorithm is given in
pseudocode. This is a right-wall follow, and to keep things simple, we will stick to just following the right-wall
in this assignment. Provided that the maze meets the requirements listed above, the robot is guaranteed to
reach the goal. This might not be the fastest way to reach the goal, but it will get there eventually. On Canvas,
you will find a video about this algorithm.
2.2 Outputting the path the robot took
Running the algorithm to get the robot to the goal is one step for this assignment. The second step is showing
the path of the robot in navigating from where it started until it reached the goal. To do this, the algorithm
tracks a history or trail of the robot’s positions as it makes its way to the goal. For example, using the maze
from the background section, the robot’s path is below:
==========
=>>>>>>>v=
========v=
=>>>v<<=v=
==^=v=^<<=
=>^=>v=.==
=^===v=..=
=^<==G==.=
==========
Take careful note of the following. A robot may be at the same x, y position in the maze multiple times,
but with different orientations, such as when:
• Is moves into a space and turn rotates (turns)
• Revisiting a location after backtracking
When showing the output of the path the robot travelled, the output must show the orientation of the robot
for the last time that the robot was at that x, y location. For example, in the above maze, when the robot
reached the dead-end at location (2,7), by following the right wall, the robot then turned around the made its
way out of the dead-end. Therefore, the orientation arrows show the robot’s movements as it came out of the
dead-end. Further, at location (4,3), the orientation is, v (south), since after coming our of the dead end, the
robot followed the right-wall downward.
3 Assessment Details
The task for this assignment is to write a full C++ program that:
1. Reads in a 20×20 maze from standard-input (std::cin).
2. Finds the robot’s starting position within the maze.
3. Executes the right-wall following algorithm (Section 2.1) until the robot reaches the goal
4. Prints out maze to standard output (std::cout), filled-in with the path the robot travelled.
5. (Milestone 3 only) Prints out walking/navigation directions.
You may assume that the maze is always a fixed size of 20×20, except for Milestone 4.
This assignment has four Milestones. To receive a PA/CR 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 should be completed in sequence.
3.1 Milestone 1: Writing Tests
Before starting out on implementation, it is good practice to write some tests. 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 our program’s Output
is what we expect it to be.
4
A test consists of two text-files:
1. <testname>.maze – The input maze for the program to solve
2. <testname>.out – The expected output which is the solution to the maze.
A test passes if the output of your program matches the expected output. Section 4.4 explains how to run your
tests using the diff tool.
You should aim to write a minimum of four tests. We will mark your tests based on how suitable they are for
testing that your program is 100% correct. Just having four tests is not enough for full marks.
3.2 Milestone 2: Wall Following
It is important to have a good design for our programs and use suitable data structures and classes. In
Assignment 1, you will implement our design1
. You will implement 3 classes:
• Position class – to represent a position (x, y, orientation) of the robot.
• Trail class – to record the trail of positions as the robot navigates the maze.
• WallFollower class – that executes the wall following algorithm.
• The main file that uses these classes, and does any reading/writing to standard input/output.
You are given these classes in the starter code. You may add any of your own code, but you must not modify
the definitions of the provided class methods and fields.
3.2.1 Position Class
The Position class represents a position of the robot. It is a tuple (x,y,orientation), which is the x-y
location of the robot, and the direction (orientation) that the robot is “facing.“ It only contains accessors
methods for this information.
// Constructor/Destructor
Position(int x, int y, Orientation orientation);
~Position();
// x-co-ordinate of the robot
int getX();
// y-co-ordinate of the robot
int getY();
// Orientation the robot is facing
Orientation getOrientation();
Notice that Orientation is an enumeration:
enum Orientation {
ORIEN_NORTH,
ORIEN_EAST,
ORIEN_SOUTH,
ORIEN_WEST,
};
3.2.2 Trail Class
The Trail class stores the history of positions of the robot as it conducted the wall-following. It stores an array
of Position objects. Since it’s an array we also need to track the number of position objects in the trail.
!
You must implement the Trail class using an array.
1This won’t be the case for Assignment 2, where you will have to make these decisions for yourself.
5
// Trail of position objects
// You may assume a fixed size for M1 & M2
Position* trail[TRAIL_ARRAY_MAX_SIZE];
// Number of objects currently in the trail
int length;
The constant TRAIL_ARRAY_MAX_SIZE is the maximum number of objects that can be in a trail. This constant
is given in the Types.h header file.
#define MAZE_DIM 20
#define TRAIL_ARRAY_MAX_SIZE (4 * MAZE_DIM * MAZE_DIM)
The Trail class has the following methods:
// Constructor/Destructor.
Trail();
~Trail();
// Copy constructor – create a DEEP COPY of the Trail
Trail(Trail& other);
// Number of elements in the Trail
int size();
// Get a pointer to the i-th trail element in the array
Position* getPosition(int i);
// Add a COPY of the Position object to the BACK of the trail.
void addCopy(Position* position);
These methods let you add positions to the trail, and get a pointer to an existing position. Be aware, that the
Trail class has full control over all position objects that are stored in the array. Thus, if position objects are
removed from the array you must remember to “delete” the objects.
3.2.3 WallFollower Class
The WallFollower class executes the right-wall following algorithm by using the Trail and Position classes. It
has two main components:
1. Execute the wall following algorithm
2. Get a deep copy of the full path that the robot took
// Constructor/Destructor
WallFollower();
~WallFollower();
// Execute the wall following algorithm for the given maze
void execute(Maze maze);
// Get a DEEP COPY of the path the robot travelled
Trail* getFullPath();
This uses a custom data type Maze, which is given in the Types.h. It is a 2D array of characters that represents
a maze using the format in Section 2. It is a fixed size, because we assume the size of the maze is known.
// A 2D array to represent the maze
// REMEMBER: in a maze, the location (x,y) is found by maze[y][x]!
typedef char Maze[MAZE_DIM][MAZE_DIM];
6
It is very important to understand the Maze type. It is defined as a 2D array. If you recall from lectures/labs,
a 2D array is indexed by rows then columns. So if you want to look-up a position (x,y) in the maze, you find
this by maze[y][x], that is, first you look-up the y value, then you look-up the x value.
The execute method is given a maze, and conducts the wall following algorithm in Section 2.1. Remember,
that the initial position of the robot is recorded in the maze. Importantly, the execute method must not
modify the maze it is given.
The trail of positions that the robot takes is stored in the private field:
// Trail of positions from the start to end
Trail* path;
The getFullPath method returns a deep copy of the trail of the robot’s positions in executing the wall
following. Be aware that this is a deep copy of the trail, so you need to return a new Trail object.
3.2.4 main file
The main file:
1. Reads in a maze from standard input
2. Executes the wall following algorithm
3. Gets the full navigation path
4. Outputs the maze (with the path) to standard output
The starter code gives you the outline of this program. It has two functions for you to implement that read in
the maze and print out the solution.
// Read a maze from standard input.
void readMazeStdin(Maze maze);
// Print out a Maze to standard output.
void printMazeStdout(Maze maze, Trail* path);
Some hints for this section are:
• You can read one character from standard input by:
char c;
std::cin >> c;
• Remember that is ignores all white space including newlines!
• When printing the maze, you might find it easier to first update the maze with navigation path, and then
print out the whole maze.
3.3 Milestone 3: Robot Directions
For Milestone 3, reconsider the output in Section 2.2. It contains a long backtrack section. It would be nice to
generate the actual list of movements of the robot with the backtracking removed, so we get the most direct
route from the starting position to the goal. These movements will be a series of cardinal directions,
After your program shows the solution to the maze, your program should print out in lowercase the cardinal
directions following the arrows generated in Milestone 2, but without any backtracking. Each direction is printed
in order one-at-a-time, each on a new line (as below). Hint: The Milestone 2 algorithm should be very helpful
in generating the correct list of directions.
!
Make sure update your tests cases from Milestone 1 and add in walking directions!
For example, if we use the maze and solution from Section 2, the walking directions would be:
7
east
east
east
east
east
east
east
east
south
south
south
west
west
north
west
west
south
south
east
south
south
south