   Fishy A* behavior
  Hello GDNet, long time no posted :)While looking into my A* pathfinding code, I've noticed that a condition which I thought happened quite unfrequently was actually happening very often: when attempting to add nodes to the open list, finding that the node is already in that list with a higher cost from the source ("G" cost).For example, in a pathfind where there are no obstacles in the way:2817 nodes were opened.From those, 2128 nodes were later closed.In the process, a shorter path to an open node was found 1762 times.I don't understand how that last number could be so big. I thought that having a proper heuristic to estimate the destination distance ("H" cost) would make it an infrequent thing.Do these numbers seem fishy to you? Is it normal that a shorter path to an open node is found so often?Thanks for any help.   
  What are you using for your H?   ;  Oops, sorry, I should have mentioned it: I'm using a simple euclidian distance for the movement cost between grid cells as well as the H cost. Diagonal movements are allowed and have a cost of sqrt(2).   ;  I think so. At least, it kind of makes sense. It looks to me like there would be a greater difference between the measured path and the estimated remaining path the closer the nodes are together in the graph. I'd expect something like that on a very local scale, say on a graph made from a triangle mesh with loads of branching and merging of node paths.It would be cool to see how far back up the graph you've got to go before the two paths merge again. My bet would be that they're only a few hops back up.-Morten-   ;  I've just checked and it seems to happen only when the unit has to move diagonally. I still can't quite understand why there would be two paths diverging and merging back, as you (MortenB) suggest. I'll have a closer look at this.   ;  Yeah, that actually makes perfect sense. When the path is straight it will be a perfect match between the estimated and the actual cost.What numbers do you get for a diagonal path? Is that perfect as well?-Morten-   ;  I've done some additional tests and am now I understand more of what's going on, and it seems it could be normal.First, I've tested what happens if the path is perfectly diagonal. In that case, shorter path to open nodes are never found either. It only happens when the path is in semi-diagonal (between 0 and 45 degrees). The pathfinder follows a north-east diagonal, but and then "comes back" to attempt going east directly as the diagonal was "too costly".It seems to me that in this situation, binary heaps will perform poorly as the open nodes' G cost will have to be modified almost as frequently as the best open node will have to be popped.   ;  Isn't there also a purely logical load problem with diagonals?Going from a given square to the one to the right of it only has one direct option. Whereas going to a square that's above and right has three options:1) Diagonal2) Up then Right3) Right then UpDiagonal should "win", but if you're trying sideways movements first then you're probably wasting some tests. Maybe.;Quote:Original post by RubiconIsn't there also a purely logical load problem with diagonals?Going from a given square to the one to the right of it only has one direct option. Whereas going to a square that's above and right has three options:1) Diagonal2) Up then Right3) Right then UpDiagonal should "win", but if you're trying sideways movements first then you're probably wasting some tests. Maybe.It's one of those things. You can't know the best option without looking, so it doesn't matter if you're testing the "best" or one of the suboptimal ones first. You still have to compute the other options to know.In the trivial case, if you're navigating an open grid with nothing on it, good old Bresenham's got better options for you than A*.-Morten-   