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

 
 

bug #16512: gradient calculation cpu consumption improvements

Submitter:  Kai Antweiler <snth>
Submitted:  Wed 03 May 2006 08:25:22 PM UTC
   
 
Severity:  1 - Wish Status:  Postponed
Assigned to:  None Open/Closed:  Open
Release:  None Operating System:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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>
Group 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>
Group administrator

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

Only logged-in users can vote.

 

No changes have been made to this item

Back to the top

Powered by Savane 3.13-d3ae.
Corresponding source code