Skip to main content
added 184 characters in body
Source Link
elonma1234
  • 109
  • 1
  • 6

Sample run:

enter image description here

Bottom left is the starting point (0, 6) Top right is the ending point (6, 0)

solve.c

solve.c

Sample run:

enter image description here

Bottom left is the starting point (0, 6) Top right is the ending point (6, 0)

solve.c

Source Link
elonma1234
  • 109
  • 1
  • 6

Maze SOLVER in C

a maze solver in C.

I have not included the maze generation code because i'm not looking for a review on that in this post, but the maze solver operates on a 1D array of cells, for more info: Maze generation algorithm review

solve.c

#include "../struct.h"
#include "../maze.c"
#include "../cell.c"
#include <stdio.h>
#include <stdlib.h>


bool topwall(Maze *maze, point *p);
bool botwall(Maze *maze, point *p);
bool leftwall(Maze *maze, point *p);
bool rightwall(Maze *maze, point *p);

bool equal(point p, point p2);

void solve(Maze *maze, point p, point e) {
    static bool found = false;
    if (found) return;

    if (equal(p, e)) {
        found = true;  
    }

    (*cell_at(maze, p.x, p.y)).visited = true;
    point temp;
    if (p.x < (colMAX - 1) && !rightwall(maze, &p) && !is_visited(maze, p.x + 1, p.y)) {
        temp = p;
        temp.x++;
        solve(maze, temp, e);
    } 
    if (p.x > 0 && !leftwall(maze, &p) && !is_visited(maze, p.x - 1, p.y)) {
        temp = p;
        temp.x--;
        solve(maze, temp, e);
    }
    if (p.y > 0 && !topwall(maze, &p) && !is_visited(maze, p.x, p.y - 1)) {
        temp = p;
        temp.y--;
        solve(maze, temp, e);
    }
    if (p.y < (rowMAX - 1) && !botwall(maze, &p) && !is_visited(maze, p.x, p.y + 1)) {
        temp = p;
        temp.y++;
        solve(maze, temp, e);
    }

    if (found) {
        (*cell_at(maze, p.x, p.y)).path = true;
    }
    return;
}

bool equal(point p, point p2) {
    return (p.x == p2.x && p.y == p2.y);
}

bool rightwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x, p->y)).right_wall;
}

bool leftwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x - 1, p->y)).right_wall;
}

bool botwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x, p->y)).bottom_wall;
}

bool topwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x, p->y - 1)).bottom_wall;
}

cell.c

#ifndef C
#define C
#include "struct.h"
#include <stdbool.h>

cell *cell_at(Maze *maze, size_t x, size_t y) {
    return &maze->cells[x + y * maze->width];
}

bool is_visited(Maze *maze, size_t x, size_t y) {
    return (*cell_at(maze, x, y)).visited;
}

#endif

main.c

#include <stdio.h>
#include "generate/generate.c"
#include "solve/solve.c"
#include "maze.c"

int main(int argc, char *argv[]) {
    srand(time(0));

    if (argc == 1) {    
        colMAX = rowMAX = 7; // default 
    } else colMAX = rowMAX = (atoi(argv[2]));
    stack = malloc((rowMAX * colMAX) * sizeof(point));
    Maze maze = {colMAX, rowMAX, malloc(rowMAX * colMAX)};

    initcells(&maze);
    point p = {0, 0};
    push(p);
    while (sp > 0) {
        generatemaze(&maze);
    }
    printmaze(&maze);
    putchar('\n');
    
    cell* cellptr = maze.cells;
    for (int i = 0; i < (rowMAX * colMAX); ++i) {
        cellptr->path = false;                          // reset
        cellptr++->visited = false;    
    }

    point s = {0, 1};               // custom starting / end point not yet implemented
    point e = {6, 0};
    solve(&maze, s, e);

    printmaze(&maze);
    return 0;
}

struct.h

#ifndef H
#define H
#include <stddef.h>

typedef struct cellstruct {
    bool bottom_wall: 1;
    bool right_wall: 1;
    bool visited: 1;
    bool path: 1;
} cell;

typedef struct mazestruct {
    size_t width;
    size_t height;
    cell *cells;
} Maze;

typedef struct {
    size_t x;
    size_t y;
} point;

typedef enum {
    LEFT,
    RIGHT,
    TOP,
    BOTTOM
} direction;
    
#endif