Python: How can I make this function for calculating distances faster?

plankins 0
Viewed 39

I am making a simple car game with Python and PyGame to experiment with neural nets and especially the NEAT algorithm. The player is supposed to drive the car through a track and must not touch the border. In order to make the neural nets "see", there are a couple of "sensors" which the net can use to get position information. They calculate the distances to the border, which is defined by a mask, in various degrees.

Works fine for a couple of cars but when 20 or more are on the track, things slow down a lot.

A part of cProfile output:

         38382471 function calls in 52.762 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001   52.762   52.762 <string>:1(<module>)
    26435    0.158    0.000    1.086    0.000 cargame.py:113(draw)
    26435    0.045    0.000    0.045    0.000 cargame.py:121(drawRadars)
    26435   14.103    0.001   22.550    0.001 cargame.py:128(checkRadars)
    26435    0.129    0.000   24.262    0.001 cargame.py:149(update)
    26435    0.060    0.000    0.282    0.000 cargame.py:157(checkColliding)
      273    0.001    0.000    0.011    0.000 cargame.py:169(drawOnMouse)

As far as I understand those lines, my checkRadars() is bottlenecking quite a bit. It gets called for every car (when they are updated, which happens every frame).

   def checkRadars(self, mask):
        xcenter, ycenter = self.rect.center
        #self.radars.clear()
        v = (180-180*self.blindspot)/(self.radarCount-1)
        w = (90-90*self.blindspot)
        # dont mind these weird calculations
        for n in range(self.radarCount):
            length = 1
            x, y = xcenter, ycenter

            rangle = v*n-w
            rad = -math.radians(self.angle+rangle)


            while isInBound(x, y) and not mask.get_at((x, y)) and length < 100:
                length += 1
                x = int(xcenter + math.sin(rad) * length)
                y = int(ycenter - math.cos(rad) * length)
            if length == 100:
                length = length*10

I have optimized that method as far as I can, moving some calculations out of the loops, and so on, but it is still not fast enough. Lowering the length is not an option since it's already too low for my taste.

trigonometry performance python
1 Answers

Well, I tried to implement this function in other ways and managed to make it a little more efficient.

Turns out, there were more calculations than necessary and for range loops are better than while loops.

new code:

def checkRadars(self, mask):
        xcenter, ycenter = self.rect.center
        startd = -90+self.blindspot
        stopd = 90-self.blindspot
        dg = 180-self.blindspot*2

        self.radars.clear()
        for d in range(startd, stopd+1, int(dg/(self.radarCount-1))):
            x, y = xcenter, ycenter
            rad = math.radians(360 - (self.angle + d + 90))
            xvector = math.cos(rad)
            yvector = math.sin(rad)
            length = 1
            for length in range(1,200,5):
                if(not isInBound(x, y) or mask.get_at((x,y))):
                    break
                x = int(xcenter + xvector * length)
                y = int(ycenter + yvector * length)
            else: # nobreak
                length = 2000

            self.radars.append(((x, y),length))

new cProfile output:

         65266150 function calls in 49.991 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002   49.991   49.991 <string>:1(<module>)
   215157    0.619    0.000    4.604    0.000 cargame.py:112(draw)
   215157   18.651    0.000   27.422    0.000 cargame.py:131(checkRadars)
   215157    0.449    0.000   34.656    0.000 cargame.py:156(update)

checkRadars() now clearly takes less time.

plankins0
Related