[Numpy-discussion] Optimization advice
John Eikenberry
jae at zhar.net
Tue Jul 16 00:12:13 CDT 2002
After getting some advice off the pygame list I think I have a pretty
good version of my influence map now. I thought someone on this list
might be interested or at least someone checking the archives.
The new and improved code is around 6-7x faster. The main gain was
obtained by converting all the array functions to slice notation and
eliminating most of the needless copying of arrays.
The new version is attached and is much better commented. It is also
unabridged, as it was pointed out that it wasn't entirely clear what was
going on in the last (edited) version. Hopefully things are more obvious
in this one.
Anyways... I just hating leaving a thread without a conclusion. Hope
someone finds this useful.
--
John Eikenberry
[jae at 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
-------------- next part --------------
# /usr/bin/env python
#
# John Eikenberry <jae at zhar.net>
from Numeric import *
from types import *
FACTOR = array(6.).astype(Float32)
EDGE_MOD = array(0.66).astype(Float32)
ONE = array(1.).astype(Float32)
ZERO = array(0.).astype(Float32)
class InfluenceMap:
"""
There are 2 primary ways to setup the influence map, either might be useful
depending on your needs. The first is to recreate the map each 'turn' the
second is to keep the map around and just update it each turn. The first
way is simple and easy to understand, both in terms of tweaking and later
analysis. The second gives the map a sense of time and allows for fewer
iterations of the spreading algorithm per 'turn'.
Setting up the map to for one or the other of these is a matter of tweaking
the code. There are 3 main bits of code which are described below and
indicated via comments in the code.
First some terminology:
- 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 = weightmap = zeros((map_size[0],map_size[1]),Float32)
# constmap == initial unit locations
self.constmap = zeros((map_size[0],map_size[1]),Float32)
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
constmap *= ZERO
# 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(Float32)
def reset(self):
""" Reset an existing map back to zeros """
map_size = self.map_size
self.weightmap = zeros((map_size[0],map_size[1]),Float32)
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
# It might be possible to pre-allocate the memory for neighbors in the
# init method. But I'm not sure how to update that pre-allocated array.
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)
# 'putmask' adds almost 40% to the overhead. There should be a
# faster way. A little testing seems to show that this problem is
# related to the usage of floats for the map values.
# prepare for next iteration
weightmap,neighbors = neighbors,weightmap
iterations -= 1
# save for next turn
self.weightmap = weightmap
More information about the Numpy-discussion
mailing list