[Solved] KIT107 Assignment3

The assignment is to construct a program that given some representation of a maze will find the path through to the end without you lifting a pencil or getting mud on your shoes!

An example of a maze is the following:

The challenge is to find a path from the square marked Start to the square marked Stop! by moving forwards, turning left, and turning right (with all directions relative to the current direction of travel) without going through walls which are indicated as black squares.

The application of this game to computing is the design of a program that allows a starting square to be given and then for the user to be graphically shown a solution derived by the computer. The computer will select moves by creating a game tree. A game tree consists of all the possible states of the game and in this assignment the computer determines any possible solution as the best one. Each node of the game tree has children that indicate the states of the game that follow from the state of the parent for each possible move, i.e. each node in the tree possesses three branches which represent the maximum possible moves from the parent node.

This assignment uses many data structures (trees, linked-lists, stacks, and queues) to solve the puzzle. The game will be text only.

A sample run of the game is shown below for depth-first:

And breadth-first:

Task

A Visual Studio project file is available for download from MyLO. The project contains many header (.h) and source (.c) files. All required files are present.

Your task is to complete the functions within the program files which have been declared but for which the function bodies are missing and to update the header comments for the source files that you change.

Program Style

Your program should follow the following coding conventions:

• const variable identifiers should be used as much as possible, should be written all in upper case and should be declared before all other variables;
• Variable identifiers should start with a lower case letter, be meaningful, and variables should only be declared at the top of a function;
• Every if and if-else statement should have a block of code (i.e. collections of lines surrounded by { and }) for both the if part and the else part (if used);
• Every loop should have a block of code;
• The keyword continue should not be used;
• The keyword break should only be used as part of a switch statement; Opening and closing braces of a block should be aligned;
• All code within a block should be aligned and indented 1 tab stop (or 4 spaces) from the braces marking this block; Commenting:
  • There should be a block of header comment which includes at least
    • file name
    • student names
    • student identity numbers
    • a statement of the purpose of the program
    • date o Each variable declaration should be commented
  • There should be a comment identifying groups of statements that do various parts of the task
  • Comments should describe the strategy of the code and should not simply translate the C into English

Style marks will be awarded proportionally, i.e. if you attempt only half the coding you can expect only half the style marks.