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<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.h"
Map::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.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;
}
sleepfunction could be replaced bythis_thread::sleep_for\$\endgroup\$