Jonathan Teutenberg
2007-07-28
Hi, I recently installed S.C.O.U.R.G.E and it seems like a lot of fun. However, it was pretty clear that the pathfinding was broken.
I've patched up a few of the problems and it works quite nicely now for me, but I'm not sure of the best way to get the changes into sourceforge. I'll just describe the changes here and let you update them if you like. All the changes are to the findPath function in util.cpp, and to the CPathNode class in util.h
Core Problem: The Heuristic
---------------------------
There's an odd heuristic being used:
int DX = abs(dx - Node.x);
int DY = abs(dy - Node.y);
int Orthogonal = abs(DX - DY);
int Diagonal = abs(((DX + DY) - Orthogonal)/2);
Node.heuristic = Diagonal + Orthogonal + DX + DY;
The last three lines are equivalent to:
Node.heuristic = max(DX,DY)*2 + min(DX,DY);
But the correct heuristic for square tiles that allow diagonal moves should be:
Node.heuristic = max(DX,DY);
The worst part is that the current heuristic is not even admissible, so this is not a proper A* and it will often not find the shortest path. The rest of the errors in the algorithm seem to be patches to make up for an invalid heuristic.
Heap misuse
-----------
The whole point of a heap is that you can get the next largest item without sorting. With an admissible heuristic you never have to update values in the open list, and so you should never sort.
This chunk has to be removed:
// Check to see if already on OPEN
for (int t=0; t<(int)OPEN.size(); t++) {
...
}
Now these two lines are irrelevant:
sort_heap(OPEN.begin(), OPEN.end());// Ascending sort based on overloaded operators below
and later on:
make_heap( OPEN.begin(), OPEN.end() ); // Re-Assert heap, or will be short by one
The other problem is that the STL heap seems to be a max-heap, but of course we need a min-heap to get the *shortest* path. The easiest way to make the heap work properly is to change the overridden operators in CPathNode, so:
inline bool operator<(const CPathNode &b) {
return this->f < b.f;
}
becomes:
inline bool operator<(const CPathNode &b) {
return this->f > b.f;
}
And do the same for the ">" operator. Now the heap provides the next node with minimum f(x) not maximum.
Problem checking CLOSED list
----------------------------
The CLOSED list is being checked before adding a node. It should be checked (and *then* have a node added) when nodes are first popped from the OPEN list.
So straight after the line
OPEN.pop_back();
We should have (sorry if this is too long):
// If at destination, break and create path below
if ((BestNode.x == dx) && (BestNode.y == dy)) {
CLOSED.push_back(BestNode);//add the goal to our path
break;
}
// Check to see if already on CLOSED
bNodeFound = false;
for (int t=0; t<(int)CLOSED.size(); t++) {
if ((BestNode.x == CLOSED[t].x) &&
(BestNode.y == CLOSED[t].y)) {
bNodeFound = true;
break;
}
}
if(bNodeFound){
continue;
}
CLOSED.push_back(BestNode); // Push the BestNode onto CLOSED
and then it continues to check whether too many nodes are on CLOSED etc.
The CLOSED list should not be checked again when adding nodes.
Removing zig-zags
-----------------
There is some comment about adding the neighbouring nodes in clockwise order to reduce zig-zags (or something). Anyway, there is a much easier way.
First, the CPathNodes should keep their f, gone and heuristic values as doubles, not ints. In util.h:
int f, gone, heuristic; // f = gone + heuristic
becomes:
double f, gone, heuristic; // f = gone + heuristic
Which then allows a nice hack that prefers horizontal and vertical moves to diagonal ones, while leaving the heuristic admissible. The heuristic calculation can become:
int DX = abs(dx - Node.x);
int DY = abs(dy - Node.y);
if(i % 2 == 0) //a diagonal move
Node.heuristic = max(DX,DY)+0.5; //we discourage diagonals to remove zig-zagging
else
Node.heuristic = max(DX,DY);
And now the pathing works great!
I'm keen to keep working on the pathfinding for this game as it's a fun way to learn C++, but I'm hoping there's an easier way to contribute code. Some other really important changes are making the CPathNodes refer back to each other (not just keeping px and py values from their parent nodes), then the CLOSED list can be an unsorted hashtable which will be a *massive* speed up.
Anyway, let me know if there's a way to help.
Cheers,
Jono
Jonathan Teutenberg
2007-07-28
Blech. I just saw there is an SVN repository. I'll install it and try my hand at checking the update into the main trunk.
Sorry about the previous stupidly long post!
Cheers,
Jono.
Gabor Torok
2007-07-28
Hi, Please please fix it! :-) I sent you an email and I moved your post to our scourge list here:
http://scourgeweb.org/tiki-view_forum_thread.php?forumId=4&comments_parentId=586
Many thanks!
--Gabor