20191029, 255 PM
Maze Navigation
In robotics a major challenge when exploring the world is successfully navigating finding 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 find a sequence of waypoints through a maze between a nominated start location and a nominated finish location.
One such environment maze is shown below. The black lines represent impassable walls, whereas the white actually light grey in the figure 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 subtasks.
1. ReadingtheBMPfile:ABMPfilehasaheadercontaininginformationontheimage, 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 Specification. Examples of the information to be displayed are provided below.
https:edstem.orgcourses3530assessments5900 Page 1 of 10
20191029, 255 PM
2. EncodingtheBMPfile:Afterreadingthebitmappedimageyouneedtoencodeitasa matrix such that the maze can be displayed in humanreadable form. The depiction of the maze will include its walls and corridors and the start and finish locations within the maze. In preparation for solving the maze finding the shortest path from the start location to the finish 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 defined as:
1. AnyintersectionorjunctionsuchasaTintersectioninthefreespace; 2. Adeadend;or
3. WherethepathchangesdirectionsuchasanLshapeinthefreespace.
3. Solvingthemaze:Afterconstructingthegraphyouaretousethedepthfirstsearch DFS algorithm to find the path that connects the start location to the finish 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 finish coordinates .
Specification
You are required to write a program that reads, represents, displays and solves mazes that are described by bitmap files. The program must comply with the following specification.
0. In this Specification 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 file named mazegame .
Command line arguments
2. Your program shall be invoked as
.mazegame file name finish x finish y b n p.
3. The three command line flags b , n and p are optional and may be present in any combination and order. Each flag shall cause specific information to be written to stdout . The information that is caused to be printed by zero or more of the flags shall be printed in the order of the flags.
4. If the b flag is present on the command line the program shall print information about the bitmap file to stdout .
5. The b flag may be followed by zero or more characters without intervening whitespace.
https:edstem.orgcourses3530assessments5900 Page 2 of 10
20191029, 255 PM
The characters that are present shall determine what is printed to stdout , as follows: The presence of f shall cause the file name to be printed
The presence of s shall cause the file size to be printed
The presence of i shall cause the image data offset to be printed
The presence of w shall cause the image width to be printed The presence of h shall cause the image height to be printed The presence of r shall cause the row size to be printed
6. Multiple characters in any order can follow the b flag. If two or more of the above characters follow the b flag the bitmap file information shall be printed in the order specified by the characters.
7. If the b flag 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 headers. 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
RowSizeFloorBitsPerPixel ImageWidth314 32
8. If the n flag 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 flag 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. Wallshallberepresentedbythecharacter
2. The finish location shall be represented by the character F
3. ThestartlocationshallberepresentedbythecharacterS
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
https:edstem.orgcourses3530assessments5900 Page 3 of 10
20191029, 255 PM
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 flag 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 finish
location.
12. The path printed in response to the p flag shall take the form of a list of node coordinates, with one line per node, and the first coordinate corresponding to the start location and the last coordinate in the list corresponding to the finish coordinate.
13. Each entry in the path list shall be in the form of
x: x coordinate, y: y coordinate
where x coordinate and y coordinate are integers within the bounds of the maze.
Note: The start and finish locations will always be nodes. Error messages
14. The program shall emit the following error messages to stderr if any of the following specified error condition is detected.
1. If a flag 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 flag is invalid the program to print Error: Invalid Header Input. andimmediatelyexit.
3. Ifaninvalidnumberofflagsispresentonthecommandline,theprogramistoprint Error: Invalid Flag Number. and immediately exit.
4. Iftheinputfilenominatedonthecommandlinedoesnotexisttheprogramshallprint an error message Error: Input file s was not found. and immediately exit. The token s shall be replaced with the name of the file that was nominated.
5. Ifthespecifiedfinishlocationisinvalid,suchasbeinginawalloroutsidetheboundsof the maze, the program is to print Error: The finish location is invalid.
6. Iftheendpointcannotbereachedbyusingdepthfirstsearchtheprogramistoprint Error: The end goal cannot be reached! and immediately exit.
Example Maze
https:edstem.orgcourses3530assessments5900 Page 4 of 10
20191029, 255 PM
An example maze maze55.bmp has been provided in the mazes folder in the scaffold. Example Input and Output
Example use of the b flag to print information about the file Example 1
.mazegame mazesmaze55.bmp 5 5 b
File name: maze55.bmp
File size: 450
Image location offset byte: 54
Image width: 11
Image height: 11
Row size: 36
Example 2
.mazegame mazesmaze55.bmp 5 5 bisf
Image location offset byte: 54
File size: 450
File name: maze55.bmp
Example use of the n flag to print an ASCII representation of the maze
.mazegame mazesmaze55.bmp 5 5 n
N N NN N NNFN N S NN N
https:edstem.orgcourses3530assessments5900 Page 5 of 10
20191029, 255 PM
Example use of the p flag to print the shortest path from start to finish
.mazegame mazesmaze55.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 flags
If multiple flags are present the information that is printed shall be in the order that the flags appear on the command line.
Example 1
.mazegame mazesmaze55.bmp 5 5 b n p
File name: testmazesmaze55.bmp
File size: 450
Image location offset byte: 54
Image width: 11
Image height: 11
Row size: 36
N N NN N NNFN N S NN N
https:edstem.orgcourses3530assessments5900 Page 6 of 10
20191029, 255 PM
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
.mazegame mazesmaze55.bmp 5 5 bifs p n
Image location offset byte: 54
File name: maze55.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 NN N NNFN N S NN N
About the BMP File Format
Bitmap files.bmphave a relatively simple file format. A bitmap file consists of a 14byte general header followed immediately by a DIB deviceindependant bitmap header containing
https:edstem.orgcourses3530assessments5900 Page 7 of 10
20191029, 255 PM
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 scaffold.
Running the hex dump utility
xxd filename.bmp
in the terminal window is a useful way of displaying the encoded BMP information. For more information see https:en.wikipedia.orgwikiHexdump
Bitmap File Header
A bitmap file always begins with a 14byte header that describes the contents of the file. The bitmap file header always starts with the 2 bytes 0x42 0x4d i.e. BM . The next 4 bytes give the size of the file in bytes. The next 4 bytes are reserved. The next 4 bytes indicate the offset from the start of the file to where the pixel data start.
DIB Header
The bitmap file header is always immediately followed by the DIB header. The first 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 file format see
https:en.wikipedia.orgwikiBMPfileformat
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 25616,777,216 different colours, all of the pixels that represent the maze will be either black or white.
Black: R,G,B0,0,0
White: R, G, B255, 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:
https:edstem.orgcourses3530assessments5900 Page 8 of 10
20191029, 255 PM
Header stdio.h has inputoutput functions: fgets , scanf , fprintf , fread , fwrite , fopen , fseek , fclose
Header getopt.h has argument parsing function: getopt
Header stdlib.h has text to numeric functions strtod and more.
Header ctype.h has character functions: isdigit , isalpha , isspace , tolower
Header assert.h has the bugcatching 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 students 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 specification will tested by Eds automated testing process. Compliance with the specification 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 Selfdocumenting 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.
https:edstem.orgcourses3530assessments5900 Page 9 of 10
20191029, 255 PM
https:edstem.orgcourses3530assessments5900 Page 10 of 10
Reviews
There are no reviews yet.