Ray casting or ray tracing dates back to the '90s computer games as a technique of producing realistic 3D environments, although, according to Wikipedia, it was invented by Albrect DÃ¼rer already in the 16th century. No computers back then, though. While the two terms are, at times, used interchangeably, ray casting has also been described as a predecessor to recursive ray tracing.

With the limited computing power available, the first ray casting games (remember Wolfenstein 3D or Doom?) generally "cast rays" only on a horizontal level. The environment was thus not truly 3D, but only appeared to be, when moving on a flat surface. There are ways to emulate jumping or kneeling, or looking up or down, but they are not true 3D - which might not matter much in a heated game play.

The basic premise is simple: Say you have a display 800 pixels wide. Cast 800 rays horizontally, e.g. from left to right, and see what the rays hit first - in the simplest case, a wall. Then assume that wall goes from floor to ceiling, and draw the one vertical line (one pixel wide) of that wall. Do the same for each of the 800 rays, and you have filled the screen with a ray cast 3D space.

I got my inspiration to try this from raytomely's ray casting routine where he kindly also points to a step-by-step guide by F. Permadi, written already in 1996. This v0.5 is only a half-product - it does cast the rays and illustrates the technique by drawing a map with the rays, but it does not (yet) do the actual drawing of the 3D space. That will follow in a later version and post.

As usual, the Python code relies on PyGame and NumPy and can be found in my GitHub repository.

### Looping the loop

*your*time i.e. the time it takes to develop the code, is to use a Python module which can run those loops for you in a more efficient way. I have been using NumPy and, as it's easier to stick with something you know at least something about, am using it here as well. The principal idea is not to run a loop in Python but to ask for as much calculations and data as possible from NumPy in one go; for example, instead of running a loop 800 times and calculating a sine for an angle etc. every time, asking NumPy to return an array of sines for all 800 angles in one instruction.

Showing the horizontal (green) and vertical (red) grid crossings for selected rays. A big, filled circle means hitting a wall. |

### Casting exercise

def raycast(self, screen, block_size): # go through view horizontally i.e. from position and view_angle go from left view_angle_witdh / 2 to right view_angle_witdh / 2. # below "horizontal" and "vertical" refer to a map on the screen, not the view itself. # angle 0 degrees = "up", rotation clockwise # position rounded to grid and the decimals (ie. position within the grid it is in) pos = np.floor(self.position) pos_dec = self.position - pos width = self.width # this is the number of rays cast - ideally the width of the program window in pixels, so one ray per vertical line of pixels. view = self.view_blocks # nr of blocks: how far is visible (and, hence, how far must be calculated) rng_width = np.arange(width) # rng_view goes from zero to maximum view length in blocks. rng_view = np.arange(view + 1) # add 1 to make sure covers the viewable distance as blocks are "rounded down" # calculate all angles etc. in one go - faster than looping # rads is an array (size: width) of all view angles in radians. Add 0.0001 to avoid exact 0/90/180/270 deg (and hence 0 sin/cos - div by zero) # rads are not evenly spaced, as they are on a line, not a circle radius. Their tangent is evenly spaced (when view_angle not yet applied), rad_tan = np.tan(self.view_width * np.pi / 360) # rad_tan is the tangent of half the viewing angle rads = np.arctan((rng_width / (width - 1) - 0.5) * rad_tan * 2) + self.view_angle * np.pi / 180 + 0.0001 sin_a = np.sin(rads) cos_a = np.cos(rads) tan_a = np.tan(rads) sign_x = np.sign(sin_a) # sign_x = +1 for angles > 0 and < 180, -1 for angles > 180 sign_y = np.sign(cos_a) # sign_y = +1 for angles < 90 or > 270, -1 for angles > 90 and < 270 # get the first encountered coordinates when moving to next grid along ray line # if sign_y is negative, ray is cast downwards and the y distance is pos_dec[1] - 1. The same for x... x_first = (pos_dec[1] + (sign_y - 1) / 2) * tan_a y_first = (pos_dec[0] - (sign_x + 1) / 2) / tan_a

# vertical intersections of ray and grid; y coordinate increases/decreases by one, calculate respective x coordinate # x_coord_y is the "grid point" (no info on which side of grid) while x_coord_y_adj is the y coordinate adjusted for viewer position relative to it (includes side). # i.e. if grid point is higher than viewer (sign_y = -1), 1 is added to bring x_coord_y_adj to the bottom of that grid point. vert_grid_range = rng_view x_coord = self.position[0] + x_first[:, None] + vert_grid_range * (sign_y * tan_a)[:, None] x_coord_y = pos[1] - (vert_grid_range + 1) * sign_y[:, None] x_coord_y_adj = x_coord_y - (np.sign(x_coord_y - pos[1]) - 1) / 2 # get the respective grid cell data from the map. Make sure not to exceed map boundaries. Pick only "view" nr of blocks; then add a "stop block" as last block vert_grid = np.hstack(( self.map_array[(np.minimum(np.maximum(x_coord[:, :view], 0), self.map_size[0] - 1)).astype(np.int16), (np.minimum(np.maximum(x_coord_y[:, :view], 0), self.map_size[1] - 1)).astype(np.int16)], np.ones((width, 1), dtype=np.int16) # this is the farthest block and always marked as "1" to make sure argmax finds something. )) # find the first nonzero item's index for each angle. Since distance is growing with each item, this is the closest wall encountered for each ray. vert_grid_first = (vert_grid != 0).argmax(axis=1) # construct an array of grid item, side (0 = up, 1 = right, 2 = down, 3 = left) map x, map y, and distance from viewer vert_data = (np.vstack(( vert_grid[rng_width, vert_grid_first], sign_y + 1, x_coord[rng_width, vert_grid_first], x_coord_y_adj[rng_width, vert_grid_first], np.abs((x_coord[rng_width, vert_grid_first] - self.position[0]) / sin_a) ))).transpose()

# combine data on vertical and horizontal first encountered walls comb_data = np.stack((vert_data, horiz_data)) # find the closest of these two - distance being item 4 comb_closest = np.argmin(comb_data[:, :, 4], axis=0) # pick these for the closest data self.ray_data = comb_data[comb_closest, rng_width, :]

*m*key to switch viewing mode between the yellow area and green and red circles, as in the two images above.