Sokoban (Scaffolded Term Project)

This is part of the Term Project Assignment. See that document for more details.
  1. Sokoban Project Solo Rules
  2. Sokoban Project Starter Files
  3. Sokoban Project Videos (required viewing)
  4. Sokoban Project Hints
  5. Sokoban Project Grading Criteria
  1. Sokoban Project Solo Rules
    2.  To be very clear, because this project is so heavily scaffolded for you, note that:
    1. This project is 100% solo.
    2. You must work entirely alone on the entire project (except that you are always allowed to receive help from current 112 TAs and faculty).
    3. You may not work with anyone else on any part of this in any way.
    4. You may not use the internet for any help on any part of this.
    5. You may not use ChatGPT, CoPilot, or other LLMs on any part of this.
    6. You may not offer any help of any kind to anyone else doing this project.
    Any violation of these rules, no matter how seemingly minor, will result in failing the term project and the course. Of course, nobody wants that, so please be certain to follow these very-clear rules. Just work alone on this project and you will be fine. And of course, we are always here to help!

    Now, to restate this in the positive: this is a chance for you to have fun and demonstrate your hard-won coding skills by writing a really compelling app. Do your own work, enjoy the experience, and learn what you can from it!

  2. Sokoban Project Starter Files
    3.  Download the Sokoban Project starter files here.

  3. Sokoban Project Videos (required viewing)
    4.  To get started, first carefully watch all three of these videos:
    1. Sokoban Overview
    2. Sokoban Hints
    3. Sokoban More Hints + Grading Criteria


  4. Sokoban Project Hints
    5.
    1. Color Viewer Hints (for color_viewer.py)

      1. First see the getpixel and putpixel demo here.

      2. Use the PIL image to get the width, height, and pixel rgb values, and use the CMUimage to actually draw the image.

      3. Only convert the PIL image to a CMU Image once, in onAppStart and not repeatedly in redrawAll, or your app will badly lag.
    2. Sokoban Loader Hints (for sokoban_loader.py)

      1. Read these hints carefully and repeatedly (some may only start to make sense after you've made some progress on this).

      2. Run the test cases provided here by running this file directly. When you import this file into your sokoban_player, the test cases will not run.

      3. Look at the test function first! See how it returns this for a level: 
        [ [ 'w', 'w', 'w', 'w', 'w', 'w' ],
  [ 'w', '-', '-', 'p', '-', 'w' ],
  [ 'w', '-', 'r', '-', '-', 'w' ],
  [ 'w', 'w', '-', 'w', 'g', 'w' ],
  [ 'w', '-', 'b', 'v', '-', 'w' ],
  [ 'w', '-', '-', 'c', 'B', 'w' ],
  [ 'w', 'C', 'R', 'V', 'G', 'w' ],
  [ 'w', 'w', 'w', 'w', 'w', 'w' ] ],
        This is a 2d list of all the cell contents in the level, as such: 
        w: wall
p: player
r,g,b,v,c: block of the given color (red, green, blue, violet, cyan)
R,G,B,V,C: target of the given color (red, green, blue, violet, cyan)
-: empty cell
        This 2d list matches level3-8x6.png

      4. If you would rather write sokoban_player first, or if it helps with debugging sokoban_player, we have provided a function loadHardcodedLevel(). loadLevel(file), which is included in the starter code, returns the results of loadHardcodedLevel() if file is None.

        This returns a playable level with no images, so your sokoban_player file would draw non-image shapes for the walls, blocks, player, etc. Again, this can be helpful for debugging.

      5. The main function here, loadLevel(file), takes a file which is a path to a lightly-edited image of a level from the online Sokoban game. It returns a tuple of the level (using the 2d list format just described above) and an images dictionary that maps the different level content types to their corresponding sub-image in the level's image. The test function only tests the 2d list and not the images dictionary, but the images dictionary is needed by the sokoban_player.

      6. Do all your work with PIL images. Only the images dictionary returned from loadLevel should contain CMUImages (since these images will be drawn, and only drawn).

      7. Use image.width and image.height to get the PIL image's dimensions.

      8. For each cell, get its sub-image using image.crop((left, top, right, bottom)).

      9. Actually, we found that the edges of each cell sometimes included pixels from a neighboring cell. To avoid this, we just ignored any pixels within a margin of 3 of each edge of the cell.

      10. Get the dimensions of the board (rows-by-cols) by the level's file name.

      11. Use the color_viewer to complete the COLORS map. Choose your colors well.

      12. To check if a given pixel is a specific color, compare the rgb values of the pixel to the color. Think of (r, g, b) as a point in three dimensions (like (x, y, z)), and use the Euclidean Distance (our normal distance function, only in 3 dimensions rather than 2). Since colors in images vary in rgb by a bit, consider the two a match if this distance is reasonably small (say, within 50).

      13. Use the number of matching pixels to various colors to determine the contents of a cell. For example, we found that if the count of pixels matching blue is > 4000, then we could safely conclude the cell holds a blue block. This is true for any of the 4 level image files.

      14. Since analyzing images can be slow, we will cache the results of loadLevel(file) so the next time we call it will be very fast (this is a required feature).

        We will cache our results in a file. So loadLevel should follow the following steps:
        • check to see if we've saved the results of analyzing this image
        • if we have, read the results from a file and return them
        • if we haven't, analyze the image, write the results to a file, and return the results

        For saving data to files, you should use the pickle module. We have provided readPickleFile and writePickleFile for you. You should use these functions. Importantly, the contents in writePickleFile do not have to be a string. They could, for example, be a tuple of a 2d list and a dictionary mapping strings to CMUImages (how handy!).

      15. If you have a bug in your loadLevel function, or in any case you change how you pickle, then be sure to delete all your old pickle files!
    3. Sokoban Player Hints (for sokoban_player.py)

      1. If your app is called with useHardcodedLevel=True, just call loadLevel(None) (see sokoban_loader hints for details).

      2. We recommend that you make your window 600x600 and adjust each level to fit in that window.

      3. Also, assume that each cell's image is the same size, and that they are all squares (they aren't, actually, but they are close enough that this works well enough, and it simplifies your app's logic).

      4. To resize an image, just set its width and height in drawImage.

      5. We recommend that you store the game's state as such:
        • Use app.playerRow and app.playerCol to store the player's position.

        • Use app.board to store the walls and blocks. That is, it is a 2d list where each cell contains one of 'wrgbvc-'. So if app.board[1][2] == 'r', then there is a red block at row 1, col 2.

        • Use app.targets to store the targets. That is, it is a 2d list where each cell contains one of 'rgbvc-'. Note: this is not a typo: even though targets are uppercase in the level map, here we store them in lowercase to make it easier to test if a block is in the matching target. So if app.targets[1][2] == 'r', then the there is a red target at row 1, col 2. So if the board contains a red block at that location, then that red block has reached a red target! Woohoo!

      6. We found it was useful to store each move in app.moves. Then, to undo a move, instead of directly undoing it, we rather just reset the game and then did all the moves up to and not including the last one.
    4. Additional Hints

      5. We added these hints after the first two videos were cut, based on the feedback from our amazing TAs.

      1. We moved the hints from the headers of .py files into the html writeup (here!).

      2. We suggest you start by first playing the game yourself here:
        https://www.sokobanonline.com/play/community/bjertrup/sokomind-plus/123103_erim-sever-numbered-01.

      3. Because this projects uses local image files and pickle files, it must be done on your laptop (say, with VS Code) and not in CS Academy. Here are some handy guides to help you get this set up:

      4. You can make the graphical apps (color_viewer and sokoban_player) whatever size works best on your screen.

      5. In both the color_viewer and the sokoban_loader, we suggest that you immediately convert images that you open to RGB. That is, instead of something like this: 
        Image.open(path)
        do this: 
        Image.open(path).convert('RGB')

      6. Note that we made this change ourselves in the color_viewer only after the videos were made. Thus, color_viewer in the video includes an alpha value (the fourth value after the r,g,b values) which you can ignore (as we said in the video) and which you will not even see if you first convert your image to 'RGB' as just noted.

      7. In the file sokoban_loader.py, for the function loadHardcodedLevel, we showed it returning an empty list. However, it should return an empty dictionary. We have updated the starter file accordingly, changing this: 
        images = [ ]
        to this: 
        images = dict()

      8. We noted that you can scale your images in drawImage. This is true, but if you prefer, you can scale them earlier, using PIL, and then convert the already-scaled images to CMUImages. Your choice.

      9. We recommend that you wait to implement pickling until you are confident that your sokoban_loader is otherwise fully working.

  5. Sokoban Project Grading Criteria
    6.  To pass the code and UX portions of tp3 with at least a C, you do not have to match the solution video exactly to the pixel, you just have to be very close, and at least include all these features:

    • Color Viewer
      • Show RGB values as you move mouse over the image,
      • Show the x,y position over the image, where (0,0) is the image's left-top corner and not the canvas's.

    • Sokoban Loader
      • Pass the test function we included in the starter file.
      • Implement pickling properly (to speed up repeated loading of the same level).

    • Sokoban Player
      • Properly load, display, and play all 4 levels without hardcoding.
      • Show some kind of "you win" screen (it can say whatever you wish, with whatever graphics you wish) when the user solves a level.
        • So we can easily test this functionality, also add a feature (for our graders) where if the user presses 'a' on level 1, the level is 'almost solved', so it is one move away from being solved. This is only for level 1. Also, you can hardcode this particular feature any way you wish.
      • Undo move (including repeatedly undoing all the way back to the start of the level, and then not crashing if they try to undo when there are no moves made yet).
      • Load, display, and play the hardcoded level without images. You can display the player, blocks, and targets in any reasonable manner in this case.

      To pass with at least a B, you would need to implement some additional features. For example, you could implement all the smaller features below plus one medium-to-larger feature. If those additional features were completed to a sufficiently high standard, that could perhaps qualify your project for a B. There is no specific set of features that are guaranteed to get a given grade (such as a B). It all depends on the quality of the features, as per the term project writeup.

      With that, here are some additional features you might consider adding:

      • Smaller Features
        • Steps counter
        • Timer
        • Sounds
        • Title Screen with level selection (say with level thumbprint previews)
        • High score list

      • Medium-to-larger Features
        • Redo (so you can Redo moves that you Undo)
        • Change player's image direction by rotating/flipping it
          • Do this with PIL functions for some credit
          • Do this without PIL functions (except get/putpixel) for more credit
        • Save partially-solved levels and restore them so you can keep playing later.
        • Make player's clothes color settable
          • So you would use getpixel/putpixel to change the clothes color based on user preference.
        • Custom Level Editor
        • A File Explorer, so the user can select a new screenshot to play.
        • Use BFS to find a minimal-move solution.
          • Even better, use A* (A-star).
          • Note: this particular feature is challenging!

This was not an exhaustive list. There are many more creative features that you could add.

Good luck, and have fun!