# 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
strafe_speed   = 0.04
wall_height    = 1.27
resolution     = 6 #Pixels per line

texture   = pygame.image.load(os.path.join(path, 'Blood Wall Dark.bmp'))
texWidth  = texture.get_width()
texHeight = texture.get_height()
texArray  = pygame.PixelArray(texture)

HUD = pygame.transform.scale(HUD, (int(HUD.get_width() * (map_size / 64)), int(HUD.get_height() * (map_size / 64))))

old = 0

def create_level(file):
if file[-4:] != '.txt': file += '.txt'
f = open(os.path.join(path, file), 'r')

for i, line in enumerate(file):
file[i] = list(line.rstrip('\n'))
for j, char in enumerate(file[i]):
if char == ' ': file[i][j] = 0
else:           file[i][j] = int(char)
f.close()

mapBoundX  = len(file)
mapBoundY  = len(file[0])
mapGrid    = []

for i, line in enumerate(file):
mapGrid.append([])
for j, char in enumerate(file[i]):
if char != 0:
mapGrid[i].append(char)
else:
mapGrid[i].append(0)

return mapBoundX, mapBoundY, mapGrid

def Quit():
pygame.quit()
sys.exit()

def main():
mapBoundX, mapBoundY, mapGrid = create_level('Level')

posX, posY     = 8.5, 10.5
dirX, dirY     = 1.0, 0.0
planeX, planeY = 0.0, 0.66

while True:

#Input handling
for event in pygame.event.get():
if event.type == QUIT:
Quit()
return
if event.type == KEYDOWN:
if event.key == K_ESCAPE:
Quit()
return

#CEILING AND FLOOR
pygame.draw.rect(SCREEN, ceiling_colour, (0,                       0, WIDTH, (HEIGHT - map_size) / 2))
pygame.draw.rect(SCREEN,   floor_colour, (0, (HEIGHT - map_size) / 2, WIDTH, (HEIGHT - map_size) / 2))

for x in range(0, WIDTH, resolution):
#Initial setup
cameraX    = 2 * x / WIDTH - 1
rayPosX    = posX
rayPosY    = posY
rayDirX    = dirX + planeX * cameraX + 0.000000000000001 #Add small value to avoid division by 0
rayDirY    = dirY + planeY * cameraX + 0.000000000000001 #Add small value to avoid division by 0

#Which square on the map the ray is in
mapX = int(rayPosX)
mapY = int(rayPosY)

#The length of one ray from one x-side or y-side to the next x-side or y-side
deltaDistX = sqrt(1 + rayDirY ** 2 / rayDirX ** 2)
deltaDistY = sqrt(1 + rayDirX ** 2 / rayDirY ** 2)
zBuffer    = []

#Calculate step and initial sideDist
if rayDirX < 0:
stepX = -1
sideDistX = (rayPosX - mapX) * deltaDistX
else:
stepX = 1
sideDistX = (mapX + 1 - rayPosX) * deltaDistX

if rayDirY < 0:
stepY = -1
sideDistY = (rayPosY - mapY) * deltaDistY
else:
stepY = 1
sideDistY = (mapY + 1 - rayPosY) * deltaDistY

#Digital differential analysis (DDA)
while True:
if sideDistX < sideDistY:
mapX += stepX
side = 0
else:
mapY += stepY
side = 1

#Check if ray hits wall or leaves the map boundries
if mapX >= mapBoundX or mapY >= mapBoundY or mapX < 0 or mapY < 0 or mapGrid[mapX][mapY] > 0:
break

#Calculate the total length of the ray
if side == 0: rayLength = (mapX - rayPosX + (1 - stepX) / 2) / rayDirX
else:         rayLength = (mapY - rayPosY + (1 - stepY) / 2) / rayDirY

#Calculate the length of the line to draw on the screen
lineHeight = (HEIGHT / rayLength) * wall_height

#Calculate the start and end point of each line
drawStart  = -lineHeight / 2 + (HEIGHT - map_size) / 2
drawEnd    =  lineHeight / 2 + (HEIGHT - map_size) / 2

#Calculate where exactly the wall was hit
if side == 0: wallX = rayPosY + rayLength * rayDirY
else:         wallX = rayPosX + rayLength * rayDirX
wallX = abs((wallX - floor(wallX)) - 1)

#Find the x coordinate on the texture
texX = int(wallX * texWidth)
if side == 0 and rayDirX > 0: texX = texWidth - texX - 1
if side == 1 and rayDirY < 0: texX = texWidth - texX - 1

for y in range(texHeight):
#Ignore pixels that are off of the screen
if drawStart + (lineHeight / texHeight) * (y + 1) < 0: continue
if drawStart + (lineHeight / texHeight) * y > HEIGHT - map_size: break

colour = pygame.Color(texArray[texX][y])

#Darkens environment with distance
c = 255.0 - abs(int(rayLength * 32)) * 0.85
if c < 1:   c = 1
if c > 255: c = 255

#Different faces have different luminence to add to the 3D effect
if side == 1: c = c * 0.75

#Change the luminence if necessary
new_colour = []
for i, value in enumerate(colour):
if i == 0: continue #Exclude the alpha value
new_colour.append(value * (c / 255))
colour = tuple(new_colour)

pygame.draw.line(SCREEN, colour, (x, drawStart + (lineHeight / texHeight) * y), (x, drawStart + (lineHeight / texHeight) * (y + 1)), resolution)

#Render the HUD
SCREEN.blit(HUD, (0, HEIGHT - map_size))

#Mini map
for x in range(mapBoundX):
for y in range(mapBoundY):
if mapGrid[y][x] != 0: pygame.draw.rect(SCREEN, map_colour, ((x * (map_size / mapBoundX) + WIDTH) - map_size, y * (map_size / mapBoundY) + HEIGHT - map_size, (map_size / mapBoundX), (map_size / mapBoundY)))

pos_on_map = (posY * (map_size / mapBoundY) + WIDTH - map_size, posX * (map_size / mapBoundX) + HEIGHT - map_size)

#Draw player on mini map
pygame.draw.rect(SCREEN, (  0, 255,   0), pos_on_map + (2, 2))
pygame.draw.line(SCREEN, (255,   0, 127), pos_on_map, ((dirY + posY + planeY) * (map_size / mapBoundY) + WIDTH - map_size, (dirX + posX + planeX) * (map_size / mapBoundX) + HEIGHT - map_size))
pygame.draw.line(SCREEN, (255,   0, 127), pos_on_map, ((dirY + posY - planeY) * (map_size / mapBoundY) + WIDTH - map_size, (dirX + posX - planeX) * (map_size / mapBoundY) + HEIGHT - map_size))
pygame.draw.line(SCREEN, (255,   0, 127), ((dirY + posY + planeY) * (map_size / mapBoundY) + WIDTH - map_size, (dirX + posX + planeX) * (map_size / mapBoundX) + HEIGHT - map_size), ((dirY + posY - planeY) * (map_size / mapBoundY) + WIDTH - map_size, (dirX + posX - planeX) * (map_size / mapBoundY) + HEIGHT - map_size))

#Movement controls
keys = pygame.key.get_pressed()

if keys[K_w]:
if not mapGrid[int(posX + dirX * move_speed)][int(posY)]: posX += dirX * move_speed
if not mapGrid[int(posX)][int(posY + dirY * move_speed)]: posY += dirY * move_speed

if keys[K_a]:
if not mapGrid[int(posX + dirY * strafe_speed)][int(posY)]: posX += dirY * strafe_speed
if not mapGrid[int(posX)][int(posY - dirX * strafe_speed)]: posY -= dirX * strafe_speed

if keys[K_s]:
if not mapGrid[int(posX - dirX * move_speed)][int(posY)]: posX -= dirX * move_speed
if not mapGrid[int(posX)][int(posY - dirY * move_speed)]: posY -= dirY * move_speed

if keys[K_d]:
if not mapGrid[int(posX - dirY * strafe_speed)][int(posY)]: posX -= dirY * strafe_speed
if not mapGrid[int(posX)][int(posY + dirX * strafe_speed)]: posY += dirX * strafe_speed

#Look left and right
#Mouse input
difference = pygame.mouse.get_pos()[0] - (WIDTH / 2)
pygame.mouse.set_pos([WIDTH / 2, HEIGHT / 2])

#Keyboard input
if keys[K_q]: difference = -5
if keys[K_e]: difference = 5

#Vector rotation
if difference != 0:
cosrot = cos(difference * rotate_speed)
sinrot = sin(difference * rotate_speed)
old    = dirX
dirX   = dirX * cosrot - dirY * sinrot
dirY   = old  * sinrot + dirY * cosrot
old    = planeX
planeX = planeX * cosrot - planeY * sinrot
planeY = old    * sinrot + planeY * cosrot

pygame.display.update()
CLOCK.tick(FPS)

if __name__=="__main__": main()


Here are the two images that I'm using to test the program for those interested:

HUD.png

Blood Wall Dark.bmp

The file Level.txt contains 256 1's and spaces in a 16x16 configuration, with the 1's as the walls and the spaces as the gaps. But the code does work with any sized grid. The create_level() converts this file into a list.

Here is the contents of the file that I am using:

1111111111111111
1     11       1
1 111 11 11 11 1
1 1       1 11 1
1 1 1       1  1
1 1 111  11    1
1 1      1111  1
1   1  11   11 1
1 1         1  1
1 1    11   1  1
1 1  1   1 111 1
1 1   11     1 1
1 1        1 1 1
1 11 1     1   1
1    1        11
1111111111111111


The folder structure has the program in one directory, with the images and text file in a subdirectory called data like as shown:

• I haven't read all your code, but you're trying to implement a slow algorithm, without a GPU, in JITless, interpreted Python, without any libraries like NumPy that people use when they need to do serious math in Python. Of course it'll be slow. – user2357112 Apr 5 '17 at 18:22
• @user2357112 Is there a way of using the GPU in my computer to do this? – George Willcox Apr 5 '17 at 18:24
• OpenGL? DirectX? CUDA? There are Python bindings for all those, if you want to stick to Python. – user2357112 Apr 5 '17 at 18:30
• You should profile your code to find the bottlenecks: python -m cProfile mygame.py – Caridorc Apr 5 '17 at 20:15
• @Caridorc is there a way of doing this in Idle, or would I have to open the command line to do it? – George Willcox Apr 5 '17 at 20:17

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:

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

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

Then, for each column:

1. 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)

2. Compute the corresponding part of the texture:

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

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

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

4. 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)

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

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

6. 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))

• Thanks! This has really helped a lot, there are just a few things that I'd like to mention. I couldn't get your way of getting the frame rate to work properly, so instead I ran print(CLOCK.get_fps()) which worked perfectly. And the variable texStart doesn't exist, I assumed you meant yStart but this did not work either. And although it isn't as good to just blit the entire column, as you were only bliting the part on-screen, I just ran the last part of the code that you provided to get it to work. But the program now runs at 60 frames per second for me, and so I am pleased! – George Willcox Apr 7 '17 at 22:03
• Adding this to the code was enough to get it to work:column = texture.subsurface((texX, 0, 1, texHeight)) column = column.copy() column.fill((c, c, c), special_flags = BLEND_MULT) column = pygame.transform.scale(column, (resolution, int(lineHeight))) SCREEN.blit(column, (x, int(drawStart))) – George Willcox Apr 7 '17 at 22:04
• Sorry about the mistake — texStart should be colStart. For avoidance of doubt, I added the revised code to the post. The problem with your version (where you scale up to lineHeight) is that lineHeight can get arbitrarily large (when the wall is very close to the camera) and so the call to scale can take arbitrarily long (and use arbitrary amounts of memory). It's necessary to scale only the portion of the texture that is going to be drawn. – Gareth Rees Apr 8 '17 at 18:52
• You started the answer by a good paragraph (I experienced that statement when I worked with Python and OpenCV ) – Billal Begueradj Apr 18 '17 at 17:32