search.h

#ifndef SEARCH_H
#define SEARCH_H
#include "maze_gen.h"

/* Search function prototypes:
 * Each returns pathLength and expanded nodes.
 * For AStar, additionally fills path array (sequence of coordinates) and returns len.
 */
void DFS_Search(Maze *maze, int *pathLength, int *expanded);
void BFS_Search(Maze *maze, int *pathLength, int *expanded);
int AStar_Search(Maze *maze, int *pathLength, int *expanded, int path[][2], int maxpath);

#endif

search.c

#include "search.h"
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    int x, y;
    int g, h;
    struct Node *parent;
} Node;

static int heuristic(int x, int y, int gx, int gy) {
    int dx = x - gx; if (dx < 0) dx = -dx;
    int dy = y - gy; if (dy < 0) dy = -dy;
    return dx + dy;
}

/* DFS (stack) */
void DFS_Search(Maze *maze, int *pathLength, int *expanded) {
    int w = maze->width, h = maze->height;
    char visited[h][w];
    memset(visited, 0, sizeof(visited));
    *expanded = 0; *pathLength = 0;

    Node *stack[100000];
    int top = 0;

    Node *start = malloc(sizeof(Node));
    start->x = maze->startX; start->y = maze->startY; start->parent = NULL;
    stack[top++] = start;

    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

    while (top > 0) {
        Node *cur = stack[--top];
        if (visited[cur->y][cur->x]) { free(cur); continue; }
        visited[cur->y][cur->x] = 1;
        (*expanded)++;
        if (cur->x == maze->endX && cur->y == maze->endY) {
            Node *p = cur;
            while (p) {
                if (maze->grid[p->y][p->x] == ' ') maze->grid[p->y][p->x] = '.';
                (*pathLength)++;
                p = p->parent;
            }
            // free remaining stack
            while (top--) free(stack[top]);
            free(cur);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = cur->x + dirs[i][0], ny = cur->y + dirs[i][1];
            if (nx >= 0 && ny >= 0 && nx < w && ny < h && maze->grid[ny][nx] != '#' && !visited[ny][nx]) {
                Node *n = malloc(sizeof(Node));
                n->x = nx; n->y = ny; n->parent = cur;
                stack[top++] = n;
            }
        }
    }
}

/* BFS (queue) */
void BFS_Search(Maze *maze, int *pathLength, int *expanded) {
    int w = maze->width, h = maze->height;
    char visited[h][w];
    memset(visited, 0, sizeof(visited));
    *expanded = 0; *pathLength = 0;

    Node **queue = malloc(sizeof(Node*) * (w*h + 10));
    int qf = 0, qr = 0;

    Node *start = malloc(sizeof(Node));
    start->x = maze->startX; start->y = maze->startY; start->parent = NULL;
    queue[qr++] = start;

    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

    while (qf < qr) {
        Node *cur = queue[qf++];
        if (visited[cur->y][cur->x]) { free(cur); continue; }
        visited[cur->y][cur->x] = 1;
        (*expanded)++;
        if (cur->x == maze->endX && cur->y == maze->endY) {
            Node *p = cur;
            while (p) {
                if (maze->grid[p->y][p->x] == ' ') maze->grid[p->y][p->x] = '.';
                (*pathLength)++;
                p = p->parent;
            }
            // free queue
            for (int i = qf; i < qr; i++) free(queue[i]);
            free(queue);
            free(cur);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = cur->x + dirs[i][0], ny = cur->y + dirs[i][1];
            if (nx >= 0 && ny >= 0 && nx < w && ny < h && maze->grid[ny][nx] != '#' && !visited[ny][nx]) {
                Node *n = malloc(sizeof(Node));
                n->x = nx; n->y = ny; n->parent = cur;
                queue[qr++] = n;
            }
        }
    }
    free(queue);
}

/* A* (returns path array length):
 * path[][] will be filled as path[0..len-1] with coordinates from start->...->goal
 * returns len (0 if no path)
 */
int AStar_Search(Maze *maze, int *pathLength, int *expanded, int path[][2], int maxpath) {
    int w = maze->width, h = maze->height;
    char closed[h][w];
    memset(closed, 0, sizeof(closed));
    *expanded = 0; *pathLength = 0;

    Node **open = malloc(sizeof(Node*) * (w*h*4 + 10));
    int openCount = 0;

    Node *start = malloc(sizeof(Node));
    start->x = maze->startX; start->y = maze->startY; start->g = 0;
    start->h = heuristic(start->x, start->y, maze->endX, maze->endY); start->parent = NULL;
    open[openCount++] = start;

    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

    while (openCount > 0) {
        // find best f = g + h
        int best = 0;
        for (int i = 1; i < openCount; i++) {
            if (open[i]->g + open[i]->h < open[best]->g + open[best]->h) best = i;
        }
        Node *cur = open[best];
        open[best] = open[--openCount];

        if (closed[cur->y][cur->x]) { free(cur); continue; }
        closed[cur->y][cur->x] = 1;
        (*expanded)++;

        if (cur->x == maze->endX && cur->y == maze->endY) {
            // reconstruct path into array
            Node *p = cur;
            int len = 0;
            while (p && len < maxpath) {
                path[len][0] = p->x;
                path[len][1] = p->y;
                len++;
                p = p->parent;
            }
            // mark path on grid
            for (int i = 0; i < len; i++) {
                int x = path[i][0], y = path[i][1];
                if (maze->grid[y][x] == ' ') maze->grid[y][x] = '.';
            }
            *pathLength = len;
            // free open list
            for (int i = 0; i < openCount; i++) free(open[i]);
            free(open);
            free(cur);
            return len;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur->x + dirs[i][0], ny = cur->y + dirs[i][1];
            if (nx >= 0 && ny >= 0 && nx < w && ny < h && maze->grid[ny][nx] != '#' && !closed[ny][nx]) {
                Node *n = malloc(sizeof(Node));
                n->x = nx; n->y = ny;
                n->g = cur->g + 1;
                n->h = heuristic(nx, ny, maze->endX, maze->endY);
                n->parent = cur;
                open[openCount++] = n;
            }
        }
    }

    free(open);
    return 0; // no path
}

player.h

#ifndef PLAYER_H
#define PLAYER_H
#include "maze_gen.h"

void playerPlay(Maze *maze, int *steps, double *timeUsed);

#endif

player.c

#include "player.h"
#include "display.h"
#include <stdio.h>
#include <time.h>

void playerPlay(Maze *maze, int *steps, double *timeUsed) {
    int x = maze->startX;
    int y = maze->startY;
    char buf[16];
    *steps = 0;
    clock_t t0 = clock();

    while (!(x == maze->endX && y == maze->endY)) {
        // clear screen and display
        printf("\x1b[2J\x1b[H");
        displayMazeWithPlayer(maze, x, y);
        printf("\nMove (W/A/S/D) and press Enter: ");
        if (fgets(buf, sizeof(buf), stdin) == NULL) continue;
        char move = buf[0];
        int nx = x, ny = y;
        if (move == 'W' || move == 'w') ny--;
        else if (move == 'S' || move == 's') ny++;
        else if (move == 'A' || move == 'a') nx--;
        else if (move == 'D' || move == 'd') nx++;
        else {
            printf("Invalid input. Use W/A/S/D.\n");
            continue;
        }

        // bounds & wall check
        if (nx < 0 || ny < 0 || nx >= maze->width || ny >= maze->height || maze->grid[ny][nx] == '#') {
            printf("Invalid move! There's a wall. Press Enter to continue...");
            fgets(buf, sizeof(buf), stdin);
            continue;
        }
        x = nx; y = ny; (*steps)++;
    }

    clock_t t1 = clock();
    *timeUsed = (double)(t1 - t0) / CLOCKS_PER_SEC;
    // final display
    printf("\x1b[2J\x1b[H");
    displayMazeWithPlayer(maze, x, y);
    printf("\n🎉 You escaped the maze in %d steps, %.2f seconds!\n", *steps, *timeUsed);
}