Introduction to Data Structures and Algorithms
Assignment 1 Part B: Stacks
Resources and links
What To Hand In
Do not rename these files.
Sokoban.java (and any additional files you change or create for
Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.
Undo for Sokoban (Weight: 1/3)
Sokoban is a computer game of the puzzle variety that was created in
1980, and is available on many computer platforms. The game involves
controlling a worker in a warehouse who has to push boxes around the warehouse
to get them onto their destination spots. The worker can only push one
box at a time, and cannot pull boxes. It is easy for the player to get stuck in a
deadlock where it is no longer possible to move some of the boxes. Some of the
levels are extremely difficult to solve.
You can find out more about the Sokoban game from the web.
We have provided a simple implementation of the Sokoban game with four
levels. You can control the worker with buttons or keys.
Our implementation of Sokoban is frustrating because if you make a
mistake, you have to restart the game from the beginning. The game
desperately needs an undo
facility, so that you can undo actions if
you discover you have made a mistake. It should be possible to undo
all actions, all the way back to the beginning of a level.
For this assignment, you need to add an undo
should use a
that contains the history of actions since the
beginning of the current level. Every time the player performs a
(successful) action, the action should be recorded on the stack. Every
time the player clicks the
button, the program should pop the
top action from the history and "undo" it: if it was a move, the
worker should be moved back (in the opposite direction of the recorded
direction); if it was a push, the worker should be moved back, along
with the box that was pushed.
The amount of code you have to write is quite small, but to work out what is
needed and where to put it, you will have to read and understand a lot (if not
all) of the Sokoban program. This will not be trivial and you should expect to
spend time reading the program carefully.
To help you with implementing the undo functionality, we have provided
class for recording information about actions.
To implement the undo facility, you need
history field that contains a
- extra lines of code in the methods that perform the actions to create an
ActionRecord object and push it on the history stack.
- extra lines of code in the
load method to reset the history stack when the level is reset.
- an "Undo" button (plus optionally a key mapping from "u" to the undo method).
undo method that is called when the "Undo" button is clicked, which pops the top ActionRecord off the stack, and reverses the action.
Implement "Undo" for Sokoban.
Implement a "Redo" function. When the user presses "undo", the program
should not only pop the
that was on the
reverse it, it should also put the
stack. If the player pressed the "redo" button, it should pop the
stack, redo the action, and put it on the
The player could use this to undo all the actions from the end of a
game, and then replay all the moves.
One of the more frustrating parts of Sokoban is moving the worker from one side
of the puzzle to the other in order to get to the next box to push. An old
Macintosh version of Sokoban allowed the user to click the mouse on any free
cell. If there was a free path from the worker's current position to the new cell,
the program would find the path and move the worker automatically along the
Add this facility to Sokoban; it involves searching for a route
through the empty cells of the warehouse and then making the worker
step along the route.
A starting point is just to find straight paths; the full version
should find any free path.