Thinking in 2D

We are going to use the concept of a grid to demonstrate working with 2-dimensional data. Remember, an image is a two-dimensional collection of pixels:

A grid provides generic two-dimensional storage. You can store strings, integers — anything (just like lists can store anything)

To work with a simple grid, you can run the following command in a terminal:

conda run -n cs110 python -m pip install byugrid

Basic grid commands

Following is a list o fbasic grid commands:

# import grid library
from byugrid import Grid

# create a new grid with given width and height
# all cells are `None` initially
grid = Grid(width, height)

# grid width and height
grid.width
grid.height

# every cell has an (x,y) coordinate, starting at (0, 0) in the upper left

# loop over all the columns
for x in range(grid.width)

# loop over all the rows
for y in range(grid.height)

# get the cell contents at coordinate (x, y)
# raises an error if out of bounds
grid.get(x, y)
# set the cell contents at coordinate (x, y) to contain the given value
# also raises an error if out of bounds
grid.set(x, y, value)
# checks if a coordinate is in bounds
# True if in bounds, False otherwise
grid.in_bounds(x, y)

Simple grid example

Here is a simple example of how to use a grid:

You can find this code in simple_grid.py:

from byugrid import Grid

if __name__ == '__main__':
    grid = Grid(3, 2)
    print(grid.width)
    grid.set(2, 0, 'a')
    grid.set(2, 1, 'b')
    print(grid.get(2, 0))

This should print:

3
a

Flying Cougars

This program shows how to animate a two-dimensional grid. We’re going to put random letters from the word cougars in the right column and then have them fly from right to left.

Random letters in the right column

Here is a function to put random letters from cougars in the right column. We use one function from the random library that you haven’t seen before: randomrange. This function chooses a random element from a range.

For example, randomrange(3, 9) picks a random integer from 3 to 8 (since the range does not include 9). Likewise, randomrange(10) picks a random integer from 0 to 9, since zero is the default starting point for the range.

def random_right(grid):
    """
    Set 10% of the right grid column to random letters from the word 'cougars'
    :param grid: a grid
    :return: the same grid, but with random letters on the right edge
    """
    # loop through every row
    for y in range(grid.height):
        # one out of every 10 times through this loop:
        if random.randrange(10) == 0:
            # pick a random letter from 'cougars'
            char = random.choice('cougars')
            # set the cell at (grid.width - 1, y) to that letter
            grid.set(grid.width - 1, y, char)
    return grid

Move the letters from right to left

Here is a function to move any letters from right to left in a grid. We are careful here to use nested for loops to go through the grid from top to bottom and then from left to right. If we instead moved from right to left, we could move a letter on top of another one.

We have to be careful to check whether a letter is moving to a place that is not out of bounds, otherwise we could cause an error with our grid by trying to access an invalid location.

We also have to be careful to “erase” each letter after we move it.

def scroll_left(grid):
    """
    Scroll all grid cells to the left
    """
    for y in range(grid.height):
        for x in range(grid.width):
            # get value at (x, y)
            value = grid.get(x, y)
            if value is not None and grid.in_bounds(x - 1, y):
                # move letter at (x, y) to the left
                grid.set(x - 1, y, value)
            # set old location to be empty
            grid.set(x, y, None)

Running the animation

This function does one round of the animation. It createa random letters on the right column of the grid, then it draws the grid, and then it scrolls everything to the left.

The draw_grid_canvas function draws a grid on the screen.

Additional code, not shown, calls movie_action every 30ms.

def movie_action(grid, canvas):
    """ This function is called repeatedly by a timer.
    It creates letters randomly on the right, draws the canvas,
    then scrolls the letters left.
    """
    random_right(grid)
    draw_grid_canvas(grid, canvas)
    scroll_left(grid)

The full program

You can find the program in flying_cougars.py. This code:

• Takes a width and height on the command line as arguments for the program.

• Creates a grid of the specified height and width.

• Uses a drawcanvas.py file to draw a grid on the screen. That code in turn uses a library called tkinter for graphical user interfaces.

• Uses a timer to call movie_action repeatedly, once every 30 ms.

Waterfall

In this program, water appears at the top of the grid, then moves downward, avoiding rocks along the way. Every cell in the grid is either a rock '🪨', water '💧', or empty None. Every round, every water moves downward if possible. If water can’t move, it stops (and potentially forms a pool).

Is a move OK?

First, we write a function called is_move_ok(grid, x, y). This function takes three parameters:

• grid: a grid with some rocks and some water
• x: x coordinate to check
• y: y coordinate to check

This function returns True if the coordinates (x, y) are valid and that cell is empty. Otherwise it returns False.

def is_move_ok(grid, x, y):
    """
    Given a grid and possibly out-of-bounds x, y
    return True if that destination is ok, False otherwise.
    A destination is OK only if the cell is at valid coordinates
    and is empty.

    :param grid: a grid with some rocks and some water
    :param x: x coordinate to check
    :param y: y coordinate to check
    :return: True if the move is possible, otherwise False
    """
    if not grid.in_bounds(x, y):
        return False
    if grid.get(x, y) is not None:
        return False
    return True

Move water

Now we write a function called move_water(grid, x, y). This function takes three parameters:

• grid: a grid with some rocks and some water
• x: x coordinate of some water
• y: y coordinate of some water

This function assumes that the coordinate (x, y) contains water. It then moves this water downward if possible, following these rules:

1. Move down first if possible. If the square directly below the water is a valid move, move the water there and take no further actions.

2. Move down-left if possible. If the square down and left is a valid move, move the water there and take no further actions.

3. Move down-right if possible. If the square down and right is a valid move, move the water there and take no further actions.

4. Water disappears. If the above three moves are all invalid, but the water is at the bottom of the world, the water disappears.

5. Water stays. Otherwise, the water stays where it is and potentially collects in a pool.

def move_water(grid, x, y):
    """
    Assume there is water at the given (x, y) in the grid. Move the water to
    one of the 3 squares below, if possible, starting with down, then down-left,
    then down-right. If none of these are possible, the water disappears.

    :param grid: a grid with some rocks and some water
    :param x: x coordinate to check
    :param y: y coordinate to check
    :return: the modified grid
    """

    # check down
    if is_move_ok(grid, x, y + 1):
        grid.set(x, y + 1, '💧')
        grid.set(x, y, None)
        return

    # check down-left
    if is_move_ok(grid, x - 1, y + 1):
        grid.set(x - 1, y + 1, '💧')
        grid.set(x, y, None)
        return

    # check down-right
    if is_move_ok(grid, x + 1, y + 1):
        grid.set(x + 1, y + 1, '💧')
        grid.set(x, y, None)
        return

    if not grid.in_bounds(x, y + 1):
        grid.set(x, y, None)
        return

Move all water

This function moves all the water in the grid down one space if possible (otherwise that water disappears). We just need to loop through all the grid cells and call the move_water() function you wrote if that cell has water.

One trick we use is to cover the rows from the bottom up. This avoids us moving a cell with water more than once. The function called reversed takes the list of numbers generated by range() and reverses them, so we count from the maximum value (minus 1) down to zero.

def move_all_water(grid):
    """
    Move all of the water down once (for one round).

    :param grid: a grid with rocks and water
    :return: the modified grid
    """
    # tricky: do y in reverse direction (from the bottom up), so each
    # water moves only once.
    for y in reversed(range(grid.height)):
        for x in range(grid.width):
            if grid.get(x, y) == '💧':
                move_water(grid, x, y)
    return grid

Create water

This function creates water along the top of the grid. It uses a parameter called water_factor to control the probability with which water is created. The probability is 1 / water_factor, so if water_factor is 10, the probability is 1/10.

def create_water(grid, water_factor):
    """
    Create water at the top of the grid.
    The probability of creating water for any cell is 1 / water_factor.

    :param grid: a grid with rocks and water
    :param water_factor: a factor controlling how often water is created
    :return: the modified grid
    """
    for x in range(grid.width):
        if random.randrange(water_factor) == 0:
            grid.set(x, 0, '💧')
    return grid

Create rocks

This function creates rocks in the grid at the start of the program. It uses a parameter called `rock-factor to control the probability with which rocks are created, similar to the water.

def init_rocks(grid, rock_factor):
    """
    Initialize the grid with rocks. The probability of any cell containing
    rock is 1 / rock_factor.

    :param grid: an empty grid
    :param rock_factor: a factor controlling how often rocks are created
    :return: the modified grid
    """
    for y in range(grid.height):
        for x in range(grid.width):
            if random.randrange(rock_factor) == 0:
                grid.set(x, y, '🪨')
    return grid

Do one round

This function does one round of the animation. It creates water at the top, draws the grid, and then moves all the water.

def do_one_round(grid, canvas, water_factor, scale):
    """Do one round of the move, call in timer."""
    create_water(grid, water_factor)
    draw_grid_canvas(grid, canvas, scale)
    move_all_water(grid)

The full program

You can find the program in waterfall.py. It takes the following arguments:

• —width: The width of the board, 30 by default
• —height: The height of the board, 30 by default
• —speed: The speed of each round, 30ms by default
• —water-factor: The odds of creating water, 1 out of 20 by default (change it to 3 to be 1 out of 3)
• —rock-factor: The odds of creating a rock, 1 out of 10 by default

For example:

python waterfall.py --width 50 --height 50 --water-factor 10 --rock-factor 4

This will run the waterfall program with a width of 50 and a height of 50, with 1/10 of the cells at the top generating water and 1/4 of the cells initialized to have rocks.

The main function:

• Creates a grid

• Initializes the rocks, randomly

• Uses a drawcanvas.py file to draw a grid on the screen. That code in turn uses a library called tkinter for graphical user interfaces.

• Uses a timer to call do_one_round repeatedly, once every 30 ms by default