A 3D maze exploration game built from scratch using raycasting techniques
- Build project
- Showcase
- Features
- What is cub3d ?
- Controls
- Settings
- Parsing
- Initialization
- Raycasting
- Fun things we learned
- Bonus features
- Contributors
- Useful ressources
git clone https://github.com/lcalero42/cub3d.git && cd cub3d
cd lib && git clone https://github.com/42paris/minilibx-linux
cd ..
make
Then, you will be able to launch the game
./cub3d mandatory/maps/deathcave.cub
Important
make bonus if you want to build the bonus and launch the game with maps in bonus/maps
This project is clearly letting space creativity in the bonuses. So, we wanted to push the project as much as possible, implementing everything that crossed our mind using ONLY fake 2D raycasting like in Woflenstein.
Note
We could've created 3D engine and use raycsating in this engine casting rays in all directions. But we chose to stick to the original concept of Raycasting, when computers did not have the performances to run on a pure 3D engine.
- Walls
- Doors
- Fog
- Shooting
- Pitch
- Player movement (with running)
- Collisions
- Enemy (With pathfinding)
- Health pads
- Menu
- Health/Stamina bar
- Minimap
Cu3d is a project in which you need to build a Raycaster engine, coming from a map looking like this :
NO mandatory/textures/376.xpm
SO mandatory/textures/376.xpm
WE mandatory/textures/376.xpm
EA mandatory/textures/376.xpm
F 139,0,0
C 139,0,0
1111111111111111111111111
1000000000110000000000001
1011000001110000000000001
1001000000000000E00000001
111111111011000001110000000000001
100000000011000001110111111111111
11110111111111011100000010001
11110111111111011101010010001
11000000110101011100000010001
10000000000000001100000010001
10000000000000001101010010001
1100000111010101111101111000111
11110001 1110101 101111010001
11111111 1111111 111111111111
To a rendering like this using mlx :
| KEY | Action |
|---|---|
W |
Move forward |
A |
Move to the left |
S |
Move backward |
D |
Move to the right |
Shift + moving key |
Sprint |
Left Arrow |
Rotate left |
Right Arrow |
Rotate right |
Mouse |
Rotate up and down |
Left click |
shoot |
Space |
Open door |
F |
Toggle fog |
M |
Toggle mouse |
Esc |
Leave game |
There is a couple of settings that you can edit to have a better experience playing the game !
All the settings are at the top of the Makefile :
# ---------------------------------- window ---------------------------------- #
WINDOW_WIDTH = 1280 # width of window
WINDOW_HEIGHT = 720 # height of window
# --------------------------------- gameplay --------------------------------- #
MOVE_SPEED = 5.0f # player movement speed
CROSSHAIR_SIZE = 4 # size of the crosshair
CROSSHAIR_THICKNESS = 2 # thickness of the crosshair
CROSSHAIR_COLOR = 0x00FF00 # color of the crosshair in hexa format
SENSITIVITY = 0.25f # player mouse sensitivity
RELOAD_TIME_MS = 1000 # reload time of the weapon
# -------------------------------- performance ------------------------------- #
RENDER_DISTANCE = 1000 # the maximum distance where the walls will be rendered
Note
For better rendering, resolution must be in 9:16 format (1920*1080, 1280*720)
First step of the process of parsing (analyse a string or text into logical syntactic components) is to read the file(s) we will use in our project to use them in the game main logic. For that we will use the function open to be able to read the data written in the file. This function will return a fd (file descriptor) that will permit us to use the read function and store the data we want in our structs :
See .cub file example at : map example
static int open_and_validate_file(char *filename)
{
int fd;
if (check_file_extension(filename))
{
u_print_error("File extension (.cub needed)");
return (-1);
}
fd = open(filename, O_RDONLY);
if (fd < 0)
{
u_print_error("fd error");
return (-1);
}
return (fd);
}Warning
Of course, we must verify that the data is written as we want, for example if you expect an input to be an integer but the user inserts a character, we must return an error
To store our data, we prepare structures that will be able to store everything the best way (this is why you have to make scalable structs that are appropriate to a lot of case and well organized for your code workflow).
Here, we can divide the file .cub that we will parse in multiple config elements that will be :
- The textures we will be using for walls in .xpm
- The colors in
RGBused for ceiling and floor separatly - The map which is composed by 0's and 1's, the player spawn position with the direction he is looking at when he spawns (east as E, west as W, north as N, south as S)
int parse_file(char *filename, t_data *data)
{
int fd;
char *buf;
fd = open_and_validate_file(filename);
if (fd < 0)
return (1);
buf = read_entire_file(fd);
close(fd);
if (!buf)
return (1);
if (process_file_content(buf, data))
return (1);
free(buf);
if (check_map(data))
return (1);
if (find_player_pos(data))
return (1);
return (0);
}Note
The config elements will change with the bonus part for our project with doors, enemy and heal pads
Parsing is not an algorithm to follow, this is a logic and a vision of how to exploit data, there is an infinite number of ways to parse something, the key is to predict how you will use the inputs in the future for your project.
The main init function is pretty simple and looks like this :
void init(t_data *data, char **argv)
{
srand(time(NULL));
if (parse_file(argv[1], data))
close_window(data);
data->render_fog = 1;
data->mlx = mlx_init();
data->window = mlx_new_window(data->mlx, WINDOW_WIDTH, WINDOW_HEIGHT,
"cub3d");
init_walls(data);
data->door_count = 0;
data->health_count = 0;
load_sprites(data);
data->gun.is_playing = 1;
init_mouse_control(data);
data->player.stamina = MAX_STAMINA;
init_health_bar(&data->health_bar, data);
}We have 2 main parts in this initialization : mlx init and texture loading
First we initialize all the mlx data that we will need to open and handle a window (mlx pointer, window pointer...)
data->mlx = mlx_init();
data->window = mlx_new_window(data->mlx, WINDOW_WIDTH, WINDOW_HEIGHT,
"cub3d");When the window opens, we start loading all the xpm textures that we will need along the runtime directly. By storing a pointer in our main data structure
static void load_sprites(t_data *data)
{
load_texture(data, data->enemy_render.texture_path, &data->enemy.render);
load_texture(data, "bonus/textures/gun-hand-0.xpm",
&data->gun.render_arr[0]);
load_texture(data, "bonus/textures/gun-hand-1.xpm",
&data->gun.render_arr[1]);
load_texture(data, "bonus/textures/gun-hand-2.xpm",
&data->gun.render_arr[2]);
load_texture(data, "bonus/textures/heal_1.xpm",
&data->health_pad_anim.render_arr[0]);
load_texture(data, "bonus/textures/heal_2.xpm",
&data->health_pad_anim.render_arr[1]);
load_texture(data, "bonus/textures/heal_3.xpm",
&data->health_pad_anim.render_arr[2]);
load_texture(data, "bonus/textures/shot-0.xpm", &data->shot.render_arr[0]);
load_texture(data, "bonus/textures/shot-1.xpm", &data->shot.render_arr[1]);
load_texture(data, "bonus/textures/shot-2.xpm", &data->shot.render_arr[2]);
load_texture(data, "bonus/textures/play_button.xpm", &data->play_button);
load_texture(data, "bonus/textures/leave_button.xpm", &data->leave_button);
load_texture(data, "bonus/textures/menu_background.xpm",
&data->menu_background);
load_texture(data, "bonus/textures/game_over_print.xpm",
&data->game_over_print);
load_texture(data, "bonus/textures/you_won_print.xpm",
&data->you_won_print);
}But, this is not the only setup we need for this to work, we also have top setup hooks which are a big part of mlx library that are used to trigger functions depending on the event processed (mouse moved, key pressed, key released...)
int main(int argc, char **argv)
{
t_data data;
if (argc != 2)
{
u_print_error("missing map path");
return (1);
}
validate_window_size();
ft_bzero(&data, sizeof(t_data));
init(&data, argv);
mlx_hook(data.window, 2, 1L << 0, key_press_hook, &data);
mlx_hook(data.window, 3, 1L << 1, key_release_hook, &data);
mlx_hook(data.window, 6, (1L << 6), mouse_move, &data);
mlx_hook(data.window, 17, 1L << 17, close_window, &data);
mlx_mouse_hook(data.window, mouse_hook, &data);
mlx_loop_hook(data.mlx, render_loop, &data);
mlx_loop(data.mlx);
mlx_destroy_display(data.mlx);
return (0);
}Then, we can launch our loop !
Important
Well, for our case, we implemented a menu, meaning that we need to reset the game state each time the player press the play button (recalculate enemy position, close open doors, reset player position/health...)
void reset_game(t_data *data)
{
if (data->grid.grid)
u_ft_free(data->grid.grid);
parse_map(data->all_lines, data);
data->player.pitch = 0;
init_health_pad_system(data);
spawn_enemy(data);
if (data->door_grid)
u_ft_free_doors(data);
init_door_system(data);
data->game_started = 1;
data->player_won = 0;
toggle_mouse_control(data);
find_player_pos(data);
}Raycasting is a rendering technique that is used to reproduce 3D environment, even though it is not actual 3D.
Raycasting is a technique that (based on a grid that is used as the map) consists of casting rays for each column of the screen until it reaches a wall or a blocking structure (such as closed doors) and renders associated pixels in this column only.
DDA (Digital Differential Analyzer) is a line drawing algorithm used in computer graphics to generate a line segment between two specified endpoints. Here, the two endpoints are the player (his position will be where the ray starts) and the wall or blocking structure.
- Input the two endpoints of the line segment, (x1,y1) and (x2,y2).
- Calculate the difference between the x-coordinates and y-coordinates of the endpoints as dx and dy respectively.
- Calculate the slope of the line as m = dy/dx.
- Set the initial point of the line as (x1,y1).
- Loop through the x-coordinates of the line, incrementing by one each time, and calculate the corresponding y-coordinate using the equation y = y1 + m(x - x1).
- Plot the pixel at the calculated (x,y) coordinate.
- Repeat steps 5 and 6 until the endpoint (x2,y2) is reached.
Here, we have a subtle difference it term of use of the algorithm, which is that we don't know the coordinates of the point we want to go to, so we want to loop indefinitely until we reach a blocking structure.
I would sum up the use of the algorithm here to be :
- initiate the starting coordinates (player coordinates).
- increment from the starting coordinates by adding the step accordingly
void perform_dda_step(t_data *data, int i)
{
if (data->rays[i].side_dist.x < data->rays[i].side_dist.y)
{
data->rays[i].side_dist.x += data->rays[i].delta_dist.x;
data->rays[i].map_pos.x += data->rays[i].step.x;
data->rays[i].side = 0;
}
else
{
data->rays[i].side_dist.y += data->rays[i].delta_dist.y;
data->rays[i].map_pos.y += data->rays[i].step.y;
data->rays[i].side = 1;
}
}- Once we know we've reached a wall, we store the current coordinates of the ray and we calculate the distance between the player and the point reached
static int handle_hit(t_data *data, int i, t_pos map_pos)
{
t_door *door;
char cell;
if (map_pos.x < 0 || map_pos.x >= data->grid.width
|| map_pos.y < 0 || map_pos.y >= data->grid.height)
return (1);
cell = data->grid.grid[map_pos.y][map_pos.x];
if (cell == '1')
{
store_hit(data, i, map_pos, 1);
return (1);
}
else if (cell == '2')
{
door = &data->door_grid[map_pos.y][map_pos.x];
if (door)
{
store_hit(data, i, map_pos, 2);
if (door->state == DOOR_CLOSED)
return (1);
}
}
return (0);
}- repeat these 3 first steps for each column of the screen/window width
Note
Note that the logic of rendering should be the same even if you are not using mlx but the code provided will be adapted to mlx and it can differ if you use an other library
When building video games, one of the basics to know is a drawing loop. Here basically we want that loop to look be like this :
- Clear the screen (needed because we want to completely clear whatever we have drawn in the previous frame)
- Update all the data we need (player position, cast rays, calculate delta time)
- Draw the walls and doors
- Draw the sprites
And we want to iterate indefinitely in that loop until the user wants to leave. The order of rendering is very important if we want it to be a little bit realistic. This is layered rendering.
Example : In a FPS (First Person Shooter), we want to render the gun that the player is holding in the lasts sprites that you render on the screen, otherwise you would see the textures of the game above the gun which would look pretty weird
int render_loop(t_data *data)
{
if (!handle_scene(data))
return (0);
calc_delta_time_ms(data);
update_player_movement(data);
update_enemy_movement(data);
trace_ray(data, data->player.angle);
animation_routine(data);
clear_screen(data);
render_walls(data);
render_enemy_with_health(data, &data->enemy);
render_crosshair(data);
render_gun(data);
render_health_bar(data, &data->health_bar);
render_stamina(data, &data->stamina_bar);
mlx_put_image_to_window(data->mlx, data->window, data->render_img, 0, 0);
calculate_fps(data);
render_minimap(data);
return (1);
}Note
For the game to be frame rate independent, we calculate a delta time, which is the elapsed time since the program last updated and we will make scale all the movement/speed calculations with this delta time so that for example, the player goes the same speed when we have good or bad CPU
The floor or Ceiling rendering here is very simple, we just need to draw for each row from top of the screen the color of the sky until we reach half the height of the screen and then, draw the other half with the floor color.
void clear_screen(t_data *data)
{
int x;
int y;
y = -1;
while (y++ < WINDOW_HEIGHT / 2)
{
x = -1;
while (x++ < WINDOW_WIDTH)
put_pixel_to_image(data, x, y,
u_rgb_to_hex(data->ceiling.base_r,
data->ceiling.base_g, data->ceiling.base_b, 0));
}
while (y++ < WINDOW_HEIGHT)
{
x = -1;
while (x++ < WINDOW_WIDTH)
put_pixel_to_image(data, x, y,
u_rgb_to_hex(data->floor.base_r,
data->floor.base_g, data->floor.base_b, 0));
}
}Note
knowing that in the bonus part we implemented a feature that permits to the player to look up and down, we should adapt rendering knowing this by adding pitch offset every time we want to render : walls, ground/sky, sprites...
Each vertical slice of the screen represents a ray cast into the game world to detect the distance to the nearest wall. That distance is used to calculate how tall the wall should appear on screen and where to start and stop drawing it, creating a sense of depth. Texture coordinates are then mapped proportionally to that wall segment, giving the illusion of a 3D environment from a 2D grid
Main wall rendering function :
void render_walls(t_data *data)
{
int x;
int draw_start;
int draw_end;
double perp_wall_dist;
x = 0;
while (x < WINDOW_WIDTH)
{
data->rays[x].perp_wall_dist = calculate_perp_wall_dist(data, x);
perp_wall_dist = data->rays[x].perp_wall_dist;
calculate_wall_bounds(perp_wall_dist, &draw_start, &draw_end);
draw_wall_column(data, x, draw_start, draw_end);
x++;
}
}You may now understand that this is not actual 3D, it is only creating an illusion of 3D by rendering an effect of depth. Nowhere in the code we use 3D coordinates, only 2D. And this raycasting system being very useful at the time it was created, is still limited. For example, the fact that we don't have 3D coordinates makes it impossible for the player to jump, or go to different "floors".
Sprites (which are not mandatory in this project) can be hard to render properly. I would separate this part in two, first the static sprites that never move (flowers, grass...) and moving sprites :
- First, the
static sprites. An easy way to do this is by adding them to the map with a special letter/character. For example, in our game, we included heal pads that never moves, and added them to the map with the letter "H". We choose to store all their positions in a big array at the initialization of the program. Then, if we have that, we can calculate distance between the player and the pad easily and render it accordingly. Of course, we also need to know for each column of the sprite if it is hidden by a wall or a door by calculating if the distance between the first wall/door we cross is higher than the distance between the sprite and the player. If it is, we can draw the column. - Then, for
moving spritessuch as enemies, knowing that we update the position ourselves, we can easily calculate distance between the player and the moving sprite. As we do withstatic sprites, we calculate if the sprite is hidden by a wall but there is still one thing left to do, which is that we need to layer it with other sprites accordingly. For example, if the enemy is behind a pad of heal, we must render it also behind the pad of heal.
Here is all the basics you will need to implement your own raycaster engine ! Even though this is not a method used nowadays, it is still fun to practice and it definitely makes you familiar with building a game and rendering pixels on a window at a low level.
- Build a Raycaster
Math libraryusage- Window handling
- Optimization with
valgrind --tool=callgrind ./programthat permits to easily see where you can optimize your code by passing the .out file inKcachegrind - Basic game rendering logic (drawing loop, delta time...)
- Color management (RGBA or hexadecimal)
- Animation logic
Github projectsusage to create drafts of features to implement or reporting issuesA* algorithmto find the shortest path between player and enemy so that the enemy always move towards the player
When we implemented the enemy, we wanted of course that the enemy follow the player all along the game which was not so easy to do.
In order to accomplish that, we implemented an algorithm called the A* algorithm. The goal of this algorithm is to find the shortest path to go to a certain place (which here is the player position) the most optimal way.
At each iteration of its main loop, A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes :
f(n)=g(n)+h(n)
main pathfinding function :
int find_astar_path(t_data *data, t_pos start, t_pos goal, t_pos *out_path)
{
t_astar_data astar;
t_neighbor_context ctx;
int lowest;
t_astar_node *curr;
int visited[MAX_GRID_HEIGHT][MAX_GRID_WIDTH];
ft_memset(astar.nodes, 0, sizeof(astar.nodes));
ft_memset(visited, 0, sizeof(visited));
init_astar_data(data, &astar, start, goal);
ctx = (t_neighbor_context){data, &astar, goal, visited};
while (1)
{
lowest = find_lowest_f_cost(&astar);
if (lowest == -1)
break ;
curr = &astar.nodes[lowest];
curr->open = 0;
curr->closed = 1;
if (curr->pos.x == goal.x && curr->pos.y == goal.y)
return (reconstruct_path(curr, out_path, MAX_NODES));
process_neighbors_with_visited(&ctx, curr);
}
return (0);
}As you can see above, the only moment the enemy won't move is when he doesnt find a possible path to go to the enemy.
In the project of cub3d, the subject requires only to rotate the camera on the x axis. Meaning we can only rotate right or left.
We wanted to implement a pitch that would enable us to also look up and down. It may seem complicated, but it is way easier than we think. The trick is to implement a pitch variable that will increment or decrement whether the player is moving the camera up or down.
But for now, we dont have anything that would change our rendering. To change that, we calculate the pitch offset which is a value that is calculated like this pitch *(WINDOW_HEIGHT / 2)
Now, it is very easy, we just need to add the pitch offset to the y coordinates where we want to draw a pixel.
horizon_line = WINDOW_HEIGHT / 2 + (int)data->player.pitch_offset;In order to be able to resist to the enemy, the bonus maps can contain health pads that will heal the player whenever he steps above one.
For the rendering of these pads, this is pretty much the same behaviour as an usual sprite. We render it at a certain position and we layer it with the other elements (walls, enemy, doors...).
We animate it using an animation loop, which will just switch the texture using an index that increment through all the textures available using an array of texture.
static void update_hpad_indexes(t_data *data, double *acc_hpad_time,
double hpad_speed)
{
if (!data->health_pad_anim.render_arr[data->health_pad_anim.index
+ 1].info.addr)
data->health_pad_anim.index = 0;
else
data->health_pad_anim.index++;
*acc_hpad_time -= 1.0 / hpad_speed;
}- https://lodev.org/cgtutor/raycasting.html
- https://xitog.github.io/dgx/passetemps/tech_raycasting_fr.html
- https://perso.esiee.fr/~buzerl/sphinx_IMA/80%20raycast/raycast.html
- https://www.geeksforgeeks.org/computer-graphics/dda-line-generation-algorithm-computer-graphics/
- https://harm-smits.github.io/42docs/libs/minilibx/getting_started.html
- https://www.geeksforgeeks.org/dsa/a-search-algorithm/