A* Algorithm

//need struct for linked list node, list_node
struct list_node{
    list_node *next; //next in list, in whatever linked list it's in
    list_node *prev; //previous in list, whatver linked list it's in
    list_node *parent; //the parent (in regards to A* algo)
    int x,y;
    int f,g,h;
    list_node(){
        next = 0;
        prev = 0;
        parent = 0;
        x,y,f,g,h = 0;
    }
    list_node(list_node* i_next, list_node* i_prev, list_node* i_parent, int i_x, int i_y, int i_f, int i_g , int i_h){
        next = i_next;
        prev = i_prev;
        parent = i_parent;
        x = i_x;
        y = i_y;
        f = i_f;
        g = i_g;
        h = i_h;
    }
};

//generic struct for linked lists
struct list{
    list_node* first;
    list_node* last;
};

//An even better A*, gash damn!
vector<vector<int>> A_star(bool block_map[],int map_width, int x1, int y1, int x2, int y2){
    vector<vector<int>> search_q; //the main "list", could really be turned into what ever datat type you wantx

    list open_set = {nullptr,nullptr}; //the start of the open_set
    list closed_set = {nullptr,nullptr};; //the start of the closed_set

    //create first node
    list_node temp = {nullptr, nullptr, nullptr, x1, y1, 0, 0, 0};

    //add it to open_set
    open_set.first = &temp;
    open_set.last = &temp;

    //while open_set isn't empty, keep picking off the node with the smallest f
    int it2debug = 0;
    while(open_set.first!=nullptr){

        //find node in open_set with least f, make it q
        ///////////////////////////////////
        bool search_f = true;
        list_node* lowest_f = nullptr; //points to the node with lowest f
        int least_f = 999999; //start with high (lol) number
        list_node* current = open_set.first; //points to the current node, we're searching
        while(search_f){

            if(current == nullptr){
                break;
            }

            if(current->f<=least_f){ //if, it'shas a lesser f, point to it... THIS ALSO ENSURES THE LAST ONE POPPED ON GETS PICKED
                lowest_f = current;
                least_f = lowest_f->f;
            }
            if(current==open_set.last){ //if cuurently pointing to last nodee, then stop search
                search_f = false;
            }else{
                current = current->next;
            }
        }
        //when done with search, lowest_f should point to node with lowest f

        //Find lowest_f node in open_set and call it q
        ////////////////////////////
        list_node* q = lowest_f; //q has the lowest f

        /////DEBUGGG AGAIN DAMNNN
        if(it2debug>0){printf("\n Q: (%d,%d,%d,%d)",q->x, q->y, (q->parent)->x, (q->parent)->y);}
        it2debug++;

        //POPping off q from OPEN_SET
        ////////////////////////
        if(q->prev!=nullptr){ //if lowest_f is not FIRST in list
            (q->prev)->next = q->next; //update the previous node in list
        }else{ //if lowest_f is first in list
            open_set.first = q->next; //update the open_set struct
        }
        if(q->next!=nullptr){ //if lowest_f is not LAST in list
            (q->next)->prev = q->prev; //update the next node in list
        }else{ //if lowest_f is last in list
            open_set.last = q->prev; //update the open_set struct
        }
        //open_set (and it's elements) are correct and up to date

        list_node* neighbors[4]; //The FOUR neighbors
        neighbors[0] = new list_node;
        *neighbors[0] = {nullptr, nullptr, q, (q->x)-1 , q->y , 9999, 9999, 9999};
        neighbors[1] = new list_node;
        *neighbors[1] = {nullptr, nullptr, q, (q->x)+1 , q->y , 9999, 9999, 9999};
        neighbors[2] = new list_node;
        *neighbors[2] = {nullptr, nullptr, q, q->x , (q->y)-1 , 9999, 9999, 9999};
        neighbors[3] = new list_node;
        *neighbors[3] = {nullptr, nullptr, q, q->x , (q->y)+1 , 9999, 9999, 9999};

        //For each neighbor/successor
        for(int i = 0; i<4; i++){

            //if neighbor is target, then we can stop
            if((neighbors[i]->x==x2)&&(neighbors[i]->y==y2)){
                printf("reach the kind and gentle trget");
                //Just so it terminates
                open_set.first=nullptr;
                open_set.last=nullptr;
                break;
            }

            //if neighbor tile is blocked then we can stop
            //neighbor[0]->
            if(block_map[(neighbors[i]->y*map_width)+neighbors[i]->x]==true){
                continue; //move on to next neighbor
            }

            //Calculate The 3 Values: f, g, h
            neighbors[i]->g = q->g + 1;
            neighbors[i]->h = abs(y2-(neighbors[i]->y)) + abs(x2-(neighbors[i]->x));
            neighbors[i]->f = neighbors[i]->g + neighbors[i]->h;

            //Cycle Through OPEN_SET and check if the neighbor is already in there (with lower f or does it matter here?)
            bool search_o = true; //search flag
            bool in_open =  false; //flag indicating if neighbor is in OPNE_SET
            current = open_set.first; //start at beginning
            while(search_o){

                //Check if at end of list
                if(current==nullptr){
                    search_o = false;
                    break;
                }

                //Check x,y values in node
                if( (current->x==neighbors[i]->x) && (current->y==neighbors[i]->y)){
                    in_open = true;
                }

                //Move on to search next node in list
                current = current->next;

            }
            if(in_open){
                continue; //skip this neighbor
            }

            //Cycle Through CLOSED_SET and check if the neighbor is already in there (with lower f or does it matter here?)
            bool search_c = true; //search flag
            bool in_closed =  false; //flag indicating if neighbor is in CLOSED_SET
            current = closed_set.first; //start at beginning
            while(search_c){

                //Check if at end of list
                if(current==nullptr){
                    search_c = false;
                    break;
                }

                //Check x,y values in node
                if( (current->x==neighbors[i]->x) && (current->y==neighbors[i]->y)){
                    in_closed = true;
                }

                //Move on to search next node in list
                current = current->next;

            }
            if(in_closed){
                continue; //skip this neighbor
            }

            //If we've made it to this point, it isn't in CLOSED or OPEN SET
            //ADD neighbor to OPEN_SET
            neighbors[i]->next = nullptr; //indicate neighbor is at end of list
            neighbors[i]->prev = open_set.last; //update neighbor who it's behind
            if(open_set.last!=nullptr){open_set.last->next = neighbors[i];} //the (former) last item in list now points to neighbor
            open_set.last = neighbors[i]; //the open_set is updated
            if(open_set.first==nullptr){open_set.first= neighbors[i];}; //if this is the first item in open_set


        }//Done cycling through neighbors

        //ADD q to CLOSED_SET
        q->next = nullptr; //indicate q is at end of list
        q->prev = closed_set.last; //update q who it's behind
        if(closed_set.last!=nullptr){closed_set.last->next = q;} //the (former) last item in list now points to neighbor
        closed_set.last= q; //the open_set is updated
        if(closed_set.first==nullptr){closed_set.first= q;}; //if this is the first item in open_set

        //DEBUGGING
        //Print out the closed and open_sets
        //...the closed set
        bool printing = true;
        list_node* current2 = closed_set.first;
        printf("\nCLOSED: ");
        while(printing){
            if(current2==nullptr){
                printing = false;
                break;
            }
            printf(" (%d,%d) ", current2->x, current2->y );
            current2 = current2->next;

        }
        //...the open set
        printing = true;
        current2 = open_set.first;
        printf("\nOPEN: ");
        while(printing){
            if(current2==nullptr){
                printing = false;
                break;
            }
            if(current2==current2->next){current2->next = nullptr;}
            printf(" (%d,%d,%d) ", current2->x, current2->y, current2->f );
            current2 = current2->next;
        }


        //Just so it terminates
        //open_set.first=nullptr;
        //open_set.last=nullptr;

    }//end open_list empty

    //ADD final target onto CLOSED_SET
    list_node* final_node = new list_node; //a temporary node for final step
    *final_node = {nullptr, nullptr, closed_set.last, x2 , y2 , 9999, 9999, 9999};
    final_node->next = nullptr; //indicate q is at end of list
    final_node->prev = closed_set.last; //update q who it's behind
    if(closed_set.last!=nullptr){closed_set.last->next = final_node;} //the (former) last item in list now points to neighbor
    closed_set.last = final_node; //the open_set is updated
    if(closed_set.first==nullptr){closed_set.first= final_node;}; //if this is the first item in open_set

    //DEBUGGING
    //Print out the closed and open_sets
    //...the closed set
    bool printing = true;
    list_node* current = closed_set.first;
    printf("\nCLOSED: ");
    while(printing){
        if(current==nullptr){
            printing = false;
            break;
        }
        printf(" (%d,%d) ", current->x, current->y );
        list_node* temp = current; //Fo deletion
        current = current->next;
        delete temp; //Also fo deletion

    }
    //...the open set
    printing = true;
    current = open_set.first;
    printf("\nOPEN: ");
    while(printing){
        if(current==nullptr){
            printing = false;
            break;
        }
        printf(" (%d,%d,%d) ", current->x, current->y, current->f );
        list_node* temp; //fo deletion
        current = current->next;
        delete temp; //also fo deletion

    }


    printf("one day on eddsa");
    return search_q;
}