Goal: Create an interactive 3D maze

The concept is surprisingly simple

The raycasting part

The raycasting part

Some details of the implementation

I use the C library ncurses for the terminal console integration, it is the defacto standard.

Ncurses will make the console window available as a 2D buffer we can write characters to at each location individually. This way we can basically approximate a pixel-based approach.

Next to screen handling, ncurses can also be used to process key presses to make the program interactive.

There are alternatives to ncurses, check out the solutions for more details on this.

The solution code is split up in a single version for each step, but generally speaking each solution comprises of a single .cpp file. Feel free to change this to your liking, or divert from the exercise in any other way!

A possible result

Version 00: Basic console application

As a first basic step, implement a program that simply uses the console library.

It doesn’t have to be functional otherwise.

Use an IDE to create a C++ project, build it manually or use a build system like Cmake.

For example: manual build, e.g. using GCC:

$ g++ -Wall -Wextra -Wconversion -Werror -O3 -std=c++20 -o raycasting raycasting.cpp -lncursesw

Feel free to steal the Cmake configuration from the solution code.

Version 01: Ray casting

Implement the ray casting algorithm. This is by far the most involved step as we need quite some setup code.

Some of the things that are required:

• A level map representation.
• Looping over the player FOV (i.e. the screen columns).
• The ray casting itself: iteratively increment distance d, calculating the ray end point, check if a wall is hit.
• Visualization of floor/wall/ceiling.

Version 02: Wall shades

To increase the illusion of 3D, light falloff can be used.

The further away a wall is, the darker it appears (and vice versa).

The easiest method is to visualize walls using these Unicode characters:

• ‘█’ (\u2588, close by),
• ‘▓’ (\u2593),
• ‘▒’ (\u2592),
• ‘░’ (\u2591),
• ‘ ’ (space, \u20, far away).

Version 03: Moving around

Use the console library to handle key press inputs to control the player position and angle.

The solution code uses WSAD input for forward/backward/CCW rotation/CW rotation.

Version 04: Floor rendering

Another way to improve the illusion of 3D is to render the floor depending on the distance of the player.

Use a more “dense” character like ‘#’ close by, and a more sparse character like ‘.’ far away.

The solution code uses a succession of ‘#’, ‘x’, ‘-’, ‘.’ and ‘ ’ (space).

Version 05: Screen abstraction

If your code is like mine was, it can benefit from some organization.

In this step, create an abstraction of the “screen”. The overall size of the code may become slightly larger, but the main business logic is much easier to read and understand.

Version 06: Level map abstraction

If your code is like mine was, it can benefit from some organization.

In this step, create an abstraction of the level map. Again, the overall size of the code may become slightly larger, but the main business logic is much easier to read and understand.

Version 07: Player state abstraction

If your code is like mine was, it can benefit from some organization.

In this step, create an abstraction of the player state. Again, the overall size of the code may become slightly larger, but the main business logic is much easier to read and understand.

Version 08: Wall boundary visualization

Another way to improve the 3D illusion fidelity is to render the wall block boundaries.

The idea in this step is that if we detect a ray cast “wall hit”, we calculate the Euclidian vector dot product of a ray from the player with a normal vector from each one of the four wall block corners. A ray with a dot product approaching 0 indicates a ray perpendicular to the wall block. This way we can signify a screen column that hits a wall to be a wall block boundary.

Because the calculations and visualizations are not very accurate, selecting all four wall block boundaries for visualization is not visually appealing. To fix this, the solution code builds an array of wall block calculations and selects only the two most accurate ones. This is done by sorting the array of dot products by distance.

Version 09: Mini-map visualization

One of the advantages of having a simple ASCII-based implementation, is that a top-view minimap can easily be visualized. In the solution code, the map is visualized in the top-left corner.

The player location can simply be added as it directly maps to a level map location.

The simplicity of this step breaks down if your level map is very large. In that case, a more advanced approach with taking a “subview” or scaled version of the map is required. Feel free to experiment!

Version 10: Frame rate measurement

Another advantage of the ASCII-based implementation is that ridiculous frame rates can be achieved.

To measure frame rate, we must use the <chrono> module/header from the C++ standard library.

In later additional steps, the frame rate measurement can be used to performance-benchmark the program.

Version 11: Player orientation in mini-map

A nice addition to the mini-map is player orientation. Previous versions only showed the location.

The solution code uses the “double arrows” from the Unicode characters (‘\u21d0’ .. ‘\u21d9’).

Version 12: Wall shades using colors

A huge improvement of graphical fidelity can be reached by using terminal color shading rather than just different Unicode block characters for wall visualization. Depending on the terminal configuration, 256 colors, or even true color (32-bit shading) can be used. However, tests show that 16 shades already make a tremendous difference.

In ncurses, colors can be introduced by defining color/shade and index pairs. These indexes can then be used in the rendering process to select the lightness depending on the wall distance. When using an array-like data structure for storing these indexes, be sure to prevent out-of-bounds access.

Version 13: Compile-time init’ing of wall shades

This is a pretty advanced improvement step, but it may be worth looking into.

In the solution code for the previous step, the color index array is a simple monotonously increasing range of index numbers. A fixed number sequence like this is typically something that could be precalculated and stored at compile-time. This can be achieved by using template metaprogramming or using constant expressions (more readable).

Due to the static implementation there are no more run-time costs for array initialization.

Version 14: Position abstraction

One last code cleanup can be achieved by introducing a type to represent a 2D location.

In several places in the main code body, 2D locations are used (player position, printing, etc.), comprising of two locations x and y. Because these are separate variables, but are used together almost exclusively, it makes sense to create a representation to bind them together.

One of the main challenges implementing this location type is dealing with the type conversions.

Version 15: Sealing off the Screen class type

The Screen class type is a resource handle.

Lock down the Screen class type to make sure it is stationary (immovable and uncopyable).

Add tests based on static_assert(..) to verify and guarantee the type behavior.

Version 16: Improving move/collision detection

Player/wall collision detection is implemented as: move, check position, conditionally undo move.

This is a bit of a poorly readable and maintainable bit of code, we can do better than that!

Merge the player up/down move operation and the check.

Hint: Look at how behavior is passed into standard library functions like std::copy_if.