Description

Moving Figures

1           Overview

In this assignment you will write code for manipulating figures, where a figure is defined as a set of points or pixels. We are interested in displaying the figures and moving them around, detecting collisions when they occur.

The program that displays the figures will receive as input a file containing a set of figures. The figures will be rendered on a window and the user will move some them around using the keyboard. Figures cannot overlap, so your program will allow a figure to move only when its movement would not cause it to overlap with another figure or with the borders of the window. For this assignment, there will be five kinds of figures:

• fixed figures, which cannot move
• figures that can be moved by the user
• figures that are moved by the computer
• target figures, that disappear when the user-controlled figures run into them.

These figures will be part of a “pac-man”-like game. Figures moved by the computer will chase the user controlled figures. These latter in turn will try to get rid of the target figures. Fixed figures constrain the movement of the mobile ones.

We will provide code for reading the input file, for displaying the figures and for reading the user input. You will have to write code for storing the figures and for detecting overlaps bewteen figures.

2           The Figures

As stated above, each figure consists of a set of pixels. Each pixel is defined by 3 values x, y, and c; (x,y) are the coordinates of the pixel and c is its color. We will think that each figure f is enclosed in a rectangle r_f (so all the pixels are inside this rectangle and no smaller rectangle would contain all the pixels; see Fig. 1 below). The width and height of this rectangle are the width and height of the figure. To determine the position where a figure should be displayed, we need to give the coordinates (u_x,u_y) of the upper-left corner of its enclosing rectangle; (u_x,u_y) is called the offset of the figure.

For specifying coordinates, we assume that the upper-left corner of the window ω where the figures are displayed has coordinates (0,0). The coordinates of the lower-right corner of ω are (W,H), where W is the width and H is the height of ω.

Each figure will have an identifier; this is just an integer number that is used to distinguish a figure from another, as two figures might contain the same set of pixels (but not in the same position).

The pixels of a figure f will be stored in a binary search tree. Each node in the tree stores a data item (position,color), where position = (x,y) contains the coordinates of the pixel relative to the upperleft corner of the rectangle r_f enclosing the figure. For example, the coordinates of the black dot in Fig. 1 below are (20,10), so this black dot corresponds to the pixel ((20,10),black). As shown in Fig. 1, the offset of figure f₁ is (40,25), so when rendering f₁ inside the window the actual position of the black dot is (20 + 40,10 + 25) = (60,35).

Fig. 1 Window ω.

Note that by storing in the tree pixels with coordinates relative to the figure’s enclosing rectangle, the data stored in the tree does not need to change when the figure moves: The only thing that needs to change is the figure’s offset.

For each data item (position,color) stored in the tree, the field position is used as the key. To compare two positions (x,y) and (x^′,y^′) we use row order: (x,y) < (x^′,y^′) if either

• y < y^′, or
• y = y^′ and x < x^′

So, for example, (2,3) < (1,4) and (5,3) < (9,3).

3           Moving Figures

As stated above, two figures cannot overlap and a figure cannot go outside the window ω. Hence, when the user tries to move a figure, we need to verify that such a movement would not cause the figure to cross the boundaries of the window or to overlap another figure.

A movement can be represented as a pair (d_x,d_y), where d_x is the distance to move horizontally and d_y is the distance to move vertically. To check whether a movement (d_x,d_y) on figure f with offset (x_f,y_f), width w_f and height h_f is valid, we first update the offset of f to (x_f + d_x,y_f + d_y) and then check whether this new position for f would cause an overlap with another figure or with the window’s borders. To do this efficiently we proceed as follows:

• Check whether the enclosing rectangle r_f of f crosses the borders of the window ω. For example, to check whether r_f crosses the right border of ω we test if x_f +d_x +w_f ≥ W; recall that W is the width of ω.
• If r_f does not cross the borders of ω, then we check whether r_f intersects the enclosing rectangle r_f′ of another figure f^′. If there is no such intersection then f does not intersect other figures or the window’s borders, so the movement (d_x,d_y) is valid.
• On the other hand, if r_f intersects the enclosing rectangles of some set S of figures, then for each figure f^′ ∈ S we check whether f and f^′ overlap; if so, then this movement should not be allowed.

Note that for f and f^′ to overlap, f must have at least one pixel ((x,y),c) and f^′ must have a pixel ((x^′,y^′),c^′) that would be displayed at precisely the same position on ω, or in other words, x + x_f = x^′ + x_f^′ and y + y_f = y^′ + y_f^′, where (x_f^′,y_f^′) is the offset of f^′. Note that if these pixels exist then x + x_f − x_f^′ = x^′ and y + y_f − y_f^′ = y^′. Therefore, to test whether f and f^′ overlap we can use the following algorithm:

For each data item ((x,y),c) stored in the binary search tree t_f storing the pixels of f do (1) if in the tree t_f′ storing the pixels of f^′ there is a data item ((x^′,y^′),c^′) with key

(x^′,y^′) = (x + x_f − x_f′,y + y_f − y_f′), then the figures overlap.

if Condition (1) is not satisfied, then the figures do not overlap.

In the for loop above, to consider all the data items ((x,y),c) stored in the nodes of the tree t_f we can use the binary search tree operations smallest() and successor().

4           Classes to Implement

You are to implement at least five Java classes: Position, DictEntry, BinarySerachTree, BSTException, and Figure. You can implement more classes if you need to. You must write all the code yourself. You cannot use code from the textbook, the Internet, or any other sources: however, you may implement the algorithms discussed in class.

4.1         Position

This class represents the position (x,y) of a pixel. For this class you must implement all and only the following public methods:

• public Position(int x, int y): A constructor which returns a new Position with the specified coordinates.
• public int getX(): Returns the x coordinate of this Position.
• public int getY(): Returns the y coordinate of this Position.
• public int compareTo (Position p): Compares thisPosition with p using row order (defined above):
  • if this > p return 1;
  • if this = p return 0;
  • if this < p return -1.

You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e. not accessible to other classes).

4.2         DictEntry

This class represents a data item stored in the binary search tree. Each data item consists of two parts: a Position and an int color. For this class, you must implement all and only the following public methods:

• public DictEntry(Position p, int color): A constructor which returns a new DictEntry with the specified coordinates and color. Position p is the key for the DictEntry.
• public Position getPosition(): Returns the Position in the DictEntry.
• public int getColor(): Returns the color in the DictEntry.

You can implement any other methods that you want to in this class, but they must be declared as private methods.

4.3         BinarySearchTree

This class implements an ordered dictionary using a binary search tree. Each node of the tree will store a DictEntry object; the attribute Position of the DictEntry will be its key. In your binary search tree only the internal nodes will store information. The leaves are nodes (not null) that do not store any data.

The constructor for the BinarySearchTree class must be of the form public BinarySearchTree()

This will create a tree whose root is a leaf node. Beside the constructor, the only other public methods in this class are specified in the BinarySearchTreeADT interface:

• public DictEntry find (Position key): Returns the DictEntry storing the given key, if the key is stored in the tree. Returns null otherwise.
• public void insert (DictEntry data) throws BSTException: Inserts the given data in the tree if no data item with the same key is already there. If a node already stores the same key, the algorithm throws a BSTException.
• public void remove (Position key) throws BSTException: Removes the data item with the given key, if the key is stored in the tree. Throws a BSTException otherwise.
• public DictEntry successor (Position key): Returns the DictEntry with the smallest key larger than the given one (note that the tree does not need to store a node with the given key). Returns null if the given key has no successor.
• public DictEntry predecessor (Position key): Returns the DictEntry with the largest key smaller than the given one (note that the tree does not need to store a node with the given key). Returns null if the given key has no predecessor.
• public DictEntry smallest(): Returns the DictEntry with the smallest key. Returns null if the tree does not contain any data.
• public DictEntry largest(): Returns the DictEntry with the largest key. Returns null if the tree does not contain any data.

You can download BinarySearchTreeADT.java from the course’s website. To implement this interface, you need to declare your BinarySearchTree class as follows:

public class BinarySearchTree implements BinarySearchTreeADT

You can implement any other methods that you want to in this class, but they must be declared as private methods.

4.4         BSTException

This is just the class implementing the class of exceptions thrown by the insert and remove methods of BinarySearchTree. See the class notes on exceptions.

4.5         Figure

The constructor for this class must be of the form

public Figure (int id, int width, int height, int type, Position pos);

where id is the figure’s identifier, width and height are the width and height of the enclosing rectangle for this figure, pos is the offset of the figure and type is its type. The figure types are

• 0: fixed figure
• 1: figure moved by the user 2: figure moved by the computer
• 3: target figure.

Beside the constructor, the only other public methods in this class are specified in the FigureADT interface:

• public void setType (int type): Sets type of figure to the specified value.
• public int getWidth (): Returns the width of the enclosing rectangle for this
• public int getHeight(): Returns the height of the enclosing rectangle for this
• public int getType (): Returns the type of this
• public int getId(): Returns the id of this
• public Position getOffset(): Returns the offset of this
• public void setOffset(Position value): Changes the offset of this figure to the specified value
• public void addPixel(int x, int y, int color) throws BSTException: Creates a

DictEntry to represent the given pixel and inserts it into the binary search tree associated with this figure. Throws a BSTException if an error occurs when inserting the pixel into the tree.

• public boolean intersects (Figure fig): Returns true if this figure intersects the one specified in the parameter. It returns false

You can download FigureADT.java from the course’s website. To implement this interface, you need to declare your Figure class as follows:

public class Figure implements FigureADT

You can implement any other methods that you want to in this class, but they must be declared as private methods.

5           Classes Provided and Running the Program

The input to the program will be a file containing the descriptions of the figures to be displayed. Each line of the input file contains 4 values: x y type file

where (x,y) is the offset of the figure, type is the type of the figure (these 3 values are integer), and file is the name of an image file in .jpg, .bmp, or any other image format understood by java. You will be given code for reading the input file. We specify the format of the input file just in case you want to create your own inputs.

From the course’s website you can download the following classes: Board.java, Gui.java, MoveFigure.java, and Show.java. The main method is in class Show.java. To execute the program, on a command window you will enter the command

java Show inputFile where inputFile is the name of the file containing the input for the program.

6           Testing your Program

We will run a test program called TestBST to make sure that your implementation of the BinarySearchTree class is as specified above. We will supply you with a copy of TestBST to test your implementation. We will also run other tests on your software to check whether it works properly.