2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 1/8
Maze Navigation
In robotics a major challenge when exploring the world is successfully navigating (nding and
following a path) through an environment. One simple method for doing this is to construct a
sequence of waypoints in the physical environment and then to traverse them in sequence.
You have been given a set of environments (mazes) that have been kindly represented as images
so that they are easier for you to work with. As a robot programmer it is your job to read an
image, interpret it as a set of waypoints that will enable your robot to travel around inside the
maze, and then nd a sequence of waypoints through a maze between a nominated start
location and a nominated nish location.
One such environment (maze) is shown below. The black lines represent impassable walls,
whereas the white (actually light grey in the gure) areas between the walls represents free
space that can be navigated by the robot. The maze has a one pixel wide black border that
should be treated as the 'edge of the world' and should not be traversed. The red line
represents a valid path through the maze, constructed as a directed sequence of waypoints.
Coordinates are indexed from the bottom left of the image and the starting position will always
be the pixel 1,1 in the bottom left hand corner.
Approach to the Problem
The task can be split into three nearly independent sub-tasks.
1. Reading the BMP le: A BMP le has a 'header' containing information on the image,
immediately followed by the actual image data. You are to extract information from this
header and decode the image data. More information on the BMP image encoding is
included following assignment Specication. Examples of the information to be displayed
are provided below.
2. Encoding the BMP le: After reading the bitmapped image you need to encode it as a
matrix such that the maze can be displayed in human-readable form. The depiction of the
maze will include its walls and corridors and the start and nish locations within the maze.
In preparation for solving the maze (nding the shortest path from the start location to the
2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 2/8
nish location) you are then to represent the maze as a graph structure with nodes and
edges in a similar way to Quiz 5. A node is to be dened as:
1. Any intersection or junction (such as a T-intersection in the free space);
2. A dead end; or
3. Where the path changes direction (such as an L-shape in the free space).
3. Solving the maze: After constructing the graph you are to use the depth-rst search (DFS)
algorithm to nd the path that connects the start location to the nish location. Unlike in
Quiz 5, where you were to print out each node that DFS visited, here you are to print the
coordinates of every node (intersection) on the shortest route from the start coordinates to
the nish coordinates .
Specication
You are required to write a program that reads, represents, displays and solves mazes that are
described by bitmap les. The program must comply with the following specication.
0. In this Specication the word "shall" indicates a mandatory requirement and the word
"should" indicates a feature that is desirable but not mandatory.
1. Your project must have a Makefile that builds your code to produce an executable le
named maze_game .
Command line arguments
2. Your program shall be invoked as
./maze_game [-b] [-n] [-p] .
3. The three command line ags -b , -n and -p are optional and may be present in any
combination and order. Each ag shall cause specic information to be written to stdout . The
information that is caused to be printed by zero or more of the ags shall be printed in the order
of the ags.
4. If the -b ag is present on the command line the program shall print information about the
bitmap le to stdout .
5. The -b ag may be followed by zero or more characters without intervening whitespace. The
character(s) that are present shall determine what is printed to stdout , as follows:
The presence of f shall cause the to be printed
The presence of s shall cause the to be printed
The presence of i shall cause the to be printed
The presence of w shall cause the to be printed
The presence of h shall cause the to be printed
2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 3/8
The presence of r shall cause the to be printed
6. Multiple characters in any order can follow the -b ag. If two or more of the above characters
follow the -b ag the bitmap le information shall be printed in the order specied by the
characters.
7. If the -b ag is followed by no character (i.e. whitespace) then all of the information shall be
printed in the order given in clause 5.
Note that all information except the row size can be directly extracted from the header(s). Since
each row has 'padding' added to ensure that the number of bytes is always a multiple of 4, to
calculate the row size in bytes you need to use the formula
Row Size  =  F loor ⋅( 32
BitsP erP ixel  ⋅ ImageW idth + 31( ) ) 4
8. If the -n ag is present on the command line the program shall print an ASCII representation
of the maze to stdout .
9. The output produced by the -n ag shall use the following ASCII characters to represent
elements of the maze, where a single character is to be printed to represent the state of each
pixel in the bitmap representation of the maze:
1. Wall shall be represented by the character ' # '
2. The nish location shall be represented by the character 'F'
3. The start location shall be represented by the character ' S '
4. A node shall be represented by the character 'N'
5. Open space shall be represented by the character ' '
10. Since only one character is to be printed to represent each pixel in the bitmap, the
precedence of characters shall be as per the list in clause 9. That is, if more than one character
could be printed at a location, the character with the smaller number in the list shall take
precedence.
11. If the -p ag is present on the command line the program shall calculate and print to
stdout the shortest path to traverse from node to node from the start location to the nish
location.
12. The path printed in response to the -p ag shall take the form of a list of node coordinates,
with one line per node, and the rst coordinate corresponding to the start location and the last
coordinate in the list corresponding to the nish coordinate.
13. Each entry in the path list shall be in the form of
x: , y:
where and are integers within the bounds of the maze.
Note: The start and nish locations will always be nodes.
2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 4/8
Error messages
14. The program shall emit the following error messages to stderr if any of the following
specied error condition is detected.
1. If a ag other than -n , -b or -p is present on the command line the program is to print
Error: Invalid Input. and immediately exit.
2. If any character following the -b ag is invalid the program to print Error: Invalid
Header Input. and immediately exit.
3. If an invalid number of ags is present on the command line, the program is to print
Error: Invalid Flag Number. and immediately exit.
4. If the input le nominated on the command line does not exist the program shall print an
error message Error: Input file %s was not found. and immediately exit. The token
%s shall be replaced with the name of the le that was nominated.
5. If the specied nish location is invalid, such as being in a wall or outside the bounds of the
maze, the program is to print Error: The finish location is invalid.
6. If the end point cannot be reached by using depth-rst search the program is to print
Error: The end goal cannot be reached! and immediately exit.
Example Maze
An example maze maze-5-5.bmp has been provided in the mazes folder in the scaold.
Example Input and Output
Example use of the -b ag to print information about the le
Example 1
$ ./maze_game mazes/maze-5-5.bmp 5 5 -b

File name: maze-5-5.bmp
File size: 450
Image location offset byte: 54
Image width: 11
Image height: 11
Row size: 36
Example 2
$ ./maze_game mazes/maze-5-5.bmp 5 5 -bisf

Image location offset byte: 54
File size: 450
File name: maze-5-5.bmp
2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 5/8
Example use of the -n ag to print an ASCII representation of the
maze
$ ./maze_game mazes/maze-5-5.bmp 5 5 -n

###########
#N N N#N#
##### # # #
#N N# # #
# ##### # #
# #N#F# # #
# # # # # #
# # #N N# #
# # # ### #
#S N#N N#
###########
Example use of the -p ag to print the shortest path from start to
nish
$ ./maze_game mazes/maze-5-5.bmp 5 5 -p

x: 1, y: 1
x: 1, y: 7
x: 5, y: 7
x: 5, y: 9
x: 7, y: 9
x: 7, y: 3
x: 5, y: 3
x: 5, y: 5
Multiple ags
If multiple ags are present the information that is printed shall be in the order that the ags
appear on the command line.
Example 1
$ ./maze_game mazes/maze-5-5.bmp 5 5 -b -n -p

File name: test_mazes/maze-5-5.bmp
File size: 450
Image location offset byte: 54
Image width: 11
Image height: 11
Row size: 36

###########
2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 6/8
#N N N#N#
##### # # #
#N N# # #
# ##### # #
# #N#F# # #
# # # # # #
# # #N N# #
# # # ### #
#S N#N N#
###########

x: 1, y: 1
x: 1, y: 7
x: 5, y: 7
x: 5, y: 9
x: 7, y: 9
x: 7, y: 3
x: 5, y: 3
x: 5, y: 5
Example 2
$ ./maze_game mazes/maze-5-5.bmp 5 5 -bifs -p -n

Image location offset byte: 54
File name: maze-5-5.bmp
File size: 450

x: 1, y: 1
x: 1, y: 7
x: 5, y: 7
x: 5, y: 9
x: 7, y: 9
x: 7, y: 3
x: 5, y: 3
x: 5, y: 5

###########
#N N N#N#
##### # # #
#N N# # #
# ##### # #
# #N#F# # #
# # # # # #
# # #N N# #
# # # ### #
#S N#N N#
###########
About the BMP File Format
2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 7/8
Bitmap les ( *.bmp ) have a relatively simple le format. A bitmap le consists of a 14-byte
general header followed immediately by a DIB (device-independant bitmap) header containing
metadata about the pixel format and image size. The pixel data follows immediately after the
DIB header. The size of the pixel data can be calculated from the information in the header. An
example maze has been included in the scaold.
Running the hex dump utility
xxd
in the terminal window is a useful way of displaying the encoded BMP information. For more
information see https://en.wikipedia.org/wiki/Hex_dump
Bitmap File Header
A bitmap le always begins with a 14-byte header that describes the contents of the le. The
bitmap le header always starts with the 2 bytes 0x42 0x4d (i.e. BM ). The next 4 bytes give the
size of the le in bytes. The next 4 bytes are reserved. The next 4 bytes indicate the oset from
the start of the le to where the pixel data start.
DIB Header
The bitmap le header is always immediately followed by the DIB header. The rst 4 bytes of the
DIB header indicate the size of the DIB header. The next 4 bytes indicate the number of pixels in
the horizontal direction. The next 4 bytes indicate the number of pixels in the vertical direction.
The remainder of the DIB header contains additional information about the image, such as
colour data and compression, that is not relevant to this assignment.
If you are interested in learning more about the BMP le format see
https://en.wikipedia.org/wiki/BMP_le_format
Image Pixel Data
Each pixel in the image is represented by 3 bytes that give the values of the red, green and blue
(R, G, B) content of the pixel. Each of the 3 bytes can have a value between 0 and 255 that
indicates the amount of R, G or B in a pixel. Although a pixel can therefore have many (256 x 256
x 256 = 16,777,216) dierent colours, all of the pixels that represent the maze will be either black
or white.
Black: (R, G, B) = (0, 0, 0)
White: (R, G, B) = (255, 255, 255)
Libraries
You may use any functions in the C11 Standard Library. You may not use any external sources of
code, regardless of licensing.The following libraries are likely to be most useful:
Header has input/output functions: fgets() , scanf() , fprintf() , fread() ,
fwrite() , fopen() , fseek() , fclose()
2019/10/28 (11) MTRX1702 – Assessments
https://edstem.org/courses/3530/assessments/5900 8/8
Header has argument parsing function: getopt()
Header has text to numeric functions strtod() and more.
Header has character functions: isdigit() , isalpha() , isspace() ,
tolower()
Header has the bug-catching macro assert()
Academic Honesty
This assignment is to represent individual work. You are not to collaborate with your peers, this
is an individual assignment. You may discuss your approach to the problem with other students,
but you may not share code, look at another student's code, or allow another student to look at
your code. Similar code will be treated with suspicion. All submissions will be checked for
similarity.
Marking
Compliance with the specication will tested by Ed's automated testing process. Compliance with
the specication is worth 75% of this assignment.The remaining 25% of the assignment is
awarded for quality of your code. Things that will be assessed include, but are not limited to:
Appropriate and consistent formatting and style
Project layout
Good coding practices (e.g. no global variables or "magic numbers")
Self-documenting code, including appropriate commenting
Appropriate use of functions
Late Submission
Late submissions will be penalised at a rate of 5 marks per day or part thereof. Submissions that
are more than 10 calendar days late will not be accepted. The last submission is the one that will
be assessed, regardless of whether an earlier one has a greater value in test cases solved.