Checking where/if another creature lies in a creature's field of view

Question

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(n²). 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[0]-pos1[0]
 dy=pos2[1]-pos1[1]
 rads=math.atan2(dy,dx)
 rads%=2*math.pi
 degs=math.degrees(rads)
 return degs
def getDist(pos1, pos2):
 return math.hypot(pos1[0] - pos2[0], pos1[1] - pos2[1])
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[0]=1 #left side
 else:
 creature.vision[1]=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?

• Peilonrayz: How do you get a creature that is looking from (0, 0) to (1, 0), with a FOV of 180? How do you also make a creature that is looking from (0, 0) to (1, 1) with a FOV of 30?
• Luke B: @Peilonrayz Sorry, I don't quite understand. What do you mean by "make a creature" and "get a creature"? In the code above, the creatures' headings and positions are just randomly generated. The FOV is per-side, so 30 degrees means it can see 30 degrees to its left and 30 degrees to its right. I realize that that is probably not the traditional sense of FOV, but that is what it is here.
• Peilonrayz: Change them to "How do you instantiate a creature" that is looking from (0, 0)... . In your code, where is FOV defined and what direction are the creatures looking?
• Peilonrayz: What direction is heading relative to?
• Luke B: @Peilonrayz 0 degrees=toward positive Y, 90 degrees=toward positive X

Answer 1

In this case, you should divide your world into a 2D grid, where each grid cell is at least as large as your viewing distance. Lets say that the grid has \$k\$ cells. Then, in each step of the iteration you place each creature into its appropriate gridcell \$(O(n))\,ドル then for each cell you iterate over the creatures in it, and check it against every creature in the up to 9 closest cells \$(O(\frac{9n^2}{k}))\$.

This is still not perfect, but it could provide a significant speedup if you have a lot of creatures, and if your viewing distance is small compared to the size of your world. This would imply that you can make \$k\$ large, and thus you could make your algorithm 10-1000 times faster depending on your situation.

Another thing: since calculating the difference in heading takes longer time than checking pairwise distance, you should check the distance first, and only compare the heading if the creatures are close to each other.

If you want to get even more efficient, you could save half the pairwise distance checks by not comparing B to A if you have already compared A to B. To do this, you could sort the creatures by some ID once, and in your iteration you only compare distances if the first creature has lower ID than the second. However, this will most likely not impact you runtime significantly.

EDIT: I tried implementing a grid structure, but since the creatures are spaced on a 500x500 area, and their view distance is 100, the maximum speedup is only about \$\frac{25}{9}\$. However, I managed to get everything running about 3 times faster by switching to checking distance first, checking distance squared instead of distance, and using a grid. It's not very pretty, but it's something that can be improved:

import math
import random
import time
def getAngle(c1, c2):
 dx=c2.x-c1.x
 dy=c2.y-c1.y
 rads=math.atan2(dy,dx)
 return rads
def getDist(c1, c2):
 return (c1.x-c2.x)**2 + (c1.y-c2.y)**2
def angleDiff(source,target):
 a = target - source
 a = (a + math.pi) % (2*math.pi) - math.pi
 return a
class Creature(object):
 """A virtual creature"""
 def __init__(self):
 self.x = 500*random.random()
 self.y = 500*random.random()
 self.heading=random.random()*2*math.pi
 self.vision_right = False
 self.vision_left = False
 self.FOV = 60/180*math.pi
 self.viewDistanceSq = 100**2
def check_visibility(creature, other_creature):
 if getDist(creature, other_creature) < creature.viewDistanceSq:
 ang = angleDiff(creature.heading,getAngle(creature,other_creature))
 if abs(ang) < creature.FOV:
 if ang < 0:
 creature.vision_left = True #vision_left side
 if creature.vision_right:
 return True
 else:
 creature.vision_right = True #vision_right side
 if creature.vision_left:
 return True
 return False
def check_neighbors(creature, grid, i, j):
 for di in range(-1, 2):
 if not 0 <= i+di < 5:
 continue
 for dj in range(-1, 2):
 if not 0 <= j+dj < 5:
 continue
 for other_creature in grid[i+di][j+dj]:
 if creature == other_creature:
 continue
 checked = check_visibility(creature, other_creature)
 if checked:
 return
def run_simulation(creatures, grid):
 for creature in creatures:
 grid[int(creature.x/100)][int(creature.y/100)].append(creature)
 for i, row in enumerate(grid):
 for j, cell in enumerate(row):
 for creature in cell:
 check_neighbors(creature, grid, i, j)
creatures=[Creature() for _ in range(2000)]
t0 = time.clock()
for _ in range(1):
 grid = [[[] for i in range(5)] for j in range(6)]
 run_simulation(creatures, grid)
t1 = time.clock()
print(t1-t0)

• AJNeufeld: (c1.x-c2.x)**2 is slow in CPython, but fast in PyPy. You may get a speed improvement using (c1.x-c2.x)*(c1.x-c2.x) instead.
• Luke B: Thanks for this useful answer. Is this still efficient if the creatures are moving every tick? I think you have accounted for this since you reset the grid every frame, but I just wanted to be sure. Thank you for providing a good explanation as well as testing your code's speed.
• maxb: Yeah, it should still be efficient. I have used it to simulate particle collisions between \10ドル^5\$ particles, where the speedup was huge compared to the overhead of creating and managing the grid. I got that running in real time (in Java), but the principle is the same.
• AJNeufeld: Bug: angle, in radians, is being compared to creature.FOV, in degrees.
• maxb: @AJNeufeld good catch, I made a last second change from degrees to radians, I'll change it

Answer 2

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...
 if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
 ...

But first, do the partitioning as suggested by maxb.

---

If you maintain a heading vector for each creature (dx,dy), you could "dot" that with a displacement vector to the observed creature. If the dot product is negative, the observed creature is more than 90° away from the heading/viewing direction. This will, on average, remove more than half of the creatures.

If the heading vector is normalized, the dot product would also need to be less than or equal to the viewing distance.

This will give you a fast filter, using only two multiples, two subtractions, and an addition:

dot_product = c.nx * (otherC.x - c.x) + c.ny * (otherC.y - c.y)
if dot_product >= 0 and dot_product <= creatureViewDistance:
 ....

---

It occurs to me, you should also do the trivial reject first.

dx = otherC.x - c.x
dy = otherC.y - c.y
if abs(dx) > creatureViewDistance or abs(dy) > creatureViewDistance:
 continue
if dx*dx + dy*dy > creatureViewDistSquared:
 continue
dot_product = c.nx * dx + c.ny * dy
if dot_product >= 0 and dot_product <= creatureViewDistance:
 ....

At this point, you can do the angle calculation, to ensure the creature is in the 60° limit