bugGlobulation 2 - Bugs: bug #16512, gradient calculation cpu...

 
 

bug #16512: gradient calculation cpu consumption improvements

Submitted by:  Kai Antweiler <snth>
Submitted on:  Wed 03 May 2006 08:25:22 PM UTC  
 
Severity: 1 - WishStatus: Postponed
Assigned to: NoneOpen/Closed: Open
Release: NoneOperating System: None

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Fri 05 May 2006 09:09:13 PM UTC, comment #1:

2.3: Gradient maps are recalculated from scratch.

  • If the gradient maps do not change too much, it would be more

efficient to reuse the old gradient maps and only update the
changes. The problems are vanishing sources and newly added
obstacles, since they might spawn fields whose old gradient values
were higher then their new would be. And this case we can't handle
during gradient computation.

Solution:
We comb through the necessary parts of the gradient map twice:
1. we erase the gradient values that are too large and remember the
fields that border this region.
Here we avoid removing much too much by observing that, if field A
has higher gradient as field B, then field B had no influence on field
A's gradient value - or B was an obstacle. If it was an obstacle, we
eventually encounter a proper source which will propagate the gradient
to the former obstacle B.
2. we run a modified updateGlobalGradient using the sources that were
added since the last turn and the remembered fields.

Kai Antweiler <snth>
Project Administrator
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.)

Kai Antweiler <snth>
Project Administrator

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

Do you think this task is very important?
If so, you can click here to add your encouragement to it.
This task has 0 encouragements so far.

Only logged-in users can vote.

 

Please enter the title of George Orwell's famous dystopian book (it's a date):

 

 

No Changes Have Been Made to This Item

Back to the top


Powered by Savane 3.1-cleanup