Somehow, it takes the diagonal ways...
I currently check every node in the environment, and take the one with the lowest G score.
When I take the lowest F score, it sometimes finds the better path and sometimes it crashes! However, when I output something to the console it does not crash...very weird.
With debugging I get Segmentation fault messages...
Any ideas?
A* pathfinding: it takes the longer way!
March 27, 2008 09:41 AM
Okay, I've been working on this for a few days. Finnaly got it working but not good, see picture:
Somehow, it takes the diagonal ways...
I currently check every node in the environment, and take the one with the lowest G score.
When I take the lowest F score, it sometimes finds the better path and sometimes it crashes! However, when I output something to the console it does not crash...very weird.
With debugging I get Segmentation fault messages...
Any ideas?
Somehow, it takes the diagonal ways...
I currently check every node in the environment, and take the one with the lowest G score.
When I take the lowest F score, it sometimes finds the better path and sometimes it crashes! However, when I output something to the console it does not crash...very weird.
With debugging I get Segmentation fault messages...
Any ideas?
[size="2"]SignatureShuffle: [size="2"]Random signature images on fora
March 27, 2008 09:44 AM
Given the code you've shown, I'm guessing that your problem is that someone hid an easter egg in your computer and the decomposition is causing random quantum fluctuations that is making your programs misbehave.
March 27, 2008 10:20 AM
I csn show the code, but it is kind of long.
Relevant part:
Relevant part:
bool Movement::ai_search(int i){ int h = 0; double lowest[8]; int lowest_h[8], a = 0; // contains the nodes with best path chance int new_parent[8]; // contains the 'better path' for each surrounding node, if it exists /* set the surrounding nodes */ a = ai_check_node(h, i, 0, 1, 0, lowest, lowest_h, a, new_parent); // right a = ai_check_node(h, i, 1, 1, 1, lowest, lowest_h, a, new_parent); // right-down a = ai_check_node(h, i, 2, 0, 1, lowest, lowest_h, a, new_parent); // down a = ai_check_node(h, i, 3, -1, 1, lowest, lowest_h, a, new_parent); // left-down a = ai_check_node(h, i, 4, -1, 0, lowest, lowest_h, a, new_parent); // left a = ai_check_node(h, i, 5, -1, -1, lowest, lowest_h, a, new_parent); // left-up a = ai_check_node(h, i, 6, 0, -1, lowest, lowest_h, a, new_parent); // up a = ai_check_node(h, i, 7, 1, -1, lowest, lowest_h, a, new_parent); // up-right /* pick one node to continue with */ ai_sort(lowest_h, lowest, a); for (int o = 0; o < a; o++) { int y, u; if (new_parent[lowest_h[o]] > 0) { // if the picked node is token by another node which has a better path, get it >:) !!! y = (int) ((new_parent[lowest_h[o]] - (u + 1)) / 10); u = (new_parent[lowest_h[o]] % 10) - 1; } else { y = i; u = lowest_h[o]; } nodes[y].node.opened = false; if (nodes[y].node.x == destination.x && nodes[y].node.y == destination.y) { // found one! ai_finish(y, u); return true; } else { // onto the next node Nodes nodes_list; nodes.push_back(nodes_list); nodes[nodes.size() - 1].parent = y; nodes[nodes.size() - 1].parent_node = nodes[y].node; if (ai_search(nodes.size() - 1)) { return true; } } } return false;}class Movement{ struct Node { bool active; // is it active? or should we ignore it? double g; // g value - traveled distance so far double h; // h value - estimated distance to go int x; // x position int y; // y position bool opened; // is it opened? or is it already taken care of? }; struct Nodes { Node parent_node; // middle one Node node[8]; // 8 surrounding nodes int parent; // the parent ID of the parent_node - used to track back what the path is. }; std::vector<Nodes> nodes; // each containing a group of (max. 9) nodes - parent_node is the middle one, the rest is around - node[0] = right, node[1] = right-down, ... (clock-wise) public: struct Path { int x; int y; Path() : x(0), y(0) {} Path(int x, int y) : x(x), y(y) {} }; bool is_valid_move(int, int, int, int); bool ai_start(int, int, int, int); // find a path bool ai_search(int); // looks for surrounding nodes (recursive) int ai_check_node(int, int, int, int, int, double *, int *, int, int *); // look for one particular node void ai_sort(int *, double *, int); // sort an array int ai_availability(int, int, int, int); // check if node is available to open double ai_g(bool, int, int); // get the G value of a certain node double ai_h(int, int, int, int); // get the H value of a certain node (Euclidean distance method) void ai_finish(int, int); // when a path is found, this will put the path into 'std::vector<std::vector<Path> > paths' with the differences after each step (so it says: go one left, go one up-right) void ai_clear(); // if start or end position has changed (user input?), remove the calculated path struct Character { int x, y; int xp, yp; int xpp, ypp; double x_offset, y_offset; } character; std::vector<Path> path; // the path we found int path_i; // position we are in the path vector Path destination; // x,y position of our goal};bool Movement::is_valid_move(int x1, int y1, int x2, int y2){ if (x2 > -1 && y2 > -1 && x2 < daecrya->graphics->world->width && y2 < daecrya->graphics->world->height && !(x1 == x2 && y1 == y2) && daecrya->graphics->world->walkable(x2, y2)) // can we move to the requested position? { int dx = (x2 - x1); int dy = (y2 - y1); if (dx && dy) // will we move diagonally? { if (daecrya->graphics->world->walkable(x1 + dx, y1) || daecrya->graphics->world->walkable(x1, y1 + dy)) // be sure not both of the side tiles you move-over when going diagonally are not both unwalkable { return true; } } else { return true; } } return false;}bool Movement::ai_start(int x1, int y1, int x2, int y2){ ai_clear(); nodes.clear(); nodes.reserve((int) ceil(ai_h(x1, y1, x2, y2))); destination.x = x2; destination.y = y2; Nodes nodes_list; nodes.push_back(nodes_list); // set our start node, this has as parent node ID -1, easy to track back nodes[0].parent = -1; nodes[0].parent_node.active = true; nodes[0].parent_node.g = 0; nodes[0].parent_node.h = ai_h(x1, y1, x2, y2); nodes[0].parent_node.x = x1; nodes[0].parent_node.y = y1; nodes[0].parent_node.opened = false; return ai_search(0);}bool Movement::ai_search(int i){ int h = 0; double lowest[8]; int lowest_h[8], a = 0; // contains the nodes with best path chance int new_parent[8]; // contains the 'better path' for each surrounding node, if it exists /* set the surrounding nodes */ a = ai_check_node(h, i, 0, 1, 0, lowest, lowest_h, a, new_parent); // right a = ai_check_node(h, i, 1, 1, 1, lowest, lowest_h, a, new_parent); // right-down a = ai_check_node(h, i, 2, 0, 1, lowest, lowest_h, a, new_parent); // down a = ai_check_node(h, i, 3, -1, 1, lowest, lowest_h, a, new_parent); // left-down a = ai_check_node(h, i, 4, -1, 0, lowest, lowest_h, a, new_parent); // left a = ai_check_node(h, i, 5, -1, -1, lowest, lowest_h, a, new_parent); // left-up a = ai_check_node(h, i, 6, 0, -1, lowest, lowest_h, a, new_parent); // up a = ai_check_node(h, i, 7, 1, -1, lowest, lowest_h, a, new_parent); // up-right /* pick one node to continue with */ ai_sort(lowest_h, lowest, a); for (int o = 0; o < a; o++) { int y, u; if (new_parent[lowest_h[o]] > 0) { // if the picked node is token by another node which has a better path, get it >:) !!! y = (int) ((new_parent[lowest_h[o]] - (u + 1)) / 10); u = (new_parent[lowest_h[o]] % 10) - 1; } else { y = i; u = lowest_h[o]; } nodes[y].node.opened = false; if (nodes[y].node.x == destination.x && nodes[y].node.y == destination.y) { // found one! ai_finish(y, u); return true; } else { // onto the next node Nodes nodes_list; nodes.push_back(nodes_list); nodes[nodes.size() - 1].parent = y; nodes[nodes.size() - 1].parent_node = nodes[y].node; if (ai_search(nodes.size() - 1)) { return true; } } } return false;}int Movement::ai_check_node(int h, int i, int o, int dx, int dy, double *lowest, int *lowest_h, int a, int *new_parent){ nodes.node[o].active = false; nodes.node[o].opened = false; nodes.node[o].x = 0; nodes.node[o].y = 0; nodes.node[o].g = 0; nodes.node[o].h = 0; if (daecrya->graphics->world->walkable(nodes.parent_node.x + dx, nodes.parent_node.y + dy)) { nodes.node[o].g = nodes.parent_node.g + ai_g((dx && dy), dx, dy) + (10.0 / daecrya->graphics->world->walkable(nodes.parent_node.x + dx, nodes.parent_node.y + dy)); nodes.node[o].h = ai_h(nodes.parent_node.x + dx, nodes.parent_node.y + dy, destination.x, destination.y); nodes.node[o].x = nodes.parent_node.x + dx; nodes.node[o].y = nodes.parent_node.y + dy; nodes.node[o].opened = true; new_parent[o] = ai_availability(i, o, nodes.parent_node.x + dx, nodes.parent_node.y + dy); if (new_parent[o]) { nodes.node[o].active = true; lowest[a] = nodes.node[o].h + nodes.node[o].g; lowest_h[a] = o; a++; } } return a;}void Movement::ai_sort(int *index, double *value, int size){ for (int i = 1; i < size; i++) { for (int o = i; o > 0; o--) { if (value[o - 1] > value[o]) { index[o - 1] ^= index[o]; index[o] ^= index[o - 1]; index[o - 1] ^= index[o]; double temp = value[o - 1]; value[o - 1] = value[o]; value[o] = temp; } else { break; } } }}int Movement::ai_availability(int ie, int ii, int x, int y){ // check if the move is valid - '(x == character.x && y == character.y)' says that it can not occupy the begin node, this node is only as parent_node and not in the normal list of nodes, but is the only parent_node that should be checked if (!is_valid_move(nodes[ie].parent_node.x, nodes[ie].parent_node.y, nodes[ie].node[ii].x, nodes[ie].node[ii].y) || (x == nodes[0].parent_node.x && y == nodes[0].parent_node.y)) { return 0; } // check if other nodes are on the same position for (int e = 0; e < (int) nodes.size(); e++) { if (e != ie) { for (int i = 0; i < 8; i++) { if (i != ii && nodes[e].node.active && nodes[e].node.x == x && nodes[e].node.y == y) { // check if it is open and has a better path - else we don't use the node (it is already in use) if (nodes[e].node.opened && (nodes[e].node.g) < (nodes[ie].node[ii].g)) { return (e * 10) + i + 1; // +1 to be sure its not zero } return 0; } } } } return -1;}double Movement::ai_g(bool diagonal, int dx, int dy){ double g = 10.0; if (diagonal) { g *= sqrt(2); } return g;}double Movement::ai_h(int x1, int y1, int x2, int y2){ return sqrt((double) (((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)))) * 10.0; // http://en.wikipedia.org/wiki/Euclidean_distance}void Movement::ai_finish(int i, int h){ // first check how many steps we have int o = i; int steps = 1; while (nodes[o].parent != -1) { o = nodes[o].parent; steps++; } path.assign(steps, Path()); // then add them to vector<Path> path - and check the _change_ of x and y int x = nodes.node[h].x; int y = nodes.node[h].y; //printf("----\n%i, %i; %i, %i\n", x, y, nodes.node[h].x, nodes.node[h].y); for (int s = (steps - 1); s > -1; s--) { path.x = (x - nodes<span style="font-weight:bold;">.parent_node.x);<br> path.y = (y - nodes<span style="font-weight:bold;">.parent_node.y);<br> x = nodes<span style="font-weight:bold;">.parent_node.x;<br> y = nodes<span style="font-weight:bold;">.parent_node.y;<br> <span class="cpp-comment">//printf("%i, %i; %i, %i\n", x, y, path.x, path.y);</span><br> i = nodes<span style="font-weight:bold;">.parent;<br> }<br>}<br><br><span class="cpp-keyword">void</span> Movement::ai_clear()<br>{<br> path.clear();<br> path_i = <span class="cpp-number">0</span>;<br><br> character.xp = <span class="cpp-number">0</span>;<br> character.yp = <span class="cpp-number">0</span>;<br>}<br></pre></div><!–ENDSCRIPT–><br><br>When I output something in the main loop (ai_search, which is recursive) it does its job. But when I dont ouput anything, it will crash at <pre>o = 4</pre>.
[size="2"]SignatureShuffle: [size="2"]Random signature images on fora
1,596
March 27, 2008 11:02 AM
You've told your computer that a diagonal move has the same length as a horizontal move or a vertical move. Therefore, two diagonal moves have the same length as two horizontal moves. Which means the path found in the picture is actually correct.
If you wish to consider diagonal lengths as being longer than non-diagonal lengths, don't forget to tell your computer.
If you wish to consider diagonal lengths as being longer than non-diagonal lengths, don't forget to tell your computer.
100
March 27, 2008 11:32 AM
Isn't that a feature? your AI is making use of available cover :)
Roger that, lets run like hell!
March 27, 2008 06:00 PM
Okay thanks...there was some other problem. Fixed.
But, new problem:
I've been thinking about this, WILL A* ever always give the best solution for this situation?
PS: I open the surrounding nodes from right, to beneath, to left to above (clock-wise), this explains why it prefers downwards...but this should not happen according to A*, should it?
But, new problem:
I've been thinking about this, WILL A* ever always give the best solution for this situation?
PS: I open the surrounding nodes from right, to beneath, to left to above (clock-wise), this explains why it prefers downwards...but this should not happen according to A*, should it?
[size="2"]SignatureShuffle: [size="2"]Random signature images on fora
520
March 27, 2008 06:09 PM
Quote: Original post by Decrius
Okay thanks...there was some other problem. Fixed.
But, new problem:
I've been thinking about this, WILL A* ever always give the best solution for this situation?
If you're using an admissible heuristic, A* will always find an optimal path (if it exists).
140
March 27, 2008 07:10 PM
You've already had a lot of help with A* here, and people have explained exactly how it works and what it guarantees. You have obviously implemented it incorrectly, judging from your last picture. Read about the algorithm and try to understand it before touching any code.
876
March 28, 2008 10:33 AM
index[o - 1] ^= index[o]; index[o] ^= index[o - 1]; index[o - 1] ^= index[o]; double temp = value[o - 1]; value[o - 1] = value[o]; value[o] = temp;for the love of pete, clean your code up. You just did two manual swaps using different methods.
ie: std::swap(a,b);
You keep on working on two dimensional coordinates: stop treating them as two unrelated integers. At any of two dozen points you could have mixed up the pairs of coordinates.
Turn this:
a = ai_check_node(h, i, 0, 1, 0, lowest, lowest_h, a, new_parent); // right a = ai_check_node(h, i, 1, 1, 1, lowest, lowest_h, a, new_parent); // right-down a = ai_check_node(h, i, 2, 0, 1, lowest, lowest_h, a, new_parent); // down a = ai_check_node(h, i, 3, -1, 1, lowest, lowest_h, a, new_parent); // left-down a = ai_check_node(h, i, 4, -1, 0, lowest, lowest_h, a, new_parent); // left a = ai_check_node(h, i, 5, -1, -1, lowest, lowest_h, a, new_parent); // left-up a = ai_check_node(h, i, 6, 0, -1, lowest, lowest_h, a, new_parent); // up a = ai_check_node(h, i, 7, 1, -1, lowest, lowest_h, a, new_parent); // up-rightinto a loop.
Why? Because as written, your code is amazingly fragile and hard to read. A simple typo in the above block of code would mean that, say, routes going up and left are favored/ruled out. Such a special case would be a nightmare to find in testing.
While there isn't a bug in the above block (unless I missed it), your code is full of such patterns.
In short: the reason why your code has bugs is that code written that way cannot help but have bugs.
Other asides: don't store std::vectors in std::vectors until C++09, we don't have efficient move semantics, and vectors are expensive to copy. Use a std::deque of std::vectors.
Have your objects zero themselves when default constructed.
Right here:
Nodes nodes_list; nodes.push_back(nodes_list); nodes[nodes.size() - 1].parent = y; nodes[nodes.size() - 1].parent_node = nodes[y].node;you just stuck a Nodes object into nodes with an array of uninitialized node objects in it.
Have one canonial map between "index of surrounding node" to "x and y offset to surrounding node". Don't hand-code it.
Stop using magic numbers:
y = (int) ((new_parent[lowest_h[o]] - (u + 1)) / 10);10? If you are using magic constants, define them once and use the symbols in ways that transmit meaning.
Add documentation that says what each step is supposed to do.
Clean up bazillion-column conditionals:
if (x2 > -1 && y2 > -1 && x2 < daecrya->graphics->world->width && y2 < daecrya->graphics->world->height && !(x1 == x2 && y1 == y2) && daecrya->graphics->world->walkable(x2, y2)) // can we move to the requested position?Toss that into a function that works out the conditional step by step. Putting everything into one line does not make it more efficient, it just makes it less readable and more prone to single-character oopses.
Lastly, have your program display what it calculates as the cost to reach each node, and the cost+remaining distance estimate for each node. Ideally do this graphically, so you can see what of the many problems that could cause the problem.
Code sanitation isn't an afterthought. Code sanitation makes bugs easier to find and less likely to occur. The proximate cause that your algorithm isn't working is a bug somewhere in the code, but the cause of the bug is the fact that your code needs cleaning up. :)
[Edited by - NotAYakk on March 28, 2008 2:33:02 PM]
March 28, 2008 01:39 PM
Quote: Original post by Argus2
You've already had a lot of help with A* here, and people have explained exactly how it works and what it guarantees. You have obviously implemented it incorrectly, judging from your last picture. Read about the algorithm and try to understand it before touching any code.
I did. And I did get some great help, the point is that when I follow the scheme, I myself do not always find the best path (if I simulate it in my head) in the case of the picture. Either the theory in the article is not right, or A* doesn't always find the quickest path...
Quote: Original post by NotAYakkindex[o - 1] ^= index[o]; index[o] ^= index[o - 1]; index[o - 1] ^= index[o]; double temp = value[o - 1]; value[o - 1] = value[o]; value[o] = temp;
for the love of pete, clean your code up. You just did two manual swaps using different methods.
ie: std::swap(a,b);
You keep on working on two dimensional coordinates: stop treating them as two unrelated integers. At any of two dozen points you could have mixed up the pairs of coordinates.
Turn this:a = ai_check_node(h, i, 0, 1, 0, lowest, lowest_h, a, new_parent); // right a = ai_check_node(h, i, 1, 1, 1, lowest, lowest_h, a, new_parent); // right-down a = ai_check_node(h, i, 2, 0, 1, lowest, lowest_h, a, new_parent); // down a = ai_check_node(h, i, 3, -1, 1, lowest, lowest_h, a, new_parent); // left-down a = ai_check_node(h, i, 4, -1, 0, lowest, lowest_h, a, new_parent); // left a = ai_check_node(h, i, 5, -1, -1, lowest, lowest_h, a, new_parent); // left-up a = ai_check_node(h, i, 6, 0, -1, lowest, lowest_h, a, new_parent); // up a = ai_check_node(h, i, 7, 1, -1, lowest, lowest_h, a, new_parent); // up-right
into a loop.
Why? Because as written, your code is amazingly fragile and hard to read. A simple typo in the above block of code would mean that, say, routes going up and left are favored/ruled out. Such a special case would be a nightmare to find in testing.
While there isn't a bug in the above block (unless I missed it), your code is full of such patterns.
In short: the reason why your code has bugs is that code written that way cannot help but have bugs.
Other asides: don't store std::vectors in std::vectors until C++09, we don't have efficient move semantics, and vectors are expensive to copy. Use a std::deque of std::vectors.
Have your objects zero themselves when default constructed.
Right here:Nodes nodes_list; nodes.push_back(nodes_list); nodes[nodes.size() - 1].parent = y; nodes[nodes.size() - 1].parent_node = nodes[y].node;
you just stuck a Nodes object into nodes with an array of uninitialized node objects in it.
Have one canonial map between "index of surrounding node" to "x and y offset to surrounding node". Don't hand-code it.
Stop using magic numbers:y = (int) ((new_parent[lowest_h[o]] - (u + 1)) / 10);
10? If you are using magic constants, define them once and use the symbols in ways that transmit meaning.
Add documentation that says what each step is supposed to do.
Clean up bazillion-column conditionals:if (x2 > -1 && y2 > -1 && x2 < daecrya->graphics->world->width && y2 < daecrya->graphics->world->height && !(x1 == x2 && y1 == y2) && daecrya->graphics->world->walkable(x2, y2)) // can we move to the requested position?
Toss that into a function that works out the conditional step by step. Putting everything into one line does not make it more efficient, it just makes it less readable and more prone to single-character oopses.
Lastly, have your program display what it calculates as the cost to reach each node, and the cost+remaining distance estimate for each node. Ideally do this graphically, so you can see what of the many problems that could cause the problem.
Code sanitation isn't an afterthought. Code sanitation makes bugs easier to find and less likely to occur. The proximate cause that your algorithm isn't working is a bug somewhere in the code, but the cause of the bug is the fact that your code needs cleaning up. :)
Very true, thanks. This gave me a good reason to clean it up :P.
But could you explain the following a bit further?
Quote: You keep on working on two dimensional coordinates: stop treating them as two unrelated integers. At any of two dozen points you could have mixed up the pairs of coordinates.
Quote: Right here:Nodes nodes_list; nodes.push_back(nodes_list); nodes[nodes.size() - 1].parent = y; nodes[nodes.size() - 1].parent_node = nodes[y].node;
you just stuck a Nodes object into nodes with an array of uninitialized node objects in it.
Quote: Have one canonial map between "index of surrounding node" to "x and y offset to surrounding node". Don't hand-code it.
Quote: Other asides: don't store std::vectors in std::vectors until C++09, we don't have efficient move semantics, and vectors are expensive to copy. Use a std::deque of std::vectors.
Do I put vectors in vectors?
The others ones I've already implented, and it looks a lot better :) (also less function calls -> speed! xD)
[size="2"]SignatureShuffle: [size="2"]Random signature images on fora
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
