Road Intersection Simulation

Overview

For this assignment, you will use a Queue ADT to simulate traffic going through a four-way stop. You may encapsulate your List ADT from the lab tutorial in Unit 1, or you may write a Queue ADT using a different list ADT, arrays or a circular buffer. All ADTs submitted must be your own work, you may not use a third-party ADT library for this assignment. Your Queue ADT must be abstracted to take void * data and your simulation must use functions to operate on the Queue and add/remove data rather than manipulated the Queue nodes directly.

You will write a program that uses a Queue ADT to simulate traffic going through a four-way stop. The program will read data from an input file and use that data to drive the simulation. Sample input files will be given, but will not be adequate to thoroughly test the program. You are expected to create your own test data as well. Your assignment will be graded using an input file that you have not seen.

Learning Outcomes

When you have completed this assignment, you should be able to:

• Implement and test a Queue ADT that abstracts the type of data away from the ADT;
• Parse structured text data from an input file;
• Implement and test a simple simulation program;
• Provide meaningful output to users of your program;
• Provide meaningful output to users of your program;

Required Prior Knowledge

This assignment is designed to help you understand how a queue works. Queues and Stacks are very similar. You should read the topics on Queues and Stacks (in the References) before attempting this assignment.

This assignment is designed to help you understand how a queue works. Queues and Stacks are very similar. You should read the topics on Queues and Stacks (in the References) before attempting this assignment.

• Using void * pointers to pass data elements to an ADT;
• Using function pointers to pass in data management functions to the ADT (destroy, compare and print);
• Using doxygen to generate documentation for C programs;
• Writing and using makefiles to compile C programs;
• Using tar and gzip to group and archive files and folders;
• Using argv and argc to get command line arguments to a C program.

Instructions

Create a Queue ADT in C and use it in a simulation of traffic flowing through a four-way stop intersection. Your simulation is a simulation of data and time only and does not need to have any visualization of the actual traffic going through the intersection. Your Queue ADT must be abstracted to take void * data and your simulation must use functions to operate on the Queue and add/remove data rather than manipulated the Queue nodes directly.

Make the following assumptions about the four-way stop:

• All roads are single-lane. Vehicles travelling in the same direction must proceed through the intersection in single file.
• Vehicles may turn right, left or go straight through the intersection when it is their turn to proceed.
• There may be only one vehicle in the intersection at any given time. This is not how intersections are normally used, but it simplifies the simulation.
• A vehicle travelling straight through an intersection takes 2 seconds to clear the intersection.
• A vehicle turning right takes 1.5 seconds to clear the intersection.
• A vehicle turning left takes 3.5 seconds to clear the intersection.
• The next vehicle in a queue takes 1 second to move forward into a position where travelling through the intersection is possible.
• The data file will always have one vehicle clearly arriving first to begin the simulation
• Vehicles should proceed through the intersection in a first-come, first-through fashion. In the event of two vehicles arriving at the front of the queue at the same time, use the vehicular traffic rules for Right of Way.

The data file will be space delimited and consists of three data elements in each row:

• The first element represents the direction the car is travelling prior to getting to the intersection. This element is represented by the letters N, S, E, W.
• The second element of each row represents the direction that the car will proceed through the intersection. The letters F(forward), L(left), and R(right) will be used.
• The third element is the time, in seconds, that the vehicle reaches the queue of vehicles at the intersection.

A sample set of data is shown below:

N F 1
S F 2
E R 2
W R 2
W F 3
N F 3
N L 9
N R 11
W L 5
W R 8
W F 15

Your simulation must load the data file, taking the filename for the data file as a command line argument. Use four queues, one for each initial direction of travel to simulate vehicles arriving at the intersection. Use a counter (known as a simulation clock) to move the simulation forward 1 second at a time. Note that you are not intended to make the simulation run in real time. Instead the counter will advance to 1, and the simulation will make decisions about the vehicles that arrived at time 1. Since a vehicle takes at least 1.5 seconds to go through the intersection, the counter will then be at least 2.5, and any vehicles that arrived at the front of the queue at time 2 or earlier can be considered in the next decision about which vehicle crosses the intersection. The simulation proceeds step by step, keeping track of the simulation clock and the time that each vehicle crossed the intersection.

When the last simulated vehicle is through the intersection, your program should output the following report:

This report should be printed out to stdout as well as written to a file called report.txt. It should be formatted to be easily readable and so that the different elements of the report are clearly distinguishable from one another.