Title: Use Pygame to visualize bubble sort in Python, Part 2

[This program uses Pygame to animate item swapping for bubble sort in Python]

My post Implement bubble sort in Python explained the bubble sort algorithm. My next post, Use Pygame to visualize bubble sort in Python, Part 2, described the TextSprite class used by that example (and this one) to represent the items that the program animates.

This post describes the rest of the example. It explains how the program creates its TextSprite objects and how its event loop animates them.

This example uses techniques from my book Build Your Own Python Action Arcade! to animate the moving items. Read that book for all of the details.

Initialization

The following code shows how the main app class initializes Pygame.

def __init__(self, game_name, screen_size, max_fps, delay, bg_color): # Save game parameters. self.game_name = game_name self.screen_size = screen_size self.max_fps = max_fps self.delay = delay self.bg_color = bg_color # Initialize pygame. pygame.init() pygame.display.set_caption(f'{self.game_name}') self.surface = pygame.display.set_mode(self.screen_size) self.bounds = self.surface.get_rect() # Make initial sprites. self.make_sprites() # Start the event loop. self.event_loop()

This code saves various game values such as the game's name, screen size, and delay in seconds between bubble sort steps. It then initializes Pygame, sets the display surface's caption and size, and gets the surface's bounds. It then calls make_sprites to create the sprites and event_loop to run the algorithm simulation.

Creating Sprites

Here's the code the program uses to create its sprites.

def make_sprites(self): '''Make the sprites.''' self.all_sprites = [] # Define the values to sort. numbers = [3, 1, 2, 0, 4, 5, 6, 9, 8, 7] # Set rectangle size. wid = 50 hgt = 25 gap = (self.bounds.height - len(numbers) * hgt) / (len(numbers) + 1) spacing = hgt + gap # Set drawing parameters. font = pygame.font.SysFont('Calibri', 16) # Make sprites. self.items = [] cx = self.bounds.width / 2 cy = gap + hgt / 2 for number in numbers: center = pygame.math.Vector2(cx, cy) item = TextSprite(str(number), center, wid, hgt, font) self.items.append(item) self.all_sprites.append(item) cy += spacing # Make the Go button. button_wid = 50 button_hgt = 25 center = pygame.math.Vector2( self.bounds.width - gap - button_wid / 2, gap + button_hgt / 2) self.go_button = TextSprite('Go', center, button_wid, button_hgt, font, 'black', 'light green') self.all_sprites.append(self.go_button)

The code first creates the all-important all_sprites list. As you can probably guess from its name, this list contains all of the sprites. The program uses it to let every sprite update and draw itself.

The method then defines the numbers that it will sort. I was going to make this random, but decided to just hard-wire the numbers so the list would be unsorted just a little and provide a reasonable demonstration of bubble sort. Feel free to change the numbers if you like.

The code then sprites' dimensions so they all have the same size. The gap value is the spacing between the value sprites and divides up the available space not taken by the sprites.

The code creates a font and the loops through the numbers to create their sprites. Inside the loop, it updates the sprites' positions so they are laid out nicely.

After creating the number sprite, the code creates the Go button sprite in the window's upper right corner. It adds this sprite to all_sprites so it can draw itself and it also saves the sprite in self.go_button so we can later see if it is clicked.

Event Loop

The event loop is the heart of any Pygame program. It runs as long as the program is executing. Inside the loop, the program must look for events and take appropriate action.

The following code shows this program's event_loop method.

# Process events. def event_loop(self): # Don't move until the user clicks Go. self.next_action_time = time.time() + 1_000_000 clock = pygame.time.Clock() running = True while running: # Process system events. for event in pygame.event.get(): # Quit. if event.type == pygame.locals.QUIT: running = False break # Mouse down. if event.type == pygame.MOUSEBUTTONDOWN: # Get the mouse position. position = pygame.mouse.get_pos() # See if the Go button is at this position. if self.go_button.is_at(position): self.go_clicked() # See how much time has passed since the last update. elapsed_ticks = clock.tick(self.max_fps) elapsed_seconds = elapsed_ticks / 1000 # See if any sprite is currently moving. move_in_progress = \ any(sprite.is_moving() for sprite in self.all_sprites) # See if we are running the algorithm. if not move_in_progress and time.time() >= self.next_action_time: self.next_action_time = time.time() + self.delay # Take the next action. # Make all items light blue. for item in self.items: item.enabled_bg_color = 'light blue' # See if we've reached the end of the list. if self.i == len(self.items) - 1: # See if we made any changes. if not self.made_changes: # We made no changes on the last round. We're done. self.next_action_time += self.delay self.go_button.enabled = True else: # Otherwise start a new round. self.i = 0 self.made_changes = False else: # Not the end of the list. Compare items i and i + 1. # Make items[i] be yellow. self.items[self.i].enabled_bg_color = 'yellow' self.items[self.i + 1].enabled_bg_color = 'yellow' # If items[i] > items[i + 1], swap them. if self.items[self.i].text > self.items[self.i + 1].text: # Start them moving. self.swap_items(self.i, self.i + 1) # Swap them in the items list. self.items[self.i], self.items[self.i + 1] = \ self.items[self.i + 1], self.items[self.i] # Remember that we made changes. self.made_changes = True # Move to the next entry. self.i += 1 # Update the sprites. self.update_sprites(elapsed_seconds) # Draw the sprites. self.draw_sprites() # Update the display. pygame.display.update() # End the program. pygame.display.quit() pygame.quit()

The next_action_time value determines when the program can take the bubble sort algorithm's next step. The way I have it currently configured, bubble sort compares the next two items in its list every 0.5 seconds, however, it cannot take the next step until the previous step has finished. When the algorithm swaps two items, that swap may take longer than 0.5 seconds, so the program needs to wait until the swap is finished.

The first statement in the event loop sets next_action_time to the current time plus one million seconds so the program doesn't do anything until next_action_time changes. (You'll see that later. Spoiler alert: The Go button changes it.)

Next, the code creates a Clock that it uses to see how much time has elapsed. It then enters an infinite loop to process events.

The loop first uses pygame.event.get to read a Pygame event. These are things like the window trying to close, mouse clicks, or other window events. If the event is QUIT, code sets running to False so the outer infinite loop will end and then breaks out of the for event in pygame.event.get() loop.

If the event is MOUSEBUTTONDOWN and the mouse is over the Go button sprite, the code calls the go_clicked event handler described later.

After it checks for Pygame events, the code calls the clock's tick method, which returns the number of milliseconds (thousandths of seconds) that have passed since the last time the method was called. The self.max_fps parameter tells tick the maximum speed that we want the program to have. If you set this to 20 or 30, that should be fast enough for most games and animations. If the program can run faster, the tick method pauses to slow the program down. This prevents the program from running faster than is useful, which saves a bit of energy and more importantly prevents your CPU from heating up more than necessary. Redrawing the window 90 times per second won't make it look better and places undue strain on your CPU. (My system can become almost too hot to touch if the CPU is running full speed for too long.)

The code divides the number of milliseconds by 1000 to get the number of elapsed seconds.

Next, the method determines whether any of the sprites is currently moving. To do that, it uses any to see if a call to any of the sprites' is_moving methods returns True. (My previous post describes is_moving.)

The code then checks whether none of the sprites is currently moving and next_action_time has arrived. In that case, the code sets next_action_time to the current time plus delay so we won't start the action after this one until at least delay seconds have passed.

The code then performs the next step in the bubble sort algorithm. First, it sets the background color for all of the item sprites to light blue. It then checks to see if we have just finished a pass through the list. If we have, the code checks made_changes to see if we made any swaps during the previous pass. If we did not make any changes, the list is sorted so the code resets the next_action_time and enables the Go button sprite.

If we did make changes during the last pass, bubble sort needs to start a new pass. The code sets self.i to 0 to indicate the next item that should be tested. (This is analogous to the for i loop used by bubble sort in my previous post.) It also resets made_changes to False.

If we have not reached the end of the list, then we're in the middle of a pass through the items. In that case, the code sets the background color of the two items that it is comparing to yellow.

Next, the code performs the bubble sort test. It compares items i and i + 1. If they are out of order, the program calls the swap_items method (described next) to swap the items' sprites on the screen. It swaps the values in the items list ad sets made_changes to True so we remember that we made a swap.

After processing item i, the code increments self.i so we move to the next item during the algorithm's next step.

After it has finished taking the next algorithm step, the code calls update_sprites to let the sprites move if they should. It then calls draw_sprites to make the sprites draw themselves. Finally, it calls pygame.display.update to redraw the window so the user can see the results. (The update_sprites and draw_sprites methods just loop through the sprites and call their update and draw methods. They're really simple so I won't show them here. Download the example to see all of the glorious details.)

After the infinite while loop ends, the code shuts down Pygame.

swap_items

The following swap_items method makes two sprites swap places on the screen. This may seem like a complicated operation and the result on the window is fairly impressive, but it's actually pretty easy. Most of the work is done by the sprite class's move_to method that I described in the previous post.

def swap_items(self, i, j): '''Swap items i and j.''' # Animate the swap. item_i = self.items[i] item_j = self.items[j] p1 = item_i.center + pygame.math.Vector2(20, 0) p2 = item_j.center + pygame.math.Vector2(20, 0) p3 = item_j.center.copy() item_i.move_to([p1, p2, p3]) p1 = item_j.center - pygame.math.Vector2(20, 0) p2 = item_i.center - pygame.math.Vector2(20, 0) p3 = item_i.center.copy() item_j.move_to([p1, p2, p3])

The code first gets the two sprites that it will swap. It takes the first sprite's center position and adds a Vector2 object representing a move 20 pixels to the right. The result is the Vector2 named p1 that represents a point 20 pixels to the right of the first sprite's center position.

Next, the code performs a similar calculation to set p2 to the point 20 pixels to the right of the second sprite's center.

The code then copies the second sprite's center. The center property is a Vector2 object, so if you don't copy it, you get a reference to same object. When you update that object, both references see the change so, if you move one of the points, the other moves, too. In this example, that means the items don't end up in the positions where they should after the swap is finished. Try commenting out the .copy() part and see what happens. It's pretty confusing the first few times you do this while building a game until you learn the symptoms.

Having defined points p1, p2, and p3, the code passes them into the first sprite's move_to method. You may remember from the previous post that move_to saves the points and then moves the sprite through them when it later updates itself.

The method performs similar steps to move the second sprite 20 pixels to the left of the first sprite.

go_clicked

The last part of the program that I want to talk about is the go_clicked method that event_loop calls if you click the Go button. Here's its code.

def go_clicked(self): '''The user clicked Go. Run bubble sort.''' # Set up variables to start the algorithm. self.i = 0 self.next_action_time = time.time() # The next move should happen now. self.go_button.enabled = False

This method launches the bubble sort algorithm. It first sets self.i = 0 so the program starts the algorithm looking at the first item. It sets next_action_time to the current time so the algorithm starts right away, and it disables the Go button.

The next time the event_loop method runs its inner loop, it will start examining the items from item self.i and bubble sort will continue until the items are sorted. (You may want to go back and loop at event_loop again to see how setting self.i = 0 launches the whole process.)

Conclusion

Download the example to see additional details and to see bubble sort in action.

This may seem like a complicated example, but the pieces are reasonably simple if you take them one at a time. The TextSprite class provides move_to, update, and draw methods that control the sprite's movement and appearance. The main program creates the sprites and then its event_loop method processes Pygame events and lets the sprites do their thing. Those are the basic steps in any Pygame animation or game.

I feel the need for some graphics programs, so I'll take a break from this topic for a little while. I will get back to this kind of animation eventually, though, when I talk about the Tower of Hanoi puzzle.

My book Build Your Own Python Action Arcade! shows how to build a Blasteroids game that features a player's ship, bullets, rocks that spin and move, alien space ships, and more. Click here for a description, screen shots, and downloads. Click here to see the book at Amazon.

Be warned that the book is for beginners so its first third covers basic Python topics like loops, variables, and all the other stuff you may have learned long ago. Be prepared to skim or skip that material before you get to the game programming parts.