[glob2-devel] Pathfinding when warriors are attacking

[Bradley Arsenault]

There have been allot of weird behaviors regarding how warriors target each other in battle. The main problem is that they get stuck behind obstacles and such chasing an enemy. The core of the problem is that warriors don't actually pathfind to their targets! And when pathfinding to an enemies building, warriors used that buildings gradient, which means the warriors obeyed the-enemies forbidden areas!

I have put together and committed a solution to this weird problem. I have implemented "pointToPointPathfind" in Map, which basically uses A* algorithm to pathfind to the target. This new function is flexible enough to be used anywhere, but right now, its simply used for target pathfinding.

I have taken all stops to prevent this function from consuming much cpu power or becoming a bottleneck when there is allot of warriors and fighting. I use a pre-allocated and updated grid, binary_heaps (multiple articles cite this as fastest for A*, really easy thanks to std::priority_queue), a maximum distance, and general algorithmic optimizations.

Warriors won't go more than 12 steps out of their way to target an enemy, so if theres too much resource, the warrior won't do it. This keeps the algorithm from bogging down on, say, G2, if a warrior sees other warriors on the other side of the stone-wall. Even if it where accessible, as soon as the warrior leaves site of the targeted warriors, it would stop targeting them.

The resulting algorithm consumes very low CPU. Running a test save provided on the bug tracker by Leo where there are literally tons of units rushing to the enemy all at once, (so in theory this would be a bad-case scenario), the total cpu usage by the function was only 1.6% with no noticeable lag, and 2.3% with -O2 optimizations, again, with no noticeable lag. If measured for a complete game, and not just a short attack sequence, these numbers would be even lower.

-- 
Extra cheese comes at a cost. Bradley Arsenault.