A_star

#include <iostream>
#include <vector>
#include <functional>

const int N = 10;

enum class CellType : unsigned char
{
    Empty,
    Rock,
    Apple,
    Bomb,
    Unknown
};

class Cell final
{
public:
    Cell() = default;

    CellType GetType() const;
    void SetType(CellType type);

    //Robot* GetRobot() const;
    // void SetRobot(Robot* entity);

private:
    //Robot* m_robotOnCell{ nullptr };
    CellType m_type{ CellType::Unknown };
};


class Terrain final
{
    using TMap = std::vector<std::vector<Cell>>;
public:
    Terrain(TMap&& map);
    Terrain();

    void Resize(size_t x, size_t y);

    std::size_t GetSizeX() const;
    std::size_t GetSizeY() const;

    Cell& GetCell(size_t x, size_t y);
    const Cell& GetCell(size_t x, size_t y) const;

    const TMap& GetMap() const;
private:
    TMap m_map;
};



enum class Direction : unsigned char
{
    Left,
    Right,
    Up,
    Down
};


typedef struct Node{
    Node* parent;
    std:: pair <int, int> coords;
    int g;
    int h;
    CellType cell;
} Node;

Direction toDirection(std::pair<int, int> move){
    if ( move.first == 1 && move.second == 0) return Direction::Left;
    else if (move.first == -1 && move.second == 0) return Direction::Right;
    else if (move.first == 0 && move.second == 1) return Direction::Down;
    else if(move.first == 0 && move.second == -1) return Direction::Up;

}

int heuristic(std::pair<int, int> c1, std::pair<int, int> c2){
    return abs(c1.first - c2.first) + abs(c1.second - c2.second);
}

Node* findNodeInList(std::vector<Node*> list, std::pair<int, int> coords) {
    for (auto &node : list) {
        if ((node->coords.first == coords.first) && (node->coords.second == coords.second)) {
            return node;
        }
    }
    return nullptr;
}

std::vector<std::pair<int,int>> getCellGoodNeighbours(Node curr, std::pair<int, int> dest, Terrain map){
    std::vector<std::pair<int,int>> good_neighbours;
    Cell c1, c2, c3, c4;
    c1 = map.GetCell(curr.coords.first + 1, curr.coords.second);
    c2 = map.GetCell(curr.coords.first - 1, curr.coords.second);
    c3 = map.GetCell(curr.coords.first, curr.coords.second + 1);
    c4 = map.GetCell(curr.coords.first, curr.coords.second - 1);
    if ( c1.GetType() != CellType::Bomb && c1.GetType() != CellType::Rock ){
       std::pair<int,int> n = curr.coords;
        if ( n == dest) {good_neighbours.push_back(dest); return good_neighbours;}
       n.first++;
        good_neighbours.push_back(n);
    }
    if ( c2.GetType() != CellType::Bomb && c2.GetType() != CellType::Rock ){
        std::pair<int,int> n = curr.coords;
        if ( n == dest) {good_neighbours.push_back(dest); return good_neighbours;}
        n.first--;
        good_neighbours.push_back(n);
    }
    if ( c3.GetType() != CellType::Bomb && c3.GetType() != CellType::Rock ){
        std::pair<int,int> n = curr.coords;
        if ( n == dest) {good_neighbours.push_back(dest); return good_neighbours;}
        n.second++;
        good_neighbours.push_back(n);
    }
    if ( c4.GetType() != CellType::Bomb && c4.GetType() != CellType::Rock ){
        std::pair<int,int> n = curr.coords;
        if ( n == dest) {good_neighbours.push_back(dest); return good_neighbours;}
        n.second--;
        good_neighbours.push_back(n);
    }
    return good_neighbours;
}



std::vector<Direction> aStarSearch(
        Terrain* map,
        std::pair<int, int> start,
        std::pair<int, int> dest/*,
        std::function<bool(std::pair<int, int>)> isRobot*/)
{
    std::vector<Node*> open, closed;

    Node* startNode = new Node {nullptr, start, 0, 0};
    open.push_back(startNode);

    Node* current;

    while (!open.empty()) {

        auto currentIt = open.begin();
        current = *currentIt;

        for (auto it = open.begin(); it != open.end(); ++it) {
            auto node = *it;
            if (node->g + node->h < current->g + current->h || (
                    node->g + node->h == current->g + current->h &&
                    node->h < current->h)
                    ) {
                current = node;
                currentIt = it;
            }
        }

        open.erase(currentIt);
        closed.push_back(current);

        if ((current->coords.first == dest.first) && (current->coords.second == dest.second)){
            break;
        }

        auto neighbours = getCellGoodNeighbours(*current, dest, *map);
        for (auto& neighbourCoords : neighbours) {

            if (findNodeInList(closed, neighbourCoords) != nullptr /*|| (
                    isRobot != nullptr && isRobot(neighbourCoords))*/
                    ) {
                continue;
            }

            Node* successor = findNodeInList(open, neighbourCoords);
            if (successor == nullptr) {
                successor = new Node {
                        current,
                        neighbourCoords,
                        current->g + 1,
                        heuristic(neighbourCoords, dest)
                };
                open.push_back(successor);
            }
            else if (current->g + 1 < successor->g) {
                successor->parent = current;
                successor->g = current->g + 1;
            }
        }
    }

    if ((current->coords.first != dest.first) || (current->coords.second != dest.second)) {
        std::cout <<"Last is not equal to destination" << std :: endl;
    }

    std::vector<Direction> way;
    while (current->parent != nullptr) {
        std::pair<int, int> move;
        move.first = current->coords.first - current->parent->coords.first;
        move.second = current->coords.second - current->parent->coords.second;
        auto dir = toDirection(move);
        way.push_back(dir);
        current = current->parent;
    }

    return way;
}



int main() {
    const int N = 10;
    std::vector<std::vector<Node>> map(N, std::vector<Node>(N));

    std:: cout << "  0  1  2  3  4  5  6  7  8  9" << std:: endl;
    for (size_t h = 0; h < 10; h ++){
        char c;
        c = 'A' + h;
        std::cout << c ;
        for (size_t w = 0; w < 10; w++){
            map[h][w].cell = CellType::Empty;
            //std::cout << " " << map[h][w]<< " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;

    return 0;
}