diff options
author | ymherklotz <ymherklotz@gmail.com> | 2016-12-11 12:18:53 +0000 |
---|---|---|
committer | ymherklotz <ymherklotz@gmail.com> | 2016-12-11 12:18:53 +0000 |
commit | bda878a84a62765875dd316d8280fe1743952aee (patch) | |
tree | 81726ae6da995add2db2b13655dd11ee6c6c380a | |
parent | e3c55bd254ef26fc7ef70ad6c78141d1267c1139 (diff) | |
download | A-star-algorithm-bda878a84a62765875dd316d8280fe1743952aee.tar.gz A-star-algorithm-bda878a84a62765875dd316d8280fe1743952aee.zip |
working
-rwxr-xr-x | bin/main | bin | 417472 -> 418000 bytes | |||
-rw-r--r-- | include/astar.hpp | 2 | ||||
-rw-r--r-- | include/node.hpp | 28 | ||||
-rw-r--r-- | src/astar.cpp | 28 | ||||
-rw-r--r-- | src/main.cpp | 32 | ||||
-rw-r--r-- | src/node.cpp | 2 |
6 files changed, 55 insertions, 37 deletions
Binary files differ diff --git a/include/astar.hpp b/include/astar.hpp index 9071775..30e9d65 100644 --- a/include/astar.hpp +++ b/include/astar.hpp @@ -41,6 +41,8 @@ private: bool check_item_vec(const Node& n); int get_index_vec(const Node& n); void remove_from_vec(const Node& n); + + Node find_node(const unsigned int& x, const unsigned int& y); }; #endif // ASTAR_HPP diff --git a/include/node.hpp b/include/node.hpp index 4b19560..f126fc4 100644 --- a/include/node.hpp +++ b/include/node.hpp @@ -19,26 +19,26 @@ public: friend bool operator!=(const Node& n1, const Node& n2); friend std::ostream& operator<<(std::ostream& out, const Node& n); private: -// pointer to previous node so that I can backtrack without using recursion. - Node *previous_node; -// 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]; - -// score that is used to compare to other nodes to see if the other path is -// more efficient. + // pointer to previous node so that I can backtrack without using recursion. + int x_prev, y_prev; + // 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]; + + // score that is used to compare to other nodes to see if the other path is + // more efficient. int f_score; -// path length to get to that node. + // path length to get to that node. int g_score; -// heuristic length to destination. + // heuristic length to destination. int h_score; -// the x and y coordinates of the node in the grid + // the x and y coordinates of the node in the grid int x, y; -// see if node has been visited. -// We don't need this as we will have an open and a closed set -//bool visited; + // see if node has been visited. + // We don't need this as we will have an open and a closed set + //bool visited; }; #endif // NODE_HPP diff --git a/src/astar.cpp b/src/astar.cpp index 5374bea..9739e72 100644 --- a/src/astar.cpp +++ b/src/astar.cpp @@ -23,8 +23,6 @@ AStar::AStar(int *curr_graph, const unsigned int& width, const unsigned int& hei } 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; @@ -37,8 +35,9 @@ bool AStar::start_algorithm(int *curr_graph, const unsigned int& width, const un start_node.x = i % graph_width; start_node.y = i / graph_width; start_node.g_score = 0; - start_node.previous_node = NULL; calc_heuristic(start_node); + start_node.x_prev = -1; + start_node.y_prev = -1; calc_f(start_node); } else if(graph[i] == 2) { end_node.x = i % graph_width; @@ -69,22 +68,21 @@ bool AStar::start_algorithm() { if(!open_set.check_item(n) && !check_item_vec(n)) { n.g_score = cost; calc_f(n); - n.previous_node = ¤t; + n.x_prev = current.x; + n.y_prev = current.y; 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;*/ + recreate_path(open_set.get_first()); 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; + while(n.x != -1 && n.y != -1) { + graph[n.x + n.y * graph_width] = 8; + n = find_node(n.x_prev, n.y_prev); } } @@ -105,7 +103,6 @@ Node AStar::get_neighbour(Node& n_in, const int& neighbour_num) { n.y = n_in.y; } - n.previous_node = &n_in; calc_heuristic(n); return n; @@ -140,3 +137,12 @@ void AStar::remove_from_vec(const Node& 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; +} diff --git a/src/main.cpp b/src/main.cpp index 9031e14..4640dfe 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -29,13 +29,19 @@ int main(int argc, char *argv[]) { // 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 = 21; + // const int rows = 41; + // const int cols = 34; - // const int tile_size = 25; - // const int rows = 50; - // const int cols = 100; + const int tile_size = 25; + const int rows = 50; + const int cols = 100; + + const int start_x = 9; + const int start_y = 13; + + const int end_x = 89; + const int end_y = 38; // print out that information. cout << "tile size: " << tile_size << "px, rows: " << rows << ", cols: " << cols << endl; @@ -43,13 +49,9 @@ int main(int argc, char *argv[]) { // 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[74] = 3; - tiles[41 * 34 - 85] = 2; - // create a tile map that will be used to display the array. TileMap map; @@ -79,9 +81,17 @@ int main(int argc, char *argv[]) { tiles[(int)(mouse.x / tile_size) + cols * (int)(mouse.y / tile_size)] = 0; } + for(int i = 0; i < cols * rows; ++i) + if(tiles[i] != 1) + tiles[i] = 0; + + tiles[start_y * cols + start_x] = 3; + tiles[end_y * rows + end_x] = 2; + + path_finder.start_algorithm(tiles, cols, rows); + // 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)); diff --git a/src/node.cpp b/src/node.cpp index 9f05939..cce4b12 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(-1), y(-1) { +Node::Node() : x_prev(-1), y_prev(-1), f_score(-1), g_score(0), h_score(-1), x(-1), y(-1) { } bool operator<(const Node& n1, const Node& n2) { |