diff options
author | zedarider <ymherklotz@gmail.com> | 2016-12-21 11:01:08 +0000 |
---|---|---|
committer | zedarider <ymherklotz@gmail.com> | 2016-12-21 11:01:08 +0000 |
commit | 2d2ba3f3db635bf72b56a8f311e0468e27e68deb (patch) | |
tree | 7b95cafaa38905d1272df738c943b41596ebd479 | |
parent | 4b860bee7c48af0fd8ef6e2c749bd03a9899e347 (diff) | |
download | A-star-algorithm-2d2ba3f3db635bf72b56a8f311e0468e27e68deb.tar.gz A-star-algorithm-2d2ba3f3db635bf72b56a8f311e0468e27e68deb.zip |
changed vector to array
-rwxr-xr-x | bin/main | bin | 415456 -> 356696 bytes | |||
-rw-r--r-- | include/astar.hpp | 23 | ||||
-rw-r--r-- | include/node.hpp | 4 | ||||
-rw-r--r-- | include/priority_queue.hpp | 4 | ||||
-rw-r--r-- | src/astar.cpp | 199 | ||||
-rw-r--r-- | src/main.cpp | 4 | ||||
-rw-r--r-- | src/node.cpp | 4 |
7 files changed, 124 insertions, 114 deletions
Binary files differ 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..df2115b 100644 --- a/src/astar.cpp +++ b/src/astar.cpp @@ -1,146 +1,151 @@ #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(); + find_start_end(); + 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; + } + open_set.push(start_node); + 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 -= graph_width; + path_length = PATHLENGTH; + } else if(neighbour_num == 1 && n_in.index % graph_width < graph_width - 1) { + n.index += 1; + path_length = PATHLENGTH; + } else if(neighbour_num == 2 && n_in.index / graph_width < graph_height - 1) { + n.index += graph_width; + path_length = PATHLENGTH; + } else if(neighbour_num == 3 && n_in.index % graph_width > 0) { + n.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 -= 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 += 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 -= 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 -= 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) { |