Re: [pygame] fast sqrt? and profiling

[Casey Duncan <casey@xxxxxxxxxxx>]

On Jan 21, 2009, at 7:28 PM, Jake b wrote:

> First:
> Thanks everyone for all the replies.
> Lots of useful information.
>
> On Wed, Jan 21, 2009 at 11:11 AM, Casey Duncan <casey@xxxxxxxxxxx>  
> wrote:
> Others have made good suggestions about reducing the amount of work  
> you do detecting collision (i.e., partitioning) and using complex  
> numbers instead of euclid for 2d vectors. The latter made a big  
> performance difference for me in a vector-heavy game I was working on.
>
> 1) How do you use complex(imaginary) numbers in place of euclid  
> vectors? I tried searching for a tut/article, but, not having luck.

Here's some example code with some commonly used functions. Addition  
and subtraction are built into the complex type and work as expected  
(I use the real part for x and the imaginary part for y). complex  
multiply can be used to rotate vectors:

# 2D vectors using python complex numbers

from math import atan2
import cmath

vector2 = complex

length = abs

def to_tuple(vector):
	return (vector.real, vector.imag)

def to_tuple3(vector, z=0):
	return (vector.real, vector.imag, z)

def radians(vector):
	return atan2(vector.imag, vector.real)

def unit(radians):
	return cmath.exp(radians * 1j)

def normal(vector):
	L = length(vector)
	if L == 0:
		return vector2()
	else:
		return vector / L

def clamp(vector, max_length):
	L = length(vector)
	if L > max_length:
		return vector * (max_length / L)
	else:
		return vector

def distance(vector1, vector2):
	return length(vector1 - vector2)

> @casey:
> I thought my function was bad -- but your solution will be easy to  
> use. I'm using a factory, ie "spawn('type', 'loc | rand', *args)" to  
> spawn units. So I can append to the subgroups here. ( I am not  
> subclassing Sprite, but I do have a .dead member, that auto-deletes  
> when iterated. )

Sounds good.

> 2) Iterating on copy-of-list speed? Is there a reason to not do this?
>
> Right now, if I'm iterating on a list which might be modified  
> ( deleted, not sure if additions break it too. ), I'm in the habit  
> of iterating on a copy of the list. ( because, at least in some  
> cases, it breaks if not a copy )
>
> ie:
> def update(self):
>     for a in self.actor_list[:]: # iterate on copy, incase I delete  
> any later
>         a.update()
>         if a.dead or offscreen( a.loc ):
>             self.actor_list.remove( a )

This is good if the list may change during iteration. If you do this  
repeatedly in a given frame, it might be better to create a custom  
class (perhaps subclass set) that contains a stable set of the actors.  
When you add or remove, these are stored in ancillary sets rather than  
changing the stable set immediately. An update method called at the  
beginning of each frame adds and removes the items from the ancillary  
sets to update the stable set. These ancillary sets are then cleared.  
This mean less memory allocation/cleanup and work copying the lists:

class StableSet(set):
	"""Stable set that does not reflect changes until update() is called,
	thus can be safely mutated while iterated
	"""
	
	def __init__(self):
		self.added = set()
		self.removed = set()
	
	def add(self, item):
		if item not in self:
			self.added.add(item)
	
	def remove(self, item):
		if item in self:
			self.removed.add(item)
		else:
			self.added.remove(item)
	
	def update(self):
		self -= self.removed
		self.removed.clear()
		self |= self.added
		self.added.clear()

-Casey