struct coord
{
    int gx, gy;
};

struct node
{
    int ny, nx, cost_path, cost_heuristic, cost_sum;
    coord parent;
};

void find_path ( coord initial, coord target, vector<coord> &moves )
{
    bool found = false;
    bool searching = true;

    list<node> open;
    list<node> closed;

    node start_node, best_node;
    coord new_coord;

    start_node.nx = initial.gx;
    start_node.ny = initial.gy;
    start_node.cost_heuristic = 10 * ( sum_delta ( start_node.nx, start_node.ny, target.gx, target.gy ) );
    start_node.cost_sum = start_node.cost_heuristic;
    start_node.cost_path = 0;

    open.push_back(start_node); // add the start node to the open list before beginning search loop

    while ( searching == true ) // while we have not found the target
    {
        best_node.cost_sum = 9999999; // just to make sure we pick a valid open node

        if ( open.size() == 0 ) // if there are no nodes on the open list, we have failed to find a path
        {
            searching = false;
        }

        for ( list<node>::iterator i = open.begin(); i != open.end(); ++i ) // find best open node
        {
            if ( i->cost_sum < best_node.cost_sum ) { best_node = *i; }
        }

        if ( best_node.ny == target.gy && best_node.nx == target.gx ) // are we adding the target node to the closed list?
        {
            closed.push_back(best_node); found = true; searching = false;
        }

        closed.push_back(best_node); // add the best node from the open list to the closed node list

        for ( list<node>::iterator i = open.begin(); i != open.end(); ++i ) // and remove it from the open list
        {
            if ( i->ny == best_node.ny && i->nx == best_node.nx ) { open.erase(i); --i; }
        }

        for ( int x = -1; x <= 1; ++x ) for ( int y = -1; y <= 1; ++y ) // evaluate its neighbouring nodes
        {
            // make sure the square we are testing is inside the boundaries of the map
            if ( best_node.ny+y > -1 && best_node.ny+y < 16 && best_node.nx+x > -1 && best_node.nx+x < 16 )
            {
                bool not_walkable_or_closed = false;

                if ( gridmap[best_node.ny+y][best_node.nx+x] == 1 ) { not_walkable_or_closed = true; } // ignore unwalkable nodes

                for ( list<node>::iterator i = closed.begin(); i != closed.end(); ++i ) // and those on the closed list
                {
                    if ( i->nx == best_node.nx+x && i->ny == best_node.ny+y ) { not_walkable_or_closed = true; }
                }

                if ( not_walkable_or_closed == false ) // if the node is walkable and not on the closed list
                {
                    bool found_on_open_list = false;

                    for ( list<node>::iterator i = open.begin(); i != open.end(); ++i ) // does it exist on the open list already?
                    {
                        if ( i->nx == best_node.nx+x && i->ny == best_node.ny+y ) // node exists on the open list already
                        {
                            found_on_open_list = true;

                            int cost_to_reach; // if move is orthogonal, movement cost is 10, if diagonal, 14
                            if ( x + y == 1 || x + y == -1 ) { cost_to_reach = 10; } else { cost_to_reach = 14; }

                            if ( i->cost_path > ( best_node.cost_path + cost_to_reach ) ) // if this path is less costly than old path
                            {
                                new_coord.gx = best_node.nx;                            // adjust the new_coord object to store
                                new_coord.gy = best_node.ny;                            // the location of the new parent square

                                i->parent = new_coord;                                  // assign the square's new parent,
                                i->cost_path = ( best_node.cost_path + cost_to_reach ); // and change the pathing cost and the
                                i->cost_sum = ( i->cost_path + i->cost_heuristic );     // path-plus-heuristic cost accordingly
                            }
                        }
                    }

                    if ( found_on_open_list == false )  // if this is the first time we have pathed to this square
                    {
                        new_coord.gx = best_node.nx;    // adjust the new_coord object to store
                        new_coord.gy = best_node.ny;    // the location of the new parent square

                        node new_node;                  // create a new node
                        new_node.nx = best_node.nx+x;   // and record its
                        new_node.ny = best_node.ny+y;   // co-ordinates and
                        new_node.parent = new_coord;    // its parent square

                        int cost_to_reach; // if move is orthogonal, movement cost is 10, if diagonal, 14
                        if ( x + y == 1 || x + y == -1 ) { cost_to_reach = 10; } else { cost_to_reach = 14; }

                        // update the new node's pathing, heuristic, and sum costs
                        new_node.cost_path = ( best_node.cost_path + cost_to_reach );
                        new_node.cost_heuristic = 10 * ( sum_delta ( new_node.nx, new_node.ny, target.gx, target.gy ) );
                        new_node.cost_sum = ( new_node.cost_path + new_node.cost_heuristic );

                        open.push_back(new_node);       // add this new node to the open list
                    }
                }
            }
        }
    }
    /* code that runs backward from best_node through its parents and adds each successive coord to the moves vector */
}