Due: Monday, February 27, 2017, 11:59 pm

Spatial Simulation: Parking Cars

The main purpose of this project is to use stacks to simulate the arrangement of cars in a parking garage. The simulated garage is modeled after Stephanie's favorite parking garage in Boston and is designed to maximize the number of cars that can park - not to facilitate easy movement of cars. Cars are parked in lanes, such that the first car in lanes have many cars parked behind it. It will need to be the last one out. In other words, each lane is a stack. The simulation of the parking garage will have 3 stacks representing 3 parking lanes. It will also have a 4th stack, representing a temporary parking lane (we will call it a holding area). This way, if a driver is demanding their car, the attendant can put all the cars behind it into the temporary lane, remove the driver's car, then put the other back in the lane.

Tasks

1. Car: create a Car object to represents a car that is being parked or moved around in a parking garage. The Car class is modeled after the Cell class from the previous project, but it will not have an updateState method and the alive field -- cars are passive agents. The corresponding getAlive and setAlive are gone too. The Car class should store its color, store the time it wants to be retrieved from the garage (an int that indicates at which time step it should be removed), and implement the following methods.
   • public Car(int timeToLeave) a constructor method. The parameter, timeToLeave, indicates at which timestep the car should be retrieved from the garage. By default, the car is red.
   • public Car(int timeToLeave, Color color) another constructor method.
   • public int getTimeToLeave() the accessor that returns the time at which the car should leave.
   • public String toString() returns a string that indicates the color and time the car will be retrieved from the garage.

   Implement the above methods and test them with a main method.

2. CarStack: create a CarStack class to store a stack of Cars, modeling after IntStack. It should store the index of the top of the stack, an array of Cars, and implement the following methods:
   • public CarStack( ) a constructor method. Make an array of 10 Cars and initialize the top index to be 0.
   • public void push( Car new_item ) pushes a new item onto the stack.
   • public Car pop() pops an item off the stack and returns it.
   • public Car elementAt( int index ) returns the element at the given position (do not modify the stack).
   • public int size() returns the number of items in the stack.
   • public boolean isEmpty() returns true if the stack is empty.

   Implement the above methods and test them with a main method.

3. ParkingGarage: create a ParkingGarage class to store lanes (stacks) of Cars. The ParkingGarage class is modeled after the Landscape class from the previous project, but, instead of having a simple advance method, has specific methods to park and unpark cars. The ParkingGarage is a smart object in that the logic for moving around cars belongs in its methods. Think of the ParkingGarage as indirectly simulating the parking attendants. It should have fields to store the lanes (an array of CarStacks), the holding area (a CarStack), and the maximum number of cars in any lane, including the holding area (an int). Start by implementing these methods:
   • public ParkingGarage( int numLanes, int maxLaneSize ) initializes numLanes CarStacks to act as lanes, a holding area, and sets the maximum lane size.
   • public int getNumLanes() returns the number of lanes in the garage (not including the holding area).
   • public int getMaxLaneSize() returns the maximum number of cars that will fit in each lane.
   • public boolean parkCar( Car car ). If there is a lane with an available spot, then park the car in that spot and return true. Otherwise, return false. It is up to you to determine a strategy for finding a spot. You may want to fill in the cars one lane at a time or you may want to cycle through the lanes. At this point, your strategy should not ask Car what time it wants to leave.

     Note that the CarStack object does not have a maximum size. It is up to the code in parkCar to enforce the maximum lane size. A lane is full is the CarStack's size is equal to max lane size.

   • public String toString() returns a string indicating how many cars are currently in the holding area, along with how many cars are parked in each lane.

   Implement the above methods and test them with a main method.

4. Make it possible to visualize your ParkingGarage.
   1. Copy LandscapeDisplay.java from last week, making ParkingGarageDisplay.java. Update it so that it stores a ParkingGarage instead of a Landscape.
   2. Add a method to your Car class: public void draw(Graphics g, int x, int y, int w, int h) draws a car in the rectangle that is rooted at (x,y) and has width w, and height h. Be sure to use the color field of the Car to set the color.
   3. Add a method to your ParkingGarage class: public void draw(Graphics g, int scale)draws the parking garage at the given scale. Use information about the location of each lane to determine the location of each car. At a minimum, this should draw the set of parking lanes. It could also include the holding area, but that may not be interesting (spoiler: the holding area is emptied at the end of every time step, so there will be nothing to draw).

   Test your visualization by running ParkingGarageDisplay as your main program. You will need to update the main program to create new Cars, create a ParkingGarage, and park the cars.

5. Add a method to the ParkingGarage class: public void retrieveCar( Car car ) removes the car from the lane its is parked in. If there are cars behind it, move those cars into the holding area, then remove the car, then put the others back into the lane.

   Test the method by adding code to your main method in LandscapeDisplay. Display a full garage, then display one with one of the cars removed. Note that you can create, park, and remove a car with the following code

       Car c1 = new Car( 10, new Color( 1.0f, 0.0f, 0.0f ) );
       Car c2 = new Car( 3, new Color( 0.0f, 1.0f, 0.0f ));
       parkingGarage.parkCar( c1 );
       parkingGarage.parkCar( c2 );
       parkingGarage.retrieveCar( c1 );
   

6. ParkingSimulation: create a class that will simulate Cars being parked an retrieved. This class will be modeled after LifeSimulation, but will have more logic in it.

   Implement a method public void run(double probabilityToPark, int timestep) that runs a simulation. At each time step, at most two new cars are parked, each with proability probabilityToPark (i.e. at each time step, 0, 1, or 2 cars will drive into the ParkingGarage to be parked).

   The simulation will need to generate new cars, park them, and ask for them to be retrieved. That means that whenever a new car is parked, the simulation can't lose its reference to it. It will need to maintain a master list of parked cars. On each time step, it should cycle through that list, and check its timeToLeave. If it is time for that car to be retrieved, then the simulation should retrieve the car and remove it from the master list.

   The outline of the simulation is:

   • Initialize your variables. You will need a ParkingGarage (with 3 lanes and a maximum of 10 cars in each lane), a random number generator (Random gen = new Random();), a ParkingGarageDisplay (I used a scale of 20), a master list of cars (an ArrayList<Car>), a list of cars that have been retrieved (an ArrayList<Car>), the number of cars who failed to park, and the number of cars who tried to park.
   • Loop over the time steps. For each time step
     • Loop twice
       • If a randomly chosen value between 0.0 and 1.0 (use nextFloat()) is less than the probabilitytoPark, then
         • Generate a new Car with a randomly chosen timeToLeave value between current time step (which I have called i) and 100 time steps after i and with a randomly chosen color:

         	Car c = new Car( i + 1 + gen.nextInt(100), 
                            new Color( gen.nextFloat(), 
                            gen.nextFloat(), 
                            gen.nextFloat() ) );
         

         • Increment the counter associated with the number of cars that have tried to park.
         • Park the car in the garage. If it is successful, add that car to the master list. If not, increment the counter associated with cars that fail to park
     • Loop through the cars in the master list, to see if any of them need to be retrieved. If a car's timeToLeave value matches the current time step, then ask the garage to retrieve the car, and remove the car from the master list. But be careful how you do this. If you try to modify a list while you are looping through it using an iterator, then Java will object.

       Here is an example with an ArrayList of Integers. Our goal is to loop through the list and remove all the 3's as we go. There are two options shown. The first works. The second will throw a java.util.ConcurrentModificationException.

       ArrayList<Integer> a = new ArrayList<Integer>();
       a.add( 3 );
       a.add( 1 );
       a.add( 2 );
       a.add( 3 );
       a.add( 3 );
       a.add( 4 );
       a.add( 3 );
       
       // Option 1 - use indices directly
       for (int idx = 0; idx < a.size(); idx++) {
           if (a.get(idx) == 3) {
               a.remove(idx);
               idx--;
           }
       }
       
       // Option 2 (doesn't work) - use an iterator
       for (Integer int_obj: a) {
           if (int_obj == 3) {
               a.remove( int_obj ); // can't modify list as you iterate through it.
           }
       }
       

     • Repaint the display, save the image, and make the thread sleep
   • Finally, print out the statistics (the number of cars that tried to park and the number of cars that failed to park.)
   • Test your code by trying to park a small number of cars. E.g. set the probabilityToPark to 0.5 and tiemstep to 10. This will park about 0 to 20 cars. See whether your code works correctly.

Extensions

1. Compute and report additional information. For example, it would be interesting to know how many times cars need to be placed in the holding area.
2. Develop more than one parking strategy and compare their performance. The best performance will use the holding area for the fewest number of cars.
3. Develop a parking strategy that asks each Car what time it wants to leave. Will it outperform "blind" strategies?
4. For any assignment, a good extension will be to implement a Java class yourself and demonstrate that it has the same functionality as the Java class. For example, you could implement your own ArrayList class for this assignment.

Writeup

Your writeup should have a simple format.

• A brief description of the overall task, in your own words.
• An explanation of your solution, focusing on the interesting bits. In this assignment, for example, parking cars, retrieving cars, and the overall simulation are the interesting bits. You can include code snippets in your writeup to help describe your solution. A code snippet is usually less than 10 lines of code.
• Printouts, pictures, or results to show what you did. For this assignment, you should include an animated gif of at least one simulation and the statistics mentioned in the task instructions.
• Other results to demonstrate extensions you undertook. If you tried different parking strategies, for example, show how those affected the overall simulation results.
• A brief conclusion and description of what you learned.
• A list of people you worked with, including TAs, and instructors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester.

To check whether you've made your summary clear, you may ask yourself the following questions:

• Does it describe the CS purpose of the project?
• Does it describe the specific project application?
• Does it describe the solution or how it was developed?
• Does it describe the results or outputs?
• Is it concise?
• Are all of the terms well-defined?
• Does it read logically and in the proper order?

Handin

Make your writeup for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.

Once you have written up your assignment, give the page the label:

cs231s17project3

You can give any wiki page a label using the label field at the bottom of the page. The label is different from the title.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it in your folder on the Courses fileserver. Create a directory for each project inside the private folder inside your username folder.

© 2017 Ying Li. Page last modified: .