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.
_______________________________________________
glob2-devel mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/glob2-devel
