This code is my solution to this Reddit challenge:Description:NASA has contracted you to program the AI of a new probe. This new probe must navigate space from a starting location to an end location. The probe will have to deal with Asteroids and Gravity Wells. Hopefully it can find the shortest path.Map and Path:This challenge requires you to establish a random map for the challenge. Then you must navigate a probe from a starting location to an end location.Map:You are given N -- you generate a NxN 2-D map.30% of the spots are A asteroids10% of the spots are G gravity wells (explained below)60% of the spots are . empty space.  When you generate the map you must figure out how many of each spaces is needed to fill the map. The map must then be randomly populated to hold the amount of Gravity Wells and Asteroids based on N and the above percentages.N and ObstaclesAs n changes so does the design of your random space map. Truncate the  amount of obstacles and its always a min size of 1. (So say N is 11 so  121 spaces. At 10% for wells you need 12.1 or just 12 spots) N can be  between 2 and 1000. To keep it simple you will assume every space is  empty then populate the random Asteroids and Gravity wells (no need to  compute the number of empty spaces - they will just be the ones not  holding a gravity well or asteroid)AsteroidsProbes cannot enter the space of an Asteroid. It will just be  destroyed.Empty SpacesProbes can safely cross space by the empty spaces of space. Beware of  gravity wells as described below.Gravity WellsGravity wells are interesting. The Space itself is so dense it cannot  be travelled in. The adjacent spaces of a Gravity well are too strong  and cannot be travelled in. Therefore you might see this. . = empty  space, G = gravity well ..... ..... ..G.. ..... .....But due to the gravity you cannot pass (X = unsafe) ..... .XXX. .XGX. .XXX. .....You might get Gravity wells next to each other. They do not effect  each other but keep in mind the area around them will not be safe to  travel in. ...... .XXXX. .XGGX. .XXXX. ......Vector2.h #pragma oncestruct Vector2{    int x, y;    Vector2(int, int);    Vector2();    Vector2 operator +(const Vector2&) const;};Vector2.cpp#include Vector2.hVector2::Vector2(int _x, int _y) : x(_x), y(_y){ }Vector2::Vector2(){ }Vector2 Vector2::operator+(const Vector2& other) const{    Vector2 temp;    temp.x = this->x + other.x;    temp.y = this->y + other.y;    return temp;}map.h#pragma once#include vector2.h#include <vector>#include <iostream>#include <random>#include <algorithm>class Map{    Vector2 startPos, endPos;    std::vector<char> data;    std::vector<char> datad;    std::vector<Vector2> directions;    int size;    void fillDangerMap();    Vector2 clamp(int min, int max, Vector2 position) const;public:    Map(int size, Vector2 startPosition, Vector2 endPosition);    Map();    void setSize(int size);    void fill(char, char, char, char, char);    void setElement(Vector2 position, char element);    void setDangerElement(Vector2 position, char);    void display() const;    char getElement(Vector2 position) const;    char getDangerElement(Vector2 position) const;    int  getSize() const;};std::mt19937& getRandomEngine();map.cpp#include map.hMap::Map(int _size, Vector2 _startPos, Vector2 _endPos) : size(_size), startPos(_startPos), endPos(_endPos){    data.resize(size * size);    datad.resize(size * size);    directions.resize(8);    directions[0] = Vector2(-1, 1);    directions[1] = Vector2(-1, 0);    directions[2] = Vector2(-1, -1);    directions[3] = Vector2(0, 1);    directions[4] = Vector2(0, -1);    directions[5] = Vector2(1, 1);    directions[6] = Vector2(1, 0);    directions[7] = Vector2(1, -1);}Map::Map(){ }Vector2 Map::clamp(int min, int max, Vector2 position) const{    if (position.y < 0) position.y = 0;    if (position.x < 0) position.x = 0;    if (position.y > size) position.y = size;    if (position.x > size) position.x = size;    return position;}void Map::fill(char fillStartWith, char fillEndWith, char fillGravWheelWith, char fillAsteroidWith, char fillElseWith){    auto a = (size * size) * 0.1 / 3;    auto b = (size * size) * 0.3 / 3;    for(int i = 0; i < size * size; ++i){        if(i < a)                       data[i] = fillGravWheelWith;        else if(i < b)                  data[i] = fillAsteroidWith;        else                            data[i] = fillElseWith;    }    std::shuffle(data.begin(), data.end(), getRandomEngine());    setElement(startPos, fillStartWith);    setElement(endPos, fillEndWith);    fillDangerMap();}void Map::display() const{    for(int i = 1; i <= size * size; ++i)    {        std::cout << data[i - 1] <<  ;        if (!(i % size))            std::cout << \n;    }}void Map::setSize(int _size){    size = _size;    data.resize(size * size);}char Map::getElement(Vector2 position) const{    position = clamp(0, size, position);    position.y *= size;    return data[position.x + position.y];}char Map::getDangerElement(Vector2 position) const{    position = clamp(0, size, position);    position.y *= size;    return datad[position.x + position.y];}void Map::fillDangerMap(){    for (int i = 0; i < size * size; ++i) datad[i] = '.';    for(int y = 0; y < size; ++y){        for(int x = 0; x < size; ++x){            Vector2 current(x,y);            if      (getElement(current) == 'E') setDangerElement(current, 'E');            else if (getElement(current) == 'S') setDangerElement(current, 'S');            else if (getElement(current) == 'A') setDangerElement(current, 'X');            for (const auto& direction : directions){                auto current2 = current + direction;                if (current2.x < 0 || current2.x > size - 1 || current2.y < 0 || current2.y > size - 1)                    continue;                if (getElement(current) == 'G'){                    setDangerElement(current, 'X');                    setDangerElement(current2, 'X');                }            }        }    }}void Map::setElement(Vector2 position, char elem){    position = clamp(0, size, position);    position.y *= size;    data[position.x + position. y] = elem;}void Map::setDangerElement(Vector2 position, char elem){    position = clamp(0, size, position);    position.y *= size;    datad[position.x + position.y] = elem;}int Map::getSize() const{    return size;}std::mt19937& getRandomEngine(){    static std::mt19937 randomEngine(std::random_device{}());    return randomEngine;}Node.h#pragma once#include Vector2.h#include <cmath>struct Node{    Vector2 position;    int G, H, F;    Node* parent = nullptr;    Node();    Node(const Node& other) = default;    Node(Vector2 pos);    void calc(const Vector2&);    bool operator==(const Node&) const;    bool operator!=(const Node&) const;    bool operator<(const Node&)  const;};Node.cpp#include node.hNode::Node(){ }Node::Node(Vector2 pos) : position(pos){ }void Node::calc(const Vector2& endPos){    H = static_cast<int>((abs(static_cast<double>(position.x - endPos.x)) + abs(static_cast<double>(position.y - endPos.y))));    G = parent ? parent->G + 1 : 1;    F = G + H;}bool Node::operator==(const Node& other) const{    return (position.x == other.position.x && position.y == other.position.y);}bool Node::operator!=(const Node& other) const{    return !(*this == other);}bool Node::operator<(const Node& other) const{    return(F < other.F);}solver.h#pragma once#include node.h#include map.h#include <ctime> //clock_t#include <list>class Solver{    Vector2 startPos, endPos;    Map map;    std::vector<Vector2> directions;    //SETTINGS    bool eachStep;    bool nonDiagonal;    void sleep(unsigned int mseconds);public:    Solver(const int& size, const Vector2& _startPos, const Vector2& _endPos, bool _eachStep, bool _diagonal);    void displayMap() const;    bool aStar();};solver.cpp (here is the algorithm)#include solver.hSolver::Solver(const int& size, const Vector2& _startPos, const Vector2& _endPos, bool _eachStep, bool _diagonal)    : startPos(_startPos), endPos(_endPos), eachStep(_eachStep), nonDiagonal(_diagonal){    Map temp(size, startPos, endPos);    map = temp;    map.fill('S', 'E', 'G', 'A', '.');    if (nonDiagonal){        directions.resize(4);        directions[0] = Vector2(-1, 0);        directions[1] = Vector2(0, 1);        directions[2] = Vector2(0, -1);        directions[3] = Vector2(1, 0);    }    else{        directions.resize(8);        directions[0] = Vector2(-1, 1);        directions[1] = Vector2(-1, 0);        directions[2] = Vector2(-1, -1);        directions[3] = Vector2(0, 1);        directions[4] = Vector2(0, -1);        directions[5] = Vector2(1, 1);        directions[6] = Vector2(1, 0);        directions[7] = Vector2(1, -1);    }}void Solver::sleep(unsigned int mseconds){    clock_t goal = mseconds + clock();    while (goal > clock());}void Solver::displayMap() const{    map.display();}bool Solver::aStar(){    Node startNode(startPos);    Node goalNode(Vector2(endPos.x - 1, endPos.y - 1));    if ((map.getDangerElement(startNode.position) == 'X') || map.getDangerElement(goalNode.position) == 'X'){        std::cout << Either the start of this map is obstructed or so is the end.;        return false;    }    std::list<Node> openList;    std::list<Node> closedList;    startNode.calc(endPos);    openList.push_back(startNode);    while (!openList.empty()){        auto current = Node(*std::min_element(openList.begin(), openList.end()));        current.calc(endPos);        closedList.push_back(current);        openList.remove(current);        for (const auto& direction : directions){            Node successor(direction + current.position);            if (map.getDangerElement(successor.position) == 'X' ||                successor.position.x >= map.getSize() - 1 || successor.position.y >= map.getSize() - 1 ||                successor.position.x < 0 || successor.position.y < 0 ||                 std::find(closedList.begin(), closedList.end(), successor) != closedList.end()){                continue;            }            successor.calc(endPos);            auto inOpen = std::find(openList.begin(), openList.end(), successor);            if (inOpen == openList.end()){                auto curr = &closedList.back();                successor.parent = curr;                successor.calc(endPos);                openList.push_back(successor);            }            else{                if (successor.G < inOpen->G){                    auto curr = &closedList.back();                    successor.parent = curr;                }            }        }        if (eachStep){            for (const auto& display : openList)                map.setElement(display.position, 'O');            for (const auto& display : closedList)                map.setElement(display.position, 'P');            map.display();            std::cout << \n\n;            sleep(150);        }        if (current == goalNode) break;    }    if (!openList.size()){        std::cout << There's no solution to this map.;        return false;    }    auto inClosed = std::find(closedList.begin(), closedList.end(), goalNode);    if (inClosed != closedList.end()){        while (*inClosed != startNode){            map.setElement(inClosed->position, 'Y');            map.setDangerElement(inClosed->position, 'Y');            *inClosed = *inClosed->parent;        }    }    return true;}Source.cpp#include solver.hint main(){    const int SIZE = 21;    const Vector2 startPos(0, 0);    const Vector2 endPos(SIZE - 1, SIZE - 1);    char ans;    bool eachStep;    bool nonDiagonal;    std::cout << Do you want to see each step? (y/n)\n;    std::cin >> ans;    eachStep = (ans == 'y');    std::cout << Do you allow diagonal movement? (y/n)\n;    std::cin >> ans;    nonDiagonal = (ans == 'n');    Solver solve(SIZE, startPos, endPos, eachStep, nonDiagonal);    solve.aStar();    std::cout << \n\n;    solve.displayMap();    std::cin.ignore(2);    return 0;}
A* algorithm solution to intermediate space probe challenge
c++;algorithm;c++11