Maze-solving, structures and linked lists, Programming Languages

Assignment Help:

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.


Related Discussions:- Maze-solving, structures and linked lists

Develop a socket program in unix, Develop a socket program in UNIX/Linux th...

Develop a socket program in UNIX/Linux that uses (i) TCP as the transport protocol and  (ii) UDP as the transport protocol for transferring  a short message between a client and  s

Define a prolog predicate that asserts list, Define a Prolog predicate flat...

Define a Prolog predicate flatten(List, FlattenedList)  that asserts List  is any nested list of atoms and  FlattenedList  is the same list with the nesting removed. The atom [] sh

A Simple Distributed Computing Platform , You are asked to develop a replic...

You are asked to develop a replicator (client) that distributes a large job over a number of computers (a server group) on a single switched LAN (our BU04 lab). In this assignment,

Write a procedure to prints the avl tree, (a) Write a procedure called (loo...

(a) Write a procedure called (lookup n t). This procedure has 2 arguments: n is the value being looked up, t is the AVL tree. The subtree with n as its root is returned (or '() if

Develop an html document with a nested list, 1. Develop a Web page, indicat...

1. Develop a Web page, indicating an ordered list of the names of your five friends. 2. Develop an HTML document with a nested list indicating the content page of any book 3.

Write a program that lets the user play an adventure game, Let the player (...

Let the player (denoted U in the diagram below) navigate around the board until she wins the game by finding the exit or is killed by a monster. A player begins the game with a sli

Miranda, Hi, Can you do exercises: D2, D3, D4, and D5 on page 230 of the fo...

Hi, Can you do exercises: D2, D3, D4, and D5 on page 230 of the following book: http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html . The book can be downloaded for free from t

Matlab, want to do an image-mean. but image is and mean is so an error ...

want to do an image-mean. but image is and mean is so an error showing Error using ==> minus Number of array dimensions must match for binary array op. wat to do?

Dating game program, You are to write a program that determines the day of ...

You are to write a program that determines the day of the week for New Year's Day in the year 3000. To do this, you must create your own date class (MyDate) and use the following i

1 real and 2 complex eigenvalues, 1 Real and 2 Complex Eigenvalues    ...

1 Real and 2 Complex Eigenvalues    From the real eigenvalue/vector pair, l 1 and ?h 1 e l1 t ?h 1 We find the other two solutions in identical manner which we did

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd