[SOLVED] Csci 1933 project 1 to 5 solutions

Battleboat is a probability-based boardgame that challenges the user to locate enemy boats hidden
on a rectangular grid. The purpose of the game is to locate and destroy every enemy boat in the
least number of guesses.
You will be modelling this game in Java. You must implement every part of the description
below. This means you must follow and specified modifiers and signatures exactly as
they are specified. Examples of changes that could lose you points: changing a variable to public
when it is listed as private, changing the return type of a function, etc.
Your code will also be judged based on style. This should not be a stressful requirement – it simply
means that you must create logically organized, well-named and well-commented code so the TAs
can grade it.
IMPORTANT: You cannot import anything to help you complete this project. The only
exception is importing Scanner to handle the I/O. Note that you do not have to explicitly
import Math because Java already does it for you. In other words, you can use Math methods
without importing Math
Note: Writing useful helper methods for the functions listed above is allowed and encouraged!
Remember part of your grade comes from style and readability of the code you write.
Note: You will find it useful to write your own tests to prove to yourself that your code
works. Please include any test classes you write with your submission.
1 Cell Class
The Battleboats game board is composed of many cells. You are required to create a Cell class
that contains the following private attributes:
• private int row: indicates the row value of the Cell
• private int col: indicates the column value of the Cell
• private char status: character indicating the status of the Cell. There are four different
possibilities for this field:
2
PROJECT 1 2. BATTLEBOAT CLASS
Character Conditions
’ ’ (space) Has not been guessed, no boat present
’B’ Has not been guessed, boat present
’H’ Has been guessed, boat present
’M’ Has been guessed, no boat present
In addition, you are required to implement the following functions:
• public char get_status(): getter method for status attribute
• public void set_status(char c): setter method for status attribute
• public Cell(int row, int col, char status): Cell class constructor
2 Battleboat Class
A Battleboat object will have the following attributes:
• private int size: indicates the number of Cell objects a Battleboat spans. Default this
value to 3
• private boolean orientation: indicates the orientation of the Battleboat (horizontal or
vertical, can be randomly decided)
• private Cell[] spaces: array of the Cell objects associated with the Battleboat
And the following functions:
• public boolean get_orientation(): getter method for orientation attribute
• public boolean get_size(): setter method for size attribute
• public boolean get_spaces(): setter method for spaces attribute
• public Battleboat(): Battleboat class constructor
Hint: To generate random numbers, the Math.random() method can be used. However, this
method returns a double in the range 0 to 1. We will need to scale this and then round it to
a whole. To do this, use the Math.floor(x) function, which takes a double x and rounds
it down to the nearest integer. For example, Math.floor(2.9) is 2.
3 PROJECT 1 3. BOARD CLASS
3 Board Class
The computer will simulate a rectangular m × n board. A Board object will contain the following:
• private int num_rows: indicates the number of rows a Board has
• private int num_columns: indicates the number of columns a Board has
• private int num_boats: indicates the number of Battleboat objects a Board has
• private Battleboat[] boats: array of all the Battleboat objects associated with a Board
object
• private Cell[][] board: 2-dimensional Cell array required to represent the Board
• private boolean debugMode: flag to indicate if Board should be printed in debugMode
The minimum Board size is 3 × 3 and the maximum is 12 × 12. Assume that the points in the
Board range from (0, 0) to (m − 1, n − 1) inclusive.
Each boat is represented by a line of consecutive squares on the board. Boats may not overlap
other boats, extend outside the game board, or be placed diagonally. They may be horizontal or
vertical. A boat is considered “sunk” when all the squares of the boat have been “hit” by the user.
Examples: Valid coordinates for a boat of size 3 are {(0, 0),(0, 1),(0, 2)} and
{(1, 1),(2, 1),(3, 1)}. Examples of invalid coordinates are {(0, 0),(0, 1)}, which is invalid
because there are not enough points. {(0, 0),(0, 2),(0, 3)} is invalid because the points are
not consecutive. {(−1, 0),(0, 0),(1, 0)} is invalid because the first coordinate is out of bounds.
Finally, two boats cannot contain the same point because they cannot overlap.
After the gameboard has been sized, the program should place boats randomly on the
board. This requires randomly generating a coordinate (x, y) where the boat will be placed as well
as randomly choosing whether the boat should be horizontal or vertical. The quantity of boats is
defined by the width and height of the game board. As mentioned prior, all boats should be of
length 3. Recall the smallestBoardis 3 × 3 and the largestBoardis 12 × 12.
Smallest Dimension Boat Quantity
width == 3 or height == 3 1
3 < width <= 5 or 3 < height <= 5 2
5 < width <= 7 or 5 < height <= 7 3
7 < width <= 9 or 7 < height <= 9 4
9 < width <= 12 or 9 < height <= 12 6
4
Use the table above to determine how many boats to place. Recall that the Board may be rectangular, so a Board that is 9 × 3 should have just one boat of length 3 (the first case). The user
should be told how many boats are on the Board when the game begins.
Hint: To randomly place a boat, consider the coordinate in the upper left. If the upper left
corner was (0, 0), consider how the boat looks if it is horizontal or vertical. What upper left
corner coordinates are invalid? The placing of the boats may be the most challenging aspect
of this project: see what assumptions you can make to simplify it.
Required functions:
• public Board(int m , int n, boolean debugMode): constructor for theBoardclass. This
method should assign appropriate number of boats to num_boats variable, initialize theBoard
as a 2-D Cell array, initialize boats as a Battleboat array, place Battleboat objects appropriately on the Board, and add them to the board’s boats
• public int guess(int r, int c): returns an int based on the guess for the cell. The
statuses of the Cell must also be changed according reflect the statuses from the table in the
Cell class portion of this writeup
• public int unsunkBoats(): calculates the number of unsunk boats on the Board
4 The main method and debug mode
A main method is provided to you in the Game class which will run the game once all the functions
are implemented as specified. If the debugMode flag is set to false, the view of the board will be
obscured during play so that the player only sees the spots they have already guessed. Setting
debugMode to true may be helpful to you while debugging and testing your code.
5

Introduction In this project you are going to implement a list [1] interface to construct your own ArrayList data structure. Using this you will construct an ElephantHerd to hold a family of elephants [2]. [1]. Lists: A List is a list of ordered items that can also contain duplicates. In Java, lists are constructed either using an array or linked list data structure. The implementations for each have certain pros and cons with respect to cost of space and runtime. In this project, you will implement lists using only an array data structure from a custom List interface. [2]. Inheritance: Interface: Interfaces are an important aspect of inheritance in Object Oriented Programming. All methods defined in an Interface are un-implemented and required to be implemented by an inheriting class. In Java an Interface class is inherited by other classes using the keyword implements. See the example code below. 1 List: An interface A List must consist of specific methods irrespective of underlying data structure. These methods are defined as part of an interface that you are required to inherit in your array list and linked list implementations. Refer to List.java for methods and their definitions. Note that methods have generic types∗ and you are required to implement your inherited classes as generic types too (continue reading to see what it means…). ∗A generic type is a generic class or interface that is parameterized over types. In the context of List, T is the type of the object that is in the list, and note that T extends Comparable. 3 CSCI 1933 PROJECT 2  Inheritance Java Example: // An interface. interface IName { public void printName(); } // This class implements the Name interface. class PeopleName implements IName { String firstName; String secondName; // Need to implement printName(). public void printName() { System.out.println(this.firstName + ” ” + this.secondName); } } 1.1 Array List Implementation The first part of this project will be to implement an array list. Create a class ArrayList that implements all the methods in List interface. Recall that to implement the List interface and use the generic compatibility with your code, ArrayList should have following structure: public class ArrayList> implements List { … } The underlying structure of an array list is (obviously) an array. This means you will have an instance variable that is an array. Since our implementation is generic, the type of this array will be T[]. Due to Java’s implementation of generics† , you CANNOT simply create a generic array with: T[] a = new T[size]; Rather, you have to create a Comparable (since T extends Comparable) ‡ array and cast it to an array of type T. T[] a = (T[]) new Comparable[size]; Your ArrayList class should have a single constructor: public ArrayList() { … } that initializes the underlying array to a length of 2. † specifically because of type erasure ‡had T not extended Comparable, you would say T[] a = (T[])new Object[size]; 4 CSCI 1933 PROJECT 2 Due: Wednesday, February 28th 2018 Implementation Details • In addition to the methods described in the List interface, the ArrayList class should contain a private class variable isSorted. This should be initialized to true in the constructor (because it is sorted if it has no elements) and updated when the list is sorted, or more elements are added or set. For the purposes of this class, isSorted is only true if the list is sorted in ascending order. • When the underlying array becomes full, both add methods will automatically add more space by creating a new array that is twice the length of the original array, copying over everything from the original array to the new array, and finally setting the instance variable to the new array. Hint: You may find it useful to write a separate private method that does the growing and copying • When calling either remove method, the underlying array should no longer have that spot. For example, if the array was [“hi”, “bye”, “hello”, “okay”, …] and you called remove with index 1, the array would be [“hi”, “hello”, “okay”, …]. Basically, the only null elements of the array should be after all the data. • Initially and after a call to clear(), the size method should return 0. The “size” refers to the number of elements in the list , NOT the length of the array. After a call to clear(), the underlying array should be reset to a length of 2 as in the constructor. After you have implemented your ArrayList class, include junit tests that test all functionality. 5 CSCI 1933 PROJECT 2  2 An Elephant Herd You will use array list and linked list implementations to now construct a herd of elephants. Elephants have a name, age and height. You will use the ArrayList data structure to construct this Elephant Herd. You are provided with Elephant.java which implements Comparable (Refer to the Elephant.java file for details) which is a class with three properties: name, age, and height, setters and getters, a compareTo() and a toString() method. 2.1 The Herd Create a class ElephantHerd. To create this herd you will use your ArrayList class as the underlying object list. The type for the object in the list will be Elephant. Your ElephantHerd should include the following methods: • private List list – Your underlying list of Elephants. • public ElephantHerd() – This constructor will initialize the underlying list. • public boolean add(Elephant ellie) – This will add ellie to the end of the list and return true if successful, false otherwise. • public Elephant find(String name) – This will try to find an elephant with name field that contains name. Note that the name need not be exactly the same as the name of elephant. You can use the built in String method public boolean contains(String anotherString ) § . Return null if no Elephant was found. • public Elephant remove(int index) – This will remove the elephant object currently at index index, if index is out of bounds, return null. • public void sort() – This will sort the list in order of height, from tallest to shortest. Note that you cannot just use the ArrayList sort method that you wrote earlier, because that method sorts based on the results of compareTo(), not on the basis of height. • public Elephant[] getTopKLargestElephants(int k) – This will return an array of length k containing the top-k elephants sorted by their height, from tallest to shortest. If the list is empty, return null. If the number of elephants (M) in the list is smaller than k, then return an array of length M. After you have implemented your ElephantHerd class, write junit tests that test all functionality. §The actual signature of contains is public boolean contains(CharSequence s) but you don’t have to worry about that 6 CSCI 1933 PROJECT 2 3 File Input Now that you have created your ElephantHerd, it is time to make a convenient way to input the data for the herd. You will do this by creating an ElephantReader class which will be able to read data from a file into an ElephantHerd object and to write data from the herd to a file. To do this, you will need to import File, Scanner, and PrintWriter. These are the only imports allowed. To read the data, you will create a File object, and then use a Scanner to parse the data. The following code gives examples of how to read and write to files called “fileName”. // assume our filename is stored in the string fileName Scanner s = null; // declare s outside try-catch block try { s = new Scanner(new File(fileName)); } catch (Exception e) { // returns false if fails to find fileName return false; } // Now use s in the same way we used Scanners previously for user input to write to an arbitrary textfile, do the following: // assume our filename is stored in the string fileName PrintWriter p = null; // declare p outside try-catch block try { p = new PrintWriter(new File(fileName)); } catch (Exception e) { return false; } At this point, it is not critical that you understand exactly how the try/catch block works, but know that the contents of the “try” portion are what could throw an Exception, while the contents of the “catch” block are what you want the program to do if the Exception is thrown. This class only contains two method: • public static boolean readElephants(ElephantHerd e, String fileName) – This method removes all previous elephants in e and replaces them with elephants from the file of the given name. If there is an error, or e is null, return false. Otherwise, return true. You can assume that the file is formatted such that there is data for one elephant per line. The data will be in the form of “name age height”. An example text file is provided for testing. • public static boolean writeElephants(ElephantHerd e, String fileName) – This method will write all elements of e to a file of the given name. If there is an error, or e is null or 7 CSCI 1933 PROJECT 2  empty, return false. Otherwise, return true. The file should be written using the toString function in List. This should give the same format as the file being read, so a written file can be reloaded later. 4 Iterators (Honors) Note: This section is **required** for students in Honors section only. Optional for others but no extra credit. An iterator is an object that traverses a list, going through each element exactly once. This section will require you to write another class, and to make modifications to the ArrayList class. You will write a ArrayListIterator class which will iterate over a list. This iterator should implement java’s iterator interface in addition to the List interface. Make sure to import java.util.Iterator. This class will have two functions and a constructor. It will also need class variables to store a pointer to its ArrayList and the current index. 1. ArrayListIterator(ArrayList a) – the constructor. This constructor will never be directly called by the user. Instead, it will be called in the iterator() function in the ArrayList class. 2. hasNext() – This will return true if there is another object to iterate on, and false otherwise. 3. next() – This will return the next object if there is one, and null otherwise. The first line of the ArrayListIterator class should be as follows: private class ArrayListIterator implements Iterator, List Note that in order for a class to be private, it must be in the same document as another class, and within the curly braces of that class. This means that ArrayListIterator should be in the ArrayList.java file, and should be in the curly braces of ArrayList, with the methods of ArrayList. You will also need to make some modification to the ArrayList class. First, the class now needs to implement Iterable. public class ArrayList> implements Iterable, List Secondly, you will need to add the method public Iterator iterator(). This method should 8 return an ArrayListIterator object by calling the ArrayListIterator constructor and passing itself to the constructor (via the this keyword). Make sure to create junit tests to ensure that your iterator functions as desired. Example code using the iterator is provided below: Iterator Example: // the main method of a class using the ArrayListIterator ArrayList arr = new ArrayList(); arr.add(‘‘hello”); arr.add(‘‘how”); arr.add(‘‘are”); arr.add(‘‘you?”); Iterator it = arr.iterator(); System.out.println(it.next()); //prints ‘‘hello” System.out.println(it.hasNext())); //prints true while (it.hasNext()) { System.out.print(it.next()); //prints ”how are you?” } 9

IMPORTANT: This project utilizes similar concepts and java skills to Project 2. For brevity, this write-up omits discussions of generics and interfaces. For more information, see the instructions for Project 2. In this project you are going to implement a list [1] interface to construct your own LinkedList data structure. Using this you will construct an ElephantHerd to hold a family of elephants [2]. 1.1 LinkedList Implementation The first part of this project will be to implement a linked list. Create a class LinkedList that implements all the methods in List interface. Recall that to implement the List interface and use the generic compatibility with your code, LinkedList should have following structure: public class LinkedList> implements List { … } The underlying structure of a linked list is a node. This means you will have an instance variable that is the first node of the list. The provided Node.java contains a generic node class that you will use for your linked list implementation∗ . Your LinkedList class should have a single constructor: public LinkedList() { … } that initializes the list to an empty list. Implementation Details • In addition to the methods described in the List interface, the LinkedList class should contain a private class variable isSorted. This should be initialized to true in the constructor (because it is sorted if it has no elements) and updated when the list is sorted, or more elements ∗ You may implement your linked list as a headed list, i.e., the first node in the list is a ‘dummy’ node and the second node is the first element of the list, or a non-headed list, i.e., the first node is the first element of the list. Depending on how you choose to implement your list, there will be some small nuances. 3 CSCI 1933 PROJECT 3 are added or set. For the purposes of this class, isSorted is only true if the list is sorted in ascending order. • Initially and after a call to clear(), the size should be zero and your list should be empty. • In sort(), do not use an array or ArrayList to sort the elements. You are required to sort the values using only the linked list data structure. You can move nodes or swap values but you cannot use an array to store values while sorting. • Depending on your implementation, remember that after sorting, the former first node may not be the current first node. After you have implemented your LinkedList class, include junit tests that test all functionality. 2 An Elephant Herd Slightly modify your class ElephantHerd from Project 2 to use an underlying LinkedList rather than an ArrayList. Then verify that the methods still work as intended. If you did the previous project correctly, this step should only require the modification of one line of code. 3 Analysis Now that you have implemented and used both an array list and linked list, which one is better? Which methods in List are more efficient for each implementation? For each of the 13 methods in List, compare the runtime (Big-O) for each method and implementation. Ignore any increased efficiency caused by the flag isSorted. Include an analysis.txt or analysis.pdf with your submission structured as follows: Method ArrayList Runtime LinkedList Runtime Explanation boolean add(T element) O(…) O(…) … boolean add(int index, T element) O(…) O(…) … . . . . . . . . . . . . Your explanation for each method only needs to be a couple sentences briefly justifying your runtimes. 4 CSCI 1933 PROJECT 3  4 Iterators (Honors) Note: This section is **required** for students in Honors section only. Optional for others but no extra credit. Much like in Project 2, you will create an iterator for the LinkedList class. This section will require you to write another class, and to make modifications to the LinkedList class. You will write a LinkedListIterator class which will iterate over a list. This iterator should implement java’s iterator interface in addition to the List interface. Make sure to import java.util.Iterator. This class will have two functions and a constructor. It will also need class variables to store a pointer to its LinkedList and the current index. 1. LinkedListIterator(LinkedList a) – the constructor. This constructor will never be directly called by the user. Instead, it will be called in the iterator() function in the LinkedList class. 2. hasNext() – This will return true if there is another object to iterate on, and false otherwise. 3. next() – This will return the next object if there is one, and null otherwise. The first line of the LinkedListIterator class should be as follows: private class LinkedListIterator> implements Iterator Note that in order for a class to be private, it must be in the same document as another class, and within the curly braces of that class. This means that LinkedListIterator should be in the LinkedList.java file, and should be in the curly braces of LinkedList, with the methods of LinkedList. You will also need to make some modification to the LinkedList class. First, the class now needs to implement Iterable. public class LinkedList> implements Iterable, List Secondly, you will need to add the method public Iterator iterator(). This method should return a LinkedListIterator object by calling the LinkedListIterator constructor and passing itself to the constructor (via the this keyword). Make sure to create junit tests to ensure that your iterator functions as desired. 5

Introduction
Suppose the popularity of a bus route has increased and now the customers are complaining about
longer waits and full buses. In order to keep ridership up, the bus company has decided to run
a simulation to help figure out whether they should add more buses along this route or buy
larger buses for the route.
The company wants to minimize the average travel time (wait time + ride time). However, they
also want to maximize the Passenger Miles Per Gallon (PMPG). The PMPG is calculated by
multiplying the Miles Per Gallon of the bus by the Average Occupancy of the vehicle. Normal
Buses run at 6MPG and hold 40 passengers, while Extended Buses run at 4MPG and hold 60
passengers. In the case that both these buses are run at full capacity all the time they have the
same PMPG; however, in practice they may not be run at full capacity (to reduce wait time). You
are tasked to create the simulation and return a report with your findings.
The Car Wash example that we “acted out” in lecture has many parallels to this project. You may
find it helpful to use some of the code for the Car Wash example in your simulation project, and
that is O.K. Specifically, you should use the priority queue (PQ.java) as-is. Be sure to credit any
code “borrowed” from the posted lecture examples.
Setup
We will assume the following adjustable system parameters:
• A variable number of buses.
• Bus lengths, i.e. you may have a mix of larger and normal sized buses.
3
CSCI 1933 PROJECT 4 SETUP
• A variable average inter-arrival rate of passengers at each stop (this will be referred to as the
load).
We will assume the following constraints:
• Passengers will be passive, but they will contain data such as:
– Time they arrived at the stop
– Destination/stop they want to go to
– Direction of the stop they want to go to (eastbound or westbound)
• Arrival of a passenger at a stop will be provided by an arrival class that will generate arrivals
for all the stops (determined statistically, see below)
• Wait/travel time will be determined by arrival time and passenger count (see below)
• If a passenger cannot get onto the bus (when the bus is full) they must wait for the next one
Simulation of the system is achieved by creating classes to model the behavior of each element
of the system as well as each activity (event) that occurs in the system. There is NOT an
overall controller that calls for actions to happen at particular times except for a main driver loop
that runs queued events until time runs out. Each element in the system models its own behavior
and interactions with other elements in the system. Each NON-passive element class has an Event
class associated with it. The associated event defines a run() method (as discussed in lecture) that
simulates the specific behavior of that event.
Some of the classes that we will want are:
• Bus Stops (Stop) – contains Passenger queues
• Agenda (PQ)
• Event – an interface for all our events
• BusEvent – occurs each time a Bus arrives at a stop
• PassengerEvent – one occurs for each Passenger arriving at a stop
Let’s look at each of these components, and see what they should contain. Please note that you
may need to include other information, but what is given here is considered fundamental.
PassengerEvent
This is instantiable once for each Passenger creation event. One PassengerEvent will be made for
each stop, allowing you to have some stops that are more popular than others. This will implement
the Event interface similar to how the CarMaker class was implemented as described in lecture.
PassengerEvent will reschedule itself (using the agenda), create a Passenger, decide where they
want to go on the route, which direction that is from the current stop, and place the Passenger in
the appropriate queue at the current stop.
4
CSCI 1933 PROJECT 4 SETUP
Stop
This is instantiable once for each stop on the route. Each Stop will have two queues associated
with it (one for eastbound passengers and one for westbound passengers), and a name to designate
which stop it is on the route.
Info: University Ave and 27th Street SE and Union Depot each only need to have one
queue, since passengers who arrive at those stops cannot go further east or west, respectively.
There are exactly 10 bus stops:
• University Ave and 27th Street SE
• Raymond Ave Station
• University Ave and Fairview Ave
• University Ave and Snelling Ave
• University Ave and Lexington Parkway
• University Ave and Dale Street
• University Ave and Marion Street
• Cedar Street and 5th Street
• Minnesota Street and 4th Street
• Union Depot
BusEvent
This implements the Event interface. A BusEvent is created for every arrival of a bus at a stop.
When a bus arrives at a stop, the BusEvent causes the bus associated with it to look at its passenger
list to see if there are passengers that wish to exit the bus. If there are, the bus removes those
passengers. The BusEvent will then look at passengers at the Stop that want to go the direction
the bus is going and put as many of them as possible on itself. Finally, the BusEvent will create
a new BusEvent and schedule it (via the agenda) for the arrival at the next stop at a time in the
future depending on the number of passengers that got off and got on. If the Bus has reached the
last stop on either side, it will start going the other direction. For example, if an eastbound bus
arrives at the Union Depot Stop, it will then leave the Union Depot Stop going westbound.
PQ
This is the priority queue (likely to be called the agenda within your code). This code is provided.
You will need one instance of it. This one instance will be used to schedule all events for your
simulation.
5
CSCI 1933 PROJECT 4 SETUP
Statistics
You will want to keep track of relevant Statistics such as:
• How full each bus is
• The maximum time a passenger spends waiting at a stop
• The maximum queue length at a stop
• etc.
Randomness
You will need to use a random distribution to model the arrival of Passengers at each stop. This
is determined by method calls made in the run() method for the PassengerEvent. You will also
need to randomly generate which stop each Passenger wants to go to.
For the arrival of passengers at a stop, you should start with an average inter-arrival rate of 1
Passenger every 120 seconds. But, you will want to run your model with both higher and lower
demand by decreasing and increasing this inter-arrival time. To more realistically represent the
pattern of arrival of Passengers, we will introduce some randomness according to the table below
(calculations shown using a 120 second inter-arrival time as an example):
• 10% of the time: 75% above average arrival interval (120 + 0.75 × 120)
• 15% of the time: 50% above average arrival interval (120 + 0.50 × 120)
• 20% of the time: 20% above average arrival interval (120 + 0.20 × 120)
• 10% of the time: right at average arrival interval (120)
• 20% of the time: 20% below average arrival interval (120 − 0.20 × 120)
• 15% of the time: 50% below average arrival interval (120 − 0.50 × 120)
• 10% of the time: 75% below average arrival interval (120 − 0.75 × 120)
Downtown stops (listed below) are more popular than others, therefore, at these stops passengers
should arrive 50 percent more frequently than at normal stops. They are also *two* times as likely
to be a destination for a passenger than another stop.
Of the 10 stops, there are 3 downtown stops (Cedar Street and 5th Street, Minnesota Street and
4th Street, and Union Depot), and 7 normal stops (those not listed in the downtown category). If
we sum the weight (likelihood) of each stop, we get 13 (2 × 3 + 1 × 7). This means each downtown
stop has a 2/13 chance of being chosen, and each other stop has a 1/13 chance of being chosen.
Determining processing time
To determine the amount of time a bus will take between stops, we use these rules:
6
CSCI 1933 PROJECT 4 WHAT TO DO
• A bus will take 3 minutes (180 seconds) between each stop
• A bus will wait for at least 15 seconds at each stop
• It takes a passenger 2 seconds to get off and 3 second to get on
Therefore, a bus will take at least 3 minutes and 15 seconds to get from one stop to another. If
the time it takes passengers to get on and get off is larger than 15 seconds, it will take 3 minutes
plus the amount of time it took for passengers to get on and off. Even though each stop isn’t the
same distance from the next one, the times between each stop has been simplified to make the
calculation easier.
Assumptions
• Assume that passenger arrival distribution and destination stop will use the distributions
given.
• Assume that the maximum number of buses is 18 (one for each stop going each direction)
– Buses at University Ave and 27th Street SE and Union Depot cannot go any further east and west respectively. Consequently, there can only be at most 18 buses running
at a given time.
• Use the rules above for calculating the amount of time between each stop for a train.
Variables
• Load: the average inter-arrival rate of passengers
• Number of buses (1-18, this can also be considered the frequency of buses)
• Bus Size
What to do
First, get the simulation system to work, but start small and verify each feature works before
proceeding to the next one. Then, produce a detailed report that gives a convincing presentation
for what the bus company needs to do to satisfy its customers while maximizing their fuel economy.
In order to provide a convincing argument, you will need to collect good statistics, verify them,
and present them in a clear manner.
Something to watch for and correct when you run your simulations….If left unchecked, the busses
will tend to clump together and even pass each other in situations where there are not a lot of
busses in the system. This is a problem because busses that are clumped together will not serve
evenly the potential riders at some stops. You should check to see if clumping is happening. If it
is, try to incorporate something into the Bus class to keep a bus from getting to close to the bus
in front of it. In the real world, a bus will hang out at a stop if the driver can see another bus
7
CSCI 1933 PROJECT 4 WHAT TO DO
ahead of it less than two stops away. We recommend that you first determine whether clumping
is happening and prove it with some output from your simulator. Then, build in some code into
your Bus class to slow down busses that are getting too close to the bus ahead of it. Note that this
will only make sense when the number of busses is fewer than about one half the number of stops
in each direction.
The problem is purposely vague so that you can decide what statistics you need to gather and
what simulation tests you should run. But, you need to present enough information so that the
bus company can decide how many buses and what bus size it needs for various loads. (Keep in
mind that the bus company will want statistics for the busy times (lunch and rush hour) and well
as off-peak times such as weekends and nights. A significant portion of the grading will be based on
the write-up of your results which will include your simulation results presented in a useful format,
conclusions and recommendations. This means that you will need to have a working simulator in
order to have results to write about.
8
CSCI 1933 PROJECT 4 THE WRITE-UP
The Write-up
The write-up must be submitted as a .pdf document along with the rest of your source code. 25%
of your project grade will be somehow connected to the write-up. When deciding on statistics to
maintain and the simulations to run, think about the need to support your conclusions in your
write-up. The write-up should be in the form of a report–such as a consulting report–that you
might submit to the bus company. The report should include data (such as average travel time
and passenger miles per gallon) summarized in a concise and readable fashion along with specific
data that proves that the simulation results are correct. Please be sure that the report is concise.
For example, do the numbers make sense? Are your simulation runs at equilibrium? (That is,
as you run the same model with the same parameters for longer times, do the stats tend to stay
constant?) Certainly, some statistics are more difficult to properly calculate than others. So, don’t
try to do it all at once. Get some stats going, and verify them, before moving on.
In order for this to be a successful project, you need to start NOW, and have your simulator working
about 5-7 days before the project is due. That will give you enough time to run all the tests, make
modifications and produce the report. Remember, the bus company will be interested in how many
buses and what size buses they will need for various loads, average number of passengers at each
stop, the average and maximum passenger wait times, and average travel time. You will need to
run your simulation multiple times. It will take some thinking to know what runs to make, how to
effectively present your findings and deal with, or account for, bus clumping and passing.
9
CSCI 1933 PROJECT 4 THE README
The Readme
A common expectation of large software projects is that they provide a readme file to familiarize
the user with the project. You must provide a readme file along with your project; it needs to
contain (at-least) the following items, which are often included in readme files for other projects:
• The project name and author information.
• Instructions for running your project on a new machine.
• An overview of the project organization and hierarchy.
• The data structures and algorithms used in the project, and why they are a good choice.
• Any known bugs or issues associated with the project.
As this project is largely left up to student design, the intent of this readme file is to familiarize
your TAs with your project. A good readme file will make grading the project easier, and be the
capstone on your submission.
10

BOUNDING VOLUME HIERARCHY Bounding Volume Hierarchy A bounding volume hierarchy (BVH) is an essential tool in computer graphics. It’s used in rendering, collision detection, and much more. There are different kinds of acceleration structures, but the one you’re required to implement is an Axis-Aligned Bounding Box (AABB) tree, with top-down construction. The fun thing about acceleration structures is that they make use of several fundamental techniques in Computer Science, such as trees, recursion, queues/stacks, polymorphism, and more. This is a good opportunity to make use of the skills and knowledge you’ve acquired in this course in a (hopefully) fun and interesting final project. AABB Tree Geometric objects in space are grouped together in overlapping boxes. Boxes with one object in them are the leaf nodes of a tree. Larger boxes that enclose smaller ones are parent nodes. The image below (left) shows various shapes in world space being partioned into a tree (right). Although its leaf nodes have two objects each, it illustrates the general idea. See this Wiki page for more details. How can we use this tree? Let’s say there was a screen open with the geometry of the above figure and the user wants to select the circle with a mouse by clicking on it. To see if the circle was selected, we start at the root node (A). Then, based on the coordinates of the mouse, we check which of its children the pointer is hovering over (B). We traverse to the (B) node, traverse its children (and so forth), until we reach a leaf and see if the click was in bounds of the shape. Why not just loop over all of the geometry and test them directly? Consider what happens when we have one million shapes instead of six. What about ten million? Checking if the cursor is within the bounds of a box is a lot less expensive to compute than a 15-pointed star. Using a tree to process the selection of the click will cull millions of these expensive point-in-geometry tests, making the run time of your interface significantly faster. This day and age, having to wait a few seconds to process a mouse click ends up with angry users and 1-star app ratings. We can’t have that… 3 CSCI 1933 PROJECT 5 OBJECTIVE Objective You are required to implement the primary function of building and traversing the AABB tree. Code that generates geometry, rendering, and handling mouse input is provided. The following files are on moodle: • AABBTree.java: Contains the code for generating geometry and processing graphics. You won’t have to change this file, but it might be helpful to look at and understand it. • Bounds.java: The class for an axis-aligned bounding box. You’ll need to implement this. • Circle.java: The class for a cicle, containing geometry-intersection tests and rendering. You won’t have to change this. • Node.java: The class that makes up our tree! Most of the work you will be doing is here. • Shape.java: A base class for geometry. You won’t have to change this. • Vec2.java: The class for points in space. You won’t have to change this. When running the program, a window should pop up containing a bunch of circles. Once you’ve finished your BVH implementation, clicking a circle should make it turn red. Clicking again will make it turn back to gray. For this project, you can assume that no shapes will overlap. If your tree traversal is correct, this should run in real time. That is, you won’t have to wait for the object to change colors. 4 CSCI 1933 PROJECT 5 1. AXIS-ALIGNED BOUNDING BOX Hint: It’s highly recommended to test your methods with fewer geometry than the default. In AABBTree.java there is an int max_shapes variable in main. Start by setting this to one or two when implementing your tree for the first time. 1 Axis-Aligned Bounding Box The first step is to implement the Axis-Aligned Bounding Box (AABB), found in Bounds.java. Be sure to fully test your methods. Methods marked with “TODO” are for you to complete. To get full points for this section you must implement • boolean isOutside(double x, double y): Returns true if the point (x, y) is outside the bounds of the box, false otherwise. • void extend(double x, double y): Grows the box (increases max, decreases min) to enclose the point. • void extend(Bounds b): Grows the box to enclose another box. • double exteriorDistance(double x, double y): Distance between the AABB’s surface and a point in space. If the point is inside the bounds, return 0. 2 Node Constructor Node(Stack stack, int axis) The node constructor takes a stack of shapes, a splitting plane axis, and initializes itself. The splitting plane axis is a number (0 or 1) that describes what axis on which we will do the partitioning. See §3 for more details. To get full points for this section, implement the following: • Extend the AABB to contain all shapes in the stack. • If stack size is 1, become a leaf node. • If stack size > 1, partition the stack using the splitStack method, increment the axis, and create children recursively. 5 CSCI 1933 PROJECT 5 3. SPLITTING THE STACK 3 Splitting the Stack void splitStack(Stack stack, int axis, Stack leftStack, Stack rightStack) The role of this method is to partition the stack into two new stacks (though not necessarily in half). The metric we’re using to decide the partion is the spatial median. This is simply the average centroid of all objects in the stack (for a given axis). For example, let’s say the splitting axis was 0 (x-axis) and you had two shapes, centered at (1,2) and (2,3). The spatial median is 1.5. And so, the former shape (1,2) goes on the left stack, and the latter (2,3) on the right. Do not create new shapes with the same location/radius. Make sure you are moving around the same shape object since their references are used internally by the renderer. To get full points for this section, you must: • Compute the spatial median. • Partition the stack into leftStack and rightStack based on the spatial median. 4 Shape Selection boolean select(double x, double y, int[] counter) On a left-click, the select method is used to traverse the tree and identify the shape whose boundary includes the point (x,y). It returns true if an object was selected, false otherwise. Here you will take advantage of the tree data structure to accelerate the search. That is, if the point (x,y) is outside the bounds of the node’s AABB, the point is also outside the bounds of children nodes, thus we can simply return false. Otherwise, continue searching down the tree. To get full points for this section, implement the following: • Early exiting if the point (x,y) is outside the bounds of the node. • If on a leaf, check to see if (x,y) is physically within the bounds of the shape. • Recursive traversal of the left and right children. 6 CSCI 1933 PROJECT 5 5. HONORS 5 Honors boolean nearest(double x, double y, double[] currentMin, Shape[] shapeRef, int[] counter) The nearest method is very similar to the select method from §4. Instead of selecting a shape when the (x,y) coordinate is above it, however, nearest will select the nearest shape with respect to the input point. It returns true if it found a shape closer to the point (x,y), false otherwise. This happens on a right-click. There are two more arguments to set. Note that both currentMin and shapeRef are single-element arrays. When you’ve found a candidate nearest object, in that its exterior distance to the point is the current minimum, set both currentMin[0] and shapeRef[0]. The former is that exterior distance, while the latter is a reference to shape itself. Remember that exterior distance is zero if the point is inside the shape. The other major difference between nearest and select is that you should traverse the node that is closer to the point (x,y) first. This is because it’s more likely to contain the actual nearest shape, and possibly cull future traversals! To get full points for this section, implement the following: • Early exiting if the node’s boundary is further away than the candidate nearest shape. • If on a leaf, check to see if the node holds a closer shape. If so, set the necessary references. • Recursive traversal of the left and right children. 7