Optimisation of Shadow Casting Python
I have been working on a Shadow Caster for a small RPG I'm doing.
The trouble I have is that when I use it in my game it is just way way way to slow and induces a horrible lag.
Please do not be too frighten by the lenght of the post. It is fairly straightforward but so that you can run the code I included all the Bresenham's algorithms as well.
The principle is as follow: - make a black surface - define a light source with a position and a radius. - get all the points on the circumference of the circle defined by this position and radius using Bresenham's Circle Algorithm. - for each point along the circumference draw a ligne from the position of the light source using Bresenham's Line Algorithm. - then iterate over the points of the line and check if they collide with every obstacle displayed on the screen. - If there is no collision draw a WHITE circle centered on that point with a radius of 10 pixels or so. - If there is a collision move on to the next point along the circle circumference. - finally blit the surface with all the white circles on a surface which has a transparency value of 100 for the black color and a full transparency for the WHITE color.
So far I have attempted the following: Which did reduce the lag: - restrict the obstacle list to the ones displayed on the screen - consider the screen edges as obstacles to reduce the iteration of area not visible. - iterate only over every 3 points around the circle and 12 points along the lines. Which didn't change anything: - using ellipses going from the light source to the edge of the range or the obstacle instead of lots of circles along the line. The problem was that I had to redraw surface for each ellipse and then rotate the whole lot.
If you have any suggestions on how to make this more efficient I would be happy to here then.
Bresenham's Line Algo:
def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
>>> points1 = get_line((0, 0), (3, 4))
>>> points2 = get_line((3, 4), (0, 0))
>>> assert(set(points1) == set(points2))
>>> print points1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> print points2
[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1
# Determine how steep the line is
is_steep = abs(dy) > abs(dx)
# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
y = y1
points = []
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx
# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points
Bresenham's Circle Algo:
def get_circle((dx,dy),radius):
"Bresenham complete circle algorithm in Python"
# init vars
switch = 3 - (2 * radius)
points = set()
x = 0
y = radius
# first quarter/octant starts clockwise at 12 o'clock
while x <= y:
# first quarter first octant
points.add((x,-y))
# first quarter 2nd octant
points.add((y,-x))
# second quarter 3rd octant
points.add((y,x))
# second quarter 4.octant
points.add((x,y))
# third quarter 5.octant
points.add((-x,y))
# third quarter 6.octant
points.add((-y,x))
# fourth quarter 7.octant
points.add((-y,-x))
# fourth quarter 8.octant
points.add((-x,-y))
if switch < 0:
switch = switch + (4 * x) + 6
else:
switch = switch + (4 * (x - y)) + 10
y = y - 1
x = x + 1
offset_points = set()
for pt in points:
offset_points.add((pt[0]+dx,pt[1]+dy))
return offset_points
def shadow_gen(shadow_surf,source,cir_pt,obstacles):
line_points = get_line(source.pos,cir_pt)
for line_pt in line_points[0::12]:
for obs in obstacles:
pygame.draw.circle(shadow_surf, WHITE, line_pt, 20, 0) #radius to 5px and 0 to fill the circle
if obs.rect.collidepoint(line_pt) or pygame.Rect(0,0,500,500).collidepoint(line_pt) == False:
return
My Classes for the light sources, obstacles and shadow mask:
class Obstacle(object):
def __init__(self,x,y):
self.surf = pygame.Surface((150,150))
self.rect = pygame.Rect((x,y),(150,150))
self.surf.fill(pygame.color.Color('blue'))
class Light_Source(object):
def __init__(self,x,y,range_):
self.range = range_
self.pos = (x,y)
class Night_Mask(object):
def __init__(self):
self.surf = pygame.Surface((500,500)) #Screenwidth and height
self.alpha = 100
self.light_sources = []
'''setting initial alpha and colorkey'''
self.surf.set_colorkey(WHITE)
self.surf.set_alpha(self.alpha)
def apply_shadows(self, obstacles):
shadow_surf = pygame.Surface((500,500))
for source in self.light_sources:
circle_pts = list(get_circle(source.pos,source.range))
for cir_pt in circle_pts[0::3]:
shadow_gen(shadow_surf,source,cir_pt,obstacles)
self.surf.blit(shadow_surf, (0, 0))
The shadow generation functions which allows me to break out of both line and obstacle loop without using an exception in my apply_shadows method of the Night_Mask class:
def shadow_gen(shadow_surf,source,cir_pt,obstacles):
line_points = get_line(source.pos,cir_pt)
for line_pt in line_points[0::12]:
for obs in obstacles:
pygame.draw.circle(shadow_surf, WHITE, line_pt, 20, 0) #radius to 5px and 0 to fill the circle
if obs.rect.collidepoint(line_pt) or pygame.Rect(0,0,500,500).collidepoint(line_pt) == False:
return
And finally the main pygame example loop to run all of the above:
pygame.init()
screen = pygame.display.set_mode((500, 500))
bg = pygame.Surface((500,500))
bg.fill(pygame.color.Color('yellow'))
ob_a = Obstacle(75,80)
ls = Light_Source(75,75,300)
night_m = Night_Mask()
night_m.light_sources.extend([ls])
while True:
screen.fill(pygame.color.Color('black'))
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
ls.pos = pygame.mouse.get_pos()
night_m.apply_shadows([ob_a])
screen.blit(bg, (0, 0))
screen.blit(ob_a.surf,ob_a.rect)
screen.blit(night_m.surf, (0, 0))
pygame.display.flip()
Here is the entire code from start to finish for an easy copy paste:
import pygame
import sys
WHITE = (255,255,255)
'''FUNCTIONS'''
def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
>>> points1 = get_line((0, 0), (3, 4))
>>> points2 = get_line((3, 4), (0, 0))
>>> assert(set(points1) == set(points2))
>>> print points1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> print points2
[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1
# Determine how steep the line is
is_steep = abs(dy) > abs(dx)
# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
y = y1
points = []
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx
# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points
def get_circle((dx,dy),radius):
"Bresenham complete circle algorithm in Python"
# init vars
switch = 3 - (2 * radius)
points = set()
x = 0
y = radius
# first quarter/octant starts clockwise at 12 o'clock
while x <= y:
# first quarter first octant
points.add((x,-y))
# first quarter 2nd octant
points.add((y,-x))
# second quarter 3rd octant
points.add((y,x))
# second quarter 4.octant
points.add((x,y))
# third quarter 5.octant
points.add((-x,y))
# third quarter 6.octant
points.add((-y,x))
# fourth quarter 7.octant
points.add((-y,-x))
# fourth quarter 8.octant
points.add((-x,-y))
if switch < 0:
switch = switch + (4 * x) + 6
else:
switch = switch + (4 * (x - y)) + 10
y = y - 1
x = x + 1
offset_points = set()
for pt in points:
offset_points.add((pt[0]+dx,pt[1]+dy))
return offset_points
def shadow_gen(shadow_surf,source,cir_pt,obstacles):
line_points = get_line(source.pos,cir_pt)
for line_pt in line_points[0::12]:
for obs in obstacles:
pygame.draw.circle(shadow_surf, WHITE, line_pt, 20, 0) #radius to 5px and 0 to fill the circle
if obs.rect.collidepoint(line_pt) or pygame.Rect(0,0,500,500).collidepoint(line_pt) == False:
return
'''CLASSES'''
class Obstacle(object):
def __init__(self,x,y):
self.surf = pygame.Surface((150,150))
self.rect = pygame.Rect((x,y),(150,150))
self.surf.fill(pygame.color.Color('blue'))
class Light_Source(object):
def __init__(self,x,y,range_):
self.range = range_
self.pos = (x,y)
class Night_Mask(object):
def __init__(self):
self.surf = pygame.Surface((500,500)) #Screenwidth and height
self.alpha = 100
self.light_sources = []
'''setting initial alpha and colorkey'''
self.surf.set_colorkey(WHITE)
self.surf.set_alpha(self.alpha)
def apply_shadows(self, obstacles):
shadow_surf = pygame.Surface((500,500))
for source in self.light_sources:
circle_pts = list(get_circle(source.pos,source.range))
for cir_pt in circle_pts[0::3]:
shadow_gen(shadow_surf,source,cir_pt,obstacles)
self.surf.blit(shadow_surf, (0, 0))
'''MAIN GAME'''
pygame.init()
screen = pygame.display.set_mode((500, 500))
bg = pygame.Surface((500,500))
bg.fill(pygame.color.Color('yellow'))
ob_a = Obstacle(75,80)
ls = Light_Source(75,75,300)
night_m = Night_Mask()
night_m.light_sources.extend([ls])
while True:
screen.fill(pygame.color.Color('black'))
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
ls.pos = pygame.mouse.get_pos()
night_m.apply_shadows([ob_a])
screen.blit(bg, (0, 0))
screen.blit(ob_a.surf,ob_a.rect)
screen.blit(night_m.surf, (0, 0))
pygame.display.flip()
Your lag issue appears to be coming from the method Night_Mask.apply_shadows(self, obstacles). This appears to be due to the pure amount of iterations the nested for loop needs to go through.
Reducing the value of range_ in the constructor of Light_Source(x, y, range_) reduces the lag by reducing the aforementioned methods iterations, but the visual effect is worse. I found that the fps started to really drop for me after setting the variable past ~65-70.
There is a Pygame graphics library, that handles shadows very well.
Link to the page:http://pygame.org/project-Pygame+Advanced+Graphics+Library-660-4586.html Direct download for version 8.1.1 from site:link
This is the description of the library from the site:
This is an all purpose graphics library for easily creating complicated effects quickly, and with a minimum of code. Run the very well commented examples, each less than a page long (not counting comments), and learn how to make complicated effects like shadows and antialiasing.
Here is an image from the page showing an example of shadows.
I downloaded and tested the library, and it works very well. I tested on Pygame1.9.2a0 for python 3.4
I believe this to be the easiest fix for your problem, and should help you with future projects as well. I hope this helps.
- Change value in Ini to empty using Python configparser
- Script works with error line but won't run corectly when bad line is removed
- FFMPEG not saving logs when converting to audio format
- Numerically obtaining response of a damped driven oscillator gives peak at wrong frequency
- What is the deal with the pony in Python community?
- 'Area' object is not callable
- ValueError: Attribute Users.request is required
- How to place class in its own file when it appears to be inheriting from an instance?
- Python 3.6 with pony 0.7 gives error on commit to oracle db
- Why pyqt tablewigdet is only displaying row number and no data?
- How to check if a value exists in a dictionary?
- OpenCV: draw a rectangle around a region
- Python, Tkinter, trying to pull random numbers from a list based off user input for number and have results open in mew window
- How to remove repeated elements in a vector, similar to 'set' in Python
- Understanding descriptor protocol for 'wrapper-descriptor' itself
- Passing a NumPy 3d array to a C function with a triple pointer as an argument
- How do I create variable variables?
- Turn a tf.data.Dataset to a jax.numpy iterator
- Django 5.1 + Postgresql (debian server)
- Passing in arguments to Dependency function makes it recognized as a Query Parameter
- How to pass parameters to an endpoint using `add_route()` in FastAPI?
- How to make Depends optional in FastAPI?
- Streaming multiple videos through FastAPI to Web Browser causes HTTP requests to stall
- FastAPI error when handling file together with form-data defined in a Pydantic model
- Use serial port in Python without installing external packages
- How can i get the output to print 10 circles instead of 9 in python turtle module
- Unable to install TA-Lib on Ubuntu
- Unable to install Python without sudo access
- Size of an open file object
- two if or more with one ELSE