CSCI 136
Fundamentals of Computer Science II
Spring 2022

Montana Tech of The University of Montana
Computer Science & Software Engineering

Assignment 6 - Ultima 0

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. Next week you will be adding threaded monsters to your game, so build carefully. You need to add all the methods in the API in this assignment. A good habit is to always provide a descriptive comment of every method, in your comments, in your programs. The comments should include a description of the method, its input parameters, and its return values. Stub methods provided to you have already been commented, but if you choose to add methods, you should comment them appropriately. We will be looking for this during grading.

Basics. The game is played on a rectangular grid of tiles. The grid of tiles is specified in a 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. forest, etc.).

Files. The file 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

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:
NameFilenameImageOpaque?Passable?String code
Brick floorbrickfloor.gifNoYesB
Grasslands grasslands.gifNoYesG
Stone wallstonewall.gifYesNoS

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:
class Tile
            __init__(self, string code)  # Create a new tile based on a String code
    boolean getLit(self)                 # Return whether this Tile is lit or not
            setLit(self, boolean value)  # Change the lit status of this Tile
            draw(self, int x, int y)     # Draw at index position (x, y)
    boolean isOpaque(self)               # Does this type of Tile block light?
    boolean isPassable(self)             # Can the Avatar walk on this Tile?
We have provided a test main for Tile. Here is our output:
% python
0 0 : lit True	opaque False	passable True
0 1 : lit False	opaque False	passable True
1 0 : lit False	opaque False	passable True
1 1 : lit True	opaque False	passable True
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

Avatar. An 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:
class Avatar
            __init__(self, int x, int y)    # Create a new Avatar at index position (x,y)
        int getX(self)                      # Get the current x-position of the Avatar
        int getY(self)                      # Get the current y-position of the Avatar
            setLocation(self, int x, int y) # Update the position of the Avatar to index (x,y)
      float getTorchRadius(self)            # Get the current torch radius   
            increaseTorch(self)             # Increase torch radius by 0.5
            decreaseTorch(self)             # Decrease torch radius by 0.5, minimum is 2.0
            draw(self)                      # Draw at the current position

We have provided a test main for Avatar. Here is our output:
% python
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
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 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:
class World
      __init__(self, String filename)        # Load the tiles and Avatar based on the given filename
      handleKey(self, char ch)               # Handle a keypress from the main game program
      draw(self)                             # Draw all the tiles and the Avatar
  int light(self, int x, int y, float 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.
  int lightDFS(self, int x, int y, int currX, int currY, float r)
                                             # Recursive lighting method called by light(). (x, y) is still 
                                             # the position of the avatar, and (currX, currY) is the
                                             # position being considered for lighting.
The constructor of World reads in a file using Python 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 in your World class should handle the following keys: 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:
     lightDFS(self, int x, int y, int currentX, int currentY, float r)

The basic approach is to first set all the Tile objects to being unlit. Then 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 recurse 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: 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 within 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:
% python 10x5.txt
light(3, 1, 4.0) = 23

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

Grade ItemPoints PossiblePoints Earned
Program Compiles and Runs
Comments on All Classes and Methods
Used Recursion for Torch Light

Do I need to follow the prescribed APIs? Yes. You must implement all the methods described in the APIs; however, you may add additional methods if they are helpful to your code.

I seem to have the number 16 in multiple spots in my code. Is that okay? No. You should be able to declare the tile size exactly once in the project. If you do it this way, it will make it easy if in the future you need to change your program to use a different tile size.

My world is upside down. What is going on? The drawing coordinate system has (0,0) in the lower-left. If you have your 2D array arranged to have [0][0] in the lower-left, you are going to need to transform the y-index appropriately when you read in the dungeon text file (since the first line of the dungeon is the upper line of cells).

My tiles are all offset and appear in the borders of the drawing window. Remember that the StdDraw.picture() method expects the center (x,y) position of the picture, not the lower-left corner. You need to adjust appropriately to get things to line up nicely.

The blank areas of my map have strange lines. What is going on? This is caused by drawing black squares or rectangles using StdDraw. Draw a blank tile using the provided blank.gif file instead.

Do I need to modify the size of the drawing window? Yes. Since each tile is 16 pixels by 16 pixels, you need to size the drawing window to accommodate this by calling StdDraw.setCanvasSize(). Since you only want to do this one time, an appropriate place to do this would be in your World constructor since this is only called once in Ultima.

Do I need to modify the StdDraw coordinate system? Not necessarily, but you can if you want. And it will make your life easier. As with the window size, you'll want to do this in the constructor of World.

Can I send pixel coordinates as the x and y parameters to methods in World, Tile, and Avatar? No. The API is that these are the integer index positions of the game tile, not a pixel or other type of coordinate.

Extra credit level 1. Create interesting new level(s).

Extra credit level 2. Enhance your lighting algorithm so that opaque objects block what can be seen. Something along the lines of my version shown on the right.

Extra credit level 3. Make it so some tile types can be light sources of a given radius. On the video on the right, I made lava tiles generate light out to a distance of 2.5. The light should obey the same occlusion algorithm as for the Avatar's torch.

Submission. Submit your programs,, and using Moodle. Be sure each submitted source file has the required header with your name and a description of the program. For extra-credit submissions, please submit a single zip file containing all your programs/graphics/sounds via the special assignment extra-credit drop box.

Page last updated: February 23, 2022