|
Path-finding issue |
imaxcs
Member #4,036
November 2003
|
Hi! I am just working on a test-program for my path-finding algorithm and I found out that it doesn't always work correct. Here are the files: path.cpp void load(const string& filename) map.resize(MAPSIZE); if(file.is_open()) // read the map and store it // read the start // read the target return; int get_h(int ac, int ar, int bc, int br) bool node_valid(int c, int r) bool node_in_list(int c, int r, list<CNode*>& list_) void delete_list(list<CNode*>& list_) list<CNode*>::iterator get_best_f(list<CNode*>& list_) bool create_path(void) // see, if we can return immediately // add the current node to the closedlist // create a target-node ( not in one of the lists ), so we can use target_reached() more easily // set the current node, which will be altered during the walk through the map while(cur->get_c() != bc || cur->get_r() != br) // add the surrounding nodes to the openlist (in a random order) if (tmp<i> == 0) if (node_valid(c, r) && map[c][r] != '1' && !node_in_list(c, r, openlist) && !node_in_list(c, r, closedlist)) // check, if the openlist is empty or the closedlist too full // put the node with the best f-value in the closedlist // change the cur-variable // coming here, it means that there is a valid path return true; void save_screenshot(const char *path) glReadPixels(0,0,SCREEN_W,SCREEN_H,GL_RGBA,GL_UNSIGNED_BYTE,buff); int y; save_bitmap(path,bmp,NULL); destroy_bitmap(bmp); void draw(void) // draw the grid // draw the obstacles // draw the openlist // draw the closedlist // draw the path GfxRend::RefreshScreen(); save_screenshot("screenshot.png"); void unload(void) int main(void) // load the map // create the path // draw the path // loop // destroy the path and the lists // unload the map path.h #include <OpenLayer.hpp> #include "node.h" using namespace ol; vector< vector<char> > map; const static int SCREENW = 800; #endif node.cpp CNode::CNode(int c, int r, int g, int h, const CNode* parent) CNode::~CNode() CNode::CNode(const CNode& src) node.h class CNode inline int get_c(void) const { return (c_); } virtual bool operator < (const CNode& node) const { return (f_ > node.f_); } #endif (I will omit text.cpp and text.h because they aren't necessary) I attached a picture of the problem. The yellow circle shows where the algo makes the mistake. IMO, the path should go straight down instead of doing a zigzag. Finally, here is the map-file for this example: map.map The first two numbers after the grid are the starting position in columns and rows and the second four are the position of the target (the two 1s don't have any meaning yet). Thanks for your help!
|
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. -- Ryan Patterson - <http://cgamesplay.com/> |
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: 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? [edit] -- Ryan Patterson - <http://cgamesplay.com/> |
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 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 00000010200000020000 The 2s are nodes, and the character simply moves in a straight line between them. -- Ryan Patterson - <http://cgamesplay.com/> |
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. -- Ryan Patterson - <http://cgamesplay.com/> |
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. 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) :
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. |
CGamesPlay
Member #2,559
July 2002
|
Well, in his model diagonal movement is as fast as normal up/down movement. [edit] [edit] -- Ryan Patterson - <http://cgamesplay.com/> |
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 path.h
path.cpp
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 ? |
imaxcs
Member #4,036
November 2003
|
I attached the map with g = 20! 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 edit: 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.htm |
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 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#S8 Hope this helps. _______________________________________________________ |
|