6
\$\begingroup\$

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")
disp=im.load()
col = Image.open("data/colour.png")
rgb_im = col.convert('RGB')
rgb=rgb_im.load()

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?

\$\endgroup\$
  • \$\begingroup\$ cdef is exotic and fragile. At this point, why aren't you just using C? \$\endgroup\$ – Reinderien Oct 10 '19 at 2:05
  • 1
    \$\begingroup\$ Because I have no knowledge in C \$\endgroup\$ – Russell356 Oct 10 '19 at 2:12
  • 1
    \$\begingroup\$ Perhaps it's time to learn :) it'll buy you a lot more efficiency, at the cost of more awkward libraries. \$\endgroup\$ – Reinderien Oct 10 '19 at 2:13
  • 1
    \$\begingroup\$ @Reinderien Let's be honest, C is a programming language for masochists ;-) A little bit awkward, and lots of opportunities to hurt yourself. \$\endgroup\$ – AlexV Oct 10 '19 at 7:22
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Russell356 Oct 13 '19 at 7:31
1
\$\begingroup\$

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

    def load_color_data(self, str color_path):
        cdef object image
        image = Image.open(color_path).convert("RGB")
        self.color_data = np.asarray(image)

    def load_height_data(self, str height_path):
        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()
map.load_color_data("./images/C1W.png")
map.load_height_data("./images/D1.png")
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()
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.