Project 2 - Falling Sand Simulation

Objectives

Practice the use of higher order functions
Practice the use of functional programming techniques
Practice the use of Object Oriented Programming techniques
Practice adding code to an existing code base
Practice writing function level doc tests
Practice using tests to validate code refactoring

Introduction

In this project, we are going to use the Grid class you developed to create a 2D simulation of sand falling through a world with rocks as obstacles. We will provide the code that will do the animation and handle mouse clicks but you will be writing the code that simulates the world.

This project will consist of two parts. In the first part (due 2024-02-16), you will code up the simulation in a more functional programming style. Once you have that working, in the second part (due 2024-03-01) you'll convert (or rewrite) the program into a more Object Oriented style. Like the previous project, you've written some of the code already in your labs and homework and this project will draw on code written in Labs 8-11 and Homeworks 3 & 4.

image of program with sand falling

In this program, there are rocks (black grid squares) and sand (yellow grid squares). You can draw rocks and drop sand by clicking with your mouse. Inside the grid, we indicate sand with the letter 's' and rocks with the letter 'r'.

Sand movement rules

Sand always moves down into an empty space. The figure below shows examples of how sand can move.

sand movement examples

In example (a), sand can move straight down into an empty space. In examples (b) and (c), sand can move diagonally down into an empty space. In example (d) the sand is blocked if the space below it is not empty. In example (e), the sand is blocked from moving diagonally if the space above the destination is not empty. This last example is known as the corner rule.

We will move the sand down in the following order:

sand will move straight down if possible
sand will move diagonally left if possible
sand will move diagonally right if possible

If none of these apply, the sand won’t move.

Setup

Download proj2A.zip, which contains the files you will need for this part of the project. This folder contains the following files:

sand_functional.py - You will write your code for Part 1 here
Grid.py - This will originally be empty. You should copy your Grid class into this file
test_sand_functional.py - The autograder tests for this part of the project

The files for part 2 are located in proj2B.zip, which can be found at the top of the assignment instructions for that part of the project.

sand_functional.py contains additional code that handles mouse clicks and drawing the GUI for the project. You will not have to modify this code, just the code that simulates the world.

Look through the code to familiarize yourself with the layout. Don't worry about any of the code currently there. You will not need to modify it but if you're interested in how the program works, you can explore the existing code. All the code you will write in this part of this project will be at the top of the sand_functional.py files where the comments indicate.

The next thing you will need is your Grid class. You should copy your Grid class into the empty Grid.py file, then add an import line at the top of sand_functional.py to import your Grid class. You'll be using it throughout this project.

Part 1 - Functional programming version

Task 1 - Checking for a vaild move

The next step is to write the is_move_ok() function. This function has the following signature:

is_move_ok(grid, x_from, y_from, x_to, y_to)

This function checks whether it is OK to move a piece of sand from (x_from, y_from) to (x_to, y_to). Assume there is sand at (x_from, y_from) and that this location is in bounds. If the move is valid, the function returns True and if not, returns False. You need to check all the rules for moving sand we discussed in the introduction above. For a move to be OK:

the destination must be in bounds,
the destination must be empty, and
for diagonal moves, the move must not violate the corner rule.

Once you've written your function, or even better, before, you should write some doctests to validate your method. For example the following test (which you can use in your code) tests case (a) from the image above.

>>> grid = Grid.build([[None, 's',   'r'], [None, None, None]])
>>> is_move_ok(grid, 1, 0, 1, 1)  # down ok
    True

You should write at least 5 tests (and probably more) that check for both good and bad moves and verify that your code returns the correct result.

Task 2 - Move the sand

Now that you know that a move is valid, you need to be able to actually move the sand particle. Write a do_move() function that has the following signature:

do_move(grid, x_from, y_from, x_to, y_to)

You can assume that there is a sand particle in (x_from, y_from) and that (x_to, y_to) is empty. The function should return the updated grid. Remember that empty grid spaces contain the value None.

Task 3 - Add gravity

Now you will write the do_gravity() function. It has the following signature:

do_gravity(grid, x, y)

This function is given a coordinate (x, y) that you can assume is in bounds. The function then checks if there is sand at this coordinate. If there is, it tries to move it, trying the following moves in order:

sand will move straight down if possible
sand will move diagonally left if possible
sand will move diagonally right if possible

In some cases, the sand can’t move. In all cases, return the grid. Remember, you can do an early return for an obvious case that should not do anything.

Use the helper functions written above this code to do most of the work. This is a good illustration of decompostion!

Like the is_move_ok() function, you will need to write some doctests for this function. Here are two tests that check that nothing changed if there is no sand, and that the sand successfully fell straight down.

>>> # not sand
>>> grid1 = Grid.build([[None, 's', None], [None, None, None]])
>>> do_gravity(grid1, 0, 0)
Grid([[None, 's', None], [None, None, None]])
>>> # down
>>> grid2 = Grid.build([[None, 's', None], [None, None, None]])
>>> do_gravity(grid2, 1, 0)
Grid([[None, None, None], [None, 's', None]])

Feel free to add these to your code. You need to write at least 5 additional tests (and you may want to write more) that check the various sand falling conditions to verify that the sand is moving properly.

Task 4 - Do the whole grid

Write the function called do_whole_grid(grid). This function loops over all the squares in the grid and does one round of moving sand in each location where it is possible. The function returns the grid when done.

First, write two tests, with at least one test featuring a 3x3 world with sand at the top row.

Once you have your tests, write the code for the function. You must be careful to loop from the bottom up, just like we did in the waterfall problem. Remember, you can use the following for loop over the y values in reverse order:

for y in reversed(range(grid.height))

Your code should process all the squares on the bottom row, then process the squares on the next row up, and so forth.

What’s wrong with regular top-down order? Suppose the loops went top-down, and at y=0, a sand moved from y=0 down to y=1 by gravity. Then when the loop got to y=1, that sand would get to move again. Going bottom-up avoids this problem.

Run your doctests in do_whole_grid() to make sure that your code is working correctly.

The do_whole_grid() does one round of movement for the world, calling do_gravity() a single time for each square. The provided GUI code calls this function every millisecond when the gravity checkmark is checked to make the game run.

Task 5 - Interactive Testing

Once you have do_whole_grid() written and tested, along with all the other functions listed above, you can try running the whole program. You can do this with:

python sand_functional.py

Click the rock or sand buttons and then click the mouse button to scribble rocks or sand onto the world. If everything is implemented correctly, gravity should work. There are also buttons for erasing and a big eraser.

Normally when a program runs the first time, there are many problems. But here we have used careful decomposition and testing, so there is a chance your code will work perfectly the first time. If your program works the first time, try to remember the moment. On projects where code is not so well tested, the first run of the program is often a mess. Having good tests changes the story.

Task 6 - Run the test cases

Now that you have everything working, you can try running the supplied tests in the test_sand_functional.py file:

pytest test_sand_functional.py

This file contains a few tests that use all of your functions in sand_functional.py to process some predefined grids. If you've implemented everything correctly, the tests should pass. If they don't, there is something wrong and you'll need to go back and debug (and maybe write a few more test cases) to figure out the issue.

Submit Part 1

Congratuations, you've now created a small application that allow you to simulate basic gravity and collions and allows you to play with the simulation in an interactive manner.

You'll submit your sand_functional.py and Grid.py files on Canvas via Gradescope where it will be checked via the auto grader. We will be testing your code with some pre-defined initial grids to verify that you end up with the same final grid. We do not guarantee that all scenarios are tested by the test cases that we have provided you.