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

Re: [pygame] Numeric optimization advice




Ok. I've got a new and improved version of my influence map ready for
perusal.  Pete's code gave me the idea to use only slicing for shifting
instead of the array functions. I've also dumped the edge mod, deciding
it wasn't worth the cycles.

Attached is the new (unabridged) version of the code. Along with a few
more comments/doc strings. Hopefully what's going on will be a bit
more clear now. 

Simple profiling shows close to a 10x speedup. The generated map looks
very similar and is just as useful for my purposes.

Does it look like there is any more superfluous array coping going on? I
think I've got it down to one explicit copy per iteration, but I don't
have the experience to spot these things readily.

Thanks for all the help.

-- 

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)

class InfluenceMap:

    _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

    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
 
        # spread the influence
        while iterations:
            # new copy to update
            neighbors = weightmap.copy()
            # diamond_hex layout
            # shift up
            neighbors[:-1,:] += weightmap[1:,:]
            # shift down
            neighbors[1:,:] += weightmap[:-1,:]
            # shift left
            neighbors[:,:-1] += weightmap[:,1:]
            # shift right
            neighbors[:,1:] += weightmap[:,:-1]
            # hex up (odd)
            neighbors[1::2][:-1,:-1] += weightmap[::2][1:,1:]
            # hex down (odd)
            neighbors[1::2][:,:-1] += weightmap[::2][:,1:]
            # hex up (even)
            neighbors[::2][:,1:] += weightmap[1::2][:,:-1]
            # hex down (even)
            neighbors[::2][1:,1:] += weightmap[1::2][:-1,:-1]

            # keep influence values balanced
            neighbors *= (ONE/FACTOR)
            
            # maintain scores in unit hexes
            #putmask(neighbors,constmap,constmap)
            # only needed if more variation is needed in map scores
            # - ie. higher scores on units with fast dropoff

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

        # save for next turn
        self.weightmap = weightmap