Optimizing performance of randomly generated pygame maze game

Question

I made a random maze generator that is also playable. The performance is crap and I'd like to improve it. I'll be working on this for a few more days to make it run better myself, but just thought I'd leave this here if people want to help.

import random, sys, time, pygame
from fractions import gcd
from pygame.locals import *
from random import *
#End goal: Make a random labyrinth generator
#Generate random, completable walls
 #Have generate_maze be actually completable (Atm moves before assigning, which creates a lot of problems when moving out of already assigned tiles)
#This is stolen. Credit to John Millikin from stackoverflow.com and john-millikin.com. I'd never come up with a solution this compact
def gcd(a, b):
 while b:
 a, b = b, a%b
 return a
if input('Would you like to enable blind mode (recommended)? y/n >>> ') == 'y':
 blind_mode = True
else: blind_mode = False
tile_amount_multiplier = 1 #!!! NEVER SET ABOVE 2! IF YOU DO, THE RESULTS ARE TOTALLY INTENTIONAL GAME DESIGN THAT I JUST DON'T WANT YOU TO SEE
pygame.init()
window_resolution = 800, 600
window = pygame.display.set_mode((window_resolution[0], window_resolution[1]))
score = 0
stag_line_width = 5
line_width = stag_line_width
tile_width_height = gcd(window_resolution[0], window_resolution[1]) // 4 // tile_amount_multiplier
touched = []
wall_drawn = False
player_posx = 0
player_posy = 0
border = window_resolution[0]//100 *2 * tile_amount_multiplier -1, window_resolution[1]//100 *2 * tile_amount_multiplier -1
goal_posx = randint(0, border[0])
goal_posy = randint(0, border[1])
player_pos = player_posx, player_posy
goal_pos = goal_posx, goal_posy
keys = pygame.key.get_pressed()
tile_amount = window_resolution[0] // tile_width_height * (window_resolution[1] // tile_width_height)
def is_border(coordinates, direction):
 if direction == 'right':
 if coordinates[0] >= border[0]:
 return True
 else:
 return False
 elif direction == 'left':
 if coordinates[0] <= 0:
 return True
 else: 
 return False
 elif direction == 'up':
 if coordinates[1] <= 0:
 return True
 else:
 return False
 elif direction == 'down':
 if coordinates[1] >= border [1]:
 return True
 else: 
 return False
 else:
 print('You are safe from the end of the fucking world')
 return False
 print('Unexpected error in determining border location. You should probably fix that')
def is_wall(dire):
 if is_border(player_pos, dire) == False:
 for pos in no_wall_tiles:
 if (dire == 'right' or 'left') and ((player_pos[1] == pos[0][1]) or (player_pos[1] == pos[1][1])):
 if dire == 'right':
 if ((player_pos[0] == pos[0][0]) or (player_pos[0] == pos[1][0])) and (((player_pos[0] + 1) == pos[1][0]) or ((player_pos[0] + 1) == pos[0][0])):
 return False
 elif dire == 'left':
 if ((player_pos[0] == pos[0][0]) or (player_pos[0] == pos[1][0])) and (((player_pos[0] - 1) == pos[1][0]) or ((player_pos[0] - 1) == pos[0][0])):
 return False
 if (dire == 'up' or 'down') and ((player_pos[0] == pos[1][0]) or (player_pos[0] == pos[0][0])):
 if dire == 'up':
 if ((player_pos[1] == pos[0][1]) or (player_pos[1] == pos[1][1])) and (((player_pos[1] - 1) == pos[1][1]) or ((player_pos[1] - 1) == pos[0][1])):
 return False
 elif dire == 'down':
 if ((player_pos[1] == pos[0][1]) or (player_pos[1] == pos[1][1])) and (((player_pos[1] + 1) == pos[1][1]) or ((player_pos[1] + 1) == pos[0][1])):
 return False
 return True
 else:
 return True
def random_direction():
 digit = randint(1, 4)
 if digit == 1:
 return 'right'
 if digit == 2:
 return 'left'
 if digit == 3:
 return 'up'
 return 'down'
def generate_maze():
 wall_generated = False
 generation_visited = []
 global no_wall_tiles
 no_wall_tiles = []
 generation_pos = [randint(0, border[0]), randint(0, border [1])]
 generation_last_pos = []
 first_run = True
 while wall_generated == False:
 if tuple(generation_pos) in generation_visited:
 is_visited = True
 else:
 is_visited = False
 if is_visited == False:
 generation_visited.append(tuple(generation_pos))
 if first_run == False:
 no_wall_tiles.append((tuple(generation_last_pos), tuple(generation_pos)))
 direction = random_direction()
 generation_last_pos = generation_pos.copy()
 if is_border(tuple(generation_pos), direction) == False: #Checks for bounds
 if direction == 'right': #Checks every direction possible
 generation_last_pos = generation_pos.copy()
 generation_pos[0] += 1
 elif direction == 'left': # ^
 generation_last_pos = generation_pos.copy()
 generation_pos[0] -= 1
 elif direction == 'up': # ^
 generation_last_pos = generation_pos.copy()
 generation_pos[1] -= 1
 elif direction == 'down': # ^
 generation_last_pos = generation_pos.copy()
 generation_pos[1] += 1
 first_run = False
 if len(generation_visited) == tile_amount:
 print(no_wall_tiles)
 wall_generated = True
def is_touched(x):
 return x in touched
def draw_walls():
 opposite_cord = 0
 line_color = 100, 0 , 100
 if blind_mode == True:
 line_color = 0,0,0
 for z in range(window_resolution[0] // tile_width_height):
 global line_width
 coordinatex = window_resolution[0] // 10
 coordinatey = window_resolution[1] // 10
 posx = 0
 for x in range(coordinatex // 10 * 4 * tile_amount_multiplier):
 for i in range(1, 4):
 if i == 1:
 for coord in no_wall_tiles:
 if (x, z) in coord and (x, z+1) in coord:
 should_draw = False
 break
 should_draw = True
 if should_draw == True:
 pygame.draw.line(window,(line_color),(posx, opposite_cord + tile_width_height), (tile_width_height + posx, opposite_cord + tile_width_height), line_width)
 elif i == 2:
 for coord in no_wall_tiles:
 if (x, z) in coord and (x+1, z) in coord:
 should_draw = False
 break
 should_draw = True
 if should_draw == True:
 pygame.draw.line(window,(line_color),(posx + tile_width_height, opposite_cord), (posx + tile_width_height, opposite_cord + tile_width_height), line_width)
 posx += tile_width_height
 line_width = stag_line_width
 for y in range(coordinatey // 10 * 4 * tile_amount_multiplier):
 posx += tile_width_height
 line_width = stag_line_width
 opposite_cord += tile_width_height
 posx = 0
def is_victory ():
 if player_pos == goal_pos:
 return True
 return False
def draw_tileset():
 opposite_cord = 0
 for z in range(window_resolution[0] // tile_width_height):
 global line_width
 rect_color = 0,0,0
 rect_coror_perma = rect_color
 coordinatex = window_resolution[0] // 10
 coordinatey = window_resolution[1] // 10
 posx = 0
 for x in range(coordinatex // 10 * 4 * tile_amount_multiplier):
 if goal_posx == x and goal_posy == z:
 line_width = 0
 rect_color = (255, 0, 0)
 elif player_posx == x and player_posy == z:
 rect_color = (0, 0, 255)
 line_width = 0
 elif is_touched((x, z)):
 rect_color = 50,200,200
 line_width = 0
 pygame.draw.rect(window, rect_color, (posx, opposite_cord, tile_width_height, tile_width_height), line_width)
 rect_color = rect_coror_perma
 posx += tile_width_height
 line_width = stag_line_width
 for y in range(coordinatey // 10 * 4 * tile_amount_multiplier):
 if player_posy == z and player_posy == y:
 line_width = 1
 pygame.draw.rect(window,(rect_color),(opposite_cord, posx, tile_width_height, tile_width_height), line_width)
 posx += tile_width_height
 line_width = stag_line_width
 opposite_cord += tile_width_height
 posx = 0
#Dumb ass system to coordinates conversion guide: coord main_coordinate = main_coordinate, secondary coordinate = z
generate_maze()
draw_tileset()
draw_walls()
pygame.display.update()
while True:
 player_pos = player_posx, player_posy
 if is_victory() == True:
 score += 1
 print('Your score is now', score)
 player_posx = 0
 player_posy = 0
 goal_posx = randint(0, border[0])
 goal_posy = randint(0, border[1])
 goal_pos = goal_posx, goal_posy
 touched = []
 generate_maze()
 window.fill((0, 0, 0))
 draw_tileset()
 draw_walls()
 pygame.display.update()
 for event in pygame.event.get():
 if event.type == QUIT:
 print('You got a score of', score)
 pygame.quit()
 sys.exit()
 if event.type == pygame.KEYDOWN:
 if event.key == K_a and is_wall('left') == False:
 if player_pos not in touched:
 touched.append(player_pos)
 player_posx -= 1
 window.fill((0, 0, 0))
 draw_tileset()
 draw_walls()
 pygame.display.update()
 elif event.key == K_d and is_wall('right') == False:
 if player_pos not in touched:
 touched.append(player_pos)
 player_posx += 1 
 window.fill((0, 0, 0))
 draw_tileset()
 draw_walls()
 pygame.display.update()
 elif event.key == K_s and is_wall('down') == False:
 if player_pos not in touched:
 touched.append(player_pos)
 player_posy += 1
 window.fill((0, 0, 0))
 draw_tileset()
 draw_walls()
 pygame.display.update()
 elif event.key == K_w and is_wall('up') == False:
 if player_pos not in touched:
 touched.append(player_pos)
 player_posy -= 1
 window.fill((0, 0, 0))
 draw_tileset()
 draw_walls()
 pygame.display.update()

Answer 1

First of all, everything @Carcigenicate said.

Next:

1. Replace strings with constants:

   LEFT = "l"
   RIGHT = r"
   ...
   if dire == LEFT:
   

2. Replace a "complete" list of if statements on directions with a dictionary of lambda functions:

    _BORDER_CHECK = {
    RIGHT: lambda c, b: c[0] >= b[0],
    LEFT: lambda c, b: c[0] <= 0,
    ...
   }
   def is_border(coordinates, direction):
    return _BORDER_CHECK[direction](coordinates, border)
   

   Doing this lets you replace 4 comparisons with a single dictionary lookup, which is implemented in C.

3. Don't use the global symbols True and False if you can avoid them.

   You may not realize this, but Python treats those as symbols. They are not magically replaced in the compiler, as they are in C or Java.

   Older versions of Python would see "True" and do this:

   load the symbol string "True"
   go a global name lookup
   use the result
   

   Newer versions know about constants somewhat, so they do this:

   fetch the constant "True" (still a global name lookup)
   use the result
   

   Here's an example:

   >>> import dis
   >>> def f(x):
   ... if x == True:
   ... print("true")
   ... 
   >>> dis.dis(f)
    2 0 LOAD_FAST 0 (x)
    2 LOAD_CONST 1 (True)
    4 COMPARE_OP 2 (==)
    6 POP_JUMP_IF_FALSE 16
   

   On the other hand, if you skip using True and False, you can get better code, like this:

   >>> def f(x):
   ... if x:
   ... print("true")
   ... 
   >>> dis.dis(f)
    2 0 LOAD_FAST 0 (x)
    2 POP_JUMP_IF_FALSE 12
   

   That's literally 4 opcodes versus 2. Either 50% or 100% faster, depending on whether you work in marketing...

4. Use random.choice to pick a direction.

5. Use collections.namedtuple to create a Position class, instead of converting from list to tuple over and over again, and indexing all the time.

   Turn this code:

   if (dire == 'up' or 'down') and ((player_pos[0] == pos[1][0]) or (player_pos[0] == pos[0][0])):
   

   Into something like:

   if dire in (UP, DOWN) and (player_pos.x == pos[0].x or player_pos.x == pos[1].x):
   

6. Write a Position class method called random that takes border parameters and returns a random location therein. You can use that to get rid of the other calls to random.randint.

7. Promote all your "against the wall" code to either global constants (with NAMES_LIKE_THIS) or to an init function that you call from main.

8. Add the if __name__ == "__main__": block that (削除) PEP-8 mentions. (削除ここまで) is mentioned in the documentation.

9. In generate_maze, and other places, stop using lists for unique collections. Use set instead, which has \$O(1)\$ query time. (Lists have \$O(n)\$ query time for if x in list.)

• Aakoo7: Sorry for the late reply. I have a couple of questions: 1. #5 is very unclear to me. Could you rephrase the question or maybe provide an example? 2. What's a class method? I tried looking it up but I understand nothing. 3. In #9, do you mean sets? If not, I have no idea what you mean. 4. In #8, I could not find that block in the document. I'm pretty sure I misunderstood, so please clarify.
• aghast: I have edited the answer to address most of your questions. Sorry about the PEP-8 confusion-- it's in the documentation. Yes, I meant sets in #9, with the set keyword.

Answer 2

I'm going to just touch on style issues mostly.

if input('Would you like to enable blind mode (recommended)? y/n >>> ') == 'y':
 blind_mode = True
else: blind_mode = False

This could be made a little cleaner and more succinct. First, I'm personally not a fan of putting things on the same line as else:. In the vast majority of cases (here included), I think it hurts readability.

I'd suggest something closer to this though:

answer = input('Would you like to enable blind mode (recommended)? y/n >>> ')
blind_mode = answer.lower() == 'y'

• I'm using lower so the user can enter 'Y' as well, and it will still match.
• == already evaluates to a Boolean value. Using an if here to dispatch to True/False is redundant.

Along the same lines, you have this function:

def is_victory ():
 if player_pos == goal_pos:
 return True
 return False

The if is redundant:

def is_victory ():
 return player_pos == goal_pos

And also here:

line_color = 100, 0 , 100
if blind_mode == True:
 line_color = 0,0,0

Can be:

line_color = (0, 0, 0) if blind_mode else (100, 0 , 100)

And the bits like:

if coordinates[0] <= 0:
 return True
else: 
 return False

Can simply be:

return coordinates[0] <= 0

---

while wall_generated == False:

Would be arguably better as:

while not wall_generated:

If you ever write something == True or something == False, you're better off just writing something and not something. Comparing against True and False is again redundant.

---

Then directly below that you have:

if tuple(generation_pos) in generation_visited:
 is_visited = True
else:
 is_visited = False

This would be more succinct as:

is_visited = tuple(generation_pos) in generation_visited

I'd also rethink if the tuple conversion is necessary. You're constantly converting a list to a tuple just to do a comparison. I'd just keep it as a list instead of converting to the coordinates to a tuple, unless you really want/need to immutability benefits of tuples.

---

if (dire == 'right' or 'left') . . .
. . .
if (dire == 'up' or 'down') . . .

This code is actually broken. dire == 'up' or 'down' will never (ever) be false. It will always be True. See here for an explanation of why.

You want something like:

if (dire in {'right', 'left'}) . . .

{. . .} is a set, and in is doing a membership lookup.

---

from random import *

Try to limit (or outright avoid) using from . . . import * statements like that. Wildcard imports like that have two main problems:

• You're polluting the namespace. Because you're dumping all the names from the module into your file, that reduces what names you have available to you to use, and increases the chance of a name collision.
• It makes it harder for readers of your code to know where functions in your code come from, and what the purpose of the imported modules are.

I'd explicitly import exactly what you need:

from random import randint

Or, use a qualified import:

import random
. . .
random.randint(. . .)

Now it's clear what's being import, why you're using the random modules, and there is no longer any chance of a collision.

---

You have magic numbers floating around in a few places, like:

for y in range(coordinatey // 10 * 4 * tile_amount_multiplier):

Why 4? Why 10? Why not 40? If those numbers have well-defined purposes, ideally, they should have a name attached to them.

# At the top of your file
MY_MULT = 4 # These are poor names because I don't know their purpose
MY_OTHER_MULT = 10
. . .
max_coord = coordinatey // MY_OTHER_MULT * MY_MULT * tile_amount_multiplier
for y in range(max_coord):

When those variables are given proper names, it will be much easier for readers of your code to know what exactly is going on math-wise.

• Aakoo7: Sorry for the very late reply. Could you explain why the line_color = (0, 0, 0) if blind_mode else (100, 0 , 100) line works? Maybe how the computer interprets it? To me it looks like it'd produce an error, but it doesn't.
• Carcigenicate: @Aakoo7 if can take two forms: as a statement and as an expression. As a statement like you're use to, it takes the form if <condition>: <do_if_true> else: <do_if_false>. When used as an expression however (meaning, we want it to evaluate to a value), it takes the form <value_if_true> if <condition> else <value_if_false>.
• Carcigenicate: @Aakoo7 As another example, here's how a conditional expression (the second form of if) can be used to write an abs function: def abs(n): return n if n > 0 else -n. "The absolute value of n is n if n is greater than 0, else it's n multiplied by -1".