Project 5 - Swarm!

Introduction

SwarmWORKS is a fictitious video game company that is developing an insect-themed game for distribution on multiple platforms. The game will involve dodging swarming insects while collecting flowers on a 2D playing field. As part of the design process, the company has decided to develop a swarm simulator that can be used to experiment with models of insect behavior. Portions of the simulator code may be incorporated into the final product, but the main objective is to develop a platform for testing design ideas.

The completed application will read a user-editable text file specifying the contents of the simulation then execute the simulation until the user exits.

Provided Code

It should not be necessary to modify any of these classes. Please do not make any changes, because your code will be graded using the original files.

StdDraw, SwarmDriver, and SwarmConstants

All of the graphics for this application will be handled by the StdDraw library developed by Robert Sedgewick and Kevin Wayne at Princeton University. This library is not particularly powerful or full-featured, but it makes it easier to develop simple graphical applications in Java.

SwarmDriver.java has been developed to load the simulation data, initialize the drawing window, and handle the main simulation loop.

It is your responsibility to develop a Simulation class that is able to read the configuration file passed to the Simulation constructor. This class must also provide an “update” method that will be responsible for updating the state of all simulation elements at each time step, and a “draw” method that will be responsible for re-drawing simulation elements after they have been updated. Your code will be tested using the driver above.

SwarmConstants.java contains a set of constant values such as the window size, the simulation update rate, etc.

Point, Pose, and PoseUtils

It will be necessary to store and update the positions and headings of simulated insects in order to model their behavior. This is complicated by the requirement that the simulation environment wraps at the edges. In other words, when an object disappears off one edge of the window, it should reappear in the corresponding location at the opposite edge.

The following classes will be helpful for maintaining and updating insect locations:

1. Point.java - The Point class is an encapsulation of a two-dimensional location.
2. Pose.java - The Pose class is a subclass of Point that includes heading information.
3. PoseUtils.java - This class contains utility methods for updating Poses so that the edges of the window are handled correctly.

Simulation Specification

A list of simulation elements will be provided to the application in a text file. The first line of the file will contain a single integer describing the total number of elements encoded in the file. The second line will be blank. The remainder of the file will consist of entries describing the simulation elements.

The first line of each entry will contain an element type identifier. Subsequent lines will contain information appropriate to that element type. Where there are multiple values on a single line, each value will be separated by a single space. There will be a single blank line after each entry, including the last. You may assume that the file will be free of defects.

The remainder of this section will describe each simulation element along with the associated file entry formats.

Bees

Within the simulation, bees are represented as small isosceles triangles that move forward at a fixed speed while making random heading changes.

Bee File Format

File entries for bees have the following format:

bee
RED GREEN BLUE SPEED ANGLE_STD

The RED, GREEN and BLUE values will be integers in the range 0-255 indicating the values of the indicated color channels.

The SPEED value is a double indicating the bee’s forward speed. The speed is provided in units of pixels/time step.

The value of ANGLE_STD specifies the amount of randomness in the bee’s heading. A value of 0 indicates that the bee’s path will be perfectly straight. Larger values will lead to more random trajectories. Specifically, the bee’s heading should be updated with values drawn from a Gaussian (i.e., normal) distribution with a mean of zero and a standard deviation determined by the value of ANGLE_STD.

Bee Appearance

Bees should be drawn as isosceles triangles with a base width of 5.0 pixels and a height of 10.0 pixels. The PoseUtils.drawPoseAsTriangle method provides the necessary functionality for drawing bees. Bees (and all other simulation elements) should be drawn using the default StdDraw pen radius of .002.

Bee Behavior

The poses of all bees should be generated randomly at the start of the simulation. Positions should be selected uniformly from the entire simulation window. Orientations should be drawn uniformly from the interval [0, 2π).

The following pseudocode describes the behavior that a bee must exhibit on each time step:

Randomly update the heading:
       x <- A random number drawn from the appropriate Gaussian distribution.
       heading <- heading + x
Move forward SPEED units.

where the leftward pointing arrows <- indicate assignment.

Bee Example

Here is a sample configuration file specifying two bees: a red bee that moves slowly and erratically, and a black bee that moves more quickly with no random changes to its heading.

2

bee
255 0 0 1.0 0.3

bee
0 0 0 3.0 0.0

This video shows a possible simulation run that might result from processing this file:

Note that this video was created after modifying SwarmConstants.java to specify a smaller window size. Using the default settings, you should expect your bees to appear somewhat smaller relative to the window.

Bee examples

We have captured several examples of the result of drawing a Bee to help support your understanding of the Point and Pose coordinate system. Take a look at the Bee Gallery.

Swarms

A swarm is a collection of bees with a single queen and an arbitrary number of drones. The queen moves randomly and the drones follow the queen.

Swarm File Format

File entries for swarms have the following format:

swarm
NUM_DRONES
RED GREEN BLUE SPEED ANGLE_STD
RED GREEN BLUE SPEED ANGLE_STD MAX_TURN_RATE

The NUM_DRONES value will be an integer indicating the number of drones in the swarm.

The next line specifies the characteristics of the queen. The format here is the same as the bee format described above.

The final line specifies the characteristics of the individual drones. In addition to the four entries required to specify a bee, drones have an additional attribute, MAX_TURN_RATE, that governs how quickly they are able to turn in order to track the movements of the queen. This will be a double specified in radians per time step.

Swarm Behavior

The poses of all bees in the swarm should be generated randomly at the start of the simulation. Positions should be selected uniformly from the entire simulation window. Orientations should be drawn uniformly from the range [0, 2π).

The following pseudocode describes the behavior that a swarm must exhibit on each time step:

 Randomly update the heading of the queen.
 Move the queen forward according to her speed.
 For each drone in the swarm:
     Turn toward the queen at the maximum rate.
     Perform a random update to the heading.
     Move forward according to the drone's speed.

Swarm Example

Here is a sample configuration file specifying a single swarm composed of a red queen and three black drones:

1

swarm
3
255 0 0 2.0 0.2
0 0 0 2.0 0.2 0.07

This video shows a possible simulation run that might result from processing this file:

For the sake of simplicity, this example only includes one swarm. It should be possible to simulate multiple swarms simultaneously.

Beetles

Beetles differ from bees in both their appearance and their motion pattern. On most updates beetles move straight ahead without changing their heading. They occasionally select a new random heading.

Beetle File Format

File entries for beetles have the following format:

beetle
RED GREEN BLUE SPEED TURN_PROBABILITY

The values for RED, GREEN, BLUE and SPEED have the same meaning for beetles as they do for bees. TURN_PROBABILITY will be a double between 0.0 and 1.0 indicating the probability that the beetle will change its heading on a given time step. If the value is 0, then the beetle never turns. If the value is 1, the beetle selects a new random heading on each update.

Beetle Appearance

Beetles should be drawn as filled circles with a radius of 6.0 pixels.

Beetle Behavior

The pose of all beetles should be generated randomly at the start of the simulation. Positions should be selected uniformly from the entire simulation window. Orientations should be drawn uniformly from the range [0, 2π).

The following pseudocode describes the behavior that a beetle must exhibit on each time step:

 With probability TURN_PROBABILITY:
     Update the heading to a randomly selected value in the interval [0, 2π).
 Move forward SPEED units.

Beetle Example

The following file describes two beetles: one blue beetle that changes direction with probability .01, and a yellow beetle that changes direction with probability .1.

2

beetle
0 0 255 1.0 .01

beetle
255 255 0 1.0 .1

This video shows a possible simulation run that might result from processing this file:

Flowers

For the purpose of this application, a “flower” is just a stationary filled polygon. This will make it possible to experiment with different flower shapes without making changes to the simulation source code.

Flower File Format

File entries for flowers have the following format:

flower
RED GREEN BLUE
NUM_POINTS
X_1 X_2 ... X_N
Y_1 Y_2 ... Y_N

The second line specifies the color of the polygon. The third line consists of a single number specifying the number of points on the boundary of the polygon. The fourth and fifth lines provide the x and y coordinates of the boundary points. The number of values in these lines will match the NUM_POINTS value.

Flower Behavior

Flowers do not change their state during updates.

Flower Example

The following file describes two flowers: one black square with its lower-left corner at (20.0, 20.0) and one blue polygon with its lower left corner at (120.0, 120.0).

2

flower
0 0 0
4
20.0 40.0 40.0 20.0
20.0 20.0 40.0 40.0

flower
0 0 255
5
120.0 140.0 140.0 130.0 120.0
120.0 120.0 140.0 150.0 140.0

This video shows the expected result of processing this file:

Part A: UML

By the first deadline you must submit a UML diagram illustrating your design. For full credit, your design must make appropriate use of the object oriented features that we have been covering in class: specialization, abstract classes, interfaces, etc. Your UML should be as complete as possible. It should show the attributes of each class as well as the signatures of all public and protected methods. It should also show the relationships between your classes.

Part of your grade for this portion of the assignment will be based on using correct UML syntax . Your UML diagram may be prepared electronically or very neatly hand-drawn and scanned.

In addition to the practice you’ve had with earlier labs, the reading in chapters 8 and 12 (esp. the CRC Card Method), find a few tips on this page associated with the Objected-Oriented Design Lab .

Your UML diagram must be submitted through Gradescope as a one-page PDF file.

Part B: Code

You must submit your finished project through Gradescope by the second deadline. The submission tests will not be able to verify that your swarm elements are updated or drawn correctly. Passing the autograder tests will only mean that your code is formatted correctly and doesn’t crash when it is executed. This makes it particularly important that you carefully test your code before submitting.

Here are some additional configuration files that you can use for testing:

• all_examples.txt - This contains all of the examples above in a single file.
• interesting.txt - A larger example.

Design and Implementation Suggestions

Working with Random Numbers

• The class java.util.Random should be used to generate pseudo-random numbers for this application. The nextDouble method returns a double selected uniformly from the interval [0, 1). This method can be used to generate initial poses by multiplying the generated values by the desired upper bound for each component of the pose.

• In order to create a block that occurs with a particular probability, you can compare the output of nextDouble to the desired probability. For example:

  if (generator.nextDouble() < 0.75) {
      // This block will execute with probability 75%
  }
  

• The java.util.Random class provides a nextGaussian method that can be used for generating pseudo-random numbers from a Gaussian distribution with mean 0.0 and standard deviation 1.0. If a different standard deviation is required, you can simply multiply the generated value by the desired standard deviation:

  // Here 10.0 is the desired standard deviation.
  double x = generator.nextGaussian() * 10.0;
  

Miscellaneous Advice

1. Make sure you understand the provided code. Take some time to look over the StdDraw library documentation as well as the other provided classes.
2. Develop with testing in mind. For example, it might be a good idea create your swarm elements with explicit value constructors first so that you can test them in isolation before worrying about file I/O.
3. Many steps in this project require the use of a random number generator. Programs with a random component can be challenging to debug because errors may occur at unpredictable intervals. This problem can be alleviated by using a single shared random number generator and setting an explicit seed value during testing.
4. Look for opportunities to use polymorphism to avoid code duplication. As always, if you find yourself copying and pasting code, there is a good chance you are doing something wrong.
5. Don’t wait until after the UML deadline to start working on your code. You can experiment with developing and testing classes even if you haven’t completely solidified your design. It will probably be easier to refactor functional code to match an improved design than it would be to start coding from scratch.

Acknowledgement: This assignment was originally designed by Prof. Nathan Sprague.