Ray-casting with Pygame
Hi there, in this article I'm going to discuss ray-casting theme and create raycasting algorithm from the scratch with pygame.
You could find following topics:
- Drawing map
- Ray-casting algorithm implementation on 2D map
- 3D implementation
- Collision detection
- Displating FPS
Theory about ray-casting
Raycasting is a rendering technique to create a 3D perspective in a 2D map. People came up to the idea of using raycasting in that time, when computers were way slow (early 90-s) to run a 3D engines in a realtime. The most famouse game, which uses raycasting is Wolfenstein 3D, released back in 1992. The basic idea behind raycasting is to trace rays from the 'eye' and find the closest object blocking the path of that ray. We need try to increase the length of a ray at each step of the loop and if ray does hit the wall, then ray ends at this point. This processing should be done with each ray, it could be 30 or 300, depends on needs.
More theory
As you could notice in ray-casting algorithm we need to use FOV(filed of view) for further simulating 3D. FOV determines where player's visible range begins and ends. Usually in games FOV is equal to 60% or pi/3. You could change FOV value and have a look at results.
The process of generating rays in FOV range is not hard at all. There are just a few formulas behind it.
The angle of the first ray will determined in the next way:
starting_angle = player_angle - FOV / 2
And formula for finding distance between two angles:
delta_angle = FOV / number_of_rays
Let's substitute the values in our first quation. Player_angle is pi and FOV / 2 is ((pi/3)/2). Starting_angle equal to (5pi)/6 which is right in the upper left quadrant. If you have a look at the first screenshot, you could notice, that (5pi)/6 is exact dot where FOV starts.
I think for delta_angle no explanations needed, it's really simple.
Drawing map
Now I want to provide code that draws map, player, FOV and we'll be back again to a few formulas to compute points of intersection with walls.
import pygame
import sys
import math
#global constants
SCREEN_HEIGHT = 480
SCREEN_WIDTH = SCREEN_HEIGHT * 2
MAP_SIZE = 8
TILE_SIZE = int((SCREEN_WIDTH / 2) / MAP_SIZE)
FOV = math.pi / 3
HALF_FOV = FOV / 2
CASTED_RAYS = 30
#global variables
player_x = (SCREEN_WIDTH / 2) / 2
player_y = (SCREEN_WIDTH / 2) / 2
player_angle = math.pi
MAP = ('########'
'# # #'
'# # ###'
'# #'
'## #'
'# ### #'
'# # #'
'########')
#game window
pygamepygame.init()
win = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
pygame.display.set_caption('Ray-casting')
clock = pygame.time.Clock()
#game loop
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit(0)
draw_map()
#update display
pygame.display.flip()
#set FPS
clock.tick(30)I defined global constants, variables, map and wrote minimum framework for creating a window in pygame. Let's dive into draw_map function
The idea behind creating map is simple as hell. We need to iterate over two-dimensional array and compute square index, then create tiles with correspoding color (wall or not).
def draw_map():
#colors
light_grey = (191, 191, 191)
dark_grey = (65, 65, 65)
#iterate over map
for i in range(MAP_SIZE):
for j in range(MAP_SIZE):
#calculate square index
square = i * MAP_SIZE + j
#draw map
pygame.draw.rect(win,
light_grey if MAP[square] == '#' else dark_grey,
(j * TILE_SIZE, i * TILE_SIZE, TILE_SIZE - 1, TILE_SIZE - 1))The reason why I increase 1 from TILE_SIZE is because it just looks better, we got nice-looking grid on the map.
Map is ready, now need to add player. This code is continuation of draw_map function.
#draw player pygame.draw.circle(win, (162, 0, 255), (int(player_x), int(player_y)), 12)
Ray-casting implementation
Now the most interesting part: implementation of ray-casting algorithm
The idea is to firstly get target x and target y coorditanes and then to convert that coordinates to column and row. Then, with column and row, get square index and with square index it's really simple to check if it's a wall or nothing (do we need to cast the ray or not). Of course the set of this operations should be done with each ray.
for ray in range(CASTED_RAYS):
for depth in range(MAX_DEPTH):
#get ray target coordinates
target_x = player_x - math.sin(start_angle) * depth
target_y = player_y + math.cos(start_angle) * depth
#convert target x, y coordinates to map col, row
col = int(target_x / TILE_SIZE)
row = int(target_y / TILE_SIZE)
#calculate map square index
square = row * MAP_SIZE + col
#print(square)
if MAP[square] == '#':
pygame.draw.rect(win, (195, 137, 38),
(col * TILE_SIZE, row * TILE_SIZE,
TILE_SIZE - 1, TILE_SIZE - 1))
#draw casted ray
pygame.draw.line(win, (233, 166, 49), (player_x, player_y), (target_x, target_y))
break
#increment angle by step
start_angle += STEP_ANGLEMovement of the player and updating background. With using cos and sin functions we can move player in x and y directions. Feel free to experement with signs of numbers or math functions to observe how it all works.
#update background
pygame.draw.rect(win, (0, 0, 0), (0, 0, SCREEN_HEIGHT, SCREEN_HEIGHT))
#get user input
keys = pygame.key.get_pressed()
#handle user input
if keys[pygame.K_LEFT]:
#working with radians, not degrees
player_angle -= 0.1
elif keys[pygame.K_RIGHT]:
player_angle += 0.1
elif keys[pygame.K_UP]:
player_x += -1 * math.sin(player_angle) * 5
player_y += math.cos(player_angle) * 5
elif keys[pygame.K_DOWN]:
player_x -= -1 * math.sin(player_angle) * 5
player_y -= math.cos(player_angle) * 5
Time for 3D
The idea is simple and beatiful. We need to estimate length untill wall and depending on results build wall with relevant size and color.
The are two things which affect to building a 3D wall, first is what size it should be and second what color wall should be(from white to black).
#wall shading color = 255 / (1 + depth * depth * 0.0001) #calculate wall height wall_height = 21000 / (depth + 0.0001)
Color formula is easy, further is player darker is color. Wall height formula also is a piece of cake. Instead of 21000 could be any other big number, you can experiment with this variable and get right result for your needs.
SCALE constant should be added to "global constants" part of the code with following code, below you will find out why it's important:
SCALE = (SCREEN_WIDTH / 2) / CASTED_RAYS
#draw 3D projection
pygame.draw.rect(win, (color, color, color),
(SCREEN_HEIGHT + ray * SCALE,
(SCREEN_HEIGHT / 2) - wall_height / 2, SCALE, wall_height)) This code draws wall with appropriate size, color and scale. But how it works in details? Actually we create a lot of vertical stripes with the same width(SCALE value) and shifting next stripe exactly on the SCALE value, that's why SCALE value is really important(sorry for the tautology).
Updating 3D background for upper and lower part of the screen.
#update 3D background pygame.draw.rect(win, (100, 100, 100), (480, SCREEN_HEIGHT / 2, SCREEN_HEIGHT, SCREEN_HEIGHT)) pygame.draw.rect(win, (200, 200, 200), (480, -SCREEN_HEIGHT / 2, SCREEN_HEIGHT, SCREEN_HEIGHT))
Now we got a few things to finish in project: create collision detection with walls and display FPS.
Collision detection
The same tactic which we use in ray_casting function but in place of rays coordinate we use players coordinates for detection collisions with walls.nvert player x, y coordinates to map col, row
col = int(player_x / TILE_SIZE)
row = int(player_y / TILE_SIZE)
#calculate map square index
square = row * MAP_SIZE + col
# player hits the wall (collision detection)
if MAP[square] == '#':
if forward:
player_x -= -1 * math.sin(player_angle) * 5
player_y -= math.cos(player_angle) * 5
else:
player_x += -1 * math.sin(player_angle) * 5
player_y += math.cos(player_angle) * 5
Displaying FPS
Nothing interesting what we really should talk about. SCREEN_WIDTH / 2 is going to display FPS counter right in the left corner of 3D projection.
#set FPS
fps = str(int(clock.get_fps()))
font = pygame.font.SysFont('Arial', 30)
fpssurface = font.render(fps, False, (255, 255, 255))
win.blit(fpssurface, (int(SCREEN_WIDTH / 2), 0))Perfomance considerations
Ray-casting, in fact, works slower than modern 3D engines getting rendered on our super quick computers with using 3D graphics cards. There are at least 2 big issues with this code.
- The way how we find interaction with wall is not optimized at all. What we do is just sorting through dots to the wall, by comparing each dot with wall boundary. There are a way out! Using DDA(Digital Differential Analysis). DDA is a fast algorithm typically used on square grids to find which square line hits. Javidx9 got fascinating material about this.
- Ray-casting works with vertical stripes, when our screen buffers were build to work with horizontal stripes. So, when we draw vertical stripe it is the worst scenario for memory locality. And this causes a lot of problems with speed. You may try to find interesting content about this.
Resources
I came to the conclusion that any work can be considered as "serious" if it does not have link to resources, so in the future I will always try to add them.
- https://lodev.org/cgtutor/raycasting.html (eng)
- https://killerrobotics.me/2021/08/13/raycasting-game-in-python-and-pygame-part-1/comment-page-1/ (eng)
- https://permadi.com/1996/05/ray-casting-tutorial-table-of-contents/ (old but still can get understanding how things work) (eng)
- https://replit.com/talk/ask/Move-a-sprite-at-an-angle-in-pygame/130940 (topic about movement player) (eng)
GitHub code: https://github.com/rastr-0/teletype_source_files/blob/main/ray-casting/ray-casting.py