Assignment

Aim

The objective of this assignment is to apply the concepts of threading by developing a simple C++ Pthreads program to discover the surroundings and the shortest path in a 2D maze.

Background

This assignment requires you to write a multi-threaded C/C++ "Pathfinder" program to discover the surroundings of a jungle maze. Each [x, y] location in the maze represents a ‘grid area' of the jungle terrain. A particular gird area could be :

• "impassable" (rep. by ‘#' barrier) ,
• contains danger (rep. by ‘X' danger area)
• clear, (i.e. allows you to travel)

An example of the jungle maze will be provided to you (see Appendix A, ‘mazedata.txt').

Your objective is to explore as much of the jungle maze terrain as possible, and mark the discovered area as barrier (‘#'), or danger (‘X') accordingly.

When your program terminate, it should output a map of the explored jungle maze, as well as 1 ‘safe' path, to traverse from Start to End locations.

Task Requirements

A) At startup, your program should read in the 2D maze configuration ("mazedata.txt") which stores the information about the maze dimensions, barriers, start and end locations. Please refer to Appendix A for an example.

B) For the purposes of testing your program, a sample of what information should be output is shown in Appendix B.

C) Before you start developing your program, you should take some time to review the output, and analyze the requirements of the Pathfinder program.

D) Your program should have at least 2 threads, each thread attempting to explore surrounding locations to discover whether it contains a barrier (‘#') or danger (‘X').

E) Impt 1 : your program should maintain a global Maze resource or variable, holding information about all the barriers or danger areas uncovered by your exploring threads!

F) Impt 2 : when a particular thread has encountered a barrier (‘#') or danger (‘X'), it should ...

• Record the path (history of point locations) it has traversed, since the Start Location, to reach the barrier / danger areas, and locations of barrier / danger should be marked on your ‘global Maze resource'

• The thread ‘loses its life' (i.e. should be destroyed) if it has encountered a danger area (‘X') !!

G) Whenever a thread is destroyed, your program should create another replacement thread, to traverse the jungle maze beginning from the Start Location again. But this time, it should access the ‘global Maze resource' to learn and avoid the barriers and danger areas discovered by its predecessor threads!

H) In this way, the ‘sacrifice' of the destroyed threads are not in vain, as its knowledge (of locations of the barriers / danger areas) have been recorded in the ‘global Maze resource' that can be accessed by future generations of created threads to aid their survival in order to discover a path to End Location!

I) As you probably guess by now, the access to the ‘global Maze resource' should be protected via usage of mutex locks. Whether a thread is:

• Updating its discovery of the path to barrier / danger areas OR
• Accessing the ‘global Maze resource' to learn about the discovered locations of the barriers / danger areas

Only 1 thread can access it at any one time!

J) Once the program is completed and tested to be working successfully, you are highly encouraged to add on "new features" to the program that you feel are applicable to the task of finding the shortest path thru a maze. Additional marks may be awarded subject to the relevancy and correctness of the new functionalities.

K) Your program should be written in C++, and using the library functions available in header file ‘pthread.h', to handle all aspects of thread creation, management and synchronization.

L) To encourage good program design, you should consider using different *.cpp class files to encapsulate groups of related methods/functions.

Attachment:- files.zip