# Toplevel simulation

Back to: PRE2015_2_Groep1

## Top level behavioural algorithm

Outline of the idea for an algorithm, based on the ideas presented in [Liu B Chen P Wang G], [Qi G Song P Li K] and [Nicolis S Detrain C Demolin D Deneubourg J]:

Initially (i.e. when the blackboard is empty): all robots departing from the CZ are assigned a search task (need to implement a good search algorithm)

- when pile is found by a robot: add the pile to the blackboard (coordinates and pheromones)

When a robot departs from CZ when the blackboard is non-empty:

- decide (stochastically) whether to search or to forage (based on size of blackboard)
- if decided to go forage, pick a pile from the blackboard (stochastically based on pheromones)
- then if pile is picked, if paths are known, pick a path based on pheromones, else (if no paths are known yet): move in the direction of the pile in such a way that if obstacles are encountered a way around them it is found stochastically. Keep track of the path.

When a robot arrives at a pile: update pheromones (if path is kept track of, add path to blackboard) and go to que of pile

At every time step, some pheromone "evaporates" from the blackboard.

n.b. in the dropping the pheromones and in choosing whether to search or to forage, USE aspects come in to play:

- how much priority should rescuing known victims get over searching for new victims?
- how much more priority should a pile get if we know it has n victims? (Later to be added to simulation)
- should nearby piles get priority over harder to reach piles?
- should only path length matter, or should e.g. safety play a role in dropping path pheromones? (We may add this later, but for now we'll ignore this)

## Code

This isn't functioning yet (more work needs to be done) but this is what we have so far (06-12-2015 21:55) (it's written in Python 2.7.9)

#note to self: better garbage collection still needed #idea: re-implement the paths so that new starts can benefit from the updating #before the whole path has been followed #todo add parameters for ethical choices #todo implement cone vision in accordance to the actual robots import random import math class AO(object): """Represents area of operation""" #todo: implement something for keeping track of interesting statistics __size = None __obstacles = None __piles = None robotsInAO = None blackboard =None CZ=None l=2#the "sensitivity of the choice process" speed=1 def __init__(self, size, cz, nRobots, piles, obstacles, evaporatePile = lambda x:x, evaporatePath = lambda x:x, dropPile = lambda x,y,z:y+1, dropPath = lambda x,y:x+1, l=2, speed=1): """ needs as input: -the size of the AO -the coordinates for the CZ (just one point for now) -the number of robots -a list of piles two points per pile giving two corners of the pile which is assumed to be rectangular (possibly degenerated) a list of objects as ints indicating the number of robots needed to move the object e.g. [ ((1,2), (3,4), [1,1,6,3,1]), ((6,7), (8,12), [3,1,1,3,4])] -a list of obstacles two points per obstacle giving two corners of the obstacle which is assumed to be rectangular (possibly degenerated) e.g. [((1,1),(2,2)), ((3,1),(4,3))] -a function that determines the speed of evaporation of the pheromones for the piles (mapping floats to floats in a suitable manner) -a function that determines the speed of evaporation of the pheromones for the paths (mapping floats to floats in a suitable manner) -a function called by a robot to increase the pheromone concentration at a pile (three arguments: pilesize, pheromone concentration, treshold) -a function called by a robot to increase the pheromone concentration at a path (to floats) """ self.l=l#the "sensitivity of the choice process" self.speed=speed self.__size = (int(size[0]),int(size[1])) #automatically checks for right type this way self.CZ=(int(cz[0]),int(cz[1])) self.__evaporatePile=evaporatePile self.__dropPile=dropPile self.__evaporatePath=evaporatePath self.__dropPath=dropPath #for i in range(nRobots): #self.robotsInAO.append(Robot(self.CZ,self.__drop))#fill the list with robots #want to fill the list of robots one at a time so they don't all live at the same time self.numrobots=nRobots self.__piles=[] for pile in piles:#create all the piles according to input self.__piles.append(Pile( (int(pile[0][0]),int(pile[0][1])), (int(pile[1][0]),int(pile[1][1])), [int(obj) for obj in pile[2]])) self.__obstacles = [] for obstacle in obstacles: #all obstacles are assumed to be rectangles self.__obstacles.append(( (int(obstacle[0][0]),int(obstacle[0][1])), (int(obstacle[1][0]),int(obstacle[1][1])))) self.robotsInAO = [] self.blackboard = [] def update(self): if self.numrobots>0:#release robots one at a time self.robotsInAO.append(Robot(self, self.CZ, self.__dropPile, self.__dropPath)) self.numrobots-- for robot in self.robotsInAO: robot.update() for pile in self.__piles: if min(pile.coordinates[0][0],pile.coordinates[1][0])<=robot.coordinates[0]<=max(pile.coordinates[0][0],pile.coordinates[1][0]) and \ min(pile.coordinates[0][1],pile.coordinates[1][1])<=robot.coordinates[1]<=max(pile.coordinates[0][1],pile.coordinates[1][1]): #the robot has arrived at the pile pile.update(robot, self) #self.pheromones= map(self.__evaporate,self.pheromones)#negative feedback on the pheromones #todo: implement evaporation return len(self.__piles)#this will be the check for the main loop def removePile(self, pile): pile.dropRobots() self.__piles.remove(pile) #todo: remove pile from blackboard def totalRobots(self): return len(self.robotsInAO)+sum([pile.totalRobots() for pile in self.__piles)]) #def allowedMove(self, coordinates1, coordinates2): # """Decides wether moving from coordinates1 to coordinates2 is possible""" # #a move is possible if there is no obstacle intersecting with [coordinates1, coordinates2] and also no other pile than that at coordinates2 is intersecting with [coordinates1, coordinates2] # length = ((coordinates2[0]-coordinates1[0])**2+(coordinates2[1]-coordinates1[1])**2)**.5 # direction = (float(coordinates2[0]-coordinates1[0])/length, # float(coordinates2[1]-coordinates1[1])/length) # line=[(round(coordinates1[0] + .1*n*direction[0]),round(coordinates1[1]+.1*n*direction[1])) for n in range(round(10*length)+1)] #isn't practical def getMovements(self,coordinates): freeSpace=[(coordinates[0]+n,coordinates[1]+m) for n in range(-self.speed,self.speed+1) for m in range(-self.speed, self.speed+1) if n*n+m*m<=self.speed*self.speed] #circle around the point pilepoints=[] for coord in freeSpace: #remove all points where there are obstacles for obstacle in self.__obstacles: if min(obstacle[0][0],obstacle[1][0])<=coord[0]<=max(obstacle[0][0],obstacle[1][0]) and \ min(obstacle[0][1],obstacle[1][1])<=coord[1]<=max(obstacle[0][1],obstacle[1][1]): freeSpace.remove(coord) for pile in self.__piles: if min(pile.coordinates[0][0],pile.coordinates[1][0])<=coord[0]<=max(pile.coordinates[0][0],pile.coordinates[1][0]) and \ min(pile.coordinates[0][1],pile.coordinates[1][1])<=coord[1]<=max(pile.coordinates[0][1],pile.coordinates[1][1]): pilepoints.append(coord) #now remove all coordinates that are blocked indirectly #todo implement this return (freeSpace, pilepoints) #n.b. this way a robot might go to a pile unintendedly def getPileSizeAt(self, coordinates): """returns the pile size of the pile at the coordinates""" for pile in self.__piles: if min(pile.coordinates[0][0],pile.coordinates[1][0])<=coordinates[0]<=max(pile.coordinates[0][0],pile.coordinates[1][0]) and \ min(pile.coordinates[0][1],pile.coordinates[1][1])<=coordinates[1]<=max(pile.coordinates[0][1],pile.coordinates[1][1]): return pile.pileSize() return None class Pile(object): __objects=None coordinates = None __que = None def __init__(self,coordinate1, coordinate2, *objects): #all piles are assumed to be rectangles self.__objects=[obj for obj in objects] self.__que=[] self.coordinates = (coordinate1, coordinate2) def update(self, robot, ao): self.__que.append(ao.robotsInAo.pop(ao.robotsInAo.index(robot))) try: if len(self.__que)>self.__objects[0]: obj=self.__objects.pop(0)#remove the object and get the number of needed robots for i in range(obj): rob = self.__que.pop()#remove a robot from the que rob.carrying = True #tell that robot it is carrying an object rob.sendToCZ()#send that robot to the clear zone ao.robotsInAO.append(rob)#add that robot to the list of the AO if len(self.__objects)==0: ao.removePile(self)#if the pile is empty, remove it from the list of piles except IndexError: ao.removePile(self) def totalRobots(self): return len(self.__que) def pileSize(self): return sum(self.__objects)#should change this so we also have victims def dropRobots(self): for robot in self.__que: robot.carrying = True robot.sendToCZ() ao.robotsInAO.append(rob) self.__que=[] class Robot(object): coordinates=None #Robots are assumed to be small enough to be well represented by a single coordinate __goal=None __task=None carrying=False __path=None __newpath=None ao=None __pathlength=0 def __init__(self,ao, coordinates, dropPile, dropPath): self.coordinates=(int(coordinates[0]),int(coordinates[1])) self.__dropPile = dropPile self.__dropPath = dropPath self.ao= ao def sendToCZ(self): self.__goal = self.ao.CZ self.__task="Return" #choose the fastest known path to the CZ #maybe wan't to optimize on the path back too, but don't really feel like reversed path changing yet so maybe later #last coordinate was at the pile, so for simplicity assume it is still there pile=None for elem in self.ao.blackboard: if self.coordinates == elem[0]: pile=elem break minlen = min([path[0] for path in pile[3]]) minlenpaths = [path for path in pile[3] if path[0]<= minlen+0.1] #choose a path of minimal length self.__path=minlenpaths[0]#all robots need to take the same one because they need to stay together self.pathindex=-1#since we're following backwards #todo complete this def pickCoordinates(self, target, options): """ input: the floating point coordinates the robot wants to go to output: integer coordinates in option that according to a combination of ceiling and floor correspond to target, or none if none exist """ rounders=[math.floor, math.ceil] targets=[(fun1(target[0]),fun2(target[1])) for fun1 in rounders for fun2 in rounders] targets=[e for e in targets if e in options] if len(targets)=0: return None targets.sort(lambda a, b: cmp((a[0]-target[0])**2+(a[1]-target[1])**2, (b[0]-target[0])**2+(b[1]-target[1])**2)) return targets[0] def update(self): if self.coordinates == self.ao.CZ: self.carrying = False self.__pathlength=0 #assign a task and if needed a pile and a path rnum = random.random() if rnum>self.searchChoice(): self.__task = "Search" else: self.__task = "Forage" #now, if it is assigned a forage task, pick a pile from the blackboard if self.__task=="Forage": #example of what a blackboard element may look like: #(coordinates, pheromone, treshold (k in the articles), [list of paths]) #function from articles rnum = random.random() denominator = sum([(pile[1]+pile[2])**ao.l for pile in ao.blackboard]) treshold = 0 for pile in ao.blackboard: treshold += (pile[1]+pile[2])**ao.l if rnum <treshold: self.__goal=pile[0] #this is the pile it gets assigned too #so now choose a path if available if len(pile[3])>0: rnum =random.random()#we don't need the previous rnum anymore since we'll now break from the loop #now choosing from the known paths #in the article it is done by pheromones but I'm now wondering why we shouldn't just do this by shortest known path #todo: reconsider all of this #OK, so instead of doing the pheromones for pathfinding, we'll let every robot pick either the shortest rout from the blackboard #or find a new rout #furthermore, to make short routs, instead of following the rout, we'll have the robot attempt to shorten it #actually I now understand why you need the pheromone thing: #the first found path gets optimized first so most newfound paths, when they're found, will not be shorter even though they leave more room for improvement #todo: change all to pheromone based approach if rnum >(0.25+(0.5*len(pile[3]))/(len(pile[3])+1)): # want to keep looking for new paths, but intensity should depend on number of known paths #todo: think of a better distribution #a path looks like (length (or pheromones), [coordinates]) minlen = min([path[0] for path in pile[3]]) minlenpaths = [path for path in pile[3] if path[0]<= minlen+0.1]#just in case more paths of minimal length exist (taking into account propperties of floats self.__path=random.choice(minlenpaths)[-1]# want to keep using both since one might have more potential for updating than the other #n.b. stochastics only yield good results for large number of robots self.__newpath=[self.ao.CZ] self.pathindex =0 else: #seek for new path self.__path=[] self.__newpath=[self.ao.CZ] #note to self: since now we're coming up with new paths for every robot, garbage collection should be performed on the blackboard else: self.__newpath=[self.ao.CZ] self.__path=[] break #we've found our pile and decided how to get there so break from the loop #basically, self.__task, self.__goal, self.__path, self.__pathlength and self.__newpath have been updated elif self.__task==None: #if robots start at a point different from the cz #probably need something better than this #todo implement something better self.__task = "Search" movements= self.ao.getMovements(self.coordinates)#get the list of possible movements looks like [possiblemovements, reachablepiles] if self.__task == "Search": pass #todo implement a good swarm-search algorithm elif self.__task == "Return": #simply follow the choosen path (choosen in sendToCZ()) backwards. No backwards optimization of the path at this point #n.b. at this moment we assume no new obstacles are introduced during the simulation #need to extend this part for if new obstacles are introduced #basically need to do the same path finding algorithm as for the Forage when no path is selected except we need some way to keep the robots together (since they're pushing the same piece) if self.__path[self.pathindex-1] in movements[0]: coordinates = self.__path[self.pathindex-1] self.pathindex-=1 else: pass elif self.__task == "Forage": if len(self.__path)>0: #find the next point to go to currentLength = len(self.__newpath) if self.__goal in movements[0]: #we're there self.__newpath.append(self.__goal) self.__pathlength+=((self.coordinates[0]-self.__goal[0])**2 + (self.coordinates[1]-self.__goal[1])**2 )**.5 self.coordinates = self.__goal #since self.__goal was a pile, after the update, the update() function of the ao will add this robot to the pile it's at bbElement = None for element in self.ao.blackboard:#find the corresponding pile in the blackboard if element[0]==self.coordinates: bbElement = element break #todo implement something to get rid of loops in the path (if there are any) bbElement[-1].append((self.__pathlength, self.__newpath)) #do garbage collection over the blackboard element to prevent the blackboard from getting too large minlen = min([path[0] for path in bbElement[-1]]) bbElement[-1] = [path for path in bbElement[-1] if path[0]<=1.2*minlen] #need to change this to pheromone based approach #drop pheromones to pile bbElement[1] = self.dropPile(self.ao.getPileSizeAt(self.__goal),*bbElement[1:3]) #todo change this to pheromone based approach #todo consider implementing an algorithm that optimizes over the old path points else: try: proposedScale = ((self.coordinates[0]-self.__path[self.pathindex+2][0])**2 +(self.coordinates[1]-self.__path[self.pathindex+2][1])**2)**.5 proposedDirection = ((self.__path[self.pathindex+2][0]-self.coordinates[0])/proposedScale,(self.__path[self.pathindex+2][1]-self.coordinates[1])/proposedScale) proposedCoordinate = pickCoordinates(((self.coordinates[0] + self.ao.speed*proposedDirection[0]),(self.coordinates[1] + self.ao.speed*proposedDirection[1])),movements[0]) except ZeroDivisionError: proposedCoordinate = self.__path[self.pathindex+3] self.pathindex+=1 self.pathindex+=1 if proposedCoordinate:#if it isn't None but some coordinates #at this moment, robots might get into the wrong pile accidentally. Not sure if this is bad self.__newpath.append(proposedCoordinate) self.coordinates=proposedCoordinate if self.__path[self.pathindex+2] in self.ao.getMovements(self.coordinates)[0]:#might want to reduce computation time by moving the getMovements #todo: consider moving the getMovements step to other iteration since now we're computing twice self.pathindex+=1 else:#the proposed move can't be executed if self.__path[self.pathindex] in movements[0]: self.__newpath.append(self.__path[self.pathindex]) self.coordinates = self.__path[self.pathindex] elif self.path[self.pathindex-1] in movements[0]:#might need to think of something better than this (so that all the optimizations at parts of the path where #everything went right don't get dismissed because of one point where it went wrong) self.__newpath.append(self.__path[self.pathindex-1]) self.coordinates = self.__path[self.pathindex-1] self.pathindex-=1 else: raise Exception # might want to assume a new obstacle is simply introduced and hence the old path has become invalid #in this case we want to continue to searching for a new path #todo: come up with an appropriate solution self.pathlength+= ((self.__newpath[-1][0]-self.__newpath[-2][0])**2 + (self.__newpath[-1][1]-self.__newpath[-2][1])**2)**.5 #Problem: the proposed coordinates might be further away than the operation radius due to rounding off #todo: fix this #idea: maybe project to the boundary of the disc instead of using round? else: #the algorithm comes down to this: #try to move towards the goal #if that something is blocking that move goal: # there is one minimal deflection to the left and one minimal deflection to the right, flip a coin between them # except one of them means going back the same path, that's forbidden unless it's the only option goalScale = ((self.__goal[0]-self.coordinates[0])**2+(self.__goal[1]-self.coordinates[1])**2)**.5 goalDirection = ((self.__goal[0]-self.coordinates[0])/goalScale,(self.__goal[1]-self.coordinates[1])/goalScale) goalCoordinate = (round(self.coordinates[0]+self.ao.speed*goalDirection[0]),round(self.coordinates[1]+self.ao.speed*goalDirection[1])) if goalCoordinate in movements[0]: self.__newpath.append(goalCoordinate) self.coordinates = goalCoordinate else: #get the boundary of the circle with radius self.ao.speed around self.coordinates circle = [(self.coordinates[0]+n,self.coordinates[1]+m) for n in range(-self.ao.speed, self.ao.speed+1) for m in range(-self.ao.speed, self.ao.speed+1)\ if n*n+m*m<=self.ao.speed**2 and (\ (abs(n)+1)*(abs(n)+1)+m*m >self.ao.speed**2 or n*n+(abs(m)+1)*(abs(m)+1) >self.ao.speed**2)] #take the intersection with movements[0] choiceCircle = [point for point in circle if point in movements[0]] #now select from circle #todo: implement this self.pathlength+=((self.__newpath[-1][0]-self.__newpath[-2][0])**2 + (self.__newpath[-1][1]-self.__newpath[-2][1])**2)**.5 #todo: implement this #todo implement loop cutting at the moment a path is stored def searchChoice(): """probability of a robot going for foraging""" #depending on the number of robots, size of the ao and number of known piles #this is just a place holder. The final choice will be based on USE decisions #for now we assume that there should be approximately 10 robots for every pile return min((10.*len(ao.blackboard))/ao.totalRobots,1) #although the min(...,1) doesn't really have any effect due to implementation

## Path updating idea

For reducing path length the following idea is used (a bit more thoroughly implemented above, but it comes down to the following concept shown in mathematica code) n.b. this is just a rough sketch to see the idea at work. It isn't robust (e.g. it can't handle loops very well in this form)

points = {{{0,0}, {0, -1}, {0, -2}, {1, -2}, {2, -2}, {3, -2}, {4, -2}, {4,-1}, {4, 0}, {4, 1}, {4, 2}, {3, 2}, {2, 2}, {1, 2}, {0, 2}, {0,3}, {0, 4}, {1, 4}, {2, 4}, {3, 4}, {4, 4}}} While[Length[points] < 25, previousPath = points[[Length[points]]]; newPath = {{0,0}}; While[newPath[[Length[newPath]]] != {4, 4}, If[Norm[newPath[[Length[newPath]]] - {4, 4}] <= 1, AppendTo[newPath, {4, 4}];, AppendTo[newPath, N[newPath[[ Length[newPath]]] + (previousPath[[Length[newPath] + 2]] - newPath[[Length[newPath]]])/ Norm[(previousPath[[Length[newPath] + 2]] - newPath[[Length[newPath]]])] ] ] ] ]; AppendTo[points, newPath]] Manipulate[ ListPlot[points[[i]], Joined -> True, Mesh -> All], {i, 1, Length[points], 1}]

We've worked out the path updating idea a bit further and illustrated it in the following python code (it uses pygame), however we've come to the conclusion that a more graph based approach would yield better results and will work towards that.

"""more investigation on the path simplification algorithm""" import pygame from pygame.locals import * import math import os def distance(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5 class demo(object): speed=6 def __init__(self, speed, size, iterations, path, obstacles, waitingtime=100): self.speed=speed self.size=size self.pathlist=[path] self.iterations=iterations self.obstacles=obstacles#leave this out for now self.waitingtime=waitingtime self.simplify() self.run() def pickCoordinates(self, target, options): rounders=[math.floor, math.ceil] targets=[(fun1(target[0]),fun2(target[1])) for fun1 in rounders for fun2 in rounders] targets=[e for e in targets if e in options] if len(targets)==0: return None targets.sort(lambda a, b: cmp((a[0]-target[0])**2+(a[1]-target[1])**2, (b[0]-target[0])**2+(b[1]-target[1])**2)) return targets[0] def pickDirection(self, coordinates, target):#bad name but who cares denom= distance(coordinates, target) if denom==0: return None direction= ( coordinates[0] + self.speed *(target[0]-coordinates[0])/denom, coordinates[1] + self.speed *(target[1]-coordinates[1])/denom) return direction def getMovements(self, coordinates): freeSpace=[(coordinates[0]+n,coordinates[1]+m) for n in range(-self.speed,self.speed+1) for m in range(-self.speed, self.speed+1) if n*n+m*m<=self.speed*self.speed] #circle around the point for obstacle in self.obstacles: if min(obstacle[0][0],obstacle[1][0])<=coord[0]<=max(obstacle[0][0],obstacle[1][0]) and \ min(obstacle[0][1],obstacle[1][1])<=coord[1]<=max(obstacle[0][1],obstacle[1][1]): freeSpace.remove(coord) return freeSpace def simplify(self): begin=self.pathlist[0][0] end=self.pathlist[0][-1] for i in range(self.iterations): newpath=[begin] index=0 while newpath[-1]!=end: try: if distance(newpath[-1], self.pathlist[-1][index+2])<=self.speed: index+=1 except IndexError: if distance(newpath[-1], end)>self.speed: print "got the index error, "+str(distance(newpath[-1],self.pathlist[-1][index+1])) pass if distance(newpath[-1],end)<=self.speed: #need something better than this for when obstacles are introduced newpath.append(end) elif distance(newpath[-1],end)<=2.1*self.speed: #really really need something better than this for when obstacles are introduced movements = self.getMovements(newpath[-1]) direction = self.pickDirection(newpath[-1], end) newpoint = self.pickCoordinates(direction, movements) if newpoint: newpath.append(newpoint) else: dindex=2 while not newpoint and dindex>-3: try: direction = self.pickDirection(newpath[-1],self.pathlist[-1][index+dindex]) newpoint = self.pickCoordinates(direction, movements) except IndexError: pass dindex -=1 if not newpoint: print "I don't get it anymore, "+ str(index) self.pathlist.append(newpath) raise Exception newpath.append(newpoint) else: movements = self.getMovements(newpath[-1]) direction = self.pickDirection(newpath[-1], self.pathlist[-1][index+2]) if direction: newpoint = self.pickCoordinates(direction, movements) #need to change this when obstacles are introduced newpath.append(newpoint) index+=1 else: index+=2 self.pathlist.append(newpath) def run(self): running = True #before initialising object, furst run pygame.init() self.displaysurface = pygame.display.set_mode(self.size, pygame.HWSURFACE | pygame.DOUBLEBUF) path= os.path.dirname(__file__) pointsurface = pygame.image.load(os.path.join(path, "blp.bmp")).convert() # while running: if pygame.QUIT in pygame.event.get()>0: running = False for path in self.pathlist: self.displaysurface.fill((0,0,0)) for point in path: self.displaysurface.blit(pointsurface, point) pygame.display.flip() pygame.time.wait(self.waitingtime) pygame.quit() #all the below is old def simplifyPath(path, iterations): pathlist=[path] begin=path[0] end=path[-1] for i in range(iterations): newpath=[begin] index=0 while newpath[-1]!=end: #if distance(newpath[-1],pathlist[-1][index+1])>1: print distance(newpath[-1],pathlist[-1][index+1]) #the problem is in the rounding off try: if distance(newpath[-1], pathlist[-1][index+2])<=1: index+=1 #print "did it at index "+str(index) +" with pathlist length "+str(len(pathlist)) except IndexError: if distance(newpath[-1], end)>1: print "got the index error, "+str(distance(newpath[-1],pathlist[-1][index+1])) pass if distance(newpath[-1], end)<=1: newpath.append(end) elif distance(newpath[-1], end)<=2: denom=distance(newpath[-1],end) newpoint = (round(newpath[-1][0] + (end[0]-newpath[-1][0])/denom),round(newpath[-1][1] + (end[1]-newpath[-1][1])/denom)) newpath.append(newpoint) index+=1 #not necessary else: denom=((newpath[-1][0]-pathlist[-1][index+2][0])**2 +\ (newpath[-1][1]-pathlist[-1][index+2][1])**2 )**.5 if denom!=0: newpoint = (round(newpath[-1][0] + \ (pathlist[-1][index+2][0] - newpath[-1][0])/denom,1), round(newpath[-1][1] + \ (pathlist[-1][index+2][1] - newpath[-1][1])/denom,1)) newpath.append(newpoint) index+=1 else: index+=2 pathlist.append(newpath) return pathlist def mathematify(pathlist): return str(pathlist).replace("[","{").replace("(","{").replace("]","}").replace(")","}") def givepath(start, n, direction, speed): scale = distance(direction, (0,0)) scaleddirection = (speed*direction[0]/scale, speed*direction[1]/scale) path=[start] while len(path)<=n: path.append((round(path[-1][0]+scaleddirection[0],1), round(path[-1][1]+scaleddirection[1],1))) return path if __name__=="__main__": pygame.init() startingpath = givepath((0,0),20,(0,1),20) startingpath += givepath(startingpath[-1],30,(1,0),20) #startingpath += givepath(startingpath[-1],20,(0,-1),10) demonstration = demo(20,(600,400), 150, startingpath, [], 50)

## Issues

A downside to all of this is that it relies heavily on a coordinate system, so without that, it might be significantly harder (although much of the pheromone stuff would work without a coordinate system in the case of physical pheromones, and there seem to be some papers around that use some sort of local blackboard for pheromones that does not depend on coordinates).

Furthermore, the ant colony algorithms are essentially graph algorithms, so we will opt for a heuristic algorithm instead.