Breadth first search suddenly crashes

Question

I'm trying to implement BFS on a 400x200 grid that inputs a text file with an ordered starting pair and an ordered ending pair. I used a queue to keep track of opened nodes and an array to keep tracked of closed nodes. My program keeps crashing at random on the same input while checking for opened nodes in the queue.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>


typedef struct Node Node;
typedef struct Qnode Qnode;

struct Node{
    Node* up;
    Node* down;
    Node* left;
    Node* right;
    int xpos;
    int ypos;
    int marked;
};
struct Qnode{
    Qnode* next;
    Node* Gnode; 
};
Qnode* front = NULL;
Qnode* rear = NULL;
int queuesize = 0;
int solutioncost = 0;
Node* closednodes[80000];
int nodesclosed = 0;

void enqueue(Node* node){
    if (queuesize == 0){
        rear = (Qnode*)malloc(sizeof(Qnode*));
        rear->Gnode = node;
        rear->next = NULL;
        front = rear;
    }
    else{
        Qnode* temp = (Qnode*)malloc(sizeof(Qnode*));
        rear->next = temp;
        temp->Gnode = node;
        temp->next = NULL;
        rear = temp;
    }
        queuesize++;
}

Node* dequeue(){
    Qnode* temp = front;
    if (queuesize == 0){
        printf("Error!");
    }
    else{
        Node* temp1 = front->Gnode;
        temp = temp->next;
        free(front);
        front = temp;
        queuesize--;
        return temp1;
    }

}

Node* generate(int x, int y){
    printf("Generating node (%d,%d)...\n", x, y);
    if ((x >0 && x <=400) && (y >0 && y <=200)){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->xpos = x;
    temp->ypos = y;
    temp->marked = 0;
    temp->up = NULL;
    temp->down = NULL;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
    }
    else{
        printf("Invalid starting point! \n");
    }
}

void expand(Node* node, int xend, int yend){
    int flag = 0;
    closednodes[nodesclosed] = node;
    nodesclosed++;
    dequeue();
    if(node->marked == 1){
        printf("already expanded");
    }

    else{
        printf("Expanding node (%d, %d)...\n", node->xpos, node->ypos);
        node->marked = 1;
        if (node->xpos == xend && node->ypos == yend){
            printf("Node reached!");
            queuesize = 0; 
            return;
        }
        if (node->xpos-1 >0 && node->left == NULL){
            int k = 0;
            int j = 0;
            Qnode* temp2 = front;
            printf("%d", queuesize);
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                printf("%d, %d,\n", xx, yy);
                if (xx == node->xpos-1 && yy == node->ypos)
                    flag = 1;
                temp2 = temp2->next;
                }
            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos-1 && yy == node->ypos)
                    flag = 1;
            }
            if (flag == 0){
                node->left = generate(node->xpos-1, node->ypos);
                node->left->right = node->left;
                enqueue(node->left);
            }
            else{
                printf("(%d, %d) not generated.\n", node->xpos-1, node->ypos);
                flag = 0;
            }
        }
        if (node->xpos+1 <=400 && node->right ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                printf("%d, %d,\n", xx, yy);
                if (xx == node->xpos+1 && yy == node->ypos)
                    flag = 1;
                temp2 = temp2->next;
                }

            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos+1 && yy == node->ypos)
                    flag = 1;
            }
            if (flag == 0){
                node->right = generate(node->xpos+1, node->ypos);
                node->right->left = node->right;
                enqueue(node->right);
            }
            else{
                printf("(%d, %d) not generated.\n", node->xpos+1, node->ypos);
                flag = 0;
            }
        }
        if (node->ypos+1 <=200 && node->up ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
        printf("%d", queuesize);
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                if (xx == node->xpos && yy == node->ypos+1)
                    flag = 1;
                temp2 = temp2->next;
                }


            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos && yy == node->ypos+1)
                    flag = 1;
            }

            if (flag ==0){
                node->up = generate(node->xpos, node->ypos+1);
                node->up->down = node->up;
                enqueue(node->up);
            }
            else{
                printf("(%d, %d) not generated.\n", node->xpos, node->ypos+1);
            flag = 0;
            }
        }
        if (node->ypos-1 >0 && node->down ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                printf("%d, %d,\n", xx, yy);
                if (xx == node->xpos && yy == node->ypos-1)
                    flag = 1;
                temp2 = temp2->next;
                }

            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos && yy == node->ypos-1)
                    flag = 1;
            }
            if (flag ==0){
                node->down = generate(node->xpos, node->ypos-1);
                node->down->up = node->down;
                enqueue(node->down);
            }
            else{
            printf("(%d, %d) not generated.\n", node->xpos, node->ypos-1);
            flag = 0;
            }
        }
        printf("EXPANSION ENDS\n");
        return;
    }

}

int main(){
    int x_start, y_start, x_end, y_end;
    FILE *fp;
    fp = fopen("testfile.txt", "r");
    if (fp == NULL)
        printf("Error printing output. \n");
    else
    fscanf(fp, "(%d,%d)\n", &x_start, &y_start);
    fscanf(fp, "(%d,%d)\n", &x_end, &y_end);
    printf("Starting point is (%d, %d)\n", x_start, y_start);
    printf("Ending point is (%d, %d)\n", x_end, y_end);

    Node* start = generate(x_start, y_start);
    enqueue(start);
    while(queuesize!=0){
    expand(front->Gnode, x_end, y_end);
    }

    fclose(fp);
}

using testfile.txt

(1,1)
(50,50)

this input will cause the program to crash at random. I am suspecting I have a problem with my queue.

Answer 1

In the enqueue function, you should allocate the new nodes as (Qnode*)malloc(sizeof(Qnode)) (instead of (Qnode*)). The code you wrote allocates only the size of a pointer for each struct, so any write to such an object will stomp on some other object's memory.