[Numpy-discussion] Optimization advice

[John Eikenberry]

I'm working on an influence map [1] for game civil [2]. I have a working
version, but as a real numeric newbie I thought I'd bounce it off the
people here before calling it done. I'm basically looking for an easy to
understand but fast influence spreading algorithm. I've read that this
algorithm is similar to those used to predict fire spreading or heat
transfer in metal if that helps.

The attached code is setup for a hex based map and the functions to take
this into accounts (shift_hex_up,shift_hex_down) are probably the most
naive. The others being only slight modifications of those in the
life.py example. Its not really commented but its short and hopefully
should be readily understandable.

I've only included the base influence map class and its associated
functions. If you'd like a version you can run, I can send you a .tgz
setup to run in place (for *nix systems). 

Thanks in advance for any advice or opinions.


[1] An influence map is used commonly in strategic war games. It is a
simple means of capturing the areas on the game map that one side is
strong vs the other side. Read the first post in this thread for a good
description: 

    http://www.gameai.com/influ.thread.html

[2] Civil is a cross-platform, turn-based, networked strategy game,
developed using Python, PyGame and SDL--allowing players to take part in
scenarios set during the American Civil war.

    http://civil.sourceforge.net/

-- 

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

from Numeric import *

factor = array(6.).astype(Float16)
edge_mod = array(0.66).astype(Float16)

class InfluenceMap:

    def __init__(self,hex_map):
        self.map_size = map_size = hex_map.size
        self._iterations = (map_size[0] + map_size[1])/4
        self.hex_map = hex_map

        # weightmap == influence map
        self.weightmap = zeros((map_size[0],map_size[1]),Float16)
        # constmap = initial state with constraints/constants
        self.constmap = zeros((map_size[0],map_size[1]),Float16)

    def step(self,iterations=None):
        constmap = self.constmap
        weightmap = self.weightmap
        
        if not iterations:
            iterations = self._iterations
        while iterations:
            # spread the influence
            # diamond_h
            neighbors = _shift_up(weightmap)/factor
            neighbors += _shift_left(weightmap)/factor
            neighbors += _shift_right(weightmap)/factor
            neighbors += _shift_down(weightmap)/factor
            neighbors += _shift_hex_up(weightmap)/factor
            neighbors += _shift_hex_down(weightmap)/factor
            
            # constrain initial points to prevent overheating
            putmask(neighbors,constmap,constmap)
            weightmap = neighbors
            iterations -= 1
        self.weightmap = weightmap

def shift_up(cells):
    return concatenate((cells[1:], cells[-1:]*edge_mod))

def shift_down(cells):
    return concatenate((cells[:1]*edge_mod, cells[:-1]))

def shift_left(cells):
    return transpose(shift_up(transpose(cells)))

def shift_right(cells):
    return transpose(shift_down(transpose(cells)))

# for array layout 
def shift_hex_up(cells):
    neighbors = array(cells)
    # add to odd cell rows [1::2]
    neighbors[1::2] = shift_left(shift_up(cells))[1::2]
    # even cell rows [::2]
    neighbors[::2] = shift_right(shift_up(cells))[::2]
    return neighbors
 
def shift_hex_down(cells):
    neighbors = array(cells)
    # odd cell rows [1::2]
    neighbors[1::2] = shift_left(shift_down(cells))[1::2]
    # even cell rows [::2]
    neighbors[::2] = shift_right(shift_down(cells))[::2]
    return neighbors