Note: this is a more specific form of this
I am working on a simulation of some virtual creatures. They all have vision that lets them see other creatures. To do this, I calculate the difference between the creature's current heading and the angles to other creatures. Then, I check if the distance between them is close enough so that the creature can see the other.
It works, but it is quite slow. This is because it has complexity O(n2). It has to loop through the array and apply the angle function to every combination of creatures. Then, it needs to check distance between some of them.
My current code:
import math import random def getAngle(pos1,pos2): dx=pos2-pos1 dy=pos2-pos1 rads=math.atan2(dy,dx) rads%=2*math.pi degs=math.degrees(rads) return degs def getDist(pos1, pos2): return math.hypot(pos1 - pos2, pos1 - pos2) def angleDiff(source,target): a = target - source a = (a + 180) % 360 - 180 return a class Creature(object): """A virtual creature""" def __init__(self): self.pos=[random.randint(0,500) for _ in range(2)] #random x,y self.heading=random.randint(0,360) self.vision=[0,0] #left and right relative to creature's perspective creatures=[Creature() for _ in range(100)] creatureFOV=60 #can look 60 degrees left or right creatureViewDist=100 for creature in creatures: for otherC in creatures: if otherC==creature:continue #don't check own angle ang=angleDiff(creature.heading,getAngle(creature.pos,otherC.pos)) if abs(ang) < creatureFOV: if(getDist(creature.pos,otherC.pos)<creatureViewDist): if ang < 0: creature.vision=1 #left side else: creature.vision=1 #right side if sum(creature.vision)==2: break #if there is already something on both sides, stop checking
I feel like it could be greatly sped up by using numPy or some other method. How can this code be optimized for more speed?