English Version

Summary

Raycasting is a method in which the computer represents a three-dimensional environment in which the player can move. This method led to a breakthrough in video game history in 1992.

In raycasting, the three-dimensional environment is calculated based on a two-dimensional map. Using rays, this map is “scanned” and the distance to walls is calculated. Trigonometry plays an essential role here. A raycaster performs calculations for each pixel column on the screen.

We programmed several raycasters ourselves, initially in the programming language “Scratch”, later in the language “Python”. Additionally, we wrote a program to represent the floor plan of a house in three dimensions.

The main advantage of the raycasting method is the speed with which the three-dimensional images are calculated. However, a raycaster also has some limitations. For example, all objects in the room have the same height.

Introduction

Idea Finding

For several years now, we have been programming small computer games of all kinds. And as much as the games differ from each other, they all have one thing in common: They are two-dimensional.

We began to ask ourselves how a computer program actually calculates three-dimensional environments. How is it possible to achieve deceptively realistic 3D effects on a screen? We soon came across the raycasting method, which is used in some well-known 3D computer games. We were immediately enthusiastic about the method and decided to program our own raycaster.

Goal

Our goal is to write a computer program using the raycasting method that calculates and represents a three-dimensional environment. The environment should look as realistic as possible and the player should be able to move through it as smoothly as possible. Finally, our program should represent floor plans of houses in three dimensions so that the player can move through the houses.

Method and Procedure

Used Programs

For the different raycasters, we use the programming languages “Scratch” and “Python”. For the graphical representation of shapes and colors in Python, we also use the “PyGame” library.

Functionality of a Raycaster

General Functionality

In raycasting, the three-dimensional images are calculated based on a two-dimensional map. This map represents the environment in which the player can move. The map is represented in the form of a two-dimensional array. A 0 stands for a free area and a 1 for a wall Figure 1.

Figure 1

An example map represented as an array and visually

The map is considered a coordinate system. The squares that make up the map have a length of 1.

The player is located at a certain position in this map. View rays are emitted from the player and hit the walls in the map. The view rays are responsible for “scanning” the player’s field of vision Figure 2.

Figure 2

The player’s field of vision is scanned with view rays

For each view ray, a vertical line is drawn on the screen, the size of which depends on the distance of the player to the wall. This creates the three-dimensional image Figure 3. A raycaster performs calculations for each pixel column on the screen.

Figure 3

Functionality of a raycaster visually represented. On the left, the map is scanned. On the right, the three-dimensional image is created

Calculating the Point where the View Ray Hits a Wall

For each view ray, the point must be found where the view ray hits a wall. Only with this point can the distance of the player to the wall be calculated. To find the point, it is checked each time the view ray enters a new square whether there is a wall in this zone Figure 4.

Figure 4

At the marked points, the view ray hits a new square. At these points, it must be checked whether there is a wall in the square

This section is about calculating all the points where the view ray enters a new square to ultimately find the point where the view ray hits the wall. It is sufficient to only calculate the x-positions of the points. At some points, the view ray intersects a vertical line. At other points, it intersects a horizontal line. First, we calculate the x-positions of the first horizontal and the first vertical intersection Figure 5.

Figure 5

The x-positions of the first vertical and horizontal intersections are to be calculated

The desired x-positions can be calculated as follows:

$$ \ \text{verticalIntersection } x = \lceil \text{playerX} \rceil $$

$$ \ \text{horizontalIntersection } x = \text{playerX} + \frac{1 - (\text{playerY} \mod 1)}{\tan(\text{rayDirection})} $$

Now the x-positions of the further intersections must be calculated. The further vertical intersections are always 1 apart. The distance of the horizontal intersections is also always the same Figure 6.

Figure 6

The distance between the horizontal intersections is always the same

$\Delta(x)$ gives the distance of the horizontal intersections. Using trigonometry, $\Delta(x)$ can be calculated:

$$ \ \Delta(x) = \frac{1}{\tan(\text{rayDirection})} $$

Using these formulas, the x-position of each intersection point of a view ray can be calculated. The intersections with the smaller x-position are passed by the view ray first. These formulas only apply to a view ray running to the northeast. For other directions, the formulas may need to be slightly adjusted. The intersections are calculated in their correct order, and it is checked each time whether the view ray reaches a “wall zone” at the points. If this is the case, the desired point has been found. The x-position of this point is then stored in the variable intersectionX.

Calculating the Distance of the Player to the Wall

Using the determined value intersectionX, we can now calculate the distance of the player to the wall. First, the length of the view ray must be calculated Figure 7.

Figure 7

lengthRay gives the length of the view ray and should be calculated

Die Länge des Sichtstrahls lässt sich wie folgt berechnen:

$$ \ \text{längeRay} = \frac{\text{schnittX} - \text{spielerX}}{\cos(\text{rayRichtung})} $$

Die Länge des Sichtstrahls ist nicht, wie man annehmen könnte, die Entfernung des Spielers zur Wand. Würde man die Länge des Sichtstrahls als Entfernung verwenden, würde man eine verzerrte Darstellung der Umgebung erhalten. Die tatsächliche Entfernung, die wir benötigen wird in Abbildung 8 ersichtlich.

Figure 8

The blue line is the sought distance. It runs in the same direction the player is looking.

The player’s distance to the wall is calculated as follows:

$$ \ \text{distance} = \text{lengthRay} \cdot \cos(\text{rayDirection} - \text{playerDirection}) $$

Using these formulas, the distance to the wall can be calculated for each view ray. Thus, the player’s field of view can be completely scanned.

Representation of the Three-Dimensional Image

As already mentioned, the three-dimensional image in raycasting consists of many vertical lines representing the walls (Figure 9). For each view ray, a vertical line is drawn. The greater the distance to the wall, the smaller this line must be drawn. The size of the line is calculated as follows:

$$ \ \text{lineSize} = \frac{\text{Constant}}{\text{distance}} $$

Figure 9

A raycaster consists of vertical lines. Both images show the same environment. The left image consists of a few wide lines, the right image consists of many narrow lines.

Vertical walls are darkened by a fixed factor to create a “shadow effect.” Additionally, walls located further back in the room can be displayed darker. Often, a floor and sky are also depicted as the background.

With some additional calculations, it is possible to apply textures to the walls. To do this, the exact point where the view ray hits the wall must be calculated. This allows the appropriate “texture-pixel-column” to be chosen from an array. The vertical lines then each consist of different colors, forming the corresponding texture together.

The Calculations in Python Code

In the following code block, the theoretical considerations from the previous sections are implemented in Python code. The code is an excerpt from one of our raycasters. With the inserted comments, you can follow its functionality.

"""
Part of a raycaster program that performs all necessary calculations for 
a view ray. This program is written by us. 
The program part is simplified and therefore only works for a view ray that 
runs to the northeast.
"""

#Square in which the view ray is located
squareX = int(playerX)
squareY = - int(playerY)

# x-position of the first vertical and horizontal intersection points
horizontalX = playerX + (1 - playerY % 1) / math.tan(rayDirection)
verticalX = math.ceil(playerX)

# Distance of the intersections
deltaX = 1/math.tan(rayDirection)

# Repeat until view ray hits a wall
wall = False
while not wall:
    # next intersection horizontal or vertical?
    if horizontalX < verticalX:
        # current intersection
        intersectionX = horizontalX
        # next horizontal intersection
        horizontalX += deltaX
        # view ray enters new square
        squareY -= 1
    else:
        # current intersection
        intersectionX = verticalX
        # next vertical intersection
        verticalX += 1
        # view ray enters new square
        squareX += 1

    # Ray hits wall?
    if map[squareY][squareX]:
        wall = True

# Calculate length of the view ray
rayLength = (intersectionX - playerX) / math.cos(rayDirection)

# Player's distance to the wall
distance = rayLength * math.cos(rayDirection - playerDirection)

#Size of the vertical line on the screen
lineSize = 800 / distance

Results

We have programmed different raycasters. Our latest raycaster has a very realistic 3d effect and runs smoothly. There are textures on the walls. The program is written in Python and consists of about 200 lines of code (Figure 10).

Figure 10

Our latest raycaster

Additionally, we wrote a program that converts an image of a floor plan into a two-dimensional array. This allows the player to move virtually in the house and get an idea of how it looks in reality.

Discussion

We have optimized our program to the point where it is difficult to improve it further. However, the raycasting method itself has some problems. Walls can only adjoin each other at a 90-degree angle. It is also not possible to represent round shapes. Furthermore, all walls have the same height.

The advantages of raycasting lie mainly in its speed. Since the program only calculates each pixel column, the process is significantly faster than raytracing, which calculates the brightness for each pixel. Raycasting was often used in early computer games as the process works even on low-performance computers.

Our program is written in Python. However, Python is a relatively slow programming language and not well-suited for a raycaster. In another language like “C,” we would probably have achieved even better results.

References

• https://www.youtube.com/watch?v=eOCQfxRQ2pY, (09. 2019)
• https://en.wikipedia.org/wiki/Ray_casting, (09. 2019)

Our work is based on a few sources. After we familiarized ourselves with the function of a raycaster using the given sources, we continued programming based only on our own considerations.

All images used in this report were created by us.