How can I make my ant simulation faster?

Question

I was not sure if I should post about 200 lines here. I want to make this ant simulation faster. The bottleneck is at Ant.checkdistancebetweenantsandfood().

It would be great if you have some hints for some cleaner or more efficient code. I hope this is the right place to show this code.

import random
import time
import datetime
# TODO
# food - 100 portions okay
# bring food to the hill okay
# bring food to the hill - direct way
# use food over time
# die if food is out
# bear if enough food is there
# trail okay
# trail disolves over time
# opponent - different properties
# new food
# inside ant hill ?
# make calculations faster
#############################
# PLOT - BEGIN
#############################
import matplotlib.pyplot as plt
import numpy as np
fig, ax = plt.subplots()
# field size
size = 30
# black ants
x1 = [0]
y1 = [0]
points, = ax.plot(x1, y1, marker='o', linestyle='None', alpha=0.3,
 markersize=5, c='black')
# ant hill
x2 = [0]
y2 = [0]
points2, = ax.plot(x2, y2, marker='o', linestyle='None', alpha=0.6,
 markersize=30, c='brown')
# food
foodamount = 220
foodposx = []
foodposy = []
for i in range(foodamount):
 foodposx.append(random.randint(0, 2*size)-size)
 foodposy.append(random.randint(0, 2*size)-size)
points3, = ax.plot(foodposx, foodposy, marker='o', linestyle='None',
 alpha=0.6, markersize=5, c='green')
foundenoughfood = 20
anthillfood = 0
# movement
speed = .4
# trail
trailx = [0]
traily = [0]
trail, = ax.plot(trailx, traily, marker='o', linestyle='None', alpha=0.6,
 markersize=5, c='orange')
#trailduration = []
bearingspeed = 100 # higher value = slower bearing
# red ants
#...
ax.set_xlim(-size, size)
ax.set_ylim(-size, size)
new_x = np.random.randint(10, size=1)
new_y = np.random.randint(10, size=1)
points.set_data(new_x, new_y)
plt.pause(.0000000000001)
#############################
# PLOT - END
#############################
class Antqueen:
 counter = 2
 def __init__(self, name):
 """Initializes the data."""
 self.name = name
 print("(Initializing {0})".format(self.name))
 def bear(self):
 # print Antqueen.counter, 'ants born'
 self.name = 'ant_' + str(Antqueen.counter)
 Antqueen.counter = Antqueen.counter + 1
 ants[self.name] = None
 globals()[self.name] = Ant(self.name)
class Ant:
 population = 0
 def __init__(self, name):
 """Initializes the data."""
 self.name = name
 self.food = 10
 self.posx = 0.0
 self.posy = 0.0
 #print("(Initializing {0})".format(self.name))
 Ant.population += 1
 def die(self):
 """I am dying."""
 print("{0} is dead!".format(self.name))
 Ant.population -= 1
 if Ant.population == 0:
 print("{0} was the last one.".format(self.name))
 else:
 print("There are still {0:d} ants working.".format(Ant.population))
 def sayHi(self):
 print("Hello, call me {0}.".format(self.name))
 # move + trail
 def move(self):
 if globals()[name].food < foundenoughfood:
 self.posx = self.posx + speed*(random.random()-random.random())
 self.posy = self.posy + speed*(random.random()-random.random())
 # found enough food
 # go back to home
 else:
 # close to the ant hill
 # lay down some food to the ant hill
 if abs(self.posx) < .5:
 if abs(self.posy) < .5:
 global anthillfood
 anthillfood = anthillfood + globals()[name].food - 10
 #print "anthillfood: ", anthillfood
 # lay down everything but 10
 globals()[name].food = 10
 # far away from the ant hill
 # set trail
 trailx.append(self.posx)
 traily.append(self.posy)
 # draw the trail ###
 trail.set_data(trailx, traily)
 # move towards the ant hill
 vecx = -self.posx
 vecy = -self.posy
 len_vec = np.sqrt(vecx**2+vecy**2)
 self.posx = self.posx + vecx*1.0/len_vec/3 + speed*(random.random()-random.random())/1.5
 self.posy = self.posy + vecy*1.0/len_vec/3 + speed*(random.random()-random.random())/1.5
 def eat(self, name, foodnumber, foodposx, foodposy):
 if foodtable[foodnumber][1] > 0:
 # food on ground decreases
 foodtable[foodnumber][1] = foodtable[foodnumber][1] - 1
 # food in ant increases
 globals()[name].food = globals()[name].food + 1
 #print name, globals()[name].food, "food"
 # food is empty
 if foodtable[foodnumber][1] == 0:
 #print "foodposx: ", foodposx
 del foodposx[foodnumber]
 del foodposy[foodnumber]
 points3.set_data(foodposx, foodposy)
 @classmethod
 def howMany(cls):
 """Prints the current population."""
 print("We have {0:d} ants.".format(cls.population))
 def checkdistancebetweenantsandfood(self):
 for name in ants.keys():
 for i in range(len(foodposx)-1):
 # measure distance between ant and food
 if -1 < globals()[name].posx - foodposx[i] < 1:
 if -1 < globals()[name].posy - foodposy[i] < 1:
 globals()[name].eat(name, i, foodposx, foodposy)
 # slower
 #distance = np.sqrt((globals()[name].posx - foodposx[i])**2 + (globals()[name].posy - foodposy[i])**2)
 #if distance < 1:
 # globals()[name].eat(name, i, foodposx, foodposy)
# generate ant queen
antqueen = Antqueen("antqueen")
# generate some ants
ants = {'ant_1': None}
for name in ants.keys():
 globals()[name] = Ant(name)
# amount of food
foodtable = []
for i in range(foodamount):
 foodtable.append([i, 10])
#############################
# start simulation
#############################
for i in range(100000):
 # move all ants
 for name in ants.keys():
 globals()[name].move()
 # generate more ants
 if (i % bearingspeed == 0):
 antqueen.bear()
 # plot ants
 allposx = []
 allposy = []
 for name in ants.keys():
 allposx.append(globals()[name].posx)
 allposy.append(globals()[name].posy)
 points.set_data(allposx, allposy)
 plt.draw()
 #plt.pause(0.000000000001) # draw is faster
 # ants find food
 for name in ants.keys():
 globals()[name].checkdistancebetweenantsandfood()

• 200_success: Have you tried the "slower" code without calling np.sqrt()? (In other words, work using the square of the distance.)
• kame: The square of the distance? Do you mean distance**(0.5)?
• 200_success: dist_sq = (globals()[name].posx - foodposx[i])**2 + (globals()[name].posy - foodposy[i])**2; if dist_sq < 1 * 1: eat(...)
• Janne Karila: globals() is meant for special uses only. Why don't you simply store the Ant objects in the ants dictionary?
• konijn: This could be a fun week-end CR challenge

Answer 1

It looks like you're looping through the ants twice, once inside checkdistancebetweenantsandfood() and once when you call it. That seems like it's probably wrong.

Method:

 def checkdistancebetweenantsandfood(self):
 for name in ants.keys():
 for i in range(len(foodposx)-1):
 # measure distance between ant and food
 if -1 < globals()[name].posx - foodposx[i] < 1:
 if -1 < globals()[name].posy - foodposy[i] < 1:
 globals()[name].eat(name, i, foodposx, foodposy)

Call:

 # ants find food
 for name in ants.keys():
 globals()[name].checkdistancebetweenantsandfood()

Other optimizations

Another possible optimization is to exit the loop if a food source is found. Presumably the ants can only eat from one food source at a time.

Example:

 def checkdistancebetweenantsandfood(self):
 for name in ants.keys():
 for i in range(len(foodposx)-1):
 # measure distance between ant and food
 if -1 < globals()[name].posx - foodposx[i] < 1:
 if -1 < globals()[name].posy - foodposy[i] < 1:
 globals()[name].eat(name, i, foodposx, foodposy)
 break

If there are many food sources, you might try putting the food sources into a grid based on their position. That way the ants only need to check the for food sources in adjacent cells instead of having to loop through all of the food sources.

Answer 2

PEP-8 suggest the following about function names:

Function names should be lowercase, with words separated by underscores as necessary to improve readability.

check_distance_between_ants_and_food would follow this guidance and would be easier to read.