Re: [glob2-devel] Pathfinding Ideas

[Kai Antweiler]

> 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.

You also should use one number for unaccessable areas. This is
faster in gradient computation than always looking at a different
memory location for this information.


> 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.

Flags are buildings too - I think. And they get moved more often.
But you still can treat them separately.


> So in this new theoretical system, gradient obstacles have to be tracked.

> 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.

Currently we use a fixed size queue to keep track of the active squares
during the propagation. This works fine as long as the value of every
square in the queue is the same or one less (corresponding to your
gradient order) than its successor.

If this condition isn't met, the queue can overflow. Be careful!
Even a fixed sized priority queue does not solve this.
We currently only break this condition where it is highly unlikely to
cause an overflow and check it with an assert command.


> 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.

(So you need to sort them before!)

If you use a fixed size priority queue (e.g. heap),  you would not have
to check that and could even mix your two algorithms. There were some
issues with mixing the four cases, but nothing serious - special cases
solved the problem. I wrote it down somewhere.


> 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).

Actually, because you have to sort even in the most efficient
implementation, the complexity becomes  O(w*h+r*log(r)),
where r is the (small) number of resources that changed.
But this is theoretically important only - as is the complexity analysis.
The comparison between 3 times to 2 times touching can be misleading
too.

1.The map init step touches every square exactly once (this is true),
but the gradient step "touches" them multiple times, because each time
a square is active, the algorithm touches all its neighbors.
2.Depending on the cache usage: the second/third access to the map
is a lot faster. (The init step is only 3-4 times as fast as the propagation
not 9 times as fast, as one would expect.)

As I mentioned above, you can mix the cases when you use a priority
queue. Could be faster - could be slower because of the overhead.
Only testing will tell.



> 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.

This won't help in those cases, when it is needed the most:
When the game becomes crowded and some units are far off.


> 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.

The most important advantage is, that we can address 2x2 squares using 32-bit!
This is really worth trying!


> 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.

That is a big disadvantage, because it becomes much harder to verify
whether you implemented the pathfinding correct.
But as I wrote somewhere else, when we want to localize glob more,
than we have to move away from optimal global gradients and unit
assignment anyway.
-- 
Kai Antweiler