Wed 03 May 2006 08:25:22 PM UTC, original submission:
Gradients are the background of glob2 pathfinding. They are extremely
efficient, but their computation nevertheless consumes a lot of cpu.
A simple algorithm initializes every field with a starting gradient
value which depends on the field and the type of gradient the
algorithm is calculating. Then the algorithm takes one source and
tries to improve every field adjacent to it. All improved field
become sources - the old source ceases to be a source. Now we go to
the next source. The sources list is managed by a queue. The
increased field's gradient value is one less than that of the field
which increased them.
We have three general ideas on how to improve that:
1. Using the special geometry of glob2
(sup norm => circles in glob2 are squares):
1.1: We only make improved fields new sources, if we have too. This
is based on an observation of Simon. If we have 3 fields immediately
above each other and the two outer fields are (or were) sources, then
the one in the middle does not have to become a source.
Same for 3 horizontal aligned
(Try this for yourself)
- Using two queues instead of one, we can partition the map like a
chess board. Check if this increases the source saving much.
1.2: We cluster the fields on the wave front on which the gradient
propagates into lines. Thereby we save some checks and use memory
(cache) in a better way.
- If a line gets ripped by an obstacle (two or more fields wide) it
will not be joined again by the algorithm. I want to check if it a
more fancy line joining would increase line length much. (the average
right now is between 2 - 3 fields). To check it, I propose to use a
priority queue instead of a queue (larger gradient and smaller
y-coordinate, x-coordinate => higer priority). Then measure the
average line length.
- check if Simon's trick from 1.1 would speed things up.
2. New framework:
Right now we do too much recalculation. Luckily we found a way
to get rid of some:
2.1: Each team has its own forbidden areas. There are usually
only few of them, but their effect is, that we have to calculate
every gradient (not only forbidden gradients) for each team.
- Instead we could calculate one gradient map that considers a field
forbidden if it is forbidden for at least one team. Then copy this
gradient and improve it for every team. We would do this by
correcting the wrongly forbidden fields for a team. Then check the
maximum gradient value of all adjacent fields and if necessary
reset the value for the wrongly forbidden field and make it a source.
At last: call the ordinary algorithm again with these sources.
2.2: Globs that can swim use other gradient maps than those who can't:
- Depending on the map: do the same as in 2.1 with "canSwim"
3: We don't need (correct) gradients all the time:
(This is already implemented I don't know of any plans to improve it.)
(4: I had an idea to use the direction in which the wave front propagates,
but the overhead was to much.)
|