3
\$\begingroup\$

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[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?

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Peilonrayz Jul 23 '18 at 16:10
  • \$\begingroup\$ @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. \$\endgroup\$ – pydude Jul 23 '18 at 16:16
  • \$\begingroup\$ 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? \$\endgroup\$ – Peilonrayz Jul 23 '18 at 16:20
  • \$\begingroup\$ @Peilonrayz Direction_ Looking==heading. Creature's heading is defined on line 21:self.heading=random.randint(0,360). The heading is not looking toward a point, rather it is looking at a specific angle relative to the world. FOV is on line 25:creatureFOV=60 \$\endgroup\$ – pydude Jul 23 '18 at 16:28
  • \$\begingroup\$ What direction is heading relative to? \$\endgroup\$ – Peilonrayz Jul 23 '18 at 16:37
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ (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. \$\endgroup\$ – AJNeufeld Jul 24 '18 at 1:18
  • \$\begingroup\$ 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. \$\endgroup\$ – pydude Jul 24 '18 at 2:11
  • \$\begingroup\$ 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. \$\endgroup\$ – maxb Jul 24 '18 at 7:16
  • \$\begingroup\$ Bug: angle, in radians, is being compared to creature.FOV, in degrees. \$\endgroup\$ – AJNeufeld Jul 24 '18 at 15:43
  • \$\begingroup\$ @AJNeufeld good catch, I made a last second change from degrees to radians, I'll change it \$\endgroup\$ – maxb Jul 24 '18 at 16:17
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.