[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