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?

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)

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