Ants mainly communicate with each other using odorants called pheromones. Like other insects, ants perceive smells with their long, thin, and mobile antennae. The paired antennae provide information about the direction and intensity of scents. Since most ants live on the ground, they use the soil surface to leave pheromone trails that may be followed by other ants. A forager that finds food, marks a trail on the way back to the colony. If this trail is followed by other ants, these ants then reinforce the trail when they head back with food to the colony. When the food source is exhausted, no new trails are marked by returning ants and the scent slowly dissipates.

Foraging ants travel distances of up to 200 meters from their nest and scent trails allow them to find their way back even in the dark. Distances traveled are measured using an internal pedometer that keeps count of the steps taken and also by evaluating the movement of objects in their visual field. Directions are measured using the position of the sun. They integrate this information to find the shortest route back to their nest. Ants that become separated from pheromone trails (for example because they have been moved to another location by a human being) may run around continuously until they die of exhaustion.

Assignment

In this assignment we simulate the behaviour of an ant tracking its way back to the nest by following a disturbed pheromone trail. The environment in which the ant forages is represented by a square $$n \times n$$ grid having $$n$$ row and $$n$$ columns. The ant initially is located in the bottom left corner of the grid and its nest is located in the top right corner of the grid. Each cell in the grid contains a pheromone trail that points up, down, left or right. On each turn in the simulation, the ant moves to the neighbouring cell that is pointed to by the pheromone trail, and then the direction of the trail on the cell that it has left turns 90° clockwise. If the ant is not able to move in the indicated direction because the edge of the grid blocks its path, it remains on its current cell and the direction of the trail on the cell turns 90° clockwise.

drunken ant

The original configuration of a square $$n \times n$$ grid with pheromone trails is stored in a text file. The file contains $$n$$ lines, with each line having $$n$$ direction symbols that are separated from each other by a single space. The following four characters are used as direction symbols:

You are asked to define a class DrunkenAnt that can be used to simulate the behaviour of an ant. The objects of this class must support at least the following methods:

Example

In the following interactive session we assume that the text file square.txt1 is located in the current directory.

>>> ant = DrunkenAnt('square.txt')
>>> ant.position()
(3, 0)
>>> ant
> > > >
^ < ^ v
^ v ^ ^
> > v >
>>> print(ant)
 >  >  >  > 
 ^  <  ^  v 
 ^  v  ^  ^ 
[>] >  v  > 

>>> ant.step()
(3, 1)
>>> ant.position()
(3, 1)
>>> ant
> > > >
^ < ^ v
^ v ^ ^
v > v >
>>> print(ant)
 >  >  >  > 
 ^  <  ^  v 
 ^  v  ^  ^ 
 v [>] v  > 

>>> ant.step()
(3, 2)
>>> ant.position()
(3, 2)
>>> ant
> > > >
^ < ^ v
^ v ^ ^
v v v >
>>> print(ant)
 >  >  >  > 
 ^  <  ^  v 
 ^  v  ^  ^ 
 v  v [v] > 

>>> ant.steps()
[(3, 2), (3, 2), (3, 1), (3, 1), (3, 0), (3, 0), (3, 0), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3)]
>>> ant.position()
(0, 3)
>>> print(ant)
 v  v  v [>]
 >  <  ^  v 
 >  v  ^  ^ 
 >  ^  ^  > 

Epilogue

You may have wondered whether it is possible that during a simulation an ant keeps wandering without ever reaching its nest. We can easily prove that an ant will always reach the upper right corner of the grid in a finite number of steps. Suppose by way of contradiction that an ant stays in the grid forever. Because the grid contains a finite number of cells, this means the ant will visit at least one cell an infinite number of times. And because this cell rotates after each visit, it follows that the ant visits each of its adjacent cells an infinite number of times. By extension this means that the ant will visit every cell in the grid an infinite number of times. This includes the cell in the upper right corner. Hence it's not possible for the ant to stay in the grid forever without ever reaching its nest.