Em Seg 03 Mar 2008, Leo Wandersleb escreveu:
> > - those pathfinding errors are annoying as hell, and often times units
> > get stuck spinning until you put a red square on them to make them move.
>
> near them works, too. not that this would help but maybe it helps finding the
> cause. guess it has to do with a forced refresh of the "red" gradient.
Ok, I've been mainly silent because I'm currently lacking time to work on it.
I want to try a new pathfiding algorithm on the game.
Those "errors" that make the globs spin are there by design. They are inherent
to the gradient path-fiding. I'm planning to implement an A* search, instead of
gradient hill clibing. That algorithm needs an heuristic map, that looks the same
of a gradient (just a bit simper to calculate), but the main difference is that instead
of goind directly into the hightest value, the A* uses the map only as a gide, and
only give some value back after it confirms that the path will lead to a solution.
The bad news is that A* is slower (altough the heuristic map being easier to calculate
than the current gradient gives some hope that it won't be too slow). The good news
is that it is garanteed to discover the optimal path (and can be easily tweaked to avoid
problems on narrow passages).
[]'s
Marcos
The acutal cause the of the units spinning on the spot is something called "Hidden Forbidden Areas". Basically, when a unit was not moving, say, its attacking enemies in a narrow ally, it put this hidden forbidden area on itself, and removed it when it started moving again. This system was quickly implemented and buggy, and I just removed it a few minutes ago.
The gradient, also known as wavefront, algorithms does yield the perfect path. This bug is causing units to think they are stuck inside a position. The path finding algorithm itself is perfect. Since hidden forbidden areas are inherinitly flawed and have been removed, this bug should disappear.