🗂️ search.c

#include "search.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

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

typedef struct {
    Node *data[10000];
    int front, rear;
} Queue;

static void push(Queue *q, Node *n) { q->data[q->rear++] = n; }
static Node *pop(Queue *q) { return q->data[q->front++]; }
static int empty(Queue *q) { return q->front == q->rear; }

static int heuristic(int x, int y, int gx, int gy) {
    return abs(x - gx) + abs(y - gy);
}

void DFS_Search(Maze *maze, int *pathLength, int *expanded) {
    int w = maze->width, h = maze->height;
    int visited[h][w];
    for (int i=0;i<h;i++) for (int j=0;j<w;j++) visited[i][j]=0;
    *expanded = 0; *pathLength = 0;

    int dirs[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    Node *stack[10000]; int top=0;

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

    while(top>0){
        Node *cur = stack[--top];
        if(visited[cur->y][cur->x]) continue;
        visited[cur->y][cur->x]=1;
        (*expanded)++;
        if(cur->x==maze->endX && cur->y==maze->endY){
            while(cur){ 
                if(maze->grid[cur->y][cur->x]==' ') maze->grid[cur->y][cur->x]='.';
                (*pathLength)++; 
                cur=cur->parent; 
            }
            break;
        }
        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 *next=malloc(sizeof(Node));
                next->x=nx; next->y=ny; next->parent=cur;
                stack[top++]=next;
            }
        }
    }
}

void BFS_Search(Maze *maze, int *pathLength, int *expanded) {
    int w=maze->width,h=maze->height;
    int visited[h][w]; for(int i=0;i<h;i++) for(int j=0;j<w;j++) visited[i][j]=0;
    *expanded=0; *pathLength=0;
    int dirs[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    Queue q={.front=0,.rear=0};
    Node *start=malloc(sizeof(Node));
    start->x=maze->startX; start->y=maze->startY; start->parent=NULL;
    push(&q,start);
    while(!empty(&q)){
        Node *cur=pop(&q);
        if(visited[cur->y][cur->x]) continue;
        visited[cur->y][cur->x]=1; (*expanded)++;
        if(cur->x==maze->endX && cur->y==maze->endY){
            while(cur){ 
                if(maze->grid[cur->y][cur->x]==' ') maze->grid[cur->y][cur->x]='.';
                (*pathLength)++; 
                cur=cur->parent; 
            }
            break;
        }
        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 *next=malloc(sizeof(Node));
                next->x=nx; next->y=ny; next->parent=cur;
                push(&q,next);
            }
        }
    }
}

void AStar_Search(Maze *maze, int *pathLength, int *expanded) {
    int w=maze->width,h=maze->height;
    int closed[h][w]; for(int i=0;i<h;i++) for(int j=0;j<w;j++) closed[i][j]=0;
    *expanded=0; *pathLength=0;

    Node *open[10000]; int count=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[count++]=start;

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

    while(count>0){
        int best=0;
        for(int i=1;i<count;i++){
            if(open[i]->g+open[i]->h < open[best]->g+open[best]->h)
                best=i;
        }
        Node *cur=open[best];
        open[best]=open[--count];
        if(closed[cur->y][cur->x]) continue;
        closed[cur->y][cur->x]=1; (*expanded)++;

        if(cur->x==maze->endX && cur->y==maze->endY){
            while(cur){
                if(maze->grid[cur->y][cur->x]==' ') maze->grid[cur->y][cur->x]='.';
                (*pathLength)++;
                cur=cur->parent;
            }
            break;
        }

        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 *next=malloc(sizeof(Node));
                next->x=nx; next->y=ny;
                next->g=cur->g+1;
                next->h=heuristic(nx,ny,maze->endX,maze->endY);
                next->parent=cur;
                open[count++]=next;
            }
        }
    }
}