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