# Optimizing a raycasting/voxelspace algorithm in Pygame

In the past three days, I've been developing a simple raycasting algorithm. I've made the renderer work as I'd like to. However, it is extremely slow (5 frames per second) because of two things (as far as I know).

1. Finding the values of a pixel independently many times, and often it lands on the same pixel.
2. The large amount of times the code is run.

I'm aiming for speed but the only programming language I have experience in is Python. What are the optimizations I can make to this code? Which other libraries can I use that are faster than Pygame or PIL for this use? Also, how do I make the pixel coordinates loop (-1 = 1023) without if statements to prevent the game crashing if near the boundary?

from PIL import Image
import pygame

cdef enum resolution:
resX=720
resY=540
qresX=180
cdef extern from "math.h":
double sin(double x)
double cos(double x)

screen = pygame.display.set_mode((resX,resY))
pygame.display.set_caption('VoxelSpace')

im=Image.open("data/height.png")
col = Image.open("data/colour.png")
rgb_im = col.convert('RGB')

cdef unsigned char uu
cdef unsigned char height
cdef unsigned char prevHeight
cdef unsigned char heightBuffer
cdef float t
cdef float foga
cdef unsigned char fogb
cdef int x
cdef int y
cdef unsigned char r
cdef unsigned char g
cdef unsigned char b
cdef int pX
cdef int pY
cdef float pAngle
cdef unsigned char u
cdef int v
cdef unsigned char h

def Render(pX,pY,pAngle):
screen.fill((100,100,255))
heightBuffer=disp[pX,pY]
for v from -qresX <= v < qresX by 1:
prevHeight=0
for u from 1 <= u < 124 by 1:
if u<30:
uu=u
elif u<60:
uu=u*2-45
else:
uu=u*4-180
foga=u/60.0+1
fogb=u/2

t=v/float(qresX)+pAngle
x=int(sin(t)*-uu+pX)
y=int(cos(t)*-uu+pY)
height=(float(disp[x,y]-heightBuffer-10)/uu*101+135)*2
if height>prevHeight:
r,g,b=rgb[x,y]
pygame.draw.line(screen,(r/foga+fogb,g/foga+fogb,b/foga+u) , (2*(qresX+v),resY-prevHeight),(2*(qresX+v),resY-height),2)
prevHeight=height
pygame.display.flip()



I am compiling this code as a .so (via cython) and running it from another .py. Is it faster if I simply use PyPy instead?

• cdef is exotic and fragile. At this point, why aren't you just using C? Commented Oct 10, 2019 at 2:05
• Because I have no knowledge in C Commented Oct 10, 2019 at 2:12
• Perhaps it's time to learn :) it'll buy you a lot more efficiency, at the cost of more awkward libraries. Commented Oct 10, 2019 at 2:13
• @Reinderien Let's be honest, C is a programming language for masochists ;-) A little bit awkward, and lots of opportunities to hurt yourself. Commented Oct 10, 2019 at 7:22
• You can find them on this website: github.com/s-macke/VoxelSpace Scroll down until you find the MAPS section, and you can download heightmaps there Commented Oct 13, 2019 at 7:31

Below is the code I have come up with. It basically follows the code used for the web demo in the github repo you had linked to. I will add some explanation to this answer on how I had made some basic optimizations to better fit cython's memoryview model as well as potential room for improvement later, but figured I should post the code now as it might be another few days before I can get back to it.

cimport libc.math as c_math
from libc.stdint cimport *
import math
import numpy as np
from PIL import Image

import os
os.environ['PYGAME_HIDE_SUPPORT_PROMPT'] = "hide"
import pygame
import sys
import time

ctypedef struct Point:
float x
float y

ctypedef struct Color:
uint8_t r
uint8_t g
uint8_t b

cdef class Camera:
cdef:
public int x
public int y
public int height
public int angle
public int horizon
public int distance

def __init__(self, int x, int y, int height, int angle, int horizon, int distance):
self.x = x
self.y = y
self.height = height
self.angle = angle
self.horizon = horizon
self.distance = distance

cdef class Map:
cdef:
int width
int height
int shift
const uint8_t[:, :, :] color_data
const uint8_t[:, :] height_data

def __init__(self, int width=1024, int height=1024, int shift=10):
self.width = width
self.height = height
self.shift = shift
self.color_data = None
self.height_data = None

cdef object image
image = Image.open(color_path).convert("RGB")
self.color_data = np.asarray(image)

cdef object image
image = Image.open(height_path).convert("L")
self.height_data = np.asarray(image)

cdef class Window:
cdef:
int width
int height
str title
object screen
object clock
int32_t[:] hidden_y
uint8_t[:, :, :] output
Color background_color
Camera camera
Map map

def __init__(self, int width, int height, str title):
self.width = width
self.height = height
self.screen = pygame.display.set_mode((self.width, self.height))
self.title = title
pygame.display.set_caption(self.title)
self.hidden_y = np.zeros(self.width, dtype=np.int32)
self.output = np.zeros((self.width, self.height, 3), dtype=np.uint8)
self.clock = pygame.time.Clock()

def set_background_color(self, uint8_t r, uint8_t g, uint8_t b):
self.background_color.r = r
self.background_color.g = g
self.background_color.b = b

def set_camera(self, Camera camera):
self.camera = camera

def set_map(self, Map map):
self.map = map

cdef void draw_background(self):
cdef int x, y
for x in range(self.width):
for y in range(self.height):
self.output[x, y, 0] = self.background_color.r
self.output[x, y, 1] = self.background_color.g
self.output[x, y, 2] = self.background_color.b

cdef void draw_vertical_line(self, int x, int y_top, int y_bottom, Color *color):
cdef int y

if y_top < 0:
y_top = 0
if y_top > y_bottom:
return
for y in range(y_top, y_bottom):
self.output[x, y, 0] = color.r
self.output[x, y, 1] = color.g
self.output[x, y, 2] = color.b

cdef display(self):
surf = pygame.surfarray.make_surface(np.asarray(self.output))
self.screen.blit(surf, (0, 0))
pygame.display.flip()
pygame.display.set_caption("{0}: {1} fps".format(self.title, <int>self.clock.get_fps()))

def render(self):
cdef:
int map_width_period = self.map.width - 1
int map_height_period = self.map.height - 1
float s = c_math.sin(self.camera.angle)
float c = c_math.cos(self.camera.angle)

float z = 1.0
float delta_z = 1.0
float inv_z
Point left, right, delta
int i
int map_x
int map_y
int height_on_screen
Color color

for i in range(self.width):
self.hidden_y[i] = self.height
self.draw_background()
while z < self.camera.distance:
left = Point(
(-c * z) - (s * z),
(s * z) - (c * z),
)
right = Point(
(c * z) - (s * z),
(-s * z) - (c * z),
)
delta = Point(
(right.x - left.x) / self.width,
(right.y - left.y) / self.width,
)
left.x += self.camera.x
left.y += self.camera.y

inv_z = 1.0 / z * 240
for i in range(self.width):
map_x = <int>c_math.floor(left.x) & map_height_period
map_y = <int>c_math.floor(left.y) & map_width_period
height_on_screen = <int>((self.camera.height - self.map.height_data[map_x, map_y]) * inv_z + self.camera.horizon)
color.r = self.map.color_data[map_x, map_y, 0]
color.g = self.map.color_data[map_x, map_y, 1]
color.b = self.map.color_data[map_x, map_y, 2]

self.draw_vertical_line(i, height_on_screen, self.hidden_y[i], &color)
if height_on_screen < self.hidden_y[i]:
self.hidden_y[i] = height_on_screen
left.x += delta.x
left.y += delta.y

delta_z += 0.005
z += delta_z

self.display()
self.clock.tick(60)#60 fps

pygame.init()

window = Window(width=800, height=600, title="VoxelSpace")
window.set_background_color(144, 144, 224)

map = Map()
window.set_map(map)

camera = Camera(x=512, y=800, height=78, angle=0, horizon=100, distance=800)
window.set_camera(camera)

while True:
#win.handle_input()
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_UP:
print("up")

camera.y -= 1
window.render()