have to work on the recreation of path

12 files changed, 171 insertions, 19 deletions

diff --git a/bin/main b/bin/main
index fff4c61..d261a1d 100755
--- a/bin/main
+++ b/bin/main
diff --git a/include/astar.hpp b/include/astar.hpp
index 8668c88..9071775 100644
--- a/include/astar.hpp
+++ b/include/astar.hpp
@@ -16,6 +16,10 @@ class AStar {
 public:
 	AStar();
 	AStar(int *curr_graph, const unsigned int& width, const unsigned int& height);
+
+	bool start_algorithm(int *curr_graph, const unsigned int& width, const unsigned int& height);
+
+	void recreate_path(Node n);
 private:
 	PriorityQueue<Node> open_set;
 	std::vector<Node> closed_set;
diff --git a/include/priority_queue.hpp b/include/priority_queue.hpp
index af9a4b1..e7995e3 100644
--- a/include/priority_queue.hpp
+++ b/include/priority_queue.hpp
@@ -30,6 +30,8 @@ public:
 	// removes item from queue
 	void remove_item(const T& item);
 
+	void clear();
+
 	// return element at position;
 	const T& at(const unsigned int& i) const;
 
@@ -113,6 +115,16 @@ void PriorityQueue<T>::remove_item(const T& item) {
 }
 
 template<typename T>
+void PriorityQueue<T>::clear() {
+	T *tmp = new T;
+
+	size = 0;
+	capacity = 1;
+	delete[] priority_array;
+	priority_array = tmp;
+}
+
+template<typename T>
 const T& PriorityQueue<T>::at(const unsigned int& i) const {
 	return priority_array[i];
 }
diff --git a/res/GridTileTexture2.xcf b/res/GridTileTexture2.xcf
new file mode 100644
index 0000000..b415e86
--- /dev/null
+++ b/res/GridTileTexture2.xcf
diff --git a/res/GridTileTexture3.xcf b/res/GridTileTexture3.xcf
new file mode 100644
index 0000000..ce8baca
--- /dev/null
+++ b/res/GridTileTexture3.xcf
diff --git a/res/GridTileTexture4.png b/res/GridTileTexture4.png
new file mode 100644
index 0000000..bb79fc1
--- /dev/null
+++ b/res/GridTileTexture4.png
diff --git a/res/GridTileTexture5.png b/res/GridTileTexture5.png
new file mode 100644
index 0000000..d206a51
--- /dev/null
+++ b/res/GridTileTexture5.png
diff --git a/src/astar.cpp b/src/astar.cpp
index ba89595..c00b938 100644
--- a/src/astar.cpp
+++ b/src/astar.cpp
@@ -22,13 +22,43 @@ AStar::AStar(int *curr_graph, const unsigned int& width, const unsigned int& hei
 	start_algorithm();
 }
 
+bool AStar::start_algorithm(int *curr_graph, const unsigned int& width, const unsigned int& height) {
+	Node n;
+
+	graph_width = width;
+	graph_height = height;
+	graph = curr_graph;
+
+	std::vector<Node> tmp;
+	closed_set = tmp;
+	open_set.clear();
+
+	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);
+			calc_f(start_node);
+		} 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();
+}
+
 bool AStar::start_algorithm() {
 	while(open_set.get_first() != end_node) {
 		Node current = open_set.pop();
 		closed_set.push_back(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) {
+
+			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;
 				int cost = current.g_score + path_length;
 				if(open_set.check_item(n))
 					if(cost < open_set[open_set.get_index(n)].g_score)
@@ -39,27 +69,38 @@ bool AStar::start_algorithm() {
 				if(!open_set.check_item(n) && !check_item_vec(n)) {
 					n.g_score = cost;
 					calc_f(n);
+					n.previous_node = &current;
 					open_set.push(n);
 				}
 			}
 		}
 	}
+	/*std::cout << open_set.get_first().x << ", " << open_set.get_first().y << std::endl;
+	 * std::cout << open_set.get_first().previous_node->x << ", " << open_set.get_first().previous_node->y << std::endl;
+	 * std::cout << open_set.get_first().previous_node->previous_node->x << ", " << open_set.get_first().previous_node->previous_node->y << std::endl;*/
 	return true;
 }
 
+void AStar::recreate_path(Node n) {
+	while(n.previous_node != NULL) {
+		graph[n.x + n.y * graph_width] = 9;
+		n = *n.previous_node;
+	}
+}
+
 Node AStar::get_neighbour(Node& n_in, const int& neighbour_num) {
 	Node n;
 
-	if(neighbour_num == 0) {
+	if(neighbour_num == 0 && n_in.y > 0) {
 		n.x = n_in.x;
 		n.y = n_in.y - 1;
-	} else if(neighbour_num == 1) {
+	} else if(neighbour_num == 1 && n_in.x < graph_width - 1) {
 		n.x = n_in.x + 1;
 		n.y = n_in.y;
-	} else if(neighbour_num == 2) {
+	} else if(neighbour_num == 2 && n_in.y < graph_height - 1) {
 		n.x = n_in.x;
 		n.y = n_in.y + 1;
-	} else {
+	} else if(neighbour_num == 3 && n_in.x > 0) {
 		n.x = n_in.x - 1;
 		n.y = n_in.y;
 	}
diff --git a/src/main.cpp b/src/main.cpp
index c0b9b00..4434e72 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -7,21 +7,89 @@
  *
  */
 
+#include "tilemap.hpp"
 #include "astar.hpp"
-#include "priority_queue.hpp"
+
+#include <SFML/Graphics.hpp>
 
 #include <iostream>
-#include <vector>
+#include <cstdlib>
 
 using namespace std;
 
 int main(int argc, char *argv[]) {
-	int graph[9] = {
-		3, 0, 0,
-		0, 1, 1,
-		0, 0, 2
-	};
-	AStar a(graph, 3, 3);
+	cout << "executing " << argv[0] << endl;
+	cout << "arguments given: " << argc - 1 << endl;
+
+	// create a render window of size 800x600 with a title.
+	sf::RenderWindow window(sf::VideoMode(2500, 1250), "A* Algorithm");
+
+	// print out the window size.
+	cout << "window size: " << window.getSize().x << ", " << window.getSize().y << endl;
+
+	// set the constants int the file that define the grid to be displayed.
+	// for the mac
+	//const int tile_size = 21;
+	//const int rows = 41;
+	//const int cols = 34;
+
+	const int tile_size = 25;
+	const int rows = 50;
+	const int cols = 100;
+
+	// print out that information.
+	cout << "tile size: " << tile_size << "px, rows: " << rows << ", cols: " << cols << endl;
+
+	// create the array of the right size using the constants.
+	int tiles[cols * rows];
+
+	// assign zeros to the tiles.
+	for(int i = 0; i < cols * rows; ++i)
+		tiles[i] = 0;
+
+	tiles[210] = 3;
+	tiles[4029] = 2;
+
+	// create a tile map that will be used to display the array.
+	TileMap map;
+
+	AStar path_finder;
+
+	// event loop that runs the window.
+	while(window.isOpen()) {
+		// create an event.
+		sf::Event event;
+		// check if an event has been triggered.
+		while(window.pollEvent(event))
+			// if the event is the window closing, close the window.
+			if(event.type == sf::Event::Closed)
+				window.close();
+
+		// check if mouse buttons are pressed.
+		if(sf::Mouse::isButtonPressed(sf::Mouse::Left)) {
+			// get the position of the mouse.
+			sf::Vector2i mouse = sf::Mouse::getPosition(window);
+			// set the tile colour to 1.
+			tiles[(int)(mouse.x / tile_size) + cols * (int)(mouse.y / tile_size)] = 1;
+
+			cout << (int)(mouse.y / tile_size) << " " << (int)(mouse.x / tile_size) << endl;
+		} else if(sf::Mouse::isButtonPressed(sf::Mouse::Right)) {
+			sf::Vector2i mouse = sf::Mouse::getPosition(window);
+			// set the tile colour to 2.
+			tiles[(int)(mouse.x / tile_size) + cols * (int)(mouse.y / tile_size)] = 0;
+		}
+
+		// update tile map with the correct array.
+		map.load("res/GridTileTexture5.png", sf::Vector2f(200, 200), sf::Vector2f(tile_size, tile_size), tiles, cols, rows);
+		path_finder.start_algorithm(tiles, cols, rows);
+
+		// clear the screen.
+		window.clear(sf::Color(47, 47, 47));
+		// draw the map onto the screen.
+		window.draw(map);
+		// display the window.
+		window.display();
+	}
 
 	return 0;
 }
diff --git a/src/main.cpp.test b/src/main.cpp.test
new file mode 100644
index 0000000..c0b9b00
--- /dev/null
+++ b/src/main.cpp.test
@@ -0,0 +1,27 @@
+/*
+ *
+ * description:		Displays the A* Algorithm on a grid.
+ *
+ * author:          Yann Herklotz <ymherklotz@gmail.com>
+ * date created:    DD-MM-YYYY
+ *
+ */
+
+#include "astar.hpp"
+#include "priority_queue.hpp"
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+int main(int argc, char *argv[]) {
+	int graph[9] = {
+		3, 0, 0,
+		0, 1, 1,
+		0, 0, 2
+	};
+	AStar a(graph, 3, 3);
+
+	return 0;
+}
diff --git a/src/node.cpp b/src/node.cpp
index b61c154..9f05939 100644
--- a/src/node.cpp
+++ b/src/node.cpp
@@ -1,6 +1,6 @@
 #include "node.hpp"
 
-Node::Node() : previous_node(NULL), f_score(-1), g_score(0), h_score(-1), x(0), y(0) {
+Node::Node() : previous_node(NULL), f_score(-1), g_score(0), h_score(-1), x(-1), y(-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.x == n2.x) && (n1.y == n2.y);
 }
 
 bool operator>(const Node& n1, const Node& n2) {
diff --git a/src/tilemap.cpp b/src/tilemap.cpp
index aeaac3a..3ae167d 100644
--- a/src/tilemap.cpp
+++ b/src/tilemap.cpp
@@ -29,10 +29,10 @@ bool TileMap::load(const std::string& txt_file, const sf::Vector2f& txt_size, co
 			quad[3].position = sf::Vector2f(i * tile_size.x, (j + 1) * tile_size.y);
 
 			// define texture coordinates.
-			quad[0].texCoords = sf::Vector2f(tile_number * txt_size.x, 0);
-			quad[1].texCoords = sf::Vector2f((tile_number + 1) * txt_size.x, 0);
-			quad[2].texCoords = sf::Vector2f((tile_number + 1) * txt_size.x, txt_size.y);
-			quad[3].texCoords = sf::Vector2f(tile_number * txt_size.x, txt_size.y);
+			quad[0].texCoords = sf::Vector2f((tile_number % 4) * txt_size.x, (tile_number / 4) * txt_size.y);
+			quad[1].texCoords = sf::Vector2f((tile_number % 4 + 1) * txt_size.x, (tile_number / 4) * txt_size.y);
+			quad[2].texCoords = sf::Vector2f((tile_number % 4 + 1) * txt_size.x, (tile_number / 4 + 1) * txt_size.y);
+			quad[3].texCoords = sf::Vector2f((tile_number % 4) * txt_size.x, (tile_number / 4 + 1) * txt_size.y);
 		}
 	return true;
 }