Goals
The goals of this homework are:
- Exercise using a 2D grid map and the concept of position, orientation and pose in a simplified form in 2D.
- Exercise your python programming skills.
- Exercise good programming practice by adhering to good coding rules.
- You will do so by implementing a left-hand wall-following algorithm that can work on arbitrary complicated input maps with arbitrary start poses.
Hand out
- Example input: maze.test.
- Example output: maze.test.txt.
- Log in the Gradebot to find the due date and how to clone the repository of this homework.
- This homework is for ALL students.
Check in
maze.py- Your program may not use any third-party libraries.
Policy on plagiarism
This is an individual homework. While you may discuss the ideas and algorithms of this homework with others, at no time should you read, possess, or submit the solution source code of any other person (including people outside this course), or allow anyone else to read or possess your source code. We will detect plagiarism using automated tools and will prosecute all violations to the fullest extent of the university regulations, including failing this course, academic probation, and expulsion from the university.
Description
Input:
The input to the program is a text file containing comments, the robot start pose and a 2D map. Comment lines begin with a dollar character ($) and should be ignored by your program.
The first non-comment line of that text file encodes the start pose of the robot. Those are three integer numbers separated by spaces. They encode x, y and orientation of the start, in that order.
For the purpose of this assignment the orientation is encoded as four integer values between 0 and 3.
- 0: positive in x-axis (east)
- 1: positive in y-axis (north)
- 2: negative in x-axis (west)
- 3: negative in y-axis (south)
The second part of the input is the map. It consists of either '.' (a free cell) or 'X' (occupied cell = wall). The bottom left cell in the text file is located in the origin of the coordinate system (0, 0). The x-axis follows this line to the east (right) while the y-axis follows this column to the north (up).
The width of the map is defined by the number of characters in the line (if the lines of the map have different length the program behavior is undefined - all gradebot test cases have the same line length for the map part.) The height of the map is defined by the number of lines in the map part.
Output:
The program has to output all poses the robot drives through while following the left hand wall following algorithm (see below). The output starts with the start pose and ends with the end pose. All intermediate poses have to be displayed as well. Make sure that you do not print the same pose immediately again - with the exception if start and end pose are the same! The end pose is always outside of the map (we have exited the maze).
The pose output has to have the following format:
[[x, y], o]
with x and y being the coordinates and o the orientation with the same encoding as the input. There is one space after each comma. Write each pose in a new line.
Algorithm:
The algorithm has two parts: 1) Find the Wall and 2) Follow the Wall.
Find Wall
Go forward until you either:
Reach an exit
Have a wall to the left side
Have a wall in front of you
In this case turn right once
Follow Wall
Do until you reach an exit:
If no wall on your left:
Turn left
Step forward
Else if wall in front of you:
Turn right
Else:
Go forward
Required Functions
It is required that you implement and use functions with the following name and according functionality:
# moves the provided pose one step forward
forward(...)
# turns the provided pose left
turnLeft(...)
# returns true if the cell in front of given pose is occupied
isWallInFront(...)
There are some more functions that you should implement to make your programming task easy (think about what else you need) - but those are not a requirement of this HW. It is up to you to determine which arguments to pass to those functions, what to do with those arguments and if/ what they return. The gradebot is checking if those functions are present - but the TAs will check by hand if you are actually using them according to their meaning. You will loose 50% of your score if you don't adhere to the standard.
Reason for this rule: You should practice to use a good coding style and split your problems/ algorithms into sub-tasks using properly named functions.
Length of Functions
The maximum number of lines of code (not counting blank, comment-only lines and sub-functions) per function is 40. If even a single function of your program exeeds this number you will be deducted 50% further points. (Point deductions are multiplied together - if you violate all three rules you will only get 12.5% of your gradebot points.)
Reason for this rule: You should practice to use a good coding style and split your problems/ algorithms into sub-tasks using properly named functions.
Comments in the Code
You are required to write meaningful comments for your program. Gradebot will ensure that you have a comment in at least 50% of the non-blank lines (so please do keep blank lines in your code to make it easier on the eyes). Your comments have to be in English and meaningful. The TAs will check your code by hand for comments. You will loose up to 50% of your score if you don't adhere to this rule.
Reason for this rule: Writing comments is essential once you start programming in a group/ company. This will help other programmers (TAs) to unerstand your code. Having lots of comments is a very good coding practice which is very often neglected.
Hints
Process the input through the following stages:
- Map: Write a map class with a get function that takes a position as input and returns the map value (0 or 1) or, in case the position is outside the map, another value (for example 2).
- Parser: Read the input and puts the values in the state variable (pose) and the map class.
- Executor: First executes the Find Wall algorithm and then the Follow Wall algorithm.
It might be a good idea to include a step counter in Follow Wall that exits the program after a certain number of steps. This is to prevent an endless loop if the program does not find an exit. Using the above algorithm, all test cases in the grade bot are guaranteed to find an exit in less than 500 steps.