[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [pygame] Numeric optimization advice




Hey... thanks for the idea. I figured out how to get rid of the array
copy inside the iteration loop. It didn't have a huge impact on my
simple tests (profile shows about a 1% speedup), but I think it will
have a larger effect in real usage when the map sizes will be larger.
My test map is like 18x18 where game maps could get up to the 256x256
sizes. 

I've attached yet another version with the latest changes and much more
documentation. Particularly I wrote a big docstring on the class
explaining ways to tweak the algorithm. 

Anyways, hopefully this will be the last time I spam the list with this
particular code. The only area for improvement I see left is replacing
the putmask call. It nearly doubles the execution time when used.

Just want to say thanks again Rene and Pete. I really appreciate the
help.

Rene Dudfield wrote:

> Could you get rid of that array copy? 
> What I mean is get rid of the memory allocation, and
> just copy the data.
> 
> Is
> neighbours *= 0
> neighbours += weightmap
> faster?  
> 
> Or is there some other way to copy the data, without
> doing a new memory allocation?

-- 

John Eikenberry
[jae@zhar.net - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin
# /usr/bin/env python
#
# John Eikenberry <jae@zhar.net>

from Numeric import *
from types import *

FACTOR = array(6.).astype(Float16)
EDGE_MOD = array(0.66).astype(Float16)
ONE = array(1.).astype(Float16)
ZERO = array(0.).astype(Float16)

class InfluenceMap: 
    """ 

    There are a number of ways to setup the influence map's algorithm below.
    Each potentially useful depending on how you want to use the map. There are
    3 primary things to tweak:

    - weightmap stores the current influence map
    - neighbors is used as the memory buffer to calculate a the influence
      spreading
    - constmap contains a map with only the unit's scores present
    - when I refer to a 'multi-turn map' I mean using one instance of the
      influence map throughout the game without resetting it.

    [1] neighbors *= ZERO

        At the end of each iteraction, the neighbors take on the values of the
        weightmap from the previous step. This will reset those values to
        zero.

        This has a 1% performance hit.

    [2] putmask(neighbors,constmap,constmap)

        This keeps the values of the units hexes constant through all
        iterations.

        This results in about a 40% performance hit. This needs improvement.

    [3] setDecayRate([float])
        
        This is meant to be used with a multi-turn map. It sets the floating
        point value (N>0.0<1.0)which is used on the map each turn to modify
        the current map before the influence spreading. 

        No performance hit.

    If just [1] used then it will cause all influence values to decend
    toward zero. Not sure what this would be useful for, just documenting the
    effect.

    If [1] is not used (commented out) then the map values will never balance
    out, rising with each iteration. This is fine if you plan on resetting the
    influence map each turn. Allowing you to tweak the number of iterations to
    get the level of values you want. But it would cause problem with a
    multi-turn map unless [3] is used to keep this in check. 
        
    Using [2] without [1] will accellerate the rising of the values described
    above. It will also lead to more variation amoung the influence values
    when using fewer iterations. High peaks and steep sides. Using neither [1]
    nor [2] the peaks are much lower.

    If [1] and [2] are both used the map will always attain a point of balance
    no matter how many iterations are run. This is desirable for maps used
    throughout the entire game (multi-turn maps) for obvious reasons. Given the
    effect of [1] this also limits the need for [3] as the influence values in
    areas of the map where units are no longer present will naturally decrease.
    Though the decay rate may still be useful for tweaking this.
    
    """

    _decay_rate = None

    def __init__(self,hex_map):
        """ hex_map is the in game (civl) map object """
        self.map_size = map_size = hex_map.size
        ave_size = (map_size[0] + map_size[1])/2
        self._iterations = ave_size/2
        # is the hex_map useful for anything other than size?
        self.hex_map = hex_map

        # weightmap == influence map
        self.weightmap = zeros((map_size[0],map_size[1]),Float16)
        # constmap == initial unit locations
        self.constmap = zeros((map_size[0],map_size[1]),Float16)

    def setUnitMap(self,units):
        """ Put unit scores on map 
            -units is a list of (x,y,score) tuples
             where x,y are map coordinates and score is the units influence
             modifier
        """
        weightmap = self.weightmap
        constmap = self.constmap
        # mayby use the hex_map here to get terrain effects?
        for (x,y,score) in units:
            weightmap[x,y] = score
            constmap[x,y]=score

    def setInterations(self,iterations):
        """ Set number of times through the influence spreading loop """
        assert type(iterations) == IntType, "Bad arg type: setIterations([int])"
        self._iterations = iterations

    # [3] above
    def setDecayRate(self,rate):
        """ Set decay rate for a multi-turn map. """
        assert type(rate) == FloatType, "Bad arg type: setDecayRate([float])"
        self._decay_rate = array(rate).astype(Float16)

    def reset(self):
        """ Reset an existing map back to zeros """
        map_size = self.map_size
        self.weightmap = zeros((map_size[0],map_size[1]),Float16)

    def step(self,iterations=None):
        """ One set of loops through influence spreading algorithm """
        # save lookup time
        constmap = self.constmap
        weightmap = self.weightmap
        if not iterations:
            iterations = self._iterations

        # decay rate can be used when the map is kept over duration of game,
        # instead of a new one each turn. the old values are retained,
        # degrading slowly over time. this allows for fewer iterations per turn
        # and gives sense of time to the map. its experimental at this point.
        if self._decay_rate:
            weightmap = weightmap * self._decay_rate

        # Could probably move this to the __init__ method. It would help
        # performance with multi-turn maps.
        neighbors = weightmap.copy()
        # spread the influence
        while iterations:
            # [1] in notes above
#            neighbors *= ZERO
            # diamond_hex layout
            neighbors[:-1,:] += weightmap[1:,:] # shift up
            neighbors[1:,:] += weightmap[:-1,:] # shift down
            neighbors[:,:-1] += weightmap[:,1:] # shift left
            neighbors[:,1:] += weightmap[:,:-1] # shift right
            neighbors[1::2][:-1,:-1] += weightmap[::2][1:,1:] # hex up (even)
            neighbors[1::2][:,:-1] += weightmap[::2][:,1:] # hex down (even)
            neighbors[::2][:,1:] += weightmap[1::2][:,:-1] # hex up (odd)
            neighbors[::2][1:,1:] += weightmap[1::2][:-1,:-1] # hex down (odd)
            # keep influence values balanced
            neighbors *= (ONE/FACTOR)
            
            # [2] above - maintain scores in unit hexes
#            putmask(neighbors,constmap,constmap)

            # prepare for next iteration
            weightmap,neighbors = neighbors,weightmap
            iterations -= 1

        # save for next turn
        self.weightmap = weightmap