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 non-empty string is called a minimal unique substring of s if and only if it satisfies: (i) α occurs exactly once in s (uniqueness), (ii) all proper prefixes of occur at le

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

list of 10 operating systems with their hardware specification and also list any 5 software associated with each operating system

The objectives of this assignment are to test your ability to create XML documents to contain well-defined information. This assignment will be used further in Assignment 2, so ple

You need to create a Fraction calculator program.You need to create a Fraction class to represent fraction objects and a FractionCalculator class that will perform operations on fr

Write a pseudocode for a program that reads a temperature as a whole number from a user and outputs a “probable” season (winter, sprint, summer, or fall) depending on the temperatu

Implement a two-dimensional table in Prolog. Your program will contain: An insert_entry predicate that takes a table, row, column and an entry and inserts the entry at the g

Problem Specification I/O programming is the \bread and butter", the raison d'etre, of microcontrollers. After all, our definition of a microcontroller is \a microprocessor wit

Question 1 What is CISC & RISC? Explain their addressing modes Question 2 Discuss the following- Design Specification of Assembler Design of Single Pass Assembler

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