diff options
author | zedarider <ymherklotz@gmail.com> | 2016-12-16 14:53:10 +0000 |
---|---|---|
committer | zedarider <ymherklotz@gmail.com> | 2016-12-16 14:53:10 +0000 |
commit | 94f92605d1ef644f8aedbd23d70e83e5f0aa4758 (patch) | |
tree | 664b59a04d27722bc912bc7bb45d4daf15e9921c | |
parent | 69bcea4a3b3d4c5ef166304bf2d23dba33cef150 (diff) | |
download | A-star-algorithm-94f92605d1ef644f8aedbd23d70e83e5f0aa4758.tar.gz A-star-algorithm-94f92605d1ef644f8aedbd23d70e83e5f0aa4758.zip |
memory efficient solution
-rwxr-xr-x | bin/main | bin | 416128 -> 415952 bytes | |||
-rw-r--r-- | include/astar.hpp | 1 | ||||
-rw-r--r-- | include/node.hpp | 6 | ||||
-rw-r--r-- | src/astar.cpp | 15 | ||||
-rw-r--r-- | src/main.cpp | 12 |
5 files changed, 14 insertions, 20 deletions
Binary files differ diff --git a/include/astar.hpp b/include/astar.hpp index a8225f3..d4384e3 100644 --- a/include/astar.hpp +++ b/include/astar.hpp @@ -36,7 +36,6 @@ private: Node get_neighbour(Node& n_in, const int& neighbour_num); void calc_heuristic(Node& n); - void calc_f(Node& n); bool check_item_vec(const Node& n); int get_index_vec(const Node& n); diff --git a/include/node.hpp b/include/node.hpp index f126fc4..b2c24af 100644 --- a/include/node.hpp +++ b/include/node.hpp @@ -27,11 +27,11 @@ private: // score that is used to compare to other nodes to see if the other path is // more efficient. - int f_score; + double f_score; // path length to get to that node. - int g_score; + double g_score; // heuristic length to destination. - int h_score; + double h_score; // the x and y coordinates of the node in the grid int x, y; diff --git a/src/astar.cpp b/src/astar.cpp index a8fa970..120f4e4 100644 --- a/src/astar.cpp +++ b/src/astar.cpp @@ -5,20 +5,19 @@ AStar::AStar() : graph(NULL), graph_width(0), graph_height(0), path_length(10) { } -AStar::AStar(int *curr_graph, const unsigned int& width, const unsigned int& height) : graph(curr_graph), graph_width(width), graph_height(height), path_length(1) { +AStar::AStar(int *curr_graph, const unsigned int& width, const unsigned int& height) : graph(curr_graph), graph_width(width), graph_height(height), path_length(10) { 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); + start_node.f_score = start_node.g_score + start_node.f_score; } else if(graph[i] == 2) { end_node.x = i % graph_width; end_node.y = i / graph_width; } open_set.push(start_node); - start_algorithm(); } bool AStar::start_algorithm(int *curr_graph, const unsigned int& width, const unsigned int& height) { @@ -35,9 +34,9 @@ bool AStar::start_algorithm(int *curr_graph, const unsigned int& width, const un 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; - calc_f(start_node); } else if(graph[i] == 2) { end_node.x = i % graph_width; end_node.y = i / graph_width; @@ -67,7 +66,7 @@ bool AStar::start_algorithm() { if(!open_set.check_item(n) && !check_item_vec(n)) { n.g_score = cost; calc_heuristic(n); - calc_f(n); + n.f_score = n.g_score + n.h_score; n.x_prev = current.x; n.y_prev = current.y; open_set.push(n); @@ -127,11 +126,7 @@ Node AStar::get_neighbour(Node& n_in, const int& neighbour_num) { } void AStar::calc_heuristic(Node& n) { - n.h_score = pow(10 * (end_node.x - n.x), 2) + pow(10 * (end_node.y - n.y), 2); -} - -void AStar::calc_f(Node& n) { - n.f_score = n.g_score + n.h_score; + 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) { diff --git a/src/main.cpp b/src/main.cpp index 14f46e8..f281df3 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -31,13 +31,13 @@ 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; int start_x = rand() % cols; int start_y = rand() % rows; |