Code Project: Tower of Hanoi in Python
If you've already followed our previous code projects and are using the weather for wallpaper, enjoying talking RSS feeds, running your own Ruby-powered web server and chatting to your own IRC bot, here's something new to try: we're going to show you how to make a Tower of Hanoi game using Python.
If you've never played a Tower of Hanoi-type game before, here's a quick explanation: you have three stacks on to which you can place discs. At the start, all the discs are on the left-hand stack, and your goal is to move them all to the right-hand stack. But you can only move one disc at a time and you can't put a large disc on top of a small one. Each disc has a different size, and as you try to create the stack on the right, it needs to be ordered with the biggest disc at the bottom and smallest at the top.
Our version, imaginatively titled PyHanoi, will just use a stack of three discs in order to keep the code simple. Eventually we'll explore some ways to add more discs. It helps if you have a spot of prior programming experience though. We're not going to concentrate on theory, so we can get straight into the cool stuff!
Part 1: prepare the ground
As before, we'll be using Python and PyGame: a highly readable programming language coupled with a very useful set of multimedia routines. You can download the PyHanoi source code here: copy it to your home directory and extract it. In the resulting directory you'll find a subdirectory called 'data' containing image and music files to personalise for your own game; here's what you need to know.
- backdrop.jpg A 640x480 pixel image that will be used as the background for the game. If you change this, keep it quite light and low contrast so you can still see the discs.
- disc1.png, disc2.png and disc3.png The pictures for the discs. Because we'll be looking at the stacks from a side-on perspective, these images are rectangular. Open them in Gimp to find out the resolutions if you want to create new ones.
- highlight1.png and highlight2.png These are yellow and red outlined boxes: they will be drawn over one of the stacks, and can be moved when the player uses the left and right cursor keys. We'll use the yellow box when the user is just choosing a stack, and the red box when the user has hit Enter to select a stack.
- music.mod A MOD format music file (for example created in SoundTracker) that will be played in an endless loop.
So, feel free to customise any of these (or get someone else working on them while you study the code!). Or just stick with ours and start. Before we write any code, we need a brief plan for how the game logic is to work. In PyHanoi, the player will use the keyboard to highlight one of the stacks, and press Enter to select a disc. He/she will then highlight another stack and deposit the disc. If the move is valid, we update a 'moves' counter variable. So:
- Draw everything on the screen (backdrop, discs, score counter, highlight boxes to show current selection.
- Check for keypresses (left/right arrow keys to move the highlight, Enter to select a disc, and Esc to quit).
- Try to move a disc if the user has selected one stack and then another. If the move succeeds, increment the move counter.
- Go back to 1
See the Stacks, Meet Lists box below for information on how we're going to use a particular feature of Python to implement the Tower of Hanoi disc stacks. Once that's all clear, run the program (python pyhanoi.py) to see how our implementation works.
Stacks, meet lists
In a simple Tower of Hanoi game, you have three stacks and three discs in play, so at most you can have three discs on one stack. When you're moving discs around, you're always taking them off the top of one stack and dropping them on to the top of another stack - you can't insert them at any random point, and you're always dealing with the uppermost disc.
Now, Python offers a data type called a list, which lets us perfectly emulate the behaviour of Hanoi stacks, without fidding around in arrays. Consider this list:
foo = [1, 2, 3]
This sets up a list called foo with three elements (numeric variables). If we pop an element off the end of the list, like this:
a = foo.pop()
...it will now contain 3, and foo will contain [1, 2]. The list automatically resizes; we don't have an empty or null element at the end. Similarly, we can use the append feature of a list to add a number. Following on with foo:
Now foo contains [1, 2, 99]. These features make it very simple to create Hanoi-style stacks on to which we can append numbers representing discs (3 being the biggest disc and 1 the smallest).
To keep the code simple (and make it easier to expand), we'll create a list of three stacks, each of which contains a sub-list of the discs that are currently on the stack. Look at the picture: the first stack is stack, the second is stack and the third is stack. Each of these stacks contains a list of the discs in that stack; a full stack would contain [3, 2, 1], ie the largest disc (3) is at the bottom of the stack and the smallest (1) is at the top. We can pop the smallest disc off this stack and append it on to another one.
An example of the stacks in play, and the contents of their lists. You can see that the middle stack's list contains [2, 1] because it has the medium and small-sized discs.
Part 2: understand the code
PyHanoi includes a handful of functions (subroutines), so it makes more sense to follow the code as it's executed. At the start of pyhanoi.py we have:
from pygame import *
This has been the same in all of our projects, and tells Python that we want to use all facilities of the PyGame library (the asterisk acting as a wildcard). Next we have our functions:
def wait_for_key(): ... def draw_discs(): ... def try_move(first, second):
In order, these functions: pause the program, waiting for a keypress; draw the discs according to their current positions on the stacks; and attempt to move a disc from one stack to another within the rules of Hanoi. We've cut out the actual code for these routines here, because we don't need to understand how they work yet - we'll come back to them later on. Next, we set up a new game window:
init() screen = display.set_mode((640,480)) display.set_caption('PyHanoi')
This initialises PyGame, creates a 640x480 pixel window and sets that window's title. Now we need to load the images that we discussed earlier:
backdrop = image.load('data/backdrop.jpg') disc1 = image.load('data/disc1.png') disc2 = image.load('data/disc2.png') disc3 = image.load('data/disc3.png') highlight1 = image.load('data/highlight1.png') highlight2 = image.load('data/highlight2.png')
PyGame makes image handling a doddle: you just use the image.load() routine with a filename, and it returns a picture object that you can draw to the screen and manipulate. Along with our bitmap images, we also need a font to display the move counter and an error message when an invalid move is attempted:
movesfont = font.Font(None, 40)
This creates a new font object called movesfont, using the typeface 'None' at size 40. You could replace 'None' with a real font name, but that font may not be available on everyone else's machines - so it's easier to use 'None', which just defaults to a generic sans-serif font).
It's all a bit quiet so far, so let's get some music playing:
Here we're using the mixer module of PyGame to load and play a MOD file. The -1 parameter tells PyGame that we want to play the music in an infinite loop (well, until we exit the game).
So we've got our functions set up, the graphics are loaded and we're making sweet music. It's time for the core game logic.
stack = [[3, 2, 1], , ]
This line of code creates three lists, as denoted by square brackets, to represent the Hanoi stacks. At the start of a Hanoi game, all of the discs are on the first stack, which is why the first list contains [3, 2, 1] - 3 being the biggest disc, at the bottom, and 1 being the smallest, at the top (and therefore ready to pop off for a move). The other two lists are empty to reflect the empty stacks - which is why they're just .
We also need to set up some game variables:
moves = 0 position = 0 selected1 = -1 selected2 = -1
The first is our move counter, which totals up the number of disc moves that have taken place in the game. The second indicates the stack over which we'll draw our highlight box - the player will be able to move this with the left and right cursor keys. We have three stacks numbered 0, 1 and 2, so with position being 0 the highlight will start on the first stack. selected1 and selected2 are two variables that will store where the user has pressed enter to initiate a disc move.
At the very start of the game, and whenever the user isn't in the process of selecting stacks for a move, these variables will hold -1 to show that they don't point to any stacks.
Our next job is to kick off the main game loop:
quit = 0 while (quit == 0): screen.blit(backdrop, (0,0)) draw_discs() if selected1 == -1: screen.blit(highlight1, (position * 200 + 30, 250)) else: screen.blit(highlight2, (position * 200 + 30, 250)) movestext = movesfont.render('Moves: ' + str(moves), True, (255,255,255), (0,0,0)) screen.blit(movestext, (5,5)) display.update()
We create a new variable called quit and set its value to 0. The main game loop, starting on the 'while' line, will execute all of the indented code until quit changes to a value other than 0 (ie when Esc is pressed, as we'll see in a moment). At the start of the loop we want to draw everything, so first we 'blit' (render) the background image to the main window at position 0,0 - that is, the top-left corner. In PyGame, as with most graphical libraries, pixel co-ordinates start in the top-left and count from zero. So the bottom-right pixel of our game window is co-ordinate 639,479.
After drawing the background, we call our draw_discs() routine, which goes through the three stacks, finding out which discs are on those stacks, and rendering them at the appropriate places on the screen. Then we draw the highlight box: if the user is in the process of moving a stack, and has therefore pressed Enter once, we draw highlight2 (the red box) at the current location. Otherwise we just draw highlight1 (the yellow box). The position * 200 + 30 bit sets up the horizontal position on the screen of the box: so depending on the value of our position variable, it'll be drawn at 30, 230 or 430 pixels across (and always 250 down).
Then we generate an image called movestext by calling on our movesfont object created earlier. First, we join the word Moves: with our actual moves counter (converted to a string using the str() routine). Then, with 'True' we specify that we want the text to be anti-aliased, and supply two colour values (in this case white text on a black background). Finally we blit the freshly generated movestext image to the screen.
Note that, at this point, all of our drawing operations have been to a hidden graphics buffer for performance reasons. They don't actually appear on screen until we call display.update(). Then it's time to get keyboard input from the player:
ourevent = event.wait() if ourevent.type == KEYDOWN: if ourevent.key == K_ESCAPE: quit = 1 if ourevent.key == K_LEFT and position > 0: position -= 1 if ourevent.key == K_RIGHT and position < 2: position += 1
This is fairly straightforward stuff: we tell PyGame to wait for an event, which could be a screen refresh, mouse movement and so on. We're only interested in KEYDOWN events though - that is, the player hitting something on the keyboard. So once we have a keypress, we check to see what it is: if it's the Escape key, we set the quit variable we created earlier to 1, which will stop the main loop from executing.
If the player has pressed the left or right cursor keys, we need to update the position variable, which determines were we'll draw the highlight box. But we must also check to see that the player isn't trying to move the box too far, so the position > 0 and position < 2 confines the value of position to 0, 1 or 2 - in other words, the player can't move away from the stacks.
The next part is a bit more complicated. If the player hits the Enter key, it means that he/she wants to select a stack for a disc move operation:
if ourevent.key == K_RETURN: if selected1 == -1: selected1 = position
So, if the player hasn't selected anything yet (our selected1 variable is -1), then we set selected1 to the current position. However, if selected1 isn't -1, it means that the player has already hit Enter on a stack, and has thereby already chosen the source stack in a disc move operation. So in this case, the player is choosing the another stack - the target stack.
else: selected2 = position if selected2 == selected1: selected1 = -1 selected2 = -1
We update selected2 with the current position. But what if the player has selected the same stack as both the source and target of a disc move operation? Well, it means that nothing needs to be done, so we just reset selected1 and selected2 back to their original -1 values - meaning that we start over again.
If the player has chosen different stacks for the source and target, however, this bit of code is executed:
else: x = try_move(selected1, selected2) moves += x selected1 = -1 selected2 = -1
We call our try_move() function (explained in a moment) to see if we can move a disc from the stack specified in selected1 to the stack in selected2. The try_move() function will return 1 if the move was successful, and 0 otherwise. We update our moves counter accordingly, and then reset the values of selected1 and selected2 for a new disc move operation.
That's the end of the main code! It doesn't matter for completion of the puzzle; that's something you can add later on, perhaps with congratulations text and pictures. For now, we need to look at the functions defined at the start of the program. First up we have:
def wait_for_key(): ourevent = event.wait() while ourevent.type != KEYDOWN: ourevent = event.wait()
This simply pauses execution of the program until a key is pressed. To draw the discs:
def draw_discs(): offset = 50 for x in range (0, 3): if stack[x] == [3, 2, 1]: screen.blit(disc3, (offset, 400)) screen.blit(disc2, (offset+25, 380)) screen.blit(disc1, (offset+50, 360)) ... offset += 200
This function works through the stacks (in the for x in range block), and for each stack it checks the order of discs. For the first stack we draw the discs at 50 pixels across the screen using the offset variable, and when we move on to the next stack we add 200 to offset to move further across the screen. From large to small, the discs decrease in width by 50 pixels, hence the offset+25 and offset+50, which centres the discs on the stack.
Note that we haven't printed the complete code for this routine here: there are several checks and rendering operations for different types of disc layouts, but the code is very much the same so see pyhanoi.py for the lines that we've replaced with '...' here.
Finally, we have the most important routine of all - the code that performs the disc move operations. This takes two numbers as arguments, a source and destination stack:
def try_move(first, second): if len(stack[first]) == 0: return 0
So, the source stack is in the first variable, and the destination in second. We check to see if the length of the first stack is zero; if so, it means that there's nothing to pop off, so the move isn't valid and we just return back to the main code (0 means that no move occurred). But if the first stack isn't empty:
if len(stack[first]) > 0 and len(stack[second]) == 0: a = stack[first].pop() stack[second].append(a) return 1
We check to see if the destination stack is empty. If that's the case, we simply pop a number from the first stack and append it on to the second. Voila - a disc has moved! But what happens if neither stack is empty? We can't just pop from one and append onto another, because we need to stick within Hanoi rules and prevent the player from dropping a large disc on top of a small one.
else: if len(stack[first]) > 0 and len(stack[second]) > 0: a = stack[first].pop() b = stack[second].pop()
Here we use two temporary variables, a and b, to get the top most discs from each stack. Then:
if a > b: invalidtext = movesfont.render('Invalid move!', True, (255,255,255), (0,0,0)) screen.blit(invalidtext, (235,200)) display.update() wait_for_key() stack[first].append(a) stack[second].append(b) return 0
If the source stack is bigger than the destination stack, we print an error message, wait for the player to press a key, append the discs back on to their stacks, and quit out of the routine. Otherwise:
else: stack[second].append(b) stack[second].append(a) return 1
Remember that we popped a disc off the second stack so that we could make the size comparison? Well, here we put that disc back on to its stack, and then append the disc from the first stack, completing the move operation.
The finished product: PyHanoi may err on the side of the ugly duckling, but the algorithms are sound so you can build on them however you want.
Take it further
With PyHanoi we've made good use of the skills we've learned in previous coding tutorials, and tackled a new type of game design. To extend PyHanoi, an initial (and easy) mini-project would be to check for a completed puzzle. You could add the checks at the end of the code, then display some text or an image before waiting for a keypress and quitting out.
A more taxing enhancement would be to add more discs. Many computerised versions of Tower of Hanoi let you choose the number of discs at the start, and as you'd expect, with five discs on the starting stack it takes many more moves to complete the puzzle. You shouldn't need to modify the try_move() routine, but you'll have to rewrite the draw_discs() routine to handle more combinations of discs and make the game much more complex.
Let us know how you get on! If you have any questions about the code or want to share ideas with other readers, join us on the LXF website forums at http://www.linuxformat.com/forums - especially the Programming section.
First published in Linux Format magazine