CS101 - Assignment 10

Due: Monday 2018-05-14 11:59p

Objectives

Integrate several topics learned over the semester
Learn to work with a large program
Apply run-time analysis techniques to code

Prelab

Your prelab this week is to prepare for working on the Sokoban programming assignment. Complete the following three tasks before coming to lab on Thursday/Friday:

Read through this entire homework write-up.
Download the file cs101_hw10_sokoban.zip and double-click to open it. In it, you will find the starter code you will be working with as well as a folder called levels. This contains all of the various levels in text file format. You will need to keep this folder in the same folder as your Python file so that the loader can find the level files.
Read through the starter code and try to understand it. The code includes a large number of comments to help guide you through this process.

Part 1

The main part of this assignment is the Sokoban programming assignment described here.

This problem involves understanding and modifying an object-oriented program. It will give you an opportunity to apply what you've learned about object-oriented programming by creating a working game. You are welcome and encouraged to work with a partner on this single programming problem. One of you should turn it in (using the submit script); be sure to indicate both names.

PyProcessing

pyProcessing is a Python library we'll use for graphics in Python. The pyProcessing tutorial and quick reference may be helpful, as will the O-O examples we developed in class. pyProcessing emulates the functionality of Processing, a programing language (of a sort) designed to make it easy to program for the visual arts. For the most part, we can use any of the functions that are available in Processing. So, you may want to see the Processing reference guide and tutorials for extra background.

Sokoban

In this homework problem you will implement the game of Sokoban. The game itself is fairly simple: each level is a simple maze with a couple of objects scattered about it (in our case, we will call them boxes). The goal of the game is to push the boxes to specially designated ‘goal’ locations in the maze. When all goal tiles are covered with boxes, you advance to the next level. The challenge of the game is that the boxes are really heavy, and you can only move them by pushing. In fact they are so heavy that you can only push one at a time. If you push one box into another one, it will no longer move. So you have to be a little canny about how you move the boxes around. You can play the game at sokoban.info, which has the classic levels that we are using for our version (there are many other implementations out there).

Implementing this from scratch would be a bit daunting, so we'll provide you with a substantial amount of the code, leaving it to you to fill in some of the details. Here is what you need to do (work in the order specified below and test frequently):

Read through the code and try to understand it. The code includes a large number of comments to help guide you through this process. Pay particular attention to how things get drawn and the mechanics of moving pieces around on the board.
Create the visual look of the game by adding code to the draw() functions for the tiles, boxes and the player. Make sure that you can easily distinguish between open tiles, walls, boxes, and the player.
Implement the isFree() and getNeighbor() functions of the Tile class.
Write the movePiece() method on the Board class.
Edit the code so the player object can be controlled by the arrow keys. This involves editing the move() function of the player and the keyPressed() method of the board.
Change the player’s move() function so that it shoves any obstructions out of the way if possible.
Implement the levelComplete() function and edit the keyPressed() function so that it calls levelComplete() and advances to the next level if all boxes are on goals.
Implement at least one cool thing (see below) of your choice.

Cool Things

"Cool things" are elements that you add to the program that go above and beyond what is asked for in the assignment. Here's a short list of some, but do not feel obligated to be limited by these. You also do not need to follow the below cool things to the exact letter; if you like an idea, but want to do it a little differently from how it is described, that is fine.

IMPORTANT: The one requirement is that you include in a comment at the top of your Python file a list of the cool things that you added to the assignment.

ADVICE: Make copies of the file as you make changes. In particular, before you start adding in cool things, save a clean copy of your working game somewhere safe so you can always go back to that.

Here are some potential cool things:

Clean up the map.: At the moment, the code rather naively places tiles outside of the walls. Figure out how to edit the loadLevel() function so that there are no tiles outside of the walls.
Add textual display to the windows: Dig around online for ways to add text with pyProcessing and add some indicator of the current level.
Add level scoring.: Sokoban is typically scored based on the number of moves that the player makes to complete the level. This should be combined with textual display.
Improve the graphics: Make the player more complex so we can tell which way it is heading. Make the boxes more interesting. Change the colors of the boxes when they are being pushed or when they are “home”
Add undo: Allow the player to type ‘u’ to undo the last move.
Support arbitrary numbers of undos: Keep track of every move the player makes and every move the boxes make and allow the user to undo back to the original state.
Keep track of player progress across runs: Use a file to keep track of where the player is at the end of the game. When a new game is started, give the player the option to start at the beginning or on the level they were on when they left off.
Keep track of multiple players: Have the user enter a player name at the start of the game. Store their progress in a file and display a list of the top 10 scores on demand.
Detect when a level has become unsolvable: It is easy to make a level insolvable. Detect when this happens and report this to the player somehow. This could be textual feedback or it could be something like changing the color of trapped boxes.
Write a level solver: This is a real challenge. Write a program that takes over for the player and solves the level from the current state.

For this portion of the assignment, turn in your version of sokoban.py. You do not need to turn in your levels folder.

Update all comments and add your own. Any new functions should have appropriate comments. If you change one of the given functions, update the comments to reflect the changes (this includes adding your name at the top of the file). Also, do not forget to list the cool thing(s) in the header comment.

Part 2

Answer the following written questions on complexity and submit in a file called username_hw10.pdf.

Suppose that an algorithm that is O(n^2) takes 2 seconds on your current computer to solve a problem in which n is 1,000. About how long will it take your computer to solve the problem when n is 10,000?

Consider each of the following code snippets.

(a)
n = 5
for i in range(n):
    for j in range(n):
        print('X', end=' ')
    print()

(b)
n = 5
m = 10
for i in range(n):
    for j in range(m):
        print('X', end=' ')
    print()

(c)
n = 5
for i in range(n):
    for j in range(i):
        print('X', end=' ')
    print()

For each code snippet (a)-(c) above, answer these two questions:

How many 'X's will this code print?
What is the Big-O running time of this code? Give an expression in terms of n or in terms of n and m.

Turning in your work

Be sure to comment your code. The top of each file should include a multiline comment that lists your name, the name of the assignment, and the date, at a minimum. Each function should also include a multiline comment at the beginning of the body of the function describing what the function does.

Submit 2 files using the CS 101 submit script: (1) your Python file sokoban.py; and (2) a PDF username_hw10.pdf with answers to the written questions. The Sokoban portion of the assignment may be done with a partner (only one of you needs to upload the Sokoban program code; include both names in a comment at the top of the file).