If we want to improve path finding, theres a few things we can do.
The theoretical requirements of Glob2 path finding are:
a) Two global gradient to each resource type, one for able to swim, one for not b) Two gradients to each building
c) Two gradients out of forbidden areas d) Two gradients to defense areas
As I see now, we have multiple resource gradients for each team, and buildings have both a local and global gradient, presumably this was an optimization. We also have forbidden and defense area gradients for each team, but the cpu usage is negligible and doesn't really affect performance.
When I speak of gradients below, I count up from 0, rather than down from 255. It makes more sense explaining i think, even if the implementation is slightly reversed.
Idea #1) we can keep track, on the map itself, whether a particular spot is an obstacle or not. This can be done in Case, with a Uint8 value. Every time a forbidden area, or a building, or a resource, or something makes this land impassable, it raises the value, if its removed, it lowers the value. If the value is 0, then the square in question is passable. The Uint8 allows multiple im-passable qualities to stack and work properly there-after. This would make the pre-computing a gradient map faster.
Idea #2) is to not fully re-update the gradient each time. Basically, four things can happen to a generic gradient: - A destination is added - A destination is removed - An obstacle is added - An obstacle is removed
For the building gradients, the destination squares (the building itself) rarely change, (only on upgrades), so we can safely ignore the circumstances of a destination being added or removed, and simply recompute the entire gradient when this occurs.
So in this new theoretical system, gradient obstacles have to be tracked. Gradient obstacles consist of: a) other building squares b) forbidden areas c) resources d) possibly water e) anything I've missed
When combined with the system suggested at the start, this means keeping track of when this "passable" value becomes 0 or when it goes higher.
When updating a gradient, two separate algorithms have to be run, one after another, with all of the updates to that gradient.
Say the following field:
00000000 00000000 0000X000 00000000
If square X was an obstacle and becomes passable, then it is filled with the lowest distance value of one of its neighbors, and this new lower number is propagated outwards like a normal gradient, only passing into squares of higher distance value. This can be done for call square X's at the same time, and is relatively efficient.
It gets more complex if X isn't an obstacle and becomes one. Step one, Basically, what you do is 'void' off an area, you propagate outwards from square X, marking each square as 'void' as you go, but only propagating into higher-valued squares. This creates a border around the voided area, and the voided area is every square who's value will change because of this new obstacle. If you work it out logically, you'll also realize that all of these 'border squares' have exactly the same value, a property usefull in step two.
Step two: You use these border values to propagate inwards, in the normal gradient fashion. To be able to process multiple square X's at the same time, you have to use a special trick in order to preserve the values of the gradient. Basically, for all of the border squares from all of the voided areas, you start propagating from the lowest distance valued squares up. During your prorogation, if the values reach that of another set of border squares, you start propagating from them to. This keeps all of the values correct.
Most of the changes occur at the edge of resource fields as resources grow and are removed, rarely are new paths opened. Although we'd need to test to find out. I'm pretty sure that in must cases the prorogation would end quickly for both algorithms, making these updates much faster than a full recompute. In the ultimate worst case, these algorithms have the same complexity, O(width*height), and the combined three of them touch each square on the map 3 times (algorithm 1, algorithm 2 step 1, algorithm 2 step 2), where as a full recompute touches each square twice (once to prepare destinations/obstacles, once to propagate distance values).
If you don't understand, suffice to say I determined the correct two
algorithms to update a gradient if a square goes from passable to
non-passable or vice-versa.
The algorithms for adding or removing a destination are similar. When you add a destination you use algorithm one, and propogate new lower values outwards. If you remove a source, you use algorithm two, creating a 'void' area and then recomputing inwards.
Storing changes in the map is tricky. What you want to avoid is having to make a separate list for each gradient, that consumes both memory and cpu space. So instead, imagine one master list, that stores lists of changes since the initial state, based on the step #.
When updating a gradient, you would have the step number of when it was last updated, so you can look at this "master list" for all the changes after when it was last computed up to current. In reality, this would consume allot of memory as the game gets long.
The trick here is to remove these lists of changes when they're no longer needed. So you keep track of all gradients that need updating, and when the last gradient has used the list of changes for step # x, that list of changes is removed from the "master list"
Idea #3: Building gradients don't need to be computed to their full length. Instead, we could have them only computed based on an estimate of how far they need to go. This estimate could be done many ways, a generous, simple estimate is the distance of the farthest unit + %10 (path distance, not straight-line distance). The main idea surrounding this is that if any code accesses the gradient and is outside its currently computed distance, then the gradient is updated and expanded up to the new-required distance. A good estimation algorithm could cut down on allot of unnecessary pathing.
Idea #4: Instead of computing gradients in 1 x 1 square segments, instead computing the gradients in 2x2 segments, a 2x2 square. There would need to be a few special overrides to get this right, but recall that a 2x2 square has a special property in glob2, every square is accessible from every other square! This makes doing this a feasible idea. Whether it would actually speed things up is another question.
Idea #5: Here things get more interesting. How about instead of path finding from 1 x 1 squares, you path find to a 4x4 square, and then path find locally to the specific spot. It wouldn't give you a 100% accurate path. If i think about it more, it might be possible to preserve the correct paths, but either way, your computation at the very least is done 4x4.
The trick is that a 4x4 square is only 16 total squares. That is 16 bits. Say each bit represented no-obstacle / obstacle. You could construct a table, or more likely multiple tables, that have the local-pathfinding information pre-computed for all of the combinations. Say, you could have the value pre-computed whether (3,3) can access (0,2) in this particular obstacle configuration, and you could even pre-compute the gradient values. Because theres only 2^16 obstacle/no obstacle combinations, these could all be stored in a relatively small amount of memory, the act of computing local gradient values is simply lookup into the table and no logic at all.
You can even pre-compute whether your able to enter/leave at certain end points, so passing from one 4x4 square to the next at a certain edge is simple doing a table lookup to check if they are both 'open' on that edge. With a bit of work, it might even be possible to compute the exact gradient values as if it where 1x1 using this system, by adding these precomputed adjustments with the currently propagated value, and doing other tricks. I'd have to examine it more.
The idea of pre-computed obstacle/no obstacle bit fields could also be used for idea #4. In idea #4, it could be pushed further, since it would need only 4 bits for each square, so you could pre-compute pathfinding values for one square in relation to a neighboring square to, practically eliminating all of the slow-ness arriving from the special cases needed for idea #4.
-- Extra cheese comes at a cost. Bradley Arsenault.