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 Speci cation. 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 de ned 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 . Speci cation 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 speci cation. 0. In this Speci cation 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 speci c 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 speci ed 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 speci ed 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 speci ed 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
sca old. 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 sca old. 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 o set 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) di erent 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 speci cation will tested by Ed’s automated testing process. Compliance with the speci cation 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.
