Simple maze solver in C

maze.c

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point* path;
    int path_size;
} Path;

typedef struct {
    char** board;
    char wall;
    Point start;
    Point end;
    int width;
    int height;
} Maze;

typedef struct {
    bool** visited;
    Path path;
    const Maze* maze;
} Solver;

Path maze_solver(const Maze* maze);
void destroy_path(Path* path);

// function to test the maze_solver function
void test_maze_solver() {
    char maze[6][12] = {
        {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', ' ', 'X'},
        {'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', 'X'},
        {'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', 'X'},
        {'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', ' ', 'X'},
        {'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X'},
        {'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}
    };


    Point maze_result[15] = {
        {10, 0},
        {10, 1},
        {10, 2},
        {10, 3},
        {10, 4},
        {9, 4},
        {8, 4},
        {7, 4},
        {6, 4},
        {5, 4},
        {4, 4},
        {3, 4},
        {2, 4},
        {1, 4},
        {1, 5}
    };
    int y_size = 6;
    int x_size = 12;
    Point start = {10, 0};
    Point end = {1, 5};

    // Copy maze array into a 2D array
    char** maze_copy = (char**) malloc(sizeof(char*) * y_size);
    for (int i = 0; i < y_size; i++) {
        maze_copy[i] = malloc(sizeof(char) * x_size);
        for (int j = 0; j < x_size; j++) {
            maze_copy[i][j] = maze[i][j];
        }
    }

    Maze maze_struct = {
        .board = maze_copy,
        .wall = 'X',
        .start = start,
        .end = end,
        .width = x_size,
        .height = y_size
    };

    // call the maze_solver function and store the result
    Path result = maze_solver(&maze_struct);

    // check that the result matches the expected result
    for (int i = 0; i < result.path_size; i++) {
        assert(result.path[i].x == maze_result[i].x);
        assert(result.path[i].y == maze_result[i].y);

        // Draw path points on the maze (to te maze variable)
        maze[result.path[i].y][result.path[i].x] = '.';
    }

    // Print the maze
    for (int i = 0; i < y_size; i++) {
        for (int j = 0; j < x_size; j++) {
            printf("%c", maze[i][j]);
        }
        printf("\n");
    }

    destroy_path(&result);
    // Free board 2D array
    for (int i = 0; i < y_size; i++) {
        free(maze_copy[i]);
    }
    free(maze_copy);
}

Solver create_solver(const Maze* maze) {

    // Allocate 2D array of booleans the size of the maze
    // Selection acis order is: visited[y][x]
    bool** visited = malloc(sizeof(bool*) * maze->height);
    for (int i = 0; i < maze->height; i++) {
        visited[i] = malloc(sizeof(bool) * maze->width);
        for (int j = 0; j < maze->width; j++) {
            visited[i][j] = false;
        }
    }

    Solver solver = {
        .visited = visited,
        .path = {
            .path = NULL,
            .path_size = 0
        },
        .maze = maze
    };

    return solver;
}

void destroy_solver(Solver* solver) {
    // Deallocate visited 2D array
    for (int i = 0; i < solver->maze->height; i++) {
       free(solver->visited[i]);
    }
    free(solver->visited);
}

void destroy_path(Path* path) {
    free(path->path);
}

void path_addPoint(Path* path, Point point) {
    path->path_size++;
    path->path = realloc(path->path, sizeof(Point) * path->path_size);
    path->path[path->path_size - 1] = point;
}

Path path_copyToHeap(Path path) {
    Path new_path = {
        .path = malloc(sizeof(Point) * path.path_size),
        .path_size = path.path_size
    };
    for (int i = 0; i < path.path_size; i++) {
        new_path.path[i] = path.path[i];
    }
    return new_path;
}

// Recursive function to solve the maze
Point solver_run(Solver* solver, Path branch_path, Point point) {

    /**
     * BASE CASES
    */
    // The point we are looking at is the end of the maze
    if (
        point.x == solver->maze->end.x &&
        point.y == solver->maze->end.y
    ) {
        // branch_path is stack allocated, so we need to copy it
        // to the heap, otherwise it will be corrupted when the
        // function returns
        Path final_path = path_copyToHeap(branch_path);

        // Add the final point to the heap allocated path
        path_addPoint(&final_path, point);

        // Write this final path as a result of a solver
        solver->path = final_path;

        return point;
    }
    // The point we are looking at is outside the maze
    if (
        point.x < 0 ||
        point.x >= solver->maze->width ||
        point.y < 0 ||
        point.y >= solver->maze->height
    ) {
        return (Point) {-1, -1};
    }
    // The point we are looking at is the wall
    if (solver->maze->board[point.y][point.x] == solver->maze->wall) {
        return (Point) {-1, -1};
    }
    // The point we are looking at has already been visited
    if (solver->visited[point.y][point.x]) {
        return (Point) {-1, -1};
    }

    // By this time the point is a valid point to visit

    // We need to make a path for a new recursion branch
    // and add the current point to it
    // - We can keep this path on the stack since we
    //   will never return it, only pass it to the next recursion,
    //   so while we need it, it will not be deallocated
    Point new_path_points_arr[branch_path.path_size + 1];
    Path new_branch_path = {
        .path = new_path_points_arr,
        .path_size = branch_path.path_size + 1
    };
    for (int i = 0; i < branch_path.path_size; i++) {
        new_branch_path.path[i] = branch_path.path[i];
    }
    // Add the current point to the new path
    new_branch_path.path[branch_path.path_size] = point;

    // Mark it as visited
    solver->visited[point.y][point.x] = true;

    /**
     * RECURSION
    */
    Point above = (Point) {point.x, point.y - 1};
    Point below = (Point) {point.x, point.y + 1};
    Point left = (Point) {point.x - 1, point.y};
    Point right = (Point) {point.x + 1, point.y};

    Point directions[4] = {above, below, left, right};

    // Loop over directions and call solver_run on each of them
    for (int i = 0; i < 4; i++) {
        Point result = solver_run(solver, new_branch_path, directions[i]);
        if (result.x != -1 && result.y != -1) {
            return result;
        }
    }

    return (Point) {-1, -1};
}

// Wrapper function for the recursive solver function
Path maze_solver(const Maze* maze) {

    // Create solver struct
    // It holds the necesarry context for the solver which
    // passes it recuresively to itself
    Solver solver = create_solver(maze);

    Path empty_path = {
        .path = NULL,
        .path_size = 0
    };
    // Start solving the maze
    solver_run(&solver, empty_path, maze->start);

    // Save resulting path
    Path result = solver.path;

    // Deallocate heap allocated memory in the solver
    destroy_solver(&solver);

    // Return saved path
    return result;
}

int main() {
    test_maze_solver();
    printf("All tests passed!\n");
    return 0;
}