# A* algorithm solution to “intermediate space probe” challenge

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" asteroids
• 10% 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 Obstacles

As 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)

### Asteroids

Probes cannot enter the space of an Asteroid. It will just be destroyed.

### Empty Spaces

Probes can safely cross space by the empty spaces of space. Beware of gravity wells as described below.

### Gravity Wells

Gravity 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 once

struct Vector2
{
int x, y;
Vector2(int, int);
Vector2();
Vector2 operator +(const Vector2&) const;
};


Vector2.cpp

#include "Vector2.h"

Vector2::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<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.h"

Map::Map(int _size, Vector2 _startPos, Vector2 _endPos) : size(_size), startPos(_startPos), endPos(_endPos)
{
data.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;
}

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;
}

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.h"

Node::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.h"

Solver::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.h"

int 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;
}


This is quite a bit of code, so I'll start with a few things for now:

• I appreciate that you're using <random> instead of rand(). Even in C++11 solutions, the latter seems to still be used.

• SIZE can be a constexpr instead, though this may not really matter for a simple constant.

• Since this is C++11, you can consider the <chrono> library in place of <ctime>.

• Vector2 should be a class so that its data members (x and y) can be kept under private. In addition, you can make this a templated class so that both data members aren't restricted to just ints.

• These lines seem unnecessary:

std::cin.ignore(2);
return 0;


The first one is done right before termination. The second one can be omitted because the compiler will provide the same return at this same point.

• Thanks for answering! Sorry for the late response, I have been in a trip. Do you know of something that I could use instead of a std::list in the openList and closedList to make my algorithm quicker? Oh, and also, how do I calculate my algorithm's 'speed'? – Levon Jul 7 '15 at 13:15
• @Levon: If you're only needing to remove the back element, and none in the middle, then you can use an std::vector instead. I'm not quite sure of the best way to calculate the speed, but you can use time on Linux to get the program's runtime. – Jamal Jul 7 '15 at 17:16
• I'm not only removing the back element, as you can see in solver::aStar() inside the while loop im doing this: openList.remove(current) and current can be anywhere not only on the back. – Levon Jul 7 '15 at 23:42
• @Levon: Then I'm not sure of a better structure for it, at least not in the standard library. You could first determine if the use of std::list is causing a noticeable slowdown. – Jamal Jul 7 '15 at 23:46
• Oh, ok! Also, if you did run my code you can see that when the y axis = 20 it can't run. Thats because in my map class im using only one vector instead of a vector of vectors / 2d array, and when I'm indexing my map what I do is (as you can see in map.cpp) y *= size, so depending on y you'll get to the row you desire. The problem is that y's value can be size, and since map's vector's size = size^2 when I do y*= size im doing size *= size so it will run out of bounds. I don't know if you understand what I'm trying to say but if you glance at my code and run it you'll understand.Thanks – Levon Jul 8 '15 at 1:24