A* in C

astar.c

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

#define GRID_X 3
#define GRID_Y 3

typedef struct node {
    int x, y;
    int g_cost, f_cost;
    bool open, blocked, closed;
    struct node* prev;
} node;

typedef struct list_node {
   node* value;
   struct list_node* next;
} list_node;

typedef struct {
    int open_count;
} a_star_info;

node list[GRID_X][GRID_Y];
a_star_info info;

// Init with the list of available nodes
void a_star_init(void) {
    info.open_count = 0;
    for (int x = 0; x < GRID_X; x++) {
        for (int y = 0; y < GRID_Y; y++) {
            node *ln = &list[x][y];
            ln->x=x;
            ln->y=y;
            ln->g_cost = ln->f_cost = 99999;
            ln->open = false;
            ln->closed = false;
            ln->blocked = false;
            ln->prev = NULL;
            info.open_count++;
        }
    }
    // Block certain nodes
    list[1][1].blocked = true;
}

int estimate(node *start, node *end) {
    return abs(start->x - end->x) + abs(start->y - end->y);
}

node* lowest_open() {
    node *lowest = NULL;
    for (int x = 0; x < GRID_X; x++) {
        for (int y = 0; y < GRID_Y; y++) {
            node *n = &list[x][y];
            if (n->open) {
                if (!lowest) {
                    lowest = n;
                } else if (n->f_cost < lowest->f_cost) {
                    lowest = n;
                }
            }
        }
    }
    return lowest;
}

void path(node *n) {
    while (n != NULL) {
        printf("(%d,%d),", n->x, n->y);
        n=n->prev;
    }
}

list_node * add_node(list_node *list, node *n) {
    list_node *next = (list_node *)  malloc(sizeof(list_node));
    next->value = n;
    next->next = NULL;
    if (list != NULL) list->next = next;
    return next;
}

list_node * populate_neighbours(node *current, list_node *neighbours) {
    list_node *head = NULL;
    if (current->x - 1 >= 0) {
        node *node = &list[current->x - 1][current->y];
        if (!node->blocked && !node->closed) {
            neighbours=add_node(neighbours, node);
            head = neighbours;
        }
    }
    if (current->y - 1 >= 0) {
        node *node = &list[current->x][current->y-1];
        if (!node->blocked && !node->closed) {
            neighbours=add_node(neighbours, node);
            if (head==NULL) head = neighbours;
        }
    }
    if (current->x + 1 < GRID_X) {
        node *node = &list[current->x+1][current->y];
        if (!node->blocked && !node->closed) {
            neighbours=add_node(neighbours, node);
            if (head==NULL) head = neighbours;
        }
    }
    if (current->y +1 < GRID_Y) {
        node *node = &list[current->x][current->y+1];
        if (!node->blocked && !node->closed) {
            neighbours=add_node(neighbours, node);
            if (head==NULL) head = neighbours;
        }

    }
    return head;
}

void a_star(node *start, node *end) {
    start->f_cost = estimate(start, end);
    start->g_cost = 0;
    start->open = true;
    info.open_count = 1;
    while (info.open_count > 0) {
        node *current = lowest_open();
        printf("Visting %d,%d\n", current->x, current->y );
        if (current == end) {
            path(end);
            break;
        }
        current->open = false;
        current->closed = true;
        info.open_count--;
        list_node *neigh = populate_neighbours(current, NULL);
        while (neigh != NULL) {
            node *n = neigh->value;
            printf("\t Neighbour %d,%d\n", n->x, n->y );

            int tentative_g = current->g_cost + 1;
            if (tentative_g < n->g_cost) {
                n->prev = current;
                n->g_cost = tentative_g;
                if (!n->open) info.open_count++;
                n->open = true;
                n->f_cost = n->g_cost + estimate(n, end);
            }
            neigh = neigh->next;
        }
    }
}


int main(void) {
    a_star_init();
    a_star(&list[0][0], &list[2][2]);
}