special commit

7 files changed, 127 insertions, 114 deletions

diff --git a/bin/main b/bin/main
new file mode 100755
index 0000000..87f8790
--- /dev/null
+++ b/bin/main
diff --git a/include/astar.hpp b/include/astar.hpp
index 4f1ab96..107b3c1 100644
--- a/include/astar.hpp
+++ b/include/astar.hpp
@@ -11,36 +11,41 @@
 // we don't need this as we will have the queues
 #define NEIGHBOUR_NUM 8
 
+#define PATHLENGTH 10
+#define DIAGLENGTH 14
+
 // TODO add constructors and functions to calculate heuristics etc..
 class AStar {
 public:
-	AStar();
+	AStar(int *graph_in, const unsigned int& width, const unsigned int height);
+	AStar(const AStar& other);
+	~AStar();
+
+	AStar& operator=(const AStar& other);
 
 	bool start_algorithm(int *curr_graph, const unsigned int& width, const unsigned int& height);
+	bool start_algorithm();
 
 	void recreate_path(Node n);
 private:
 	PriorityQueue<Node> open_set;
-	std::vector<Node> closed_set;
+	Node *closed_set;
 
 	int *graph;
 	unsigned int graph_width;
 	unsigned int graph_height;
+	unsigned int graph_size;
 	int path_length;
 
 	Node start_node, end_node;
 
-	bool start_algorithm();
+	bool find_start_end();
 
 	Node get_neighbour(Node& n_in, const int& neighbour_num);
 
-	void calc_heuristic(Node& n);
-
-	bool check_item_vec(const Node& n);
-	int get_index_vec(const Node& n);
-	void remove_from_vec(const Node& n);
+	void reset_closed_set();
 
-	Node find_node(const unsigned int& x, const unsigned int& y);
+	void calc_heuristic(Node& n);
 };
 
 #endif // ASTAR_HPP
diff --git a/include/node.hpp b/include/node.hpp
index b2c24af..f15c464 100644
--- a/include/node.hpp
+++ b/include/node.hpp
@@ -20,7 +20,7 @@ public:
 	friend std::ostream& operator<<(std::ostream& out, const Node& n);
 private:
 	// pointer to previous node so that I can backtrack without using recursion.
-	int x_prev, y_prev;
+	int prev_index;
 	// pointers to the next nodes of which there are 4 in a grid.
 	// We do not need this as we are implementing a priority queue;
 	//Node *next_nodes[NEIGHBOUR_NUM];
@@ -34,7 +34,7 @@ private:
 	double h_score;
 
 	// the x and y coordinates of the node in the grid
-	int x, y;
+	int index;
 
 	// see if node has been visited.
 	// We don't need this as we will have an open and a closed set
diff --git a/include/priority_queue.hpp b/include/priority_queue.hpp
index 537d6e9..f6f294d 100644
--- a/include/priority_queue.hpp
+++ b/include/priority_queue.hpp
@@ -17,7 +17,7 @@ public:
 	T pop();
 
 	// returns the lowest priority item
-	T get_first();
+	T first();
 
 	// check if item is in queue
 	bool check_item(const T& item);
@@ -88,7 +88,7 @@ T PriorityQueue<T>::pop() {
 }
 
 template<typename T>
-T PriorityQueue<T>::get_first() {
+T PriorityQueue<T>::first() {
 	return priority_array[0];
 }
 
diff --git a/src/astar.cpp b/src/astar.cpp
index 43851a1..21c518d 100644
--- a/src/astar.cpp
+++ b/src/astar.cpp
@@ -1,146 +1,154 @@
 #include "astar.hpp"
 
 #include <cmath>
+#include <iostream>
 
-AStar::AStar() : graph(NULL), graph_width(0), graph_height(0), path_length(10) {
+AStar::AStar(int *graph_in, const unsigned int& width, const unsigned int height) : graph(graph_in), graph_width(width), graph_height(height), graph_size(width * height), path_length(PATHLENGTH) {
+	closed_set = new Node[graph_size];
+	Node tmp;
+
+	for(unsigned int i = 0; i < graph_size; ++i)
+		closed_set[i] = tmp;
+
+	find_start_end();
+	open_set.clear();
+}
+
+AStar::AStar(const AStar& other) : open_set(other.open_set), closed_set(other.closed_set), graph(other.graph), graph_width(other.graph_width), graph_height(other.graph_height), graph_size(other.graph_size), path_length(PATHLENGTH), start_node(other.start_node), end_node(other.end_node) {
+}
+
+AStar::~AStar() {
+	delete[] closed_set;
+}
+
+AStar& AStar::operator=(const AStar& other) {
+	open_set = other.open_set;
+	closed_set = other.closed_set;
+	graph = other.graph;
+	graph_width = other.graph_width;
+	graph_height = other.graph_height;
+	graph_size = other.graph_size;
+	path_length = PATHLENGTH;
+	start_node = other.start_node;
+	end_node = other.end_node;
+	return *this;
 }
 
 bool AStar::start_algorithm(int *curr_graph, const unsigned int& width, const unsigned int& height) {
 	graph_width = width;
 	graph_height = height;
+	graph_size = width * height;
+
 	graph = curr_graph;
 
-	closed_set.clear();
-	open_set.clear();
+	if(find_start_end())
+		return start_algorithm();
 
-	for(unsigned int i = 0; i < graph_width * graph_height; ++i)
-		if(graph[i] == 3) {
-			start_node.x = i % graph_width;
-			start_node.y = i / graph_width;
-			start_node.g_score = 0;
-			calc_heuristic(start_node);
-			start_node.f_score = start_node.g_score + start_node.h_score;
-			start_node.x_prev = -1;
-			start_node.y_prev = -1;
-		} else if(graph[i] == 2) {
-			end_node.x = i % graph_width;
-			end_node.y = i / graph_width;
-		}
-	open_set.push(start_node);
-	return start_algorithm();
+	return false;
 }
 
 bool AStar::start_algorithm() {
-	while(open_set.get_first() != end_node) {
+	open_set.clear();
+	if(!find_start_end()) {
+		throw "Couldn't find start or end";
+		return false;
+	}
+	reset_closed_set();
+	open_set.push(start_node);
+	while(open_set.first() != end_node) {
 		Node current = open_set.pop();
-		closed_set.push_back(current);
+		closed_set[current.index] = current;
 		for(unsigned int i = 0; i < NEIGHBOUR_NUM; ++i) {
 			Node n = get_neighbour(current, i);
-
-			if(graph[n.y * graph_width + n.x] != 1 && n.x != -1 && n.y != -1) {
-				graph[n.x + n.y * graph_width] = 9;
-				graph[start_node.x + start_node.y * graph_width] = 3;
-				graph[end_node.x + end_node.y * graph_width] = 2;
+			if(n.index != -1 && graph[n.index] != 1) {
+				graph[n.index] = 9;
 				int cost = current.g_score + path_length;
 				if(open_set.check_item(n))
 					if(cost < open_set[open_set.get_index(n)].g_score)
 						open_set.remove_item(n);
-				if(check_item_vec(n))
-					if(cost < closed_set[get_index_vec(n)].g_score)
-						remove_from_vec(n);
-				if(!open_set.check_item(n) && !check_item_vec(n)) {
+				if(closed_set[n.index] == n) {
+					if(cost < closed_set[n.index].g_score) {
+						Node tmp;
+						closed_set[n.index] = tmp;
+					}
+				}
+				if(!open_set.check_item(n) && (closed_set[n.index] != n)) {
 					n.g_score = cost;
 					calc_heuristic(n);
 					n.f_score = n.g_score + n.h_score;
-					n.x_prev = current.x;
-					n.y_prev = current.y;
+					n.prev_index = current.index;
 					open_set.push(n);
 				}
 			}
 		}
 	}
-	recreate_path(open_set.get_first());
+	recreate_path(open_set.first());
 	return true;
 }
 
 void AStar::recreate_path(Node n) {
-	while(n.x != -1 && n.y != -1) {
-		graph[n.x + n.y * graph_width] = 8;
-		n = find_node(n.x_prev, n.y_prev);
+	while(n != start_node) {
+		graph[n.index] = 8;
+		n = closed_set[n.prev_index];
 	}
 }
 
+bool AStar::find_start_end() {
+	for(unsigned int i = 0; i < graph_size; ++i)
+		if(graph[i] == 3) {
+			start_node.index = i;
+			start_node.g_score = 0;
+			calc_heuristic(start_node);
+			start_node.f_score = start_node.g_score + start_node.h_score;
+			start_node.prev_index = -1;
+		} else if(graph[i] == 2) {
+			end_node.index = i;
+		}
+	Node n;
+	return !(start_node == n || end_node == n);
+}
+
 Node AStar::get_neighbour(Node& n_in, const int& neighbour_num) {
 	Node n;
 
-	if(neighbour_num == 0 && n_in.y > 0) {
-		n.x = n_in.x;
-		n.y = n_in.y - 1;
-		path_length = 10;
-	} else if(neighbour_num == 1 && n_in.x < graph_width - 1) {
-		n.x = n_in.x + 1;
-		n.y = n_in.y;
-		path_length = 10;
-	} else if(neighbour_num == 2 && n_in.y < graph_height - 1) {
-		n.x = n_in.x;
-		n.y = n_in.y + 1;
-		path_length = 10;
-	} else if(neighbour_num == 3 && n_in.x > 0) {
-		n.x = n_in.x - 1;
-		n.y = n_in.y;
-		path_length = 10;
-	} else if(neighbour_num == 4 && n_in.y > 0 && n_in.x < graph_height - 1) {
-		n.x = n_in.x + 1;
-		n.y = n_in.y - 1;
-		path_length = 14;
-	} else if(neighbour_num == 5 && n_in.y < graph_height - 1 && n_in.x < graph_width - 1) {
-		n.x = n_in.x + 1;
-		n.y = n_in.y + 1;
-		path_length = 14;
-	} else if(neighbour_num == 6 && n_in.y < graph_height - 1 && n_in.x > 0) {
-		n.x = n_in.x - 1;
-		n.y = n_in.y + 1;
-		path_length = 14;
-	} else if(neighbour_num == 7 && n_in.y > 0 && n_in.x > 0) {
-		n.x = n_in.x - 1;
-		n.y = n_in.y - 1;
-		path_length = 14;
+	if(neighbour_num == 0 && n_in.index / graph_width > 0) {
+		n.index = n_in.index - graph_width;
+		path_length = PATHLENGTH;
+	} else if(neighbour_num == 1 && n_in.index % graph_width < graph_width - 1) {
+		n.index = n_in.index + 1;
+		path_length = PATHLENGTH;
+	} else if(neighbour_num == 2 && n_in.index / graph_width < graph_height - 1) {
+		n.index = n_in.index + graph_width;
+		path_length = PATHLENGTH;
+	} else if(neighbour_num == 3 && n_in.index % graph_width > 0) {
+		n.index = n_in.index - 1;
+		path_length = PATHLENGTH;
+	} else if(neighbour_num == 4 && n_in.index / graph_width > 0 && n_in.index % graph_width < graph_height - 1) {
+		n.index = n_in.index - graph_width + 1;
+		path_length = DIAGLENGTH;
+	} else if(neighbour_num == 5 && n_in.index / graph_width < graph_height - 1 && n_in.index % graph_width < graph_width - 1) {
+		n.index = n_in.index + graph_width + 1;
+		path_length = DIAGLENGTH;
+	} else if(neighbour_num == 6 && n_in.index / graph_width < graph_height - 1 && n_in.index % graph_width > 0) {
+		n.index = n_in.index - graph_width - 1;
+		path_length = DIAGLENGTH;
+	} else if(neighbour_num == 7 && n_in.index / graph_width > 0 && n_in.index % graph_width > 0) {
+		n.index = n_in.index + graph_width - 1;
+		path_length = DIAGLENGTH;
 	}
 
 	return n;
 }
 
-void AStar::calc_heuristic(Node& n) {
-	n.h_score = 10 * sqrt(((end_node.x - n.x) * (end_node.x - n.x) + (end_node.y - n.y) * (end_node.y - n.y)));
-}
-
-bool AStar::check_item_vec(const Node& n) {
-	for(unsigned int i = 0; i < closed_set.size(); ++i)
-		if(closed_set[i] == n)
-			return true;
-	return false;
-}
+void AStar::reset_closed_set() {
+	delete[] closed_set;
+	closed_set = new Node[graph_size];
+	Node tmp;
 
-int AStar::get_index_vec(const Node& n) {
-	for(unsigned int i = 0; i < closed_set.size(); ++i)
-		if(closed_set[i] == n)
-			return i;
-	return -1;
+	for(unsigned int i = 0; i < graph_size; ++i)
+		closed_set[i] = tmp;
 }
 
-void AStar::remove_from_vec(const Node& n) {
-	std::vector<Node> tmp_set;
-	for(unsigned int i = 0; i < closed_set.size(); ++i)
-		if(closed_set[i] != n)
-			tmp_set.push_back(closed_set[i]);
-	closed_set = tmp_set;
-}
-
-Node AStar::find_node(const unsigned int& x, const unsigned int& y) {
-	Node n;
-
-	for(unsigned int i = 0; i < closed_set.size(); ++i)
-		if(closed_set[i].x == x && closed_set[i].y == y)
-			n = closed_set[i];
-	return n;
+void AStar::calc_heuristic(Node& n) {
+	n.h_score = PATHLENGTH * sqrt(((end_node.index % graph_width - n.index % graph_width) * (end_node.index % graph_width - n.index % graph_width) + (end_node.index / graph_width - n.index / graph_width) * (end_node.index / graph_width - n.index / graph_width)));
 }
diff --git a/src/main.cpp b/src/main.cpp
index f281df3..c18c198 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -57,7 +57,7 @@ int main(int argc, char *argv[]) {
 	// create a tile map that will be used to display the array.
 	TileMap map;
 
-	AStar path_finder;
+	AStar path_finder(tiles, cols, rows);
 
 	// event loop that runs the window.
 	while(window.isOpen()) {
@@ -102,7 +102,7 @@ int main(int argc, char *argv[]) {
 		tiles[start_y * cols + start_x] = 3;
 		tiles[end_y * cols + end_x] = 2;
 
-		path_finder.start_algorithm(tiles, cols, rows);
+		path_finder.start_algorithm();
 
 		tiles[start_y * cols + start_x] = 3;
 		tiles[end_y * cols + end_x] = 2;
diff --git a/src/node.cpp b/src/node.cpp
index cce4b12..b161288 100644
--- a/src/node.cpp
+++ b/src/node.cpp
@@ -1,6 +1,6 @@
 #include "node.hpp"
 
-Node::Node() : x_prev(-1), y_prev(-1), f_score(-1), g_score(0), h_score(-1), x(-1), y(-1) {
+Node::Node() : prev_index(-1), f_score(-1), g_score(0), h_score(-1), index(-1) {
 }
 
 bool operator<(const Node& n1, const Node& n2) {
@@ -10,7 +10,7 @@ bool operator<(const Node& n1, const Node& n2) {
 }
 
 bool operator==(const Node& n1, const Node& n2) {
-	return (n1.x == n2.x) && (n1.y == n2.y);
+	return n1.index == n2.index;
 }
 
 bool operator>(const Node& n1, const Node& n2) {