Maze-solving, structures and linked lists, Programming Languages

For this assignment you will use the robot/maze simulation example introduced in mini-assignments 0625ma-0627ma to develop a maze-solving program. The program will read a file containing the maze configuration and the robot's starting position, as in the mini-assignments. The robot should then explore the maze using a "right-hand-on-the-wall" strategy. As the robot traverses the maze, the robot's action at each intersection or dead-end (go straight, turn left, turn right, or u-turn) should be recorded in a linked list. The "right-hand-on-the wall" strategy will guarantee that the robot will eventually successfully complete the maze. However, the robot's path may contain many extra turns and backtracks as it explores the maze. The program should use the curses library to display an animation of the robot's travel through the maze. In addition, after completing the maze the program should display "turn-by-turn" instructions for the route followed, using the information stored in the linked list. Once the maze has been solved, the program should process the linked list of recorded turns to determine the optimal path through the maze using the path- optimization process. The robot will then re- traverse the maze using the optimized path. The program should print the optimized turn-by-turn instructions and display a curses animation of the robot traversing the maze via the optimized path. Conceptually, the maze should be considered as black lines drawn on a white background. In actuality, the maze will be represented in your program as a grid, each element of which has either the value 0 (representing white) or 255 (representing black). The maze configuration is read from a supplied text file. The first two lines of the file indicate the number or rows and columns, respectively in the maze. The remainder of the file specifies the value for each element of the maze, in by-row order. The code for reading the maze information from the file and storing it into a Maze structure is provided for you, as in the earlier mini- assignments. A robot model is also provided as in the earlier mini-assignments. The following functions for moving the robot on the maze are provided in robotModel.c: moveStraight(), moveLeft(), moveRight(), uTurn(), and moveHere().

The robot is assumed to have four sensors, which sense the color (black or white) of the maze grid at the following locations: directly in front of the robot, directly to the left of the robot, directly under the robot, and directly to the right of the robot. The sensor readings can be obtained by calls to four supplied functions: blackInFront(), blackToLeft(), onBlack(), and blackToRight(). See the file maze.c for the definitions of these functions. You can assume that the robot will be initially positioned on a maze line. The end of the maze will be represented by a "black area" large enough that all sensors will read "black" for two consecutive time steps. Additional information on how to use the sensors to determine the configuration of intersections and other maze features. As your robot traverses the maze (both before and after path optimization), your program should use curses to show an animated display of the robot's progress. A function printMazePlusCurrentPos() is provided in maze.c to assist you with this. You can control the robot's movement speed by using the curses napms() function. For instance, to cause your program to delay for one second before advancing the robot to its next position, you can use the statement:

napms(1000); //sleep for 1000 ms before continuing to next statement

The supplied directory homework/hw4 contains the curses library, along with header and C-program files containing functions for the robot and maze models. The directory also contains a partially completed main program, hw4.c, that you will need to edit to complete the assignment. The directory contains two maze definition files, maze.text and mazeLarge.txt. As inferred from the file names, the maze defined by mazeLarge.txt is much larger that the one defined by maze.txt. Remember that the name of the maze file must be supplied as a command line argument when the program is run. Code::Blocks project files are also provided for both Linux and Windows. Consult the lecture slides for June 25-27 for instructions on how to compile and run the code using either Code::Blocks or the command line.

Required Programs:

1. Program successfully solves provided maze using "right-hand-on-the-wall" strategy.

2. Program correctly maintains "turn information" in a linked list and correctly prints out "turn-by-turn" instructions for route followed in original maze traversal.

3. Program correctly optimizes the turn list to compute optimal route and correctly prints out the optimized turn-by-turn instructions.

4. Program correctly displays curses animation of robot solving maze via optimal route.

Posted Date: 2/18/2013 4:56:19 AM | Location : United States

Related Discussions:- Maze-solving, structures and linked lists, Assignment Help, Ask Question on Maze-solving, structures and linked lists, Get Answer, Expert's Help, Maze-solving, structures and linked lists Discussions

Write discussion on Maze-solving, structures and linked lists
Your posts are moderated
Related Questions
a program that enter an alphabet from the user and compare it is vowel or not?

Implement the "Nuclear Reactor" example using the following:  An ISR triggered by a button press  A task to update the temperatures  A semaphore to communicate between the ISR and

Assigment 01 Subject Code: ITE 2106 Subject Name: Software Engineering You run a software development organization catering to external clients to build software solutions. The bus

Open error message coming out when compiling

Question 1 How to call a WML Script from a WML Page? Question 2 Write short notes on WML Script Operators and Expressions Question 3 Write short notes on WML Script Statements

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

Please explain about sub programming.

A specification of a function TOARR is given below. function TOARR(n in Int, s in Stack of Int) return in Array of Int pre n ≥ 0. post The returned value is an array of size

Expertsmind brings you unique solution in java assignments Interfaces A program in the Java selection language is a fuzzy type that is used to specify a program (in the ge

You must use the keyword ''var'' to create and initialize a variable. The placement of the variable creation in your code is very important. Examples: var first = 21; var secon