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
develop a pseudocode algorithm to determine the total amount of extra cost changed to the organizers for expenses accurednduring the workshop. the code is to be written for an unde

The GuessingGame class contains a skeleton for a program to play a guessing game with the user. The program should randomly generate an integer between 1 and 10 and then ask the us

A non-empty string β is called a repeat pre x of a string s if ββ is a pre x of s. Give a linear time algorithm to find the longest repeat prefix of s. Hint: Think of using lca

2. TEST & AND TEST is like CMP, it is used for conditional statement, and doesn’t save the answer. AND is logical multiplication. 3. INS & IN IN is used for data transfer from I/O

You are required to develop a program that calculates the charges for DVD rentals, where current release cost RM3.50 and all others cost RM2.50. If a customer rents several DVDs, e

Consider a system that has the following UML models: Use Case for CalculateTotalProjectCost Trigger: End of each month Normal Flow of Events For each project in the pro

Task .Task 1 Database design This task will allow you to demonstrate the following Learning Outcomes (LOs): LO 2. Justify the design and development of the application and critica

Question: (a)  An HTML file "decor.html" uses an external Cascading Style Sheet file name  "nicedesign.css". Users are viewing the Web page making use of different kinds of  br

Suppose L is a context-free language and L' is regular. Show that L∩ L' is a context- free language. Specifically, if you're given a PDA diagram of L and a DFA diagram for L' , des

What is DOM? The Document Object Model is a platform- and language-neutral interface that will allow programs and scripts to dynamically access and update the content, structure an