Change Details

Also see https://wildfiregames.com/forum/index.php?/topic/18262-pathfinder-status/&do=findComment&comment=324961 (and below). MakeGoalReachable is a HierarchicalPathfinder function used to transform a potentially unreachable goal into a reachable 2D point for the JPS pathfinder. It's not terribly slow, but the current flood-filling algorithm is rather inefficient. In particular, it has to flood-fill everything for a non-point goal (many things), and since it's dumb it doesn't particularly go toward the goal. For these reasons, it is beneficial to switch it to the A* pathfinding algorithm. This revision does that. A* provides the following benefits: -faster. It depends on the case (see tests), but in general expect 2-3 times faster. Some particularly egregious cases can be up to 100 times faster, and OTOH it's rarely slower (but it can be now and then for long paths). Note that I also optimised the flood fill, so this isn't a comparison to SVN. -It gives a path. In the future, we could use that to split our long-paths into a few requests, which would be substantially faster overall. -It can return a better position for an unreachable goal. However, naive A* is slow if the goal is unreachable, since it becomes a slow flood fill. To avoid that, I implemented a "Global region" concept in the Hierarchical Pathfinder, which goes on top of current regions. Any regions A and B that are connected (either directly or indirectly) will share the same global ID. This means we can look up accessibility very quickly (no use for that so far except for A* though). In case the goal is unreachable, I made A* stop earlier (but still return a generally good path) However, since recomputing that global region each time something was update is slow, I changed the "Update" function of the Hierarchical Pathfinder to be cleverer. Edges used to be recomputed entirely, now they are recomputed only for chunks that need it (//should// be faster unless we have freak turns where most chunks are invalidated - unlikely), and global regions too. This should be faster than SVN, but I have not tested it. This revision is part of my UnitMotionRewrite (D13) but can be committed independently.

This diff exposes convenience functions through the pathfinder to find reachable navcells from given positions. This is used in D13 to synchronise short and long-range pathfinder, and in the future might have other uses. This diff also drastically optimises the MakeGoalReachable function, by using global regions to determine connectivity faster for non-point goals, and generally being less naive. Global regions, being an additional feature, thus slower, required some further optimisations that were not implemented before. Overall, previous testing as shown this patch as being generally faster than svn (see graphs in the comments). I can't guarantee it returns exactly the same paths as SVN, but they should be close.

Also see https://wildfiregames.com/forum/index.php?/topic/18262-pathfinder-status/&do=findComment&comment=324961 (and below)This diff exposes convenience functions through the pathfinder to find reachable navcells from given positions. This is used in D13 to synchronise short and long-range pathfinder, and in the future might have other uses. MakeGoalReachable is a HierarchicalPathfinder function used to transform a potentially unreachable goal into a reachable 2D point for the JPS pathfinder. It's not terribly slow, but the current flood-filling algorithm is rather inefficient. In particular, it has to flood-fill everything for a non-point goal (many things), and since it's dumb it doesn't particularly go toward the goal. For these reasonsThis diff also drastically optimises the MakeGoalReachable function, it is beneficialby using global regions to switch it to the A* pathfinding algorithm.determine connectivity faster for non-point goals, This revision does thatand generally being less naive. A* provides the following benefits: -faster. It depends on the case (see tests), but in general expect 2-3 times faster. Some particularly egregious cases can be up to 100 times faster, and OTOH it's rarely slower (but it can be now and then for long paths).Global regions, Note that I also optimised the flood fillbeing an additional feature, so this isn't a comparison to SVN. -It gives a path.thus slower, In the future,required some further optimisations that were not implemented before. we could use that to split our long-paths into a few requestsOverall, which would be substantially faster ovprevious testing as shown this patch as being generall. -It can return a better position for an unreachable goaly faster than svn (see graphs in the comments). However, naive A* is slow if the goal is unreachable, since it becomes a slow flood fill. To avoid that, I implemented a "Global region" concept in the Hierarchical Pathfinder, which goes on top of current regions. Any regions A and B that are connected (either directly or indirectly) will share the same global ID. This means we can look up accessibility very quickly (no use for that so far except for A* though). In case the goal is unreachable, I made A* stop earlier (but still return a generally good path) However, since recomputing that global region each time something was update is slow, I changed the "Update" function of the Hierarchical Pathfinder to be cleverer. Edges used to be recomputed entirely, now they are recomputed only for chunks that need it (//should// be faster unless we have freak turns where most chunks are invalidated - unlikely), and global regions too. This should be faster thanI can't guarantee it returns exactly the same paths as SVN, but I have not tested it. This revision is part of my UnitMotionRewrite (D13) but canthey should be committed independentlylose.