This code is my solution to [this Reddit challenge](http://www.reddit.com/r/dailyprogrammer/comments/2o5tb7/2014123_challenge_191_intermediate_space_probe/).
**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;
}
Prompt:
(diagonal movement = true & each step = false)
