CSE 143 Winter 2005

UW Home

CSE Home

Announcements

Discussion Board

Contact Info

CSE 143  Home page  Syllabus Classwork  Calendar/Lectures  Projects  Exams  Academic Conduct Staying in Touch  Mailing Lists  Discussion Board  Announcement Archive People  Instructors  TAs  Consultants  Consultant Schedule Software & Computing  Programming Lab Info  Computing at Home  Java Libraries Check Your Scores  MyUW

CSE143 Winter 2005 Project #1 Part A Traffic Jam! - A Virtual Roadway Simulation  Due: Wednesday, January 19, at 9:00 pm. No late assignments will be accepted. This is the first part of a 3-part project to create a virtual simulation of roads and vehicles. For the first part, you will implement several classes representing roads and vehicles, and programs to test them. Later parts of the project will add an event-driven graphical user interface. The project is open-ended with opportunities to earn extra credit (which will be awarded when the whole assignment is finished). You should work with your assigned partner on this project using the pair programming style discussed in class. While you may want to think about the project, sketch ideas, and try them out on the computer yourself (when your partner is not around), it works best if the two of you write the actual project together at a single computer, trading off the keyboard at least every 5 or 20 minutes. You and your partner will turn in a single set of files. After the final part of the project is done, each of you will individually individually write a final report. (Details about that will be supplied later.) Grading: When the project is complete (all 3 parts), your project will be evaluated both for how well the code works and how well it is written and tested. For the intermediate parts of the project, we will try to give you quick feedback on the scale of 0-3: 3=no major problems, 2=something needs to be fixed, 1=serious trouble, and 0=no credible effort. Be sure to include appropriate JavaDoc and other comments in your code, use meaningful names, indent sensibly, provide toString() methods where appropriate, and so forth. Keep track of the major design decisions, algorithms, and tests you perform to verify your code is working. You will be asked to include a summary of these in the report that you will write individually at the end of the final part of this project. You can also use the report to point out any special features of your work, or anything you're including for extra credit. Overview To create a virtual traffic simulation, we need to model the roads and the vehicles that travel on them. The main intent for this project is to examine how traffic flows (or doesn't) depending on such factors as how many vehicles are present, and what "driving styles" are used. Because traffic flow is what we're interested in (i.e. we're not developing a driving game), we don't particularly care about simulating cars swerving around or going off the roads. Modeling traffic flow is actually an important real-world problem. In this first part of the project, we will develop the "kit of parts" that we can use to build our virtual road system. In later parts of the project, we'll add a graphical visualization of our virtual world and a means for a human to interact with the system via keyboard and mouse (e.g. you can try to drive a vehicle). We'll also provide a way to run simulations. It may help to know a little about how simulation will work, although we won't implement this yet. We want to see how the system changes as time goes on. We'll approximate the continuous flow of time by splitting up time into tiny intervals -- "ticks" of our virtual world's "clock". For every clock tick, we'll ask every vehicle how it would move in one tick interval, and update vehicle positions, and any other state information we need, according to those moves. The two most important things you need to know about this are: The time intervals will be very small -- this will let us make some approximations when we're figuring out how things move. It will also give the appearance of smooth motion. We can't guarantee any particular order for asking the vehicles to move. For instance, if there are two vehicles on a road, one in front of the other, the one behind might get asked to make its move first, before the one in front. Also in a later part of the project, we'll add ways to get vehicles into your road network, as though they were arriving from outside, and ways to absorb vehicles that leave the network. In this first part of the project, we're just creating roads and vehicles, and testing to make sure they work properly -- the graphics, user interface, and simulation come later. This project may seem complicated at first, partly because it has a relatively long description, and we're deliberately not telling you in detail how you should do this. Don't panic! You might start by extracting the project "requirements" from this description, and putting them in your own words. Keep simplicity in mind as a goal -- get something basic working first. When designing your classes, think about what tasks objects of each class have to perform, and what information they need in order to do their jobs. (Sprinkled throughout this assignment will be questions, usually in parentheses -- these are intended to help point out things you should consider for your design.) Next, we'll describe some ideas for representing roads, then vehicles, then the interaction between them. Networks of roads A network of virtual roads can be simplified by splitting it up into pieces that are internally simple, then connecting the pieces to form more complex arrangements of roads. Constructing the complex whole out of a small number of types of parts promotes code reuse, and lets us test our parts and their interactions thoroughly. To keep things simple, we suggest that you split the roads into individual "traffic lanes" that don't connect to other road pieces except at their ends, and "intersections" that allow vehicles to get from one lane to another that continues on from the intersection. Some properties of road pieces help to define how they are connected into a network.  For instance, a lane connects to other pieces only at its two ends (ignoring lane-changing in adjacent lanes, which we won't require you to implement).  An intersection probably has more than two connection points. Each piece should "know" what other piece(s) it can deliver vehicles to. For instance, a one-way lane can only deliver vehicles to another road piece that's connected to its "exit" end, and can only receive vehicles at its "entrance" end. An intersection might be connected to several outgoing lanes, and receive vehicles from several incoming lanes. These properties are independent of the actual geometry of the network -- they only tell what's connected to what. Once we give our road pieces a way to record what they're connected to, we'll need a way to join the pieces into a network of roads, i.e. to tell each piece what it's connected to. (Your roads will very likely have routes that connect back to themselves, like going around the block. Keep this in mind while you're designing -- be sure this case works!) We'll also want to tell how the roads are laid out in our virtual world -- we'll need to define their sizes and shapes, and assign locations to them in our virtual world. The virtual world will need a two-dimensional coordinate system for specifying positions. Positions should be measured from some convenient origin (such as the bottom-left corner or center of the region). You should use real-world units of measurement for the various quantities. Positions and sizes should be measured in miles, or kilometers, or feet,... Times should be in hours, or minutes,... Speed should use appropriate distance per time units, and acceleration should use distance per time squared. Feel free to mix units if you want (e.g. feet for vehicle sizes, miles per hour for speed,...). You should use (roughly) realistic sizes, times, speeds,... Your road pieces will need to know (or be able to find out) where they are. For instance, if you have a straight, rectangular lane, you could completely specify where it is by giving (say), the coordinates of three corners, or coordinates of the middle of its entrance and exit ends, along with a width. You can decide how to describe the positions of your road pieces. (You'll want to have consistent positions for the exits of your pieces and the entrances of the other piece they're connected to, so think about what sort of position information for road pieces would make aligning exits and entrances simple. If two pieces are connected, do both of them have to know the position of the connection point? If they do, it's redundant information, and there's a risk that a mistake in your code could let the two copies become different.) Vehicles For simulating the flow of traffic, probably the most important thing about a car or other vehicle is how it's driven. So we'll include "driving style" in the behavior of our vehicles -- we'll pretend that the driver is part of the vehicle, or that our vehicles are robots that drive themselves. We're interested in road congestion, so we want vehicles to take up space -- we'll need some information about their size. You ought to control your vehicles the way you would drive a real car -- by accelerating and braking (which is just negative acceleration), rather than setting the speed directly. A non-zero acceleration will cause the speed to change over time -- a positive acceleration represents speeding up, and a negative acceleration represents braking. We may want to specify a maximum positive acceleration and a minimum negative acceleration. (This makes driving style issues a lot more interesting! It prevents the vehicle from coming to a dead halt without gradually slowing down, for instance. Think about what other behavior is realistic -- if the vehicle is slowing down due to braking, what happens when it gets to zero speed? Should it remain stopped, or should it start going backwards?) In order to tell how far a vehicle will move over some time, besides the acceleration, we need to know how fast it's already going. You (probably) remember the equations for linear motion with a constant acceleration -- the distance traveled during a time interval, and the speed at the end of the interval, are given by: distance_traveled = time * initial_speed + (.5) * acceleration * time2. final_speed = initial_speed + time * acceleration (When we run a simulation in later parts of the project, we'll be using tiny time steps, so we won't have to worry about any change in acceleration during each step. In this part, for testing, we might ask for larger time steps. If you're worried about approximation error, or that the time step might be large enough that it spans moving through entire road pieces, you could split up the move into smaller intervals.) In order to act like a driver, the vehicle will need to pay attention to what's ahead, and make decisions about how to change the acceleration. We're not doing bumper cars, so vehicles should (at least) not bash into the vehicle in front. In order to do this, the vehicle has to know about the vehicle in front. It will also need to know when it's getting to the end of the road piece it's on, so it can make a decision about where to go next, or slow down if it has to stop at the end. And that brings us to... Interactions between roads and vehicles At any point in time, we'll need to know where the vehicles are on the road network.  To update their positions for a later time, we'll need to know how they move in the interval, and the orientation of the road they're on (or more generally, the shape of the path they're traveling, e.g. if they're moving in a curve around a corner). (Think about whether vehicles should know about their positions on the roads, or if the road pieces should store that information.) In any case, in order to update vehicle positions, you'll likely need either vehicle methods that let road pieces get movement information from vehicles, or road methods that let vehicles get position and orientation information from roads. As we noted above, in order to move safely and legally, a vehicle will need to be able to tell how far it is able to move -- how far it is from any obstacle, such as another vehicle, or a required stop. You'll need a way for the vehicle to find that out. If the vehicle in front is close enough to worry about, you can probably assume it's on the same piece of road, or the next one along. You can take advantage of this: Just as we simplify the structure of the road network by splitting it into pieces, we should be able to simplify our interactions between roads and vehicles by having vehicles deal with only the road piece (or pieces) they are currently on. You might use your road pieces to keep track of what vehicles are on them. (When a vehicle moves, what needs to know about it? If the road pieces are keeping track of positions, you'll need some way for the vehicle to tell them that it has moved.) (Think about whether a vehicle can be "on" more than one road piece. What if it's moving from a road segment into an intersection? Do both the road segment and the intersection need to know about the vehicle?) (If your road piece is going to be asked frequently about the vehicle immediately in front of another, what sort of "data structure" is convenient for that, and what order should it keep its vehicles in?) If a vehicle has reached the "exit" end of a piece of road, it'll need to be able to find out what other pieces it could choose to move onto next. If a vehicle communicates only with a road piece it's on, then that piece will have to be able to tell it about other pieces it could move onto, i.e. what pieces are connected to its exits. If the road piece restricts which exits are reachable from a particular entrance, then it'll have to take the vehicle's chosen entrance into account. (Here's something to ponder: Once the vehicle has found out what road pieces it could move onto next, it could ask those pieces where it could go after that, and then ask those pieces... How could you make use of this to let your vehicles plan their routes? Could you use this to find a route to some specific destination? What if you wanted to find a route that avoids congestion? What information would you need from the road pieces?) (One simple way to pick where to go next is to make a random choice. Most of you are familiar with either Math.random, or the Random class. If not, look up the Math class and / or the Random class in the Java API documentation. Math.random is a method that gives you a uniformly-distributed double value in the range 0. to 1. If you need to pick among a small number of options, you can split the 0. to 1. range up into that number of intervals, one for each option. Choose the option according to which interval the random number falls into. Class Random has methods that can directly give you an int in the range 0 to the number of options - 1, but Random is a bit tricky to use -- you should create only one Random object and use it for all random choices, else you risk getting multiple Random objects that will produce exactly the same sequence of numbers! This is because Random uses the computer's date/time clock to get an initial "seed" for its random number generator. If you create a bunch of Random objects when your code starts up, it's likely that many of them will get the same time. So you may be better off using Math.random, which itself makes just one Random object.) Once a vehicle has decided where to go next, it will need a way to enter that next piece. (Does it have to tell the piece it's leaving when it's gone? Or can the piece figure that out for itself?) (If you're going to be adding vehicles to one end of some data structure, and taking them off of the other end, then it would be good to use a data structure that makes this easy to do, and that doesn't have to take a lot of computer time to do it. Here, we'll make a concrete suggestion. You're likely very familiar with arrays and with ArrayList. ArrayList does let you remove items, but recall that it uses an array to store its items. When you remove one, it has to shift everything after it down one position in the array. We recommend instead that you try a LinkedList. In a LinkedList, each item has a pointer to the next, and there's a pointer to the beginning and the end as well. To clip off the first item, all the LinkedList has to do is set its start pointer to the second item, which it can find trivially by getting the pointer to the second item from the first item. Look up LinkedList in the Java API documentation -- you'll see that its methods are almost the same as those of ArrayList. We also recommend that you use an Iterator to loop over items in your LinkedList instead of using a for loop and an index. The Iterator for a LinkedList keeps the pointer to the next item. Iterator provides methods hasNext and next -- these will be familiar if you've used Scanner, which many of you have. If you use a for loop instead, and ask for the Nth item, it has to start from the beginning and count, which is a waste of time.) Support for the simulation Oh yes, more more thing...  It's possible that eventually, no vehicles at all will be able to move. If the simulation asks all the vehicles to move, and none does, then the system is in gridlock (or in computerese, "deadlocked"). In order to be able to detect this (so the program can quit instead of forever asking things to move, with nothing happening), it would be helpful if the method that asks a vehicle to move would return something that could be used to tell if it was able to move -- for instance, the distance moved, or a boolean value, true if the vehicle did move. Things you can ignore Since our eventual interest is in simulating traffic flow, we can make a lot of "simplifying assumptions" that make our job of designing classes easier.  Here are some things that we aren't asking you to deal with: Diagonal or curved lanes -- You can support only lanes that are horizontal or vertical if you want. [This simplification was omitted in the draft version.] Backing up -- You can have vehicles that only go forward. Side-to-side motion within lanes -- You can pretend vehicles are locked onto the center of their lanes, or guided along appropriate turns through intersections. (Sort of like the Disneyland Autopia...) "Second-order" effects -- Because the simulation will use only small time steps, any error due to ignoring (for instance) changes in acceleration over the time interval will be trivial. Likewise, when figuring out how much free space for movement there is in front of a vehicle, you don't have to bother trying to figure out how far the vehicle in front will move. (Recall the comment above about how the simulation will work -- you may not be able to tell if the vehicle in front has already made its move for this time step.) If you want, you can say that only one vehicle can be in an intersection at a time. That way you don't have to worry about vehicles whose paths could cross. You don't have to do anything fancy to deal with requests to move a vehicle for such a long time that it would finish moving along its current road piece, have to decide where to go next, move into that other, finish that one, have to decide... You can, if you want, only handle crossing from the current piece to the next (and maybe chop off the distance moved at the end of the second piece). (On the other hand, you may find it's easy to deal with this.) When we choose a time step for simulation, we'll be sure to pick a sufficiently short interval that nothing can go through more than two road pieces in a step. What to do for part A For this part of the project, you should create (at least) two kinds of road piece -- lanes (straight, one-way sections of road that can hold a single line of vehicles) and intersections that can connect the exits of lanes to the entrances of others. You should make both of these subclasses of an abstract superclass that represents a generic piece of road. You should factor the properties and responsibilites into the superclass and subclasses appropriately. You are welcome to have more than two kinds of road piece or more elaborate inheritance hierarchies to model various sub-types of your road pieces, but this is not required. You should have an abstract class to represent a generic vehicle. Provide (at least) two vehicle subclasses with different behavior -- something that needs differences in their methods rather than just different values of instance variables. (This is where you can have fun with driving styles, or different ways of deciding where to go, etc. Or you might have something mechanically different about the vehicle that affects its motion.) Your classes should provide public methods to handle the tasks described above. For convenience, we'll summarize the major tasks below. You might need more than one method to provide all the information and commands for a given task. Because we don't want to tie you down to a particular way of doing things and because some tasks involve both roads and vehicles, some tasks aren't listed as belonging to either set of classes. All your classes (even the abstract ones) will need appropriate constructors. (Note that you don't have to provide absolutely everything an object needs to know in its constructor. In fact, this may not be possible: You may find you have road objects that need to know about vehicles, but vehicles need to know about the roads -- a "chicken and egg" problem. It's fine to do a minimal setup in the constructor, and provide methods to add information later.) You are encouraged to use private methods to avoid redundant code and make the code easier to read. It's often helpful to write comments first, along with "skeleton" code for your classes, methods, and constructors, before you begin filling in the implementation details. You must include JavaDoc comments describing each class, method, and constructor. For methods and constructors, include @param lines to tell what the parameters are for. For non-void methods, include @return lines to describe the return value. For classes, include @author lines for each partner. Summary of information and tasks for roads A road piece should provide at least the following behavior via public methods: A road piece should provide a way to find out what vehicles are on it.  That is, it should have methods that allow getting references to its vehicles, either one at a time, or as a group. (You might look at other classes, e.g. in the Java library, that have collections of items -- how do they make them available? How are you going to use the vehicles you get from the road piece? What methods would be most convenient for this use?) A road piece should be able to tell what exits it has, and what other road pieces are connected to them. It should have a way to get the reference to each of its exit road pieces. It should provide a method that lets a vehicle enter, if there's room. If there are multiple entrances and exits, it should let the vehicle specify where it's entering, and where it wants to exit. (If you need to know whether the vehicle was allowed in, then you should give this method an appropriate return value.) You'll need a way to connect an exit of one piece to an entrance of another. For debugging purposes, give your road classes their own toString methods that show whatever info about their characteristics and state you find helpful. Be sure to say what type of road piece it is. (If you give your roads names, you could include those.) Summary of information and tasks for vehicles A vehicle should provide at least the following behavior via public methods: It must have a method that can be used by the simulation to tell it to make whatever decisions it needs to make, thent move for a specified amount of time (that is, the method should take a time in hours as a parameter). It should return either a boolean value that's true if it was able to move, or a distance moved. This will likely be your most important and complicated vehicle method. Besides just moving, this is also where your vehicle will make the decisions that give it its distinctive behavior. It can decide how to change its acceleration and it can choose where to go. It will have to take care of telling any road pieces it's on how much it moved (if the road pieces are tracking positions of vehicles). It will have to inform whatever road pieces it enters. For debugging, and perhaps for use by the above method, you might want a method to set the acceleration, and a method that just computes the distance that would be moved in a specified amount of time and updates the vehicle's speed, without making any decisions or communicating with any road pieces. Note you could use this for testing even if you don't have any road pieces to put the vehicle on. Also for monitoring what's going on, provide a method to return the vehicle's current speed. Give your vehicle classes their own toString methods that show whatever info about their characteristics and state you find helpful. Be sure to say what type of vehicle it is. (If you give your vehicles any identifying info (like a license plate), you might include that.) Summary of information and tasks where you get to decide which class should handle them A vehicle needs a way to get the distance to the vehicle in front of it (if there is one on the current road piece). It will probably also need the distance to the end of the road piece, if there's no other vehicle in the way. (Do you need these two pieces of information separately? What should you return if there is no vehicle in front on the same road piece?) If your road pieces are keeping track of vehicle positions, you'll need a way for vehicles (that have been told to move) to inform the road piece(s) they're on how far they moved. Unit tests A key part of this assignment is to test your road and vehicle objects carefully to be sure that they behave as expected. That means creating instances of your classes, calling their methods, and verifying that instance variables and other observable state changes as you predict. In particular, be sure that you and your partner understand any equations or algorithms that control behavior, and how the state of the road pieces and vehicles should change as vehicles move, then verify that they actually do work that way. You should implement a set of JUnit tests to automatically test your classes. Be sure to test all the major behaviors of your classes so that in the next part of the project we can assume that they behave properly and can go on to other issues. There should be tests for every public method, and they should test for correct behavior under any distinctively different conditions that can happen. (In software engineering speak, you want your tests to have complete "coverage" -- they should test all behaviors, and cover all significant cases of parameter values and internal state values, including illegal values of parameters.) You should include tests that examine behavior of your classes when used together: Create and connect up roads, create vehicles and add them to roads. Ask vehicles to move -- try big time steps; use a loop to run multiple small time steps. It is very helpful if you think about your testing strategy first, while doing design, before starting to code. It is much harder to try to come up with tests after the fact than it is to develop them as you think through the code. In fact, if you think about and understand the tests first, it will make the job of coding the classes easier. You can do this even before you know how to construct JUnit tests. Some extra credit ideas If you're adding features that will behave differently from the required classes, please make separate subclasses for them. In your report, you can tell us how to try out your new features. Here are a random assortment of things you might try out. (Not all things on this list are equally difficult.) Better still, surprise us. Friction -- E.g. whenever the vehicle isn't told to accelerate, have it slow down gradually. Speed limits -- Let your lanes specify a maximum speed, and have your vehicles try to drive to keep under that. Traffic citations -- For each vehicle, detect when it violates some traffic rule, like barging out into an intersection, exceeding the speed limit, or hitting another vehicle. Count these for each vehicle. Parking -- Allow a vehicle to pull off the road, permitting other vehicles to pass it. Allow it to pull back into traffic at the point where it left, in a realistic manner (i.e. when there is an appropriate space available, and starting from zero speed). Have your drivers obey the legal who-goes-first order if there are multiple vehicles waiting to cross an intersection. Traffic signals -- Provide a way for vehicles to tell what color the light is for their lane. Change which lanes are blocked according to a schedule. With this feature, you can explore the effect of signal "timing" on traffic flow. Curved lanes -- You can still use the same formulae for distance and speed, if you want, but regard the distance traveled as being along a curved path. Multiple-lane roads -- Allow lane changes among a set of adjacent lanes. Intersections that allow two vehicles to pass through if their paths don't cross. Emergency vehicles -- Turn on the siren and lights, and make others get outta the way. Alien abduction. What to turn in When you are done, use this online turnin form to turn in the source files for your program and for the unit tests that verify that they work as expected. You can turn in the project more than once - we'll grade the last version you turn in. In particular, if you want to go beyond the basic requirements, we strongly suggest that you complete and turn in a project that meets the basic requirements first, then add the extras and turn in what you can before the deadline. Department of Computer Science  & Engineering University of Washington [comments to cse143-webmaster@cs.washington.edu]