Allegro.cc Forums » Programming Questions » Path-finding issue

 Path-finding issue
 CGamesPlay Member #2,559 July 2002 Is the the minimum amount of code? Perhaps you could narrow it down to say a function that has the problem? Is it create_path? Explain what c, r, g, h, and f are. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 imaxcs Member #4,036 November 2003 Quote: Is the the minimum amount of code? Yes, I guess. If I took something out, I might have taken out the error too. Quote: Perhaps you could narrow it down to say a function that has the problem? Is it create_path? Most likely! Or one of the functions it calls like get_best_f() or get_h(). I think the error is somewhere within the heuristic, but I dunno.Quote: Explain what c, r, g, h, and f are. Well, c and r are the column and the row of the node. g, h and f are the values used by every normal A* algorithm:g - cost to move from the start to this nodeh - cost to move from this node to the end (heuristic)f - g + h (determines which node to take next)I know it's not very easy. I needed to post all the code, because in most cases, it works correct, but only in very rare cases (as this one) it doesn't.
 CGamesPlay Member #2,559 July 2002 Looks to me like you can only create unidirectional paths with your method. Why aren't nodes stored as a graph where the links contain the g, h, and f?Added a negative. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 imaxcs Member #4,036 November 2003 Quote: Looks to me like you can only create unidirectional paths with your method. But there is a horizontal path in there as well! I changed the g-value to 14 instead of ten for all diagonal movements exactly like [url http://www.policyalmanac.org/games/aStarTutorial.htm]this tutorial[/url] suggested. Quote: Why aren't nodes stored as a graph where the links contain the g, h, and f? Could you explain that a bit more in detail? I don't know what you are talking about right now.
 CGamesPlay Member #2,559 July 2002 No, unidirectional as in point A to B, and not point B to C or even point B to A (though the latter could be accomplished by traversing the lsit backwards).What I mean is having each node store a list of Link structures. Each Link structure holds a Node that can be directly reached from its node, as well as the g, f, and h. This way simply coat the level with nodes and then move between them. They don't have to be on every tile. For instance: 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 02000000000000000000 02111111111111112000 00200000000000020000 00020000000000000000 00211111111111111111 00000000000000000000 00000000000000000000 00000020000002000000 00000011111111211111 00000010200002010000 00000012111111110000 00000010200000020000The 2s are nodes, and the character simply moves in a straight line between them. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 imaxcs Member #4,036 November 2003 Oh sorry, I missunderstood you!Your approach is not A*, but it seems to be more like raycasting. I want the A*-way. The units shouldn't be able to move between nodes that are not adjacent to each other in one step.I hope you understood me now.
 CGamesPlay Member #2,559 July 2002 No, my method is A*, you just don't use a grid. A* is simply using weighted steps to compute a path along a graph. A graph is just a bunch of locations that are connected.The way you have it now, every square is a node, and every node is connected to its 8 adjacent nodes. Every connection has a weight of 1, because it takes the same amount of time to move to any square.The way I suggest, you only place nodes at important places (corners), and the weight of each connection equals the distance.Perhaps a better way to demonstrate what I mean is: Use your code to find a route from A to B, then from B to C, then from C to B. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 Audric Member #907 January 2001 It looks as if g was not taken into account, making diagonal movement as fast as straight horizontal/vertical one.Could you try to make run a straight north-south line? if it zigzags, you got your problem narrowed down.Then try putting an absurdly high value of g for diagonal movement, to "forbid" it, and run your original problem: if the algorithm uses ANY diagonal, your code definitely doesn't take g into account.edit: (heuristic from above) : //return (static_cast(fabs(sqrt(pow(delta_x, 2) + pow(delta_y, 2)) * 10.0f))); return ((abs(ac - bc) + abs(ar - br)) * 10);  Your heuristic expects diagonal movement to be as fast as horizontal one. So it takes the x+1 step getting closer (from a large perspective) to the final goal, as a future step will be able to take it (at no cost) off this dead-end.Since your actual step costs are 10 and 14, you need a heuristic which weights 10 * min(abs(delta_x), abs(delta_y)) + 14 * abs(abs(delta_x) - abs(delta_y))
 CGamesPlay Member #2,559 July 2002 Well, in his model diagonal movement is as fast as normal up/down movement.Now you're saying it isn't... Is that so?In the case that you don't want diagonal movement to be weighted more than straight, simply bias it towards moving in a straight line. Say moves which are in the same direction as the previous move come at a -5 cost, adjust to suit. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 Audric Member #907 January 2001 (see my edit above) imaxcs said: I changed the g-value to 14 instead of ten for all diagonal movements When I first saw the post, there was indeed already a bunch of g_modifier+=4 in 4 of 8 direction cases, (an edit probably)
imaxcs
Member #4,036
November 2003

I have an update on my problem. It seems like my algorithm has problems with concave obstacles (see attached). The path leads slightly in the concave structure, then out again, but it should really go around it. As you see in the screenshot, it doesn't matter whether it is horizontal, vertical or diagonal, so this shouldn't be the error.

I am pretty sure the error lies in the create_path-function, so here is the shortened, wrapped in a class, path-finding-algo:

ac - start-column
ar - start-row
bc - end-column
br - end-row

path.h

 1 #ifndef __PATH_H 2 #define __PATH_H 3 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 #include "node.h" 11 12 using std::deque; 13 using std::list; 14 using std::cout; 15 using std::endl; 16 using std::cin; 17 using std::random_shuffle; 18 using std::vector; 19 20 class CPath 21 { 22 private: 23 const static int MAX_NODE_CHECKS = 1000; 24 const static int MAPSIZE = 20; 25 protected: 26 list openlist; 27 list closedlist; 28 list path; 29 public: 30 inline CPath() {} 31 inline virtual ~CPath() {} 32 inline CPath(const CPath& src) {} 33 34 int get_h(int ac, int ar, int bc, int br); 35 int get_g(int ac, int ar, int bc, int br); 36 bool node_valid(int c, int r); 37 list::iterator node_in_list(int c, int r, list& list_); 38 void delete_list(list& list_); 39 list::iterator get_best_f(list& list_); 40 bool create_path(const vector< vector >& map, int ac, int ar, int bc, int br, int bw, int bh); 41 42 void clear(void); 43 44 inline list::const_iterator get_path_begin(void) const { return (path.begin()); } 45 inline list::const_iterator get_path_end(void) const { return (path.end()); } 46 inline list::const_iterator get_openlist_begin(void) const { return (openlist.begin()); } 47 inline list::const_iterator get_openlist_end(void) const { return (openlist.end()); } 48 inline list::const_iterator get_closedlist_begin(void) const { return (closedlist.begin()); } 49 inline list::const_iterator get_closedlist_end(void) const { return (closedlist.end()); } 50 }; 51 52 #endif

path.cpp

 1 #include "path.h" 2 3 int CPath::get_h(int ac, int ar, int bc, int br) 4 { 5 int delta_x = abs(ac - bc); 6 int delta_y = abs(ar - br); 7 return (static_cast(fabs(sqrt(pow(delta_x, 2) + pow(delta_y, 2)) * 10.0f))); 8 //return ((abs(ac - bc) + abs(ar - br)) * 10); 9 } 10 11 int CPath::get_g(int ac, int ar, int bc, int br) 12 { 13 int g = 10; 14 15 if (ac != bc && ar != br) 16 g += 4; 17 18 return g; 19 } 20 21 bool CPath::node_valid(int c, int r) 22 { 23 if (c > MAPSIZE - 1 || c < 0 || r > MAPSIZE - 1 || c < 0) 24 return false; 25 return true; 26 } 27 28 list::iterator CPath::node_in_list(int c, int r, list& list_) 29 { 30 list::iterator it = list_.begin(); 31 while(it != list_.end()) 32 { 33 if ((*it)->get_c() == c && (*it)->get_r() == r) 34 return it; 35 *it++; 36 } 37 return 0; 38 } 39 40 void CPath::delete_list(list& list_) 41 { 42 list::iterator it = list_.begin(); 43 while(it != list_.end()) 44 delete *it++; 45 } 46 47 list::iterator CPath::get_best_f(list& list_) 48 { 49 list::iterator best = list_.begin(); 50 list::iterator it = list_.begin(); 51 while(it != list_.end()) 52 { 53 if ((*it)->get_f() < (*best)->get_f()) 54 best = it; 55 it++; 56 } 57 return best; 58 } 59 60 bool CPath::create_path(const vector< vector >& map, int ac, int ar, int bc, int br, int bw, int bh) 61 { 62 63 // see, if we can return immediately 64 if (ac == bc && ar == br) 65 return true; 66 67 // add the current node to the closedlist 68 openlist.push_front(new CNode(ac, ar, 0, get_h(ac, ar, bc, br))); 69 70 // create a target-node ( not in one of the lists ), so we can use target_reached() more easily 71 //const CNode* tar = new CNode(target->get_c(), target->get_r(), 0, 0); 72 73 // set the current node, which will be altered during the walk through the map 74 const CNode* cur = openlist.front(); 75 76 while(cur->get_c() != bc || cur->get_r() != br) 77 { 78 int c, r; 79 int i; 80 81 // check, if the openlist is empty or the closedlist too full 82 if (!openlist.size() || int(closedlist.size()) > MAX_NODE_CHECKS) 83 return false; 84 85 // put the node with the best f-value in the closedlist 86 list::iterator best_f = get_best_f(openlist); 87 closedlist.push_front(*best_f); 88 openlist.erase(best_f); 89 90 // change the cur-variable 91 cur = *best_f; 92 93 // add the surrounding nodes to the openlist 94 for(i = 0;i < 8;i++) 95 { 96 c = cur->get_c(); 97 r = cur->get_r(); 98 99 if (i == 0) 100 c++; 101 else if (i == 1) 102 c--; 103 else if (i == 2) 104 r++; 105 else if (i == 3) 106 r--; 107 else if (i == 4) 108 { 109 c++; 110 r++; 111 } 112 else if (i == 5) 113 { 114 c--; 115 r++; 116 } 117 else if (i == 6) 118 { 119 r--; 120 c++; 121 } 122 else if (i == 7) 123 { 124 r--; 125 c--; 126 } 127 128 int g = get_g(cur->get_c(), cur->get_r(), c, r); 129 130 if (node_valid(c, r) && map[c][r] != '1' && node_in_list(c, r, closedlist) == 0) 131 { 132 list::iterator node_in_openlist = node_in_list(c, r, openlist); 133 if (node_in_openlist == 0) 134 openlist.push_front(new CNode(c, r, cur->get_g() + g, get_h(c, r, bc, br), cur)); 135 else if ((*node_in_openlist)->get_parent()->get_g() > cur->get_g()) 136 { 137 int g = get_g(cur->get_c(), cur->get_r(), (*node_in_openlist)->get_g(), (*node_in_openlist)->get_g()); 138 139 (*node_in_openlist)->set_parent(cur); 140 (*node_in_openlist)->set_g(cur->get_g() + g); 141 (*node_in_openlist)->recalculate_f(); 142 } 143 } 144 } 145 } 146 147 // coming here, it means that there is a valid path 148 // now track back the way to the start by accessing the parent and save it in the path-variable 149 while(cur != closedlist.back()) 150 { // while start not reached 151 path.push_back(new CNode(*cur)); 152 cur = cur->get_parent(); 153 } 154 155 return true; 156 } 157 158 void CPath::clear(void) 159 { 160 delete_list(path); 161 delete_list(openlist); 162 delete_list(closedlist); 163 }

I hope this makes it easier for you to help me with my problem.

Thanks!

 Audric Member #907 January 2001 Well, it seems the diagonal moves are still not considered significantly more costly than straight moves. Any change if g = 15 for them (instead of g = 14) ? or g = 20? or g = 100 ?Even 14 is an approximation of sqrt(2)/2*10 after all.
 imaxcs Member #4,036 November 2003 I attached the map with g = 20!The path is now correct, but it takes so much more time to calculate, which can't be right. edit: and g = 15 is approximately the same as 14.
 kentl Member #2,905 November 2002 Lot's of source code to go through. Create an animation much as you have done your screenshots. Show a frame for each iteration in the loop you have in create_path, so that you visually can see how the algorithm works.Perhaps the most likely problem is that you are checking nodes which wouldn't need to be checked? In that case you will see it immediately if you do the above for debug purposes.
 Audric Member #907 January 2001 I think I'm stuck there, sorry. The g h and f values on the graph should be enough for someone experienced with A* to troubleshoot further, but I'm not one Quote: (heuristic)... slightly overestimates the remaining distance (...) On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short http://www.policyalmanac.org/games/heuristics.htmI made you reinvent the wheel.Today's lesson: When in doubt, ask google.
 imaxcs Member #4,036 November 2003 I will look into your suggestions, thanks!
 Evert Member #794 November 2000 Have you tried using another metric (weight function, or whatever the name is in graph theory) weigh the edges? Right now, you're using ; try using instead and see if that helps.I'm not sure if it will; from the description of the problem it sounds like nodes aren't properly recalculated or updated when you backtrack through the closed list, but I haven't looked at your code in detail. I also haven't touched my own in several years, so I'm probably a bit rusty on the details.
 Johan HalmÃ©n Member #1,550 September 2001 I don't know A* but I've implemented a path finder like yours, only I never implemented diagonal movements. Do you have trouble with your code or with your algorithm? Or do you want us to find out that?My algo checks every single possible cell recursively, which takes time, but the result is the shortest path. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.
 Homer Cuevas Member #3,055 December 2002 I have tried A-star a long time ago (2003) in Aether, We used the manhattan distance formula and it worked great. I tried other methods but it seems that this one was optimal for our game which uses 8 directions. You could try visiting this site for more information.http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S8Hope this helps. _______________________________________________________[Website]
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads