Versions 17 and 17.1 attempt to improve the move algorithm. It has been re-written, though still does not work successfully.

An auxiliary method called getNextGridSquare() is where the main calculations for the next movement happen. It is based on version 16, with modifications.

In this version ants do not follow trails back towards the nest successfully when they find food, this leads to trails all over the grid. Even so, some ants do make it back to the nest.

Versions 17 and 17.1 attempt to improve the move algorithm. It has been re-written, though still does not work successfully.

An auxiliary method called getNextGridSquare() is where the main calculations for the next movement happen. It is based on version 16, with modifications.

In this version ants do not follow trails back towards the nest successfully when they find food, this leads to trails all over the grid. Even so, some ants do make it back to the nest.

This version takes a different approach to dealing with pheromone trails. I wanted to eliminate the need for ants to 'know' where their nest is - apart from 'cheating', this also caused problems when obstacles where placed in the way.

I have based this version on some ideas from the MUTE file sharing application.

Ants lay a trail all the time. While they are looking for food they lay an blue trail, when they have found food they lay a green trail. The idea is that when an ant finds some food it turns around and follows its own trail back to the nest.

This version introduces a new class - PheromoneParticle. Every ant lays its own pheromone particle on the as it moves along, over other pheromone particles. The Pheromone contains a stack of PheromoneParticles. The direction of the Pheromone is the highest frequency direction in the stack of PheromoneParticles. Every 60 seconds a PheromoneParticle is removed fromt the bottom of the stack. A PheromoneParticle also knows which ant laid - so that an ant could follow his own trail.

I re-wrote the move() method again. Though its not working fully yet.

This version uses pheromone direction and strength. This works better as the food is found quicker than with just using directions (see experiment below).

Experiments

Time for ants to collect 29 pieces of food

Directed + Strength	Directed Trails (Version 15.0)
1:49	2:01
1:49	2:06
1:50	2:03
1:41	1:45
Averages
1:47	2:00

This version implements directional pheromone trails. It does not take into account pheromone strength, just the direction of the pheromone.

When an ant carries food back to the nest it sets the direction of the trail of each square to the opposite direction to the nest, i.e. towards the food. As the trail spreads out to surrounding squares they cannot point in the opposite direction to the nest, they point to the square where the pheromone originated.

Experiments

Time for ants to collect 29 pieces of food

Normail Trails (Version 14)	Directed Trails
2:03	2:01
2:55	2:06
2:09	2:03
2:17	1:45
Averages
2:20	2:00

Ants follow trails in this version - it seems to work fairly well. I re-wrote the move() method, which works a lot better. It still needs some improving - for example ants can get stuck behind food if the food is between the ant and the nest. Another problem is that because ants move toward the strongest pheromone square, they tend to move back towards the nest when another ant carrying food moves towards them. I tried having the move randomly instead of towards the strongest, but this is less effective. I will next implement direction in the trail - so ants go in the correct direction¹.

Experiments

Time for ants to collect 29 pieces of food

Trails	Trails - no sort	No Trails
2:03	2:42	3:18
2:55	3:06	2:14
2:09	2:54	2:21
2:17	2:21	2:34
Averages
2:20	2:46	2:37

Time for ants to collect 81 pieces of food

Trails	Trails - no sort	No Trails
4:09	5:26	5:54
5:01	5:56	6:41
4:17	6:35	5:43
Averages
4:29	5:59	6:06

1: Ant Navigation: Reading Geometrical Signposts - Thomas S. Collett and David Waxman.

Not very good - I attempted to shrink the ants and make them move smoother. Not very successful - I will come back to this later as these changes would not actually effect the algorithms just make the ant movement look more realistic.

Back to version 12!

In this version the bouncing ant problem is fixed - meaning that ants now walk around each other. The split trail problem is also fixed.

Ants exit the nest in the strongest direction, but can only see ahead of them at any other time.

Pheromone spreads slightly in this version (http://website.lineone.net/~john.montgomery/demos/ants.html). I have tried different strengths and radii. I have found a radius of 2 works quite well but need to experiment more with this and the strengths. It doesnt use an inverse square law to calculate -need to implement that.

Need to improve the movement algorithm - it's a bit messy as I keep adding to it and changing it! I need to think about it to get it right rather than keep adding to it!

This version implements pheromone trails - although there are problems with getting ants to follow them. When a trail splits into other smaller trails the ants 'best' next grid square is the square behind them because the trial is longer. Also ants get knocked off trails if they bump into another ant coming in the other direction.

Ants sort the gridsquares around by pheromone strength and randomly choose one, with a bias towards the highest.

It takes around the same time for ants to collect the food with or without pheromone trails. Some ants do follow the trail, but must just happen to find the food randomly - the same as with no trails.

This version includes an Ant monitor to show information about the program while it is running, including how many ants are carrying food, how much food is remaining etc.

Note: Doesn't work as applet, download Jar file.

Fixed version 9.

If an ant is carrying food it treats other food as obstacles.

An ant now won't randomly move into an obstacle.

Most importantly food strength does not get 'left behind'! The problem being the amount taken away from the food strength was never enough - there was always a very small amount left (very very small number). So to get around this, I just take an extra little bit away when recalculating food strengths (0.001 in this version - which seems to work).

No more dancing ants.

In this version ants pick up food and take it back to nest, almost!

I have changed the way the food strength is recalculated. Every square that contains Food, now gets every square in a radius of 15 around it and calculates the distance and sets the food strength. This way every square doesn't have to check every other square.

When a Food object is taken by an ant the GridSquare recalculates the food strength for those around it by doing the same calculation that it does to work out the food strength but this time it takes away that value from those GridSquares.

When a cluster of food is completely gone, the ants dance around the further most radius of where the food strength went to. This is due to not all the food strength being removed. GridSquares on the outer radius seem to get left with a very tiny food strength.

Ants don't dance at obstacles now, just when they are stuck in food. But they do enter an obstacle - this is due to them choosing a random direction one of which may be in the obstacle - this will be corrected in the next version.

Another problem is that ants will move through food when they are carrying food - the ant should treat them as obstacles at this point. Because of this the food just disappears (because the GridSquares object is set to null). This is not good because it means food strengths aren't recalculated and food strength is therefore left behind.

I have removed FoodClusters, and calculate the FoodStrength individually for each GridSquare.

Each GridSquare asks the Grid for all GridSquare's containing Food, it then calculates it's distance for every square and sets it if its within a radius of 10 of itself.

Food strength does not get updated as the food is taken. The method for calculating food strength is not very efficiency and the program runs to slow to keep recalculating.

I have put Obstacle objects around the perimeter of the Grid - to make keeping the ants in the Grid easier.

Ants go towards the food, because of the food strength.

This version doesn't take into account Food objects or other ants. They don't pick up food, and two ants can occupy the same GridSquare.

Ants get stuck in the food again. And do not return to the nest.

The Dancing Ant Problem occurs, when the ant finds the edge of the Grid.

Slider had to be removed due to the changing of how the food strengths are calculated. I will put this back in a later version.

Version 7 the slider works better although it still needs improving - doesn't seem to like to work when there is more than one FoodCluster.

Ants can will suddenly move toward Food is the radius extends into the area where they are.

Fixed growing cluster problem of version 6.

Implemented a FoodCluster class. This new class looks after a cluster of Food Objects in a certain radius.

Started to implement controls to change variables as the program is running. To start off with a slider to control the radius of Food Strength values for a Food Cluster.

Partially successfully, includes a problem that means FoodClusters grow!

GridSquares can now access squares around them in a given radius. Ants look around them 'seeing' as far as 1 GridSquare in each direction.

Due to the new method I can now easily created clumps of food by picking a GridSquare at random and picking a random radius and placing food in all the returned GridSquares.

Ants look at all the squares around them and move to the one with the highest food strength value.

The food strength value is based on the size of the food cluster and the distance away the GridSquare is from it, using an inverse square relation.

I've implemented this by having the ants ask the GridSquare for all the surrounding GridSquare's with a radius of 1 GridSquare. The Ant then sorts these based on Food Strength, and moves to the GridSquare with the highest Food Strength.

Ants move toward the strongest Food Strength - the centre of a group of food.

That's all that happens in this version - they all get stuck in the middle of the food!

Version 4 introduces Pheromone Trails. The ants behave as in version 3, but when they are carrying food they lay a trail behind them.

Every time an ant enters a GridSquare while carrying food it increases that GridSquare's pheromone strength. So the more ants using the same route the stronger the trail.

The pheromone objects are threaded and strength is decreased every 15 seconds. When the strength gets to zero the pheromone disappears. If the same path is constantly used by ants the trail won't disappear because the strength keeps getting increased.

The colour becomes light the stronger the trail.

Ants don't yet follow trails that they find

Same as version 2, but a bigger Grid.

In this version the ants start in a nest. They exit the next in a random direction (which doesn't look random!).

If an ant encounters food it picks it up and continues moving, but now treats other food as an obstacle. (An ant carrying food is yellow).

If an ant happens to find the nest it will drop its food and continue searching for more.

Note: smaller size - I was trying out a different size Grid with this version.

Ants walk around moving between GridSquares. The move in the same direction until they hit an object (an ant is an object in this verison - food is ignored) and the turn right.

If they hit the edge of the Grid they turn in the opposite direction.