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 2023-10-11), you will code up the simulation in a more functional programming style. Once you have that working, in the second part (due 2023-10-18) 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-10 and Homeworks 3 & 4.

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.

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 proj2.zip, which contains the files you will need for this project. The zipfile contains the following files:

• sand_functional.py - You will write your code for Part 1 here
• sand_oo.py - You will write your code for Part 2 here
• Grid.py - This will originally be empty. You should copy your Grid class into this file
• test_sand_functional.py and test_sand_oo.py - The autograder tests

Both sand_functional.py and sand_oo.py contain 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 as part of this project will be at the top of the sand_functional.py and sand_oo.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 and sand_oo.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(grid2, 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)
[[None, 's', None], [None, None, None]]
>>> # down
>>> grid2 = Grid.build([[None, 's', None], [None, None, None]])
>>> do_gravity(grid2, 1, 0)
[[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.

Part 2

In Part 1, you solved the problem in a Functional Programming style. Your functions return new versions of the grid that you then used for the next steps. In this part of the project, we are going to rewrite the program to use a more Object Oriented style of coding so that you can begin to get a feeling for how they differ. You already have your Grid class. In this part of the project, you'll add a Sand class, and reorganize the code to use this new class. Instead of storing strings, we'll store Sand objects in the grid.

An object of the Sand class represents a single sand particle. Instead of having general functions that move sand, the Sand class will have methods that are responsible for moving itself and updating its position in the grid.

For this part of the project, you'll work in the sand_oo.py file. You've already written most of the code you'll need to make this version of the code work. It's just going to be organized a bit differently. Feel free to copy and paste code that you wrote in Part 1 or Homework 4 as needed. Let's get started.

Task 1 - Create a Sand class

You started this class in Homework 4. If you haven't completed Homework 4 yet, you should go do so.

At the top of the sand_oo.py file, add the code for the Sand class that you wrote in Homework 4. We often put class definitions in different files and then import them, but for this Project (and ease of grading), we'll have you put the class definition in the file where it will be used instead.

With the code you've already written added, you're ready to move on.

Task 2 - Adding and Removing Sand

Since the sand particles are actual objects instead of just strings stored in the grid, we need to do a little more to add and remove them from the simulation. In addition to storing reference to the Sand object in the grid, we will store references to all of them in a list as well. This will allow us to be more efficient in our updates of the grid but that's Task 3. For now we need to add code to add and remove the sand objects from the list and grid.

The sand_oo.py file has a list variable called all_sand. This is where we will store the list of all Sand objects. Additionally there are add_sand() and remove_sand() functions. Both of these functions take a reference to the Grid class as well as an x and y coordinate to either add or remove sand from. You won't ever explicitly call these methods, but you need to implement their functionality so that the GUI works properly.

In add_sand() you need to add functionality to:

1. Verify that the position specified by the x & y coordinates is empty in the grid. If not, exit.
2. Create a new Sand object and set its position to the supplied x and y coordinates.
3. Add the new object to the all_sand list.
4. Store a reference to the new object in the correct grid position

In remove_sand() you need to add functionality to:

1. Verify that there is a sand particle in the specified position. If not, exit.
2. Remove the reference to the Sand object from the grid.
3. Remove the Sand object from the all_sand list.

In some other languages, notably C++ you'd need to also delete the unused Sand object but Python will handle that for you as long as there are no longer any references to it in the Grid object or the all_sand list.

Task 3 - Moving the Sand

In the first part of this project, we iterated over all of the positions in the grid and if there was a sand particle, we moved it. In this version of the program, we don't have to do that. We can just iterate over the list of Sand objects. Then we know we will have visited each one once and only once and we also didn't have to access any of the grid positions that were empty or had rocks in them.

Again we are going to write the do_whole_grid() function. It should probably be better named move_all_sand() but in the interest of not rewriting the GUI interface code, we'll use the same function name.

In this version of the function, instead of looping over all the grid position, we just loop over all the sand particles. For each particle we call its move() method passing in the gravity() method as the physics to use. This will check each particle and move it if it can.

Iterating from bottom to top

Even though we don't need to iterate over the entire grid, we do need to visit the sand particles in a specific order. To see why, consider this setup:

Then, with gravity turned off, imagine we add a sand particle:

Then a second sand particle:

Finally, imagine we turn gravity on and catch the two sand particles while they're falling:

Wait what?! They have a space in between them! This happens because the upper sand particle appears in all_sand before the lower particle since it was added first, and so when gravity is evaluated for the first time, the upper particle has nowhere to go. The lower particle has not yet fallen and is in the way of the upper particle. But the lower particle itself can freely fall. Then, after the first frame (where the lower particle has fallen one square and the upper particle has stayed still), both particles fall unhindered until they hit the bottom. This is what creates the gap.

To fix this, we still have to visit the sand particles from bottom to top. That way, the lower particles can fall and get out of the way for the upper particles to fall as well (if possible). To do this, we can sort all_sand before iterating over it. Thus, the first line of do_whole_grid() is this:

all_sand.sort(key=lambda particle: (-particle.y, particle.x))

key is a function that applies a transformation to the objects in the list before sorting. First, each object's key is computed, then the list is sorted by comparing the keys to each other. In our case, the key is a tuple. The first element is the negative of the particle's y coordinate. It's negative so that when it's sorted in ascending order, the higher y values (which represent spaces that are lower in the grid) will be sorted before lower y values. The second element is the particle's x coordinate. This is just to standardize the order by making particles with lower x values appear before particles with the same y value and higher x values.

Task 4 - Interactive Testing

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

python sand_oo.py

Just like in part one, click the rock or sand buttons and then click the mouse button to scribble rocks or sand onto the world. If it is all working, great! If not, debug your code until it is.

Task 5 - Run the test cases

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

pytest test_sand_oo.py

This file contains a few tests that use all of your functions in sand_oo.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 2

Congratuations, you've now created a second version of your program in a different programming paradigm.

You'll submit your sand_oo.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.

Going Further

• In the do_move() function, how might you generalize it to move any type of particles and not just sand? Maybe you already did that in your implementation but if you didn't, what would you change?