In this assignment, you will be creating the starting point for a tile-based role playing game, similar to the famous Ultima series. You will be creating a recursive algorithm to handle a variable power torch that lights your Avatar's surroundings.

Basics. The game is played on a rectangular grid of tiles. The grid of tiles is specified in a flat text file. Your Avatar moves around by moving in one of the cardinal directions (north, south, east or west). The Avatar is not allowed to move through certain features (e.g. water or mountains). It is nighttime, but luckily your Avatar has a variable brightness torch. The torch cannot see through certain features (e.g. mountains, stone walls).

Files. The file ultima.zip contains the set of graphics tiles we'll be using in this assignment. We have included a bunch of extra graphics in case you need them for an extra-credit creation. It also contains stub versions of the programs Tile, World, Avatar. We have given you a fully functional version of the main game program Ultima.java.

Avatar. A Avatar object represents a player in the game. An Avatar knows things like its current (x,y) position in the world and the current power of the Avatar's torch. The (x,y) position are indexes, so (0,0) is the lower-left tile, (1, 0) is one tile to east, (0, 1) is one tile to the north, and so on. An Avatar can do things like get its x/y position, change its location, get its current torch power, increase/decrease its torch power, and draw itself. An Avatar's torch has a minimum torch radius of 2.0. The torch power changes in increments of 0.5. The torch starts with a default radius of 4.0.

Your Avatar data type must implement the following API:

public class Avatar
----------------------------------------------------------------------------------------
Avatar(int x, int y) // Create a new Avatar at index position (x,y)
int getX() // Get the current x-position of the Avatar
int getY() // Get the current y-position of the Avatar
void setLocation(int x, int y) // Update the position of the Avatar to index (x,y)
double getTorchRadius() // Get the current torch radius
void increaseTorch() // Increase torch radius by 0.5
void decreaseTorch() // Decrease torch radius by 0.5, minimum is 2.0
void draw() // Draw at the current position

We have provided a test main for Avatar. Here is our output:

% java Avatar
5 5 4.0
1 4 4.0
1 4 4.5
1 4 4.0
1 4 3.5
1 4 3.0
1 4 2.5
1 4 2.0
1 4 2.0

Tile. A Tile object represents an individual position in the Ultima world. All tiles are the same size 16 by 16 pixels. Tiles know things like what type of tile it is and whether it is currently lit by the torch. A tile can do things like tell people about whether it is lit, set whether it is lit or not, draw itself, determine if the Avatar can walk through it, and determine if light passes through it. Tiles should default to not being lit.

Here are the details of the types of tiles your program needs to support: See image.

If a tile is not lit, you can draw it using the supplied blank.gif image. Here is the API you should implement for the Tile class:

public class Tile
-----------------------------------------------------------------------------------------
Tile(String code) // Create a new tile based on a String code
boolean getLit() // Return whether this Tile is lit or not
void setLit(boolean value) // Change the lit status of this Tile
void draw(int x, int y) // Draw at index position (x, y)
boolean isOpaque() // Does this type of Tile block light?
boolean isPassable() // Can the Avatar walk on this Tile?

We have provided a test main for Tile. Here is our output:

% java Tile
0 0 : lit true opaque false passable true
0 1 : lit false opaque false passable true
1 0 : lit false opaque false passable false
1 1 : lit true opaque false passable false
2 0 : lit true opaque false passable false
2 1 : lit false opaque false passable false
3 0 : lit false opaque true passable true
3 1 : lit true opaque true passable true
4 0 : lit true opaque false passable true
4 1 : lit false opaque false passable true
5 0 : lit false opaque true passable false
5 1 : lit true opaque true passable false
6 0 : lit true opaque true passable false
6 1 : lit false opaque true passable false

World. The World class represents all the tiles in the world as well as the Avatar. This class is responsible for handling all keystrokes from the main program in Ultima.java. The class knows things like all the Tile objects in the world and the Avatar object. The class can do things like handle keystrokes from the user, draw itself, and light a portion of the world. Your World data type must implement the following API:

public class World
-----------------------------------------------------------------------------------------
World(String filename) // Load the tiles and Avatar based on the given filename
void handleKey(char ch) // Handle a keypress from the main game program
void draw() // Draw all the tiles and the Avatar
int light(int x, int y, double r) // Set the tiles that are lit based on an initial position
// (x, y) and a torch radius of r. Returns the number of tiles
// that were lit up by the algorithm.

The constructor of World reads in a file using Java file I/O. Here is an example input file:

10 5
3 1
W W W W W G G G W W
W F W G W S G G G G
W F F G S L S G G G
W F F G G S G G G W
W W W F G G G G G G

The integers on the first line specify the width and height of the world. The integers on the second line specify the starting x- and y-index of the Avatar. The remaining letters give the code letters for each tile in the world.

The handleKey() method should handle the following keys:

• w : Move the Avatar north. Nothing should happen if the tile to the north is not passable or is off the map.
• s : Move the Avatar south. Nothing should happen if the tile to the south is not passable or is off the map.
• a : Move the Avatar west. Nothing should happen if the tile to the west is not passable or is off the map.
• d : Move the Avatar east. Nothing should happen if the tile to the east is not passable or is off the map.
• + : Increase the torch radius by 0.5, there is no maximum radius.
• - : Decrease the torch radius by 0.5, subject to a minimum radius of 2.0.

The lighting algorithm is the crux of the assignment. You will need to implement a recursive helper method that gets called by the public light method. For example:

private int lightDFS(int x, int y, int currentX, int currentY, double r)

The idea is to start lightDFS at the Avatar's current position. The lightDFS method will call itself recursively for the positions to the north, south, east and west (these four directions only, do NOT recur on the diagonals). This allows the algorithm to spread across the map. The lightDFS method needs to retain the initial (x,y) starting position so it can calculate how far the (currentX, currentY) position is from it. You must of course be careful to limit the recursion with appropriate base cases:

• Base case 1 - Current position is off the map
• Base case 2 - Current position has already been visited
• Base case 3 - Current position is opaque
• Base case 4 - Current position is outside the torch radius. A position is considered "outside" if the Euclidean distance between the (x,y) index of the Avatar and the (x2, y2) index of the tile is greater than or equal to the torch radius.

Opaque cells should still be lit, but they should not propagate the search. This is what causes certain parts of the map to appear black despite being with the radius of the torch.

We have provided a test main for World. We temporarily instrumented our light method to show you the input parameters and result value. Here are a couple runs:

% java World 10x5.txt light(3, 1, 4.0) = 23

See output: See image.

% java World 30x20.txt light(3, 4, 4.0) = 42

See output: See image.