I've noticed a few spots where the AI checks pathing distance between two points using A*, then checks to see if it is less than some threshold.
...
That could be really expensive. In the case that there is no pathing between two points, that requires you search the entire continent. And in the case that the path is long and twisty, it is almost equally horrible.
The A* code is "outside of the DLL" we have access to. But A* isn't that obscure of an algorithm. I'm wondering if implementing a "bounded A*" might improve AI performance.
A "bounded A*" would follow the A* algorithm, but once it reached a pathing total equal to the bound, it would simply give up, rather than look further.
So instead of
AstarPath(source, dest) < 8
we'd pass the 8 into the BoundedAstarPath, which would then abort. . .
But to tell if this would help, we need to understand what parts use up time. Is there any timing instrumentation in the Civ4 BST DLL? Has anyone done a profiled build?
...
That could be really expensive. In the case that there is no pathing between two points, that requires you search the entire continent. And in the case that the path is long and twisty, it is almost equally horrible.
The A* code is "outside of the DLL" we have access to. But A* isn't that obscure of an algorithm. I'm wondering if implementing a "bounded A*" might improve AI performance.
A "bounded A*" would follow the A* algorithm, but once it reached a pathing total equal to the bound, it would simply give up, rather than look further.
So instead of
AstarPath(source, dest) < 8
we'd pass the 8 into the BoundedAstarPath, which would then abort. . .
But to tell if this would help, we need to understand what parts use up time. Is there any timing instrumentation in the Civ4 BST DLL? Has anyone done a profiled build?
