Raycasting algorithm in pygame

For the past week, I've been developing a simple raycasting algorithm. And I've finally managed to work out how to add textures and to get everything working.as I'd like it to. However, even at a rather low resolution of 5 pixels per vertical scan line, the program still runs incredibly slowly. It runs a bit better in fullscreen mode, as here the mouse input works properly, but it's still really bad.

It ran smoothly before I added the textures, and just had plain colour, even at a resolution of 1 pixel per vertical scan line. But the game is nearly unplayable now. So I want to know how I can optimize my code to make the program run faster?

I'd also like it if somebody would review the code normally so that I can improve it further.

Here is my code:

```
import sys, os, pygame, time
from pygame.locals import *
from math import *

####------Colours------####
BLACK = ( 0, 0, 0)
BLUE = ( 0, 0, 255)
BROWN = (139, 69, 19)
CYAN = ( 0, 255, 255)
DARKBLUE = ( 0, 0, 64)
DARKBROWN = ( 36, 18, 5)
DARKGREEN = ( 0, 64, 0)
DARKGREY = ( 64, 64, 64)
DARKRED = ( 64, 0, 0)
GREY = (128, 128, 128)
GREEN = ( 0, 128, 0)
LIME = ( 0, 255, 0)
MAGENTA = (255, 0, 255)
MAROON = (128, 0, 0)
NAVYBLUE = ( 0, 0, 128)
OLIVE = (128, 128, 0)
PURPLE = (128, 0, 128)
RED = (255, 0, 0)
SILVER = (192, 192, 192)
TEAL = ( 0, 128, 128)
WHITE = (255, 255, 255)
YELLOW = (255, 255, 0)
####-------------------####

pygame.init()

path = os.path.join(os.path.split(__file__)[0], 'data')

WIDTH = 1360
HEIGHT = 768
map_size = int((WIDTH / 680) * 64)

CLOCK = pygame.time.Clock()
FPS = 60
SCREEN = pygame.display.set_mode((WIDTH, HEIGHT), pygame.HWSURFACE|pygame.DOUBLEBUF|pygame.FULLSCREEN)

pygame.display.set_caption("Raycaster")
pygame.mouse.set_visible(False)

map_colour = MAROON
floor_colour = DARKBROWN
ceiling_colour = DARKRED

rotate_speed = 0.01
move_speed = 0.05

Python is not a fast language — it trades execution speed for flexibility and introspectability — and the kind of repetitive numerical computation involved in CPU rendering is pretty much the worst case for Python. It would make much more sense to use a 3D rendering toolkit like PyOpenGL.

But so long as we understand that this is just an exercise, there are bound to be some improvements we can make. An important step is to measure the framerate so that we can be sure we're making improvements and not just fiddling with code. Here's code for an exponentially weighted moving average:

average_frame = 1000 / FPS
while True:
    # ...
    average_frame *= 0.9
    average_frame += 0.1 * CLOCK.tick(FPS)
    print(1000 / average_frame)

On my computer I find that the game runs at about 18 fps.

The first step in speeding this up is to understand where all the time is going. In comments, Caridorc suggested that you might use the profiler to figure this out. But the structure of the code makes it clear that the biggest fraction of the runtime is going to be spent in this loop (over the pixels in a column in a texture):

for y in range(texHeight):

So instead of looping over the pixels in the column and drawing each pixel using pygame.draw.line, let's extract the column from the texture as a surface, colour-multiply it to apply the lighting effects, scale it, and blit it onto the screen.

This involves a couple of changes elsewhere in the code:

-
Convert the texture to RGB after loading it:

texture = pygame.image.load(os.path.join(path, 'Blood Wall Dark.bmp'))
texture = texture.convert()

-
Don't create the PixelArray (this locks the texture, and we won't be needing it any more).

Then, for each column:

-
Compute the part of the screen that we're going to draw to:

yStart = max(0, drawStart)
yStop = min(HEIGHT, drawEnd)
yHeight = int(yStop - yStart)

-
Compute the corresponding part of the texture:

pixelsPerTexel = lineHeight / texHeight
colStart = int((yStart - drawStart) / pixelsPerTexel + .5)
colHeight = int((yStop - yStart) / pixelsPerTexel + .5)

-
Extract the part-column from the texture using the subsurface method:

column = texture.subsurface((texX, colStart, 1, colHeight))

-
Take a copy (so we don't update the original) and multiply the colour using the fill method with BLEND_MULT:

column = column.copy()
column.fill((c, c, c), special_flags=BLEND_MULT)

-
Scale it to the height at which we're going to draw it using transform.scale:

column = pygame.transform.scale(column, (resolution, yHeight))

-
Blit it to the screen:

SCREEN.blit(column, (x, int(yStart)))

I find that this change more than doubles the framerate, to about 40 fps.

As written above, this change causes some ugliness in the rendering of walls near the camera because of the way the computation of yStart causes the texels to line up with the screen edge. This can be avoided by recomputing yStart and yHeight after colStart and colHeight, like this:

# Recompute to ensure columns are truncated smoothly.
yStart = int(colStart * pixelsPerTexel + drawStart + .5)
yHeight = int(colHeight * pixelsPerTexel + .5)

(This also has the nice side-effect of reducing the amount of "pixel creep".)

Now that we've eliminated the inner loop, it's no longer obvious where to look for further improvements. So now would be a good time to run the profiler. But I think this is enough for one answer.

Revised code

This replaces the for y in range(texHeight): loop:

# Darken environment with distance.
# Faces with side=1 are darker to add to the 3D effect
c = max(1, (255.0 - rayLength * 27.2) * (1 - side * .25))

yStart = max(0, drawStart)
yStop = min(HEIGHT, drawEnd)
pixelsPerTexel = lineHeight / texHeight
colStart = int((yStart - drawStart) / pixelsPerTexel + .5)
colHeight = int((yStop - yStart) / pixelsPerTexel + .5)

yStart = int(colStart * pixelsPerTexel + drawStart + .5)
yHeight = int(colHeight * pixelsPerTexel + .5)

column = texture.subsurface((texX, colStart, 1, colHeight))
column = column.copy()
column.fill((c, c, c), special_flags=BLEND_MULT)
column = pygame.transform.scale(column, (resolution, yHeight))
SCREEN.blit(column, (x, yStart))

StackExchange Code Review Q#159943, answer score: 8